Merge upstream? StableSet: Adding an additional implementation, new features and tests and more.

[idanmiara]

Hi @rspeer
Thanks for this nice library!

I made a very large refactor, added another implementation, many features, tests and compatibility with other implementations and some more. The new version passes all the tests from the other 3 repositories almost completely unchanged.
https://github.com/idanmiara/ordered-set

Since that's a major addition, I didn't know how/if you would want to merge this work and since I needed to use this for some project already - I released it under to pypi under a new name stableset (with proper credits).
Having said that, I'd be happy to merge this work upstream if you are interested, if so, let me know how you'd like to proceed with this.

[twiddli]

Hi, would you mind supporting this too #79?

[NeilGirdhar]

The refactor's elimination of the list is a significant improvement. The ordering preserved by the interface for intersection is also an improvement.

FYI, You can make intersection a lot faster (linearithmic in the smallest set rather than linear in the first set) if you implement it like this: https://discuss.python.org/t/add-orderedset-to-stdlib/12730/83?u=neilgirdhar. This comes at the cost of storing some integers, which may or may not be desirable.

I also don't see the point of add returning the length of the set. It's neither in the ABC nor is it particularly helpful.

[NeilGirdhar]

@twiddli pretty sure he can't support it since dicts don't have efficient indexing.

[idanmiara]

@twiddli @NeilGirdhar
Thanks for your inputs, I'll look into it in about 2 weeks when I'm back from a holiday.

[jagerber48]

@idanmiara a few questions.

1. "Both have similar interfaces but differ in respect of their implementation and performance." I'm curious to know a listing of exactly how the interfaces differ if at all.

2. Why the name StableSet? And why do you call the dict-based set StableSet and the list-based set OrderedSet? Is the choice arbitrary? If the interfaces are the exact same (except for performance trade-offs or how equality is calculated) maybe they could all share a name (OrderedSet would be my suggestion) and the "style" could be selected with an input option during instantiation?

3. Have you seen this thread? I wonder if anything there is helpful.

[idanmiara]

@jagerber48 thanks, I'll look into it when I'm back from my holiday.

[mschilli87]

@idanmiara: Am I correct in assuming your fork abandoned?

[idanmiara]

Hi @jagerber48
Sorry I forgot to answer...

1. "Both have similar interfaces but differ in respect of their implementation and performance." I'm curious to know a listing of exactly how the interfaces differ if at all.

I went over the code again and it looks like I ended up implementing the exact same interface.

2. Why the name StableSet? And why do you call the dict-based set StableSet and the list-based set OrderedSet? Is the choice arbitrary? If the interfaces are the exact same (except for performance trade-offs or how equality is calculated) maybe they could all share a name (OrderedSet would be my suggestion) and the "style" could be selected with an input option during instantiation?

I admit I didn't think about the option of adding an style option in the constructor.
The name selection was quasi arbitrary - The idea was to make StableSet as a slim drop in replacement for set for whoever mostly needs the stable insertion order and to keep full interface compatibility with the existing OrderedSet.
If you wanted to propose a PR for adding style option to OrderdSet I will gladly review.

3. Have you seen this thread? I wonder if anything there is helpful.

It's an interesting discussion. I didn't need sorting functionality so I didn't think about this issue.
I'm willing to review a PR to add sorting if anyone needs.

[idanmiara]

Hi @mschilli87

@idanmiara: Am I correct in assuming your fork abandoned?

I just merged the recent minor fixes from this upstream into my fork.
Let me know if you are inquiring about any specific issue that needs to be addressed.

[idanmiara]

The refactor's elimination of the list is a significant improvement. The ordering preserved by the interface for intersection is also an improvement.

Thanks 👍

FYI, You can make intersection a lot faster (linearithmic in the smallest set rather than linear in the first set) if you implement it like this: https://discuss.python.org/t/add-orderedset-to-stdlib/12730/83?u=neilgirdhar. This comes at the cost of storing some integers, which may or may not be desirable.

Thanks for the pointer.

I also don't see the point of add returning the length of the set. It's neither in the ABC nor is it particularly helpful.

I wanted to keep full compatibility with the original implementation of OrderedSet.