Opened 13 years ago
Closed 13 years ago
#6621 closed enhancement (fixed)
[with patch, positive review] Permutation.inverse too slow
Reported by: | aclaesson | Owned by: | Mike Hansen |
---|---|---|---|
Priority: | major | Milestone: | sage-4.1.1 |
Component: | combinatorics | Keywords: | |
Cc: | Merged in: | Sage 4.1.1.alpha1 | |
Authors: | Anders Claesson | Reviewers: | Dan Drake |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
The running time of the current implementation of Permutation.inverse is quadratic in the length of the permutation. The attached small patch is linear.
Attachments (1)
Change History (4)
comment:1 Changed 13 years ago by
Changed 13 years ago by
Attachment: | new-inverse.patch added |
---|
comment:2 Changed 13 years ago by
Reviewers: | → Dan Drake |
---|---|
Summary: | [with patch, needs review] Permutation.inverse too slow → [with patch, positive review] Permutation.inverse too slow |
Positive review! Here are some timings:
For the permutation [6,7,8,9,4,2,3,1,5], on my machine, the timing went from 70.9 µs per loop to 24.7 µs per loop. (This is all "%timeit p.inverse()".
For [19, 5, 13, 8, 7, 15, 9, 10, 16, 3, 12, 6, 2, 20, 18, 11, 14, 4, 17, 1], it went from 263 µs per loop to 40 µs per loop.
For [14, 17, 1, 24, 16, 34, 19, 9, 20, 18, 36, 5, 22, 2, 27, 40, 37, 15, 3, 35, 10, 25, 21, 8, 13, 26, 12, 32, 23, 38, 11, 4, 6, 39, 31, 28, 29, 7, 30, 33], it went from 923 to 64.8. So it does look like this patch turns quadratic behavior into linear behavior.
This is Anders' first contribution to Sage, by the way.
comment:3 Changed 13 years ago by
Merged in: | → Sage 4.1.1.alpha1 |
---|---|
Resolution: | → fixed |
Status: | new → closed |
Uh oh, this doesn't pass doctests: I get
Instead of
return w
, you needreturn Permutation(w)