Subsets_s should support unsortable sets

[jdemeyer]

It should not force sorting the set, which may be unsortable.

[jdemeyer]

New commits:

​3930c20

Do not sort in Subsets_s

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​947cb4d

Do not sort in Subsets_s

[mantepse]

I wonder whether it is really worth the trouble (and performance hit) to keep the order of the ground set.

sage: S = [1, 8, -5, 3/2, 'a', x]
sage: import random
sage: L = [choice(S) for _ in range(10000)]
sage: %timeit list(set(L))
1000 loops, best of 3: 708 µs per loop
sage: %timeit list(stable_uniq(L))
1000 loops, best of 3: 1.4 ms per loop

(Currently, essentially all the time in Subsets_s.__init__ is spent in uniq.)

[tscrim]

It is not really fair to compare a builtin Python class set to a (pure) Python function. So the fact it is a 2x slowdown on a set that large is quite good IMO. It is a nice side-effect that the order of the groundset is preserved, but that looks like it is a facet of the (simple) implementation. This is also not the tool you should be using in a tight loop anyways, so I am not worried about the slowdown here. Thus I am giving this a positive review.

[mantepse]

fine with me, too!

[mantepse]

Travis, I think you forgot to set the flag to "positive".

[jdemeyer]

I just realized something... the existing uniq(X) really just does sorted(set(X)). It seems a bit silly to write a function just for that and one can also wonder if the sorting is the right thing to do in general.

So I suggest that this new stable_uniq would replace uniq. Of course, a deprecation period is needed for that. So I'd rather use a private name like _stable_uniq for now.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a86962c

Make _stable_uniq private

[tscrim]

That is good with me.

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. This was a forced push. New commits:

​0d45f46	Do not sort in Subsets_s
​dba4c44	Make _stable_uniq private

[jdemeyer]

Trivial rebase to 8.6.rc0

[embray]

Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sage-pending or sage-wishlist.