Opened 7 years ago

Closed 7 years ago

#7520 closed enhancement (fixed)

Improving word construction

Reported by: slabbe Owned by: slabbe
Priority: major Milestone: sage-4.3.4
Component: combinatorics Keywords:
Cc: saliola Merged in: sage-4.3.4.alpha0
Authors: Sébastien Labbé Reviewers: Franco Saliola
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by slabbe)

Improve the creation of a word from a word when the parent changes :

BEFORE:

sage: w = Word('abab')
sage: P = WordPaths('abcd')
sage: P(w)
word: abab
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_str'>
sage: type(P(w))
<class 'sage.combinat.words.word.FiniteWord_str'>

AFTER:

sage: w = Word('abab')
sage: P = WordPaths('abcd')
sage: P(w)
Path: abab
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_str'>
sage: type(P(w))
<class 'sage.combinat.words.paths.FiniteWordPath_square_grid_str'>

The following construction gets also faster with the patch applied :

BEFORE:

sage: w = Word([0,1]*10000)
sage: %timeit z = Words([2,0,1])(w)
1000 loops, best of 3: 586 µs per loop

AFTER:

sage: w = Word([0,1]*10000)
sage: %timeit z = Words([2,0,1])(w)
1000 loops, best of 3: 343 µs per loop

Attachments (2)

trac_7520_my_own_review-sl.patch (7 bytes) - added by slabbe 7 years ago.
Forget about this patch.
trac_7520_words_construction_improvements-sl.patch (9.6 KB) - added by slabbe 7 years ago.
Apply only this one.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 7 years ago by slabbe

  • Type changed from defect to enhancement

Will post a patch soon...

comment:2 Changed 7 years ago by slabbe

  • Description modified (diff)
  • Summary changed from Improving word construction and datatype handling to Improving word construction

comment:3 Changed 7 years ago by slabbe

  • Status changed from new to needs_work

My patch needs work:

sage: P = WordPaths([0,1,2,3])
sage: P
Word Paths on the square grid
sage: w = words.ChristoffelWord(5,8)
sage: P(w)
Traceback (most recent call last):
...
AttributeError: 'LowerChristoffelWord' object has no attribute '_class_str'

I must admit my patch was not that clean and it now shows its limits. The problem concerns the creation of a word from a word especially when the parent changes. Should we try to use some sort of shorcut (like simply change some important attributes like __class__) or not? I have an idea of something better which doesn't use any shortcut. For example, if the input word is a FiniteWord_list, we could simply restore the list and pass through the usual steps for when the input is a list. I think this should be more safe. I just have to think for a solution what we do when the word is defined as an iterator. A new patch (with cleaner code) to be posted soon.

Ideas are welcome.

comment:4 Changed 7 years ago by slabbe

  • Status changed from needs_work to needs_review

In the new patch, I made the corrections to words.py which handles in a some better way construction of words from words. There was one single strange doctest failing in word.py involving word morphisms. So, I improved again the __call__ method of WordMorphism which was doing to much useless stuff.

comment:5 Changed 7 years ago by slabbe

  • Owner changed from mhansen to slabbe

comment:6 follow-up: Changed 7 years ago by slabbe

  • Status changed from needs_review to needs_work

I am changing the status to "needs work" because I thought of a cleaner way of solving this.

I will fold the two actual patches, improve them and post a new patch soon...

Changed 7 years ago by slabbe

Forget about this patch.

comment:7 Changed 7 years ago by slabbe

  • Authors set to Sebastien Labbe
  • Description modified (diff)

comment:8 in reply to: ↑ 6 Changed 7 years ago by slabbe

  • Status changed from needs_work to needs_review

I am changing the status to "needs work" because I thought of a cleaner way of solving this.

I still think that the construction of words is not clean, but I will not clean it in this ticket. This ticket solves some problems and I believe it can now get a review and an eventual merge into sage.

Here are some key points I am actually thinking (I am writing them as a reference for future improvements):

  • The first version of sage-words got merged into sage in the end of December 2008. In January 2009, we quickly realized that many improvements should be done to the library (involving word construction, reorganisation of the classes and of course, many pickle problem...). In July 2009, the big reorganisation was merged into sage without breaking any pickle (Thanks to Franco for the quirk).
  • The code now looks really ugly for supporting the old pickled objects and I don't like ugly code.
  • I am looking forward to get rid of word_content, utils and friends.
  • I don't hide that I would be happy to have the right to break the pickle of the old word objects and replace the ugly code by clean and simple code.
  • Looking afterward, I think we should not have supported any pickling of word objects for the first year (by suggesting the users to save their word objects as lists). Doing so, it would have allow some time for us to find really what we think is the good solution for classes and word constructors.
  • CallableFromListOfWords inherits from tuple which I think is bad because (1) it doesn't have to and (2) it is the only last reason why one must use the datatype='callable' for word creation.
  • Then, get rid of the datatype argument.
  • I think that creating classes inline from bases classes (MathObject + DataObject) would work. And, in this case, __reduce__ should not return a class as first argument but the usual Word function. Did Nicolas Thiéry convinced anyone about creating inline classes? Was it used in the lastly merged category code?
  • WordDatatype_callable is storing its data into the attributes self._func while I think all those WordDatatype should save their data into the same self._data.
  • When writing a __reduce__ function, always make sure to put only essential things because this might become a problematic argument to be supported by creation function in the future. Moreover, the first argument of the tuple returned should be think as a function (or a class) that will always exist.
  • Right now only WordDatatype provide __reduce__ function. Now, what if the FiniteWord_class now wants to store some attributes. How to set them again after loading a pickle word? It might work by defining __setstate__ and __getstate__ for FiniteWord_class... To be checked! I would be great if we could do it without defining any function in the (inline) classes like FiniteWord_list.

I will fold the two actual patches, improve them and post a new patch soon...

So I did folded the two actual patches. I also updated the description of the patch to help the review. The patch now needs review!

Changed 7 years ago by slabbe

Apply only this one.

comment:9 Changed 7 years ago by slabbe

  • Description modified (diff)

I just separated this ticket into three parts. It will make things easier for the reviewer like that since the three parts were really independant. See #8287 and #8289 for the issues that used to be discussed here.

comment:10 Changed 7 years ago by saliola

  • Reviewers set to Franco Saliola
  • Status changed from needs_review to positive_review

Sebastien, great job with the patch. I'm really glad the efficiency of the code is improving!

The patch applies cleanly to sage-4.3.3 and all doctests pass. Positive review.

comment:11 Changed 7 years ago by mvngu

  • Authors changed from Sebastien Labbe to Sébastien Labbé
  • 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.