#19494: Make finite word method nb_subword_occurences_in much faster
-------------------------+-------------------------------------------------
Reporter: | Owner:
slabbe | Status: needs_info
Type: | Milestone: sage-6.10
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers: Vincent Delecroix
combinatorics | Work issues:
Keywords: | Commit:
Authors: | 664fd8e0650d7e9c95fab0d484ae5f800641b2a6
Sébastien Labbé | Stopgaps:
Report Upstream: N/A |
Branch: |
u/slabbe/19494 |
Dependencies: |
-------------------------+-------------------------------------------------
Changes (by vdelecroix):
* status: needs_review => needs_info
Comment:
Hola Sebastien,
Here is an example where `original` is much faster
{{{
sage: u = Word([randint(0,30) for _ in range(600)])
sage: v = Word(range(30))
sage: %time v.nb_subword_occurrences_in(u, algorithm='original')
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 3.16 ms
0
sage: %time v.nb_subword_occurrences_in(u, algorithm='matrices')
CPU times: user 132 ms, sys: 0 ns, total: 132 ms
Wall time: 123 ms
0
}}}
So we should definitely keep it.
For sparsity of matrices I was a bit wrong. In the situation I presented,
there is a big product of sparse matrices (each matrix contains exactly
`n+1` ones) but the product itself will '''not''' be sparse. Hence using
sparse matrices might not be the good strategy (depends on how the product
is implemented there). From your experiments it seems that we win nothing
which is definitely strange theoretically.
Note that the old implementation suffers several problems to be really
competitive:
- it is recursive (which is always slow in Python)
- it constructs a lot of prefixes and suffixes of words which is costly
(creation of Python objects)
What do you think?
Vincent
--
Ticket URL: <http://trac.sagemath.org/ticket/19494#comment:7>
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.
