Fast lexicographic iterator for module over ZZ/nZZ

sagemath / sage

Main repository of SageMath

https://www.sagemath.org

Other

1.46k stars 485 forks source link

Fast lexicographic iterator for module over ZZ/nZZ #19345

Open videlec opened 9 years ago

videlec commented 9 years ago

We implement a reasonably fast lexicographic iterator for modules over ZZ/nZZ. We integrate a minimum_weight method that could be used as an alternative to GAP in some part of sage.codings.

Setup

sage: R = IntegerModRing(6)
sage: M = FreeModule(R, 4)
sage: U = M.span([M((1,1,0,2)), M((2,2,3,0))])

Before

sage: timeit('for u in M: pass')
25 loops, best of 3: 9.11 ms per loop

sage: timeit('for u in U: pass')
625 loops, best of 3: 641 µs per loop

After

sage: timeit('for u in M: pass')
625 loops, best of 3: 283 µs per loop

sage: timeit('for u in U: pass')
625 loops, best of 3: 41.5 µs per loop

Depends on #6452

CC: @johanrosenkilde @sagetrac-dlucas

Component: coding theory

Author: Vincent Delecroix

Branch/Commit: u/vdelecroix/19345 @ 5773c78

Issue created by migration from https://trac.sagemath.org/ticket/19345

videlec commented 9 years ago

Dependencies: u/vdelecroix/19345

videlec commented 9 years ago

Changed branch from #6452 to u/vdelecroix/19345

videlec commented 9 years ago

New commits:

`708863f`	`Trac 6452: free module over ZZ/nZZ and submodules`
`ebb2092`	`Trac 6452: adapt some tests to facade`
`a5e3d23`	`Trac 6452: fix a doctest`
`acd707c`	`Trac 6452: cleaner code + more doc`
`ffbd6e8`	`Trac 6452: simplification + more tests`
`9d7a2cd`	`Trac 19345: iterator for vector_modn_dense`

videlec commented 9 years ago

Commit: 9d7a2cd

videlec commented 9 years ago

Changed dependencies from u/vdelecroix/19345 to #6452

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`59ab945`	`Trac 6452: free modules over ZZ/nZZ and submodules`
`96ead16`	`Trac 6452: fix a doctest`
`5773c78`	`Trac 19345: iterator for vector_modn_dense`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 9d7a2cd to 5773c78

videlec commented 9 years ago

comment:4

rebased on #6452

slel commented 9 years ago

Description changed:

--- 
+++ 
@@ -1,17 +1,23 @@
 We implement a reasonably fast lexicographic iterator for modules over `ZZ/nZZ`. We integrate a `minimum_weight` method that could be used as an alternative to GAP in some part of `sage.codings`.
+
+Setup
+
+```
+sage: R = IntegerModRing(6)
+sage: M = FreeModule(R, 4)
+sage: U = M.span([M((1,1,0,2)), M((2,2,3,0))])
+```

 Before

-sage: R = IntegerModRing(6) -sage: M = FreeModule(R, 4) sage: timeit('for u in M: pass') 25 loops, best of 3: 9.11 ms per loop

-sage: U = M.span([M((1,1,0,2)), M((2,2,3,0))]) sage: timeit('for u in U: pass') 625 loops, best of 3: 641 µs per loop

+
 After

videlec commented 8 years ago

comment:6

Apparently not ready...