Opened 12 years ago

Closed 12 years ago

# improve equality tests for words

Reported by: Owned by: slabbe sage-combinat major sage-4.3.4 combinatorics words abmasse, vdelecroix, saliola sage-4.3.4.alpha0 Sébastien Labbé Alexandre Blondin Massé N/A equality

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
```

### 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
• Status changed from new to needs_review
• Work issues set to equality

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

• Status changed from needs_review to needs_work

This patch seems to introduce some problems. See

Needs work...

### comment:5 Changed 12 years ago by slabbe

• Description modified (diff)

### 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

Merged in this order:

Note: See TracTickets for help on using tickets.