#17021: Faster creation of words by the parent
-------------------------+-------------------------------------------------
Reporter: | Owner:
slabbe | Status: needs_work
Type: | Milestone: sage-6.4
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers:
combinatorics | Work issues:
Keywords: | Commit:
Authors: | 9008b8d2986614ece259a54274ae054ef5fad40d
Sébastien Labbé | Stopgaps:
Report Upstream: N/A |
Branch: |
u/slabbe/17021 |
Dependencies: |
-------------------------+-------------------------------------------------
Description changed by slabbe:
Old description:
> 1. Move the code of {{{_construct_word}}} into {{{__call__}}} method.
>
> 2. Create {{{finite_word_list}}} methods which are shortcuts for
> {{{__call__}}} when we know the datatype.
>
> Here are some benchmarks:
>
> list:
>
> {{{
> sage: W = Words()
> sage: L = range(1000)
> sage: %timeit W(L)
> 10000 loops, best of 3: 45.5 µs per loop
> sage: %timeit W.finite_word_list(L)
> 1000000 loops, best of 3: 1.29 µs per loop
> }}}
>
> str:
>
> {{{
> sage: W = Words()
> sage: s = 'a'*1000
> sage: %timeit W(s)
> 10000 loops, best of 3: 45.2 µs per loop
> sage: %timeit W.finite_word_str(s)
> 1000000 loops, best of 3: 1.27 µs per loop
> }}}
>
> tuple:
>
> {{{
> sage: t = tuple(L)
> sage: %timeit W(t)
> 10000 loops, best of 3: 46 µs per loop
> sage: %timeit W.finite_word_tuple(t)
> 1000000 loops, best of 3: 1.39 µs per loop
> }}}
>
> char (why creation is so longer than str, tuple or list?):
>
> {{{
> sage: W = Words([0,1,2])
> sage: L = [0,1,1,2]*1000
> sage: type(W(L))
> <class 'sage.combinat.words.word.FiniteWord_char'>
> sage: %timeit W(L)
> 1000 loops, best of 3: 336 µs per loop
> sage: %timeit W.finite_word_char(L)
> 1000 loops, best of 3: 246 µs per loop
> }}}
>
> BEFORE:
>
> {{{
> sage: W = Words(range(5))
> sage: %time L = list(W.iterate_by_length(7))
> CPU times: user 4.6 s, sys: 54.7 ms, total: 4.66 s
> Wall time: 4.68 s
> }}}
>
> AFTER:
>
> {{{
> sage: W = Words(range(5))
> sage: %time L = list(W.iterate_by_length(7))
> CPU times: user 940 ms, sys: 80.4 ms, total: 1.02 s
> Wall time: 1.02 s
> }}}
New description:
1. Move the code of {{{_construct_word}}} into {{{__call__}}} method.
2. Create {{{_word_from_list}}} methods which are shortcuts for
{{{__call__}}} when we know the datatype.
Here are some benchmarks:
list:
{{{
sage: W = Words()
sage: L = range(1000)
sage: %timeit W.call__old(L) # before
10000 loops, best of 3: 45.1 µs per loop
sage: %timeit W(L) # after
10000 loops, best of 3: 17.1 µs per loop
sage: %timeit W(L, check=False)
100000 loops, best of 3: 2.21 µs per loop
sage: %timeit W._word_from_list(L)
1000000 loops, best of 3: 1.33 µs per loop
}}}
str:
{{{
sage: W = Words()
sage: s = 'a'*1000
sage: %timeit W.call__old(s) # before
10000 loops, best of 3: 45.7 µs per loop
sage: %timeit W(s) # after
10000 loops, best of 3: 18.4 µs per loop
sage: %timeit W(s, check=False)
100000 loops, best of 3: 2.62 µs per loop
sage: %timeit W._word_from_str(s)
1000000 loops, best of 3: 1.23 µs per loop
}}}
tuple:
{{{
sage: t = tuple(L)
sage: %timeit W.call__old(t) # before
10000 loops, best of 3: 45.9 µs per loop
sage: %timeit W(t) # after
10000 loops, best of 3: 18.6 µs per loop
sage: %timeit W(t,check=False)
100000 loops, best of 3: 3.25 µs per loop
sage: %timeit W._word_from_tuple(t)
1000000 loops, best of 3: 1.3 µs per loop
}}}
char (here creation is longer than str, tuple or list because a copy of
data is performed):
{{{
sage: W = Words([0,1,2])
sage: L = [0,1,1,2]*1000
sage: type(W(L))
<class 'sage.combinat.words.word.FiniteWord_char'>
sage: %timeit W.call__old(L) # before
1000 loops, best of 3: 322 µs per loop
sage: %timeit W(L) # after
1000 loops, best of 3: 292 µs per loop
sage: %timeit W(L, check=False)
1000 loops, best of 3: 248 µs per loop
sage: %timeit W._word_from_char(L)
1000 loops, best of 3: 245 µs per loop
}}}
BEFORE:
{{{
sage: W = Words(range(5))
sage: %time L = list(W.iterate_by_length(7))
CPU times: user 4.6 s, sys: 54.7 ms, total: 4.66 s
Wall time: 4.68 s
}}}
AFTER (about 20 times faster):
{{{
sage: W = Words(range(5))
sage: %time L = list(W.iterate_by_length(7))
CPU times: user 235 ms, sys: 29.1 ms, total: 264 ms
Wall time: 259 ms
}}}
--
--
Ticket URL: <http://trac.sagemath.org/ticket/17021#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 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.
