#18607: Speed-up for __contains__ in linear codes
-----------------------------+----------------------------
Reporter: dlucas | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.8
Component: coding theory | Keywords:
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
-----------------------------+----------------------------
The actual implementation of `__contains__` for linear codes is quite
slow.
It can be improved using the syndrome computation instead of checking
if the vector belongs to a specific subspace of the ambient space.
Test:
{{{
F = GF(1009)
n, k = 1000, 500
C = codes.RandomLinearCode(n, k, F)
subspace = []
syndrome = []
for i in range(20):
c = C.random_element()
start = time.clock()
A = C.ambient_space()
S = A.subspace(C.gens())
res = S.__contains__(c)
elapsed = (time.clock() - start)
assert res == True
subspace.append(elapsed)
start = time.clock()
if not v in C.ambient_space() or len(v) != C.length():
res = False
else:
res = (C.syndrome(c) == 0)
elapsed = (time.clock() - start)
assert res == True
syndrome.append(elapsed)
}}}
Results:
{{{
sage: median(subspace)
1.526604500000019
sage: median(syndrome)
0.00408399999997755
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/18607>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
