#7520: Improving word construction
-------------------------------+--------------------------------------------
Reporter: slabbe | Owner: slabbe
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.3.3
Component: combinatorics | Keywords:
Author: Sebastien Labbe | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-------------------------------+--------------------------------------------
Old description:
> (1) The {{{_check}}} function of the Combinatorial class of all words
> (checking that the 40 first letters of the word are in the parent) is
> called for each word created by the user ....and by any other function.
> It would be good to add a check parameter (True or False) whether to do
> the checking. For example, for internal function, it could be turned off.
> Here is a example of what can be gained from this modification when
> generating all words of a given length :
>
> BEFORE:
> {{{
> sage: W = Words([0,1])
> sage: time l = list(W.iterate_by_length(15))
> CPU times: user 2.60 s, sys: 0.09 s, total: 2.69 s
> Wall time: 2.71 s
> }}}
>
> AFTER:
>
> {{{
> sage: W = Words([0,1])
> sage: time l = list(W.iterate_by_length(15))
> CPU times: user 1.99 s, sys: 0.06 s, total: 2.05 s
> Wall time: 2.08 s
> }}}
>
> (2) Improvement in the creation of a word from a word when the parent
> changes :
>
> BEFORE:
>
> {{{
> sage: w = Word('abab')
> sage: P = WordPaths('abcd')
> sage: P(w)
> word: abab
> sage: type(w)
> <class 'sage.combinat.words.word.FiniteWord_str'>
> sage: type(P(w))
> <class 'sage.combinat.words.word.FiniteWord_str'>
> }}}
>
> AFTER:
>
> {{{
> sage: w = Word('abab')
> sage: P = WordPaths('abcd')
> sage: P(w)
> Path: abab
> sage: type(w)
> <class 'sage.combinat.words.word.FiniteWord_str'>
> sage: type(P(w))
> <class 'sage.combinat.words.paths.FiniteWordPath_square_grid_str'>
> }}}
>
> The following construction gets also faster with the patch applied :
>
> BEFORE:
>
> {{{
> sage: w = Word([0,1]*10000)
> sage: %timeit z = Words([2,0,1])(w)
> 1000 loops, best of 3: 586 µs per loop
> }}}
>
> AFTER:
>
> {{{
> sage: w = Word([0,1]*10000)
> sage: %timeit z = Words([2,0,1])(w)
> 1000 loops, best of 3: 343 µs per loop
> }}}
>
> (3) `WordMorphism.__call__` is doing a conversion of the input into the
> domain which is not necessary. Basicly, all what is needed is that the
> input be iterable. Here are some timing improvements :
>
> BEFORE:
>
> {{{
> sage: m = WordMorphism('a->aab,b->ba')
> sage: %timeit w = m('a'*100)
> 1000 loops, best of 3: 343 µs per loop
> }}}
>
> AFTER:
>
> {{{
> sage: m = WordMorphism('a->aab,b->ba')
> sage: %timeit w = m('a'*100)
> 1000 loops, best of 3: 242 µs per loop
> }}}
New description:
Improve the creation of a word from a word when the parent changes :
BEFORE:
{{{
sage: w = Word('abab')
sage: P = WordPaths('abcd')
sage: P(w)
word: abab
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_str'>
sage: type(P(w))
<class 'sage.combinat.words.word.FiniteWord_str'>
}}}
AFTER:
{{{
sage: w = Word('abab')
sage: P = WordPaths('abcd')
sage: P(w)
Path: abab
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_str'>
sage: type(P(w))
<class 'sage.combinat.words.paths.FiniteWordPath_square_grid_str'>
}}}
The following construction gets also faster with the patch applied :
BEFORE:
{{{
sage: w = Word([0,1]*10000)
sage: %timeit z = Words([2,0,1])(w)
1000 loops, best of 3: 586 µs per loop
}}}
AFTER:
{{{
sage: w = Word([0,1]*10000)
sage: %timeit z = Words([2,0,1])(w)
1000 loops, best of 3: 343 µs per loop
}}}
--
Comment(by slabbe):
I just separated this ticket into three parts. It will make things easier
for the reviewer like that since the three parts were really independant.
See #8287 and #8289 for the issues that used to be discussed here.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7520#comment:9>
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.
