#7520: Improving word construction
-----------------------------+----------------------------------------------
Reporter: slabbe | Owner: slabbe
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.3.1
Component: combinatorics | Keywords:
Work_issues: | Author: Sebastien Labbe
Upstream: N/A | Reviewer:
Merged: |
-----------------------------+----------------------------------------------
Changes (by newvalueoldvalue):
* author: => Sebastien Labbe
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) Creation of a word from a word when the parent changes doesn't work
> well :
>
> {{{
> 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'>
> }}}
New 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
}}}
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7520#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 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.
