#8232: cmp function for words is broken
-----------------------------+----------------------------------------------
Reporter: slabbe | Owner: sage-combinat
Type: defect | Status: new
Priority: major | Milestone: sage-4.3.3
Component: combinatorics | Keywords:
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
Comment(by slabbe):
I just applied a patch which does the following things.
1. Fixed `__cmp__` for `Word_class` which was broken.
2. Remove the `__cmp__` from `FiniteWord_class` since the same function in
`Word_class` does the job anyway and in a cleaner way : it doesn't use the
(useless?) coerce function. Surprinsingly, removing it makes it faster :
{{{
BEFORE:
sage: w = Word([0]*10000)
sage: z = Word([0]*10000, alphabet=[0,1])
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_list'>
sage: type(z)
<class 'sage.combinat.words.word.FiniteWord_list'>
sage: %timeit w.__cmp__(w)
125 loops, best of 3: 3.79 ms per loop
sage: %timeit w.__cmp__(z)
25 loops, best of 3: 13.3 ms per loop
sage: %timeit z.__cmp__(w)
5 loops, best of 3: 50.1 ms per loop
sage: %timeit z.__cmp__(z)
25 loops, best of 3: 35.7 ms per loop
AFTER:
sage: w = Word([0]*10000)
sage: z = Word([0]*10000, alphabet=[0,1])
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_list'>
sage: type(z)
<class 'sage.combinat.words.word.FiniteWord_list'>
sage: %timeit w.__cmp__(w)
125 loops, best of 3: 3.89 ms per loop
sage: %timeit w.__cmp__(z)
125 loops, best of 3: 5.4 ms per loop
sage: %timeit z.__cmp__(w)
25 loops, best of 3: 35.9 ms per loop
sage: %timeit z.__cmp__(z)
25 loops, best of 3: 35.7 ms per loop
}}}
NOTE : The difference between w and z above is that the parent of w is the
alphabet of all python objects which uses the cmp of python to compare the
letters whereas z compares its letters relatively to the order of the
letters defined by its parent (here 0 < 1 but one could also say 1 < 0)
which is slower.
3. The broken `__cmp__` was hidding one bug in `longest_common_prefix`.
Indeed a doctest was passing while it wasn't supposed to:
{{{
BEFORE:
sage: w = Word('12345')
sage: w.longest_common_prefix(Word())
word: 1
AFTER:
sage: w = Word('12345')
sage: w.longest_common_prefix(Word())
word:
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8232#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.
