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:

Status badges

Description

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

Change History (16)

comment:1 Changed 4 years ago by jdemeyer

  • Branch set to u/jdemeyer/subsets_s_should_support_unsortable_sets

comment:2 Changed 4 years ago by jdemeyer

  • Commit set to 3930c20b0d41c87f5b7ebc5c1ffd07bfcbb18832
  • Status changed from new to needs_review

New commits:

3930c20Do not sort in Subsets_s

comment:3 Changed 4 years ago by git

  • Commit changed from 3930c20b0d41c87f5b7ebc5c1ffd07bfcbb18832 to 947cb4d3651b6540f51267cd5ccde7b45e55a118

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

947cb4dDo not sort in Subsets_s

comment:4 Changed 4 years ago by 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.)

comment:5 Changed 4 years ago by tscrim

  • 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 mantepse

fine with me, too!

comment:7 Changed 4 years ago by mantepse

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

comment:8 Changed 4 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:9 Changed 4 years ago by jdemeyer

  • 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 git

  • Commit changed from 947cb4d3651b6540f51267cd5ccde7b45e55a118 to a86962c1ef260b3014aec08e78d6f27fdbe15bab

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

a86962cMake _stable_uniq private

comment:11 Changed 4 years ago by jdemeyer

  • Status changed from needs_work to needs_review

comment:12 Changed 4 years ago by tscrim

  • Status changed from needs_review to positive_review

That is good with me.

comment:13 Changed 4 years ago by git

  • Commit changed from a86962c1ef260b3014aec08e78d6f27fdbe15bab to dba4c44db4b8160952877452f5f8d74824e5a971
  • Status changed from positive_review to needs_review

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

0d45f46Do not sort in Subsets_s
dba4c44Make _stable_uniq private

comment:14 Changed 4 years ago by jdemeyer

  • Status changed from needs_review to positive_review

Trivial rebase to 8.6.rc0

comment:15 Changed 3 years ago by embray

  • 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 vbraun

  • Branch changed from u/jdemeyer/subsets_s_should_support_unsortable_sets to dba4c44db4b8160952877452f5f8d74824e5a971
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.