Opened 12 years ago

Closed 12 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:

Status badges

Description (last modified by slabbe)

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.

  1. This patch adds equality test for WordDatatype_str, WordDatatype_list and WordDatatype_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

  1. Add the __eq__ and __ne__ for Word_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)

trac_8187_equality_words-sl.patch (10.7 KB) - added by slabbe 12 years ago.
trac_8187_review-abm.patch (3.3 KB) - added by abmasse 12 years ago.
Doc, formatting and typos changes -- apply on top of the main patch

Download all attachments as: .zip

Change History (13)

comment:1 Changed 12 years ago by slabbe

  • Description modified (diff)

comment:2 Changed 12 years ago by slabbe

  • Description modified (diff)

comment:3 Changed 12 years ago by slabbe

  • Cc abmasse vdelecroix saliola added
  • Keywords words added
  • Status changed from new to needs_review
  • Work issues set to equality

comment:4 follow-up: Changed 12 years ago by slabbe

  • Status changed from needs_review to needs_work

This patch seems to introduce some problems. See

http://groups.google.com/group/sage-combinat-devel/browse_thread/thread/9e90bbeb0328034c

Needs work...

comment:5 Changed 12 years ago by slabbe

  • Description modified (diff)

Changed 12 years ago by slabbe

comment:6 in reply to: ↑ 4 Changed 12 years ago by slabbe

  • 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 12 years ago by abmasse

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.

Changed 12 years ago by abmasse

Doc, formatting and typos changes -- apply on top of the main patch

comment:8 Changed 12 years ago by abmasse

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 12 years ago by abmasse

  • Authors set to Sébastien Labbé
  • Reviewers set to Alexandre Blondin Massé

comment:10 Changed 12 years ago by slabbe

  • Status changed from needs_review to positive_review

comment:11 Changed 12 years ago by mvngu

  • Merged in set to sage-4.3.4.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.