#17016: Implement naive algorithm for factor_set method of a finite word
-------------------------+-------------------------------------------------
Reporter: | Owner:
slabbe | Status: positive_review
Type: | Milestone: sage-6.4
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers:
combinatorics | Work issues:
Keywords: | Commit:
Authors: | 7ed2922be57b5e27c8e5508963c182b80e4fe3e5
Sébastien Labbé | Stopgaps:
Report Upstream: N/A |
Branch: |
u/slabbe/17016 |
Dependencies: |
-------------------------+-------------------------------------------------
Changes (by vdelecroix):
* status: needs_review => positive_review
Comment:
The difference in timing is more impressive on
{{{
sage: W = Words([0,1,2,3])
sage: w = W(list(words.ThueMorseWord()[:10000]))
sage: %time w.number_of_factors(10, algorithm='naive')
CPU times: user 24 ms, sys: 0 ns, total: 24 ms
Wall time: 19.6 ms
28
sage: %time w.number_of_factors(10, algorithm='suffix tree')
CPU times: user 144 ms, sys: 20 ms, total: 164 ms
Wall time: 145 ms
28
}}}
But still, I am not sure this is the way to go. If you intend to do some
computations on factors it is always better to build a good data structure
for them (e.g. a SuffixTree). With small modifications it should be
possible to adapt the current implementation with an upper bound on the
length.
I set to positive review as this can be instructive for timings, but I am
not sure there might be any real case usage.
Vincent
--
Ticket URL: <http://trac.sagemath.org/ticket/17016#comment:4>
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.
