#12014: Make linearcode.__iter__ and linearcode.list() faster
-----------------------------+----------------------------------------------
Reporter: ppurka | Owner: wdj
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-5.0
Component: coding theory | Keywords: linear code, iter
Work_issues: | Upstream: N/A
Reviewer: | Author: Radoslav Kirov, Punarbasu
Purkayastha
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Changes (by ppurka):
* status: new => needs_review
Old description:
> 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
> [https://groups.google.com/d/msg/sage-devel/wmaSLdlkn-c/3Nu8Kx8DKZMJ a
> short discussion in sage-devel])
>
> I am attaching a patch which makes it faster and makes `list()` call
> `__iter__()`. This patch is simply to show you that the methods can be
> faster. So, I haven't done any doctests. Some tests will probably break
> because the order of codewords returned are not the same as earlier.
> Before going ahead and trying to fix doctests, etc, I want to be sure
> that this patch is desirable.
>
> 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.
> {{{
> ...ding_Theory/programs/sage> ~/Installations/sage-4.7.2/sage
> ----------------------------------------------------------------------
> | Sage Version 4.7.2, Release Date: 2011-10-29 |
> | Type notebook() for the GUI, and license() for information. |
> ----------------------------------------------------------------------
> sage: C = ReedSolomonCode(7, 3, GF(8, 'a'))
> sage: load('code_functions.py')
> sage: timeit('list(C.__iter__())')
> 5 loops, best of 3: 90.9 ms per loop
> sage: timeit('C.list()')
> 5 loops, best of 3: 122 ms per loop
> sage: timeit('list_codewords(C)') # new code implemented in
> list_codewords
> 125 loops, best of 3: 1.66 ms per loop
> }}}
New description:
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
[https://groups.google.com/d/msg/sage-devel/wmaSLdlkn-c/3Nu8Kx8DKZMJ 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.
{{{
...ding_Theory/programs/sage> ~/Installations/sage-4.7.2/sage
----------------------------------------------------------------------
| Sage Version 4.7.2, Release Date: 2011-10-29 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: C = ReedSolomonCode(7, 3, GF(8, 'a'))
sage: load('code_functions.py')
sage: timeit('list(C.__iter__())')
5 loops, best of 3: 90.9 ms per loop
sage: timeit('C.list()')
5 loops, best of 3: 122 ms per loop
sage: timeit('list_codewords(C)') # new code implemented in list_codewords
125 loops, best of 3: 1.66 ms per loop
}}}
----
Apply [attachment:trac_12014-make_iter_and_list_faster.patch] to
`SAGE_ROOT/devel/sage`.
--
Comment:
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 [https://spreadsheets.google.com/pub?key=pCwvGVwSMxTzT6E2xNdo5fA
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12014#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
