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:

Status badges

Description (last modified by Punarbasu Purkayastha)

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

  1. #13417
  2. trac_12014-make_iter_and_list_faster.patch to SAGE_ROOT/devel/sage.

Attachments (2)

test_file.patch (129 bytes) - added by Punarbasu Purkayastha 10 years ago.
test trac upload with "replace existing attachment"
trac_12014-make_iter_and_list_faster.patch (2.0 KB) - added by Punarbasu Purkayastha 10 years ago.
Apply to devel/sage

Download all attachments as: .zip

Change History (18)

comment:1 Changed 11 years ago by Dima Pasechnik

Cc: David Joyner added

comment:2 Changed 11 years ago by Dima Pasechnik

Cc: Keshav Kini John Pang added

comment:3 Changed 11 years ago by Punarbasu Purkayastha

Description: modified (diff)
Status: newneeds_review

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:

sage: G = matrix(GF(2), [[1, 1, 1, 0, 0, 0, 0, 0, 0],                        
....: [0, 0, 0, 1, 1, 1, 0, 0, 0],[0, 0, 0, 0, 0, 0, 1, 1, 1]])
sage: C = LinearCode(G)
sage: Cperp = C.dual_code()
sage: Cperp_iter = list(iter(Cperp))
sage: Cperp_iter == Cperp.list()
False
sage: Cperp_iter_tuples = map(tuple, Cperp)
sage: Cperp_list_tuples = map(tuple, Cperp.list())
sage: Cperp_iter_tuples == Cperp_list_tuples 
False

According to the documentation by doing help(Cperp.list) and help(Cperp.__iter__), they should both be returning the same collection.

So, I am setting this patch up for review.

comment:4 Changed 11 years ago by Punarbasu Purkayastha

Type: enhancementdefect

comment:5 in reply to:  4 ; Changed 11 years ago by Dima Pasechnik

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 in reply to:  5 Changed 11 years ago by Punarbasu Purkayastha

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 Punarbasu Purkayastha

Attachment: test_file.patch added

test trac upload with "replace existing attachment"

comment:7 Changed 10 years ago by Punarbasu Purkayastha

Keywords: sd40.5 added

Updated to sage-5.1beta0, so that it can be reviewed :)

comment:8 Changed 10 years ago by Thomas Feulner

Cc: Thomas Feulner added

comment:9 Changed 10 years ago by Punarbasu Purkayastha

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 Punarbasu Purkayastha

Dependencies: 13417#13417

comment:11 Changed 10 years ago by Punarbasu Purkayastha

Description: modified (diff)

comment:12 Changed 10 years ago by Dima Pasechnik

Status: needs_reviewneeds_work

this needs a rebase for Sage 5.6.beta/rc...

Changed 10 years ago by Punarbasu Purkayastha

Apply to devel/sage

comment:13 Changed 10 years ago by Punarbasu Purkayastha

Status: needs_workneeds_review

Ok. I have rebased this ticket and #13694 on 5.7.beta0.

comment:14 Changed 10 years ago by Dima Pasechnik

Status: needs_reviewpositive_review

comment:15 Changed 10 years ago by Jeroen Demeyer

Reviewers: Dmitrii Pasechnik

comment:16 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.7.beta2
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.