Opened 8 years ago
Closed 8 years ago
#8187 closed enhancement (fixed)
improve equality tests for words
Reported by: | slabbe | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-4.3.4 |
Component: | combinatorics | Keywords: | words |
Cc: | abmasse, vdelecroix, saliola | Merged in: | sage-4.3.4.alpha0 |
Authors: | Sébastien Labbé | Reviewers: | Alexandre Blondin Massé |
Report Upstream: | N/A | Work issues: | equality |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
More often, when we compare two words, we test their equality and not that one is less than the other. So why not implement the equatlity test!? This ticket does this for datatypes and for math objects.
- This patch adds equality test for
WordDatatype_str
,WordDatatype_list
andWordDatatype_tuple
(via__richcmp__
) usefull when comparing two words represented by the same kind of data. It is now as fast as the python object :
BEFORE: sage: w = Word(range(10000)) sage: z = Word(range(10000)) sage: %timeit w == z 125 loops, best of 3: 4.08 ms per loop AFTER: sage: w = Word(range(10000)) sage: z = Word(range(10000)) sage: %timeit w == z 625 loops, best of 3: 422 µs per loop PYTHON OBJECT: sage: w = range(10000) sage: z = range(10000) sage: %timeit w == z 625 loops, best of 3: 442 µs per loop
BEFORE: sage: w = Word(tuple(range(10000))) sage: z = Word(tuple(range(10000))) sage: %timeit w == z 125 loops, best of 3: 3.97 ms per loop AFTER: sage: w = Word(tuple(range(10000))) sage: z = Word(tuple(range(10000))) sage: %timeit w == z 625 loops, best of 3: 419 µs per loop PYTHON OBJECT: sage: w = tuple(range(10000)) sage: z = tuple(range(10000)) sage: %timeit w == z 625 loops, best of 3: 420 µs per loop
BEFORE: sage: w = Word('a'*10000) sage: z = Word('a'*10000) sage: %timeit w == z 125 loops, best of 3: 3.9 ms per loop AFTER: sage: w = Word('a'*10000) sage: z = Word('a'*10000) sage: %timeit w == z 625 loops, best of 3: 2.36 µs per loop PYTHON OBJECT: sage: w = 'a'*10000 sage: z = 'a'*10000 sage: %timeit w == z 625 loops, best of 3: 2.03 µs per loop
- Add the
__eq__
and__ne__
forWord_class
because it is faster than using__cmp__
(especially when parent alphabet are defined). These functions are used to test the equality of two words represented by different python objects (datatypes).
no parents :
BEFORE: sage: L = range(10000) sage: t = tuple(L) sage: w = Word(L) sage: z = Word(t) sage: type(w) <class 'sage.combinat.words.word.FiniteWord_list'> sage: type(z) <class 'sage.combinat.words.word.FiniteWord_tuple'> sage: %timeit w == z 125 loops, best of 3: 3.69 ms per loop AFTER: sage: L = range(10000) sage: t = tuple(L) sage: w = Word(L) sage: z = Word(t) sage: type(w) <class 'sage.combinat.words.word.FiniteWord_list'> sage: type(z) <class 'sage.combinat.words.word.FiniteWord_tuple'> sage: %timeit w == z 625 loops, best of 3: 1.44 ms per loop
with parents (!!):
BEFORE: sage: W = Words([0,1,2]) sage: w = W([0, 1, 1, 2]*4000) sage: z = W([0, 1, 1, 2]*4000) sage: %timeit w == z 5 loops, best of 3: 63 ms per loop AFTER: sage: W = Words([0,1,2]) sage: w = W([0, 1, 1, 2]*4000) sage: z = W([0, 1, 1, 2]*4000) sage: %timeit w == z 125 loops, best of 3: 2.57 ms per loop
Attachments (2)
Change History (13)
comment:1 Changed 8 years ago by
- Description modified (diff)
comment:2 Changed 8 years ago by
- Description modified (diff)
comment:3 Changed 8 years ago by
- Cc abmasse vdelecroix saliola added
- Keywords words added
- Status changed from new to needs_review
- Work issues set to equality
comment:4 follow-up: ↓ 6 Changed 8 years ago by
- Status changed from needs_review to needs_work
comment:5 Changed 8 years ago by
- Description modified (diff)
Changed 8 years ago by
comment:6 in reply to: ↑ 4 Changed 8 years ago by
- Status changed from needs_work to needs_review
This patch seems to introduce some problems.
Finally, the problem were already present. This ticket was simply making them appear! The problem is being tracked at #8232.
I just uploaded a new patch.
Needs review again!
comment:7 Changed 8 years ago by
I tested the patch and everything seems fine. Although it modifies several basic functions, it doesn't seem to have any side effect. I couldn't check all documentation since some part of the code is written in Cython, but the functions I did check built correctly.
I've made minor changes in the doc: just formatting some part of the code or correcting typos. If Sébastien agrees with my change, I allow him to set the path to positive review
.
comment:8 Changed 8 years ago by
I forgot to mention that equality tests are indeed improved in some cases, and I haven't encountered any worse case, which is good !
comment:9 Changed 8 years ago by
- Reviewers set to Alexandre Blondin Massé
comment:10 Changed 8 years ago by
- Status changed from needs_review to positive_review
comment:11 Changed 8 years ago by
- Merged in set to sage-4.3.4.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
Merged in this order:
This patch seems to introduce some problems. See
http://groups.google.com/group/sage-combinat-devel/browse_thread/thread/9e90bbeb0328034c
Needs work...