Opened 4 years ago
Closed 3 years ago
#26933 closed defect (fixed)
Subsets_s should support unsortable sets
Reported by: | jdemeyer | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.7 |
Component: | python3 | Keywords: | |
Cc: | chapoton | Merged in: | |
Authors: | Jeroen Demeyer | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | dba4c44 (Commits, GitHub, GitLab) | Commit: | dba4c44db4b8160952877452f5f8d74824e5a971 |
Dependencies: | Stopgaps: |
Description
It should not force sorting the set, which may be unsortable.
Change History (16)
comment:1 Changed 4 years ago by
- Branch set to u/jdemeyer/subsets_s_should_support_unsortable_sets
comment:2 Changed 4 years ago by
- Commit set to 3930c20b0d41c87f5b7ebc5c1ffd07bfcbb18832
- Status changed from new to needs_review
comment:3 Changed 4 years ago by
- Commit changed from 3930c20b0d41c87f5b7ebc5c1ffd07bfcbb18832 to 947cb4d3651b6540f51267cd5ccde7b45e55a118
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
947cb4d | Do not sort in Subsets_s
|
comment:4 Changed 4 years ago by
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
.)
comment:5 Changed 4 years ago by
- Reviewers set to Travis Scrimshaw
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.
comment:6 Changed 4 years ago by
fine with me, too!
comment:7 Changed 4 years ago by
Travis, I think you forgot to set the flag to "positive".
comment:8 Changed 4 years ago by
- Status changed from needs_review to positive_review
comment:9 Changed 4 years ago by
- Status changed from positive_review to needs_work
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.
comment:10 Changed 4 years ago by
- Commit changed from 947cb4d3651b6540f51267cd5ccde7b45e55a118 to a86962c1ef260b3014aec08e78d6f27fdbe15bab
Branch pushed to git repo; I updated commit sha1. New commits:
a86962c | Make _stable_uniq private
|
comment:11 Changed 4 years ago by
- Status changed from needs_work to needs_review
comment:12 Changed 4 years ago by
- Status changed from needs_review to positive_review
That is good with me.
comment:13 Changed 4 years ago by
- Commit changed from a86962c1ef260b3014aec08e78d6f27fdbe15bab to dba4c44db4b8160952877452f5f8d74824e5a971
- Status changed from positive_review to needs_review
comment:14 Changed 4 years ago by
- Status changed from needs_review to positive_review
Trivial rebase to 8.6.rc0
comment:15 Changed 3 years ago by
- Milestone changed from sage-8.6 to sage-8.7
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.
comment:16 Changed 3 years ago by
- Branch changed from u/jdemeyer/subsets_s_should_support_unsortable_sets to dba4c44db4b8160952877452f5f8d74824e5a971
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
Do not sort in Subsets_s