#7227: [with patch, needs review] Improving factor complexity of words functions
-----------------------------+----------------------------------------------
Reporter: slabbe | Owner: slabbe
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.2
Component: combinatorics | Keywords: factor complexity
Work_issues: | Author:
Reviewer: | Merged:
-----------------------------+----------------------------------------------
Changes (by slabbe):
* status: new => needs_review
Comment:
Here are some examples of the improvements made by the patch :
BEFORE:
{{{
sage: t = words.ThueMorseWord()
sage: w = t[:10000]
sage: time _ = [w.number_of_factors(i) for i in range(20)]
CPU times: user 4.19 s, sys: 0.00 s, total: 4.19 s
Wall time: 4.19 s
sage: time _ = [w.number_of_factors(i) for i in range(50)]
CPU times: user 10.28 s, sys: 0.00 s, total: 10.28 s
Wall time: 10.28 s
}}}
AFTER:
{{{
sage: t = words.ThueMorseWord()
sage: w = t[:10000]
sage: time _ = [w.number_of_factors(i) for i in range(20)]
CPU times: user 0.30 s, sys: 0.00 s, total: 0.30 s
Wall time: 0.30 s
sage: time _ = [w.number_of_factors(i) for i in range(50)]
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s
sage: time _ = [w.number_of_factors(i) for i in range(100)]
CPU times: user 0.06 s, sys: 0.00 s, total: 0.06 s
Wall time: 0.06 s
sage: time _ = [w.number_of_factors(i) for i in range(1000)]
CPU times: user 4.90 s, sys: 0.00 s, total: 4.90 s
Wall time: 4.90 s
sage: time _ = [w.number_of_factors(i) for i in range(1001)]
CPU times: user 4.85 s, sys: 0.00 s, total: 4.85 s
Wall time: 4.85 s
sage: time _ = [w.number_of_factors(i) for i in range(2000)]
CPU times: user 27.64 s, sys: 0.00 s, total: 27.64 s
Wall time: 27.64 s
}}}
I should also add some Rauzy graphs examples and some timing improvements
on palindrome complexity as well.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7227#comment:1>
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
-~----------~----~----~----~------~----~------~--~---
