Opened 11 years ago
Closed 10 years ago
#12014 closed defect (fixed)
Make linearcode.__iter__ and linearcode.list() faster
Reported by: | Punarbasu Purkayastha | Owned by: | David Joyner |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.7 |
Component: | coding theory | Keywords: | linear code, iter, sd40.5 |
Cc: | Radoslav Kirov, David Joyner, Keshav Kini, John Pang, Thomas Feulner | Merged in: | sage-5.7.beta2 |
Authors: | Radoslav Kirov, Punarbasu Purkayastha | Reviewers: | Dmitrii Pasechnik |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #13417 | Stopgaps: |
Description (last modified by )
The __iter__()
method in devel/sage/sage/coding/linear_code.py
tries to return the codewords standard form of the code. Is there a reason why it does so? This should be left to the gen_mat to provide a systematic generator matrix.
The list()
method on the other hand doesn't call __iter__()
at all. It instead calls a more generic method which is actually quite slow. (See a short discussion in sage-devel)
I am attaching a patch which makes it faster and makes list()
call __iter__()
.
As for the speedup, here is an example. The functions in Sage are the unpatched versions. list_codewords()
is a function implemented in the file that is loaded with load( )
and this contains the iterate()
method present in the patch. (Updated timings after adding this ticket and #13417).
sage: C = ReedSolomonCode(7, 3, GF(8, 'a')) sage: timeit('list(C.__iter__())') 5 loops, best of 3: 75.8 ms per loop sage: from code_functions import list_codewords # the previous patch. sage: timeit('list_codewords(C)') 625 loops, best of 3: 1.4 ms per loop sage: C = ReedSolomonCode(7, 3, GF(8, 'a')) # this new patch after adding #13417 sage: timeit('list(C.__iter__())') 625 loops, best of 3: 553 µs per loop
Apply
- #13417
- trac_12014-make_iter_and_list_faster.patch to
SAGE_ROOT/devel/sage
.
Attachments (2)
Change History (18)
comment:1 Changed 11 years ago by
Cc: | David Joyner added |
---|
comment:2 Changed 11 years ago by
Cc: | Keshav Kini John Pang added |
---|
comment:3 Changed 11 years ago by
Description: | modified (diff) |
---|---|
Status: | new → needs_review |
comment:4 follow-up: 5 Changed 11 years ago by
Type: | enhancement → defect |
---|
comment:5 follow-up: 6 Changed 11 years ago by
Replying to ppurka:
Maybe Rado can comment on this. If I recall right, GAP (GUAVA package) is called to do most things with linear codes; but the low-level GAP code it uses is buggy in GAP 4.4.12. A patch exists for GAP 4.5, but it's not backported, AFAIK. I requested such a backport quite a while ago, but it didn't happen.
comment:6 Changed 11 years ago by
Replying to dimpase:
Maybe Rado can comment on this. If I recall right, GAP (GUAVA package) is called to do most things with linear codes; but the low-level GAP code it uses is buggy in GAP 4.4.12. A patch exists for GAP 4.5, but it's not backported, AFAIK. I requested such a backport quite a while ago, but it didn't happen.
The current code for the codeword list does not call GAP. This patch also does not call GAP. I think if it did call, it would be even slower.
Changed 10 years ago by
Attachment: | test_file.patch added |
---|
test trac upload with "replace existing attachment"
comment:7 Changed 10 years ago by
Keywords: | sd40.5 added |
---|
Updated to sage-5.1beta0, so that it can be reviewed :)
comment:8 Changed 10 years ago by
Cc: | Thomas Feulner added |
---|
comment:9 Changed 10 years ago by
Dependencies: | → 13417 |
---|---|
Description: | modified (diff) |
Updated patch to be based on #13417. This will give much more consistent output.
comment:10 Changed 10 years ago by
Dependencies: | 13417 → #13417 |
---|
comment:11 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:12 Changed 10 years ago by
Status: | needs_review → needs_work |
---|
this needs a rebase for Sage 5.6.beta/rc...
Changed 10 years ago by
Attachment: | trac_12014-make_iter_and_list_faster.patch added |
---|
Apply to devel/sage
comment:13 Changed 10 years ago by
Status: | needs_work → needs_review |
---|
Ok. I have rebased this ticket and #13694 on 5.7.beta0.
comment:14 Changed 10 years ago by
Status: | needs_review → positive_review |
---|
comment:15 Changed 10 years ago by
Reviewers: | → Dmitrii Pasechnik |
---|
comment:16 Changed 10 years ago by
Merged in: | → sage-5.7.beta2 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
In fact, the original patch didn't break any doctests in
devel/sage/sage/coding
. I checked that it also fixes this bug mentioned in the Sage public notebook bugreports:It seems like iterating over the dual of a LinearCode? gives a different result from iterating over the .list() of the dual code. Here is a test case:
According to the documentation by doing
help(Cperp.list)
andhelp(Cperp.__iter__)
, they should both be returning the same collection.So, I am setting this patch up for review.