Opened 8 years ago
Last modified 6 years ago
#13346 needs_work enhancement
Add a cython implementation of the Kolakoski word
Reported by: | slabbe | Owned by: | slabbe |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | combinatorics | Keywords: | |
Cc: | abmasse, tjolivet | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #12224 | Stopgaps: |
Description (last modified by )
A Python implementation of the Kolakoski word was implemented some time ago in #8739. But, there exist much faster implementation especially some lines of C code of Dominique Bernardi shared by himself during Sage Days 28 in Orsay, France, in January 2011.
This patch adds a cython version of the code of Bernardi. It is much faster than the actual python implementation in Sage.
BEFORE:
sage: K = words.KolakoskiWord() sage: K word: 1221121221221121122121121221121121221221... sage: time K[100000] 1 Time: CPU 0.96 s, Wall: 1.36 s sage: time K[1000000] # takes forever
AFTER:
sage: K = words.KolakoskiWord() sage: K word: 1221121221221121122121121221121121221221... sage: time K[1000000] 2 Time: CPU 0.01 s, Wall: 0.02 s sage: time K[100000000] 1 Time: CPU 1.38 s, Wall: 1.92 s
Attachments (1)
Change History (13)
comment:1 Changed 8 years ago by
- Description modified (diff)
comment:2 Changed 8 years ago by
- Cc ablondin added
- Status changed from new to needs_review
comment:3 Changed 8 years ago by
- Cc abmasse added; ablondin removed
Changed 8 years ago by
comment:4 Changed 8 years ago by
comment:5 Changed 8 years ago by
- Cc tjolivet added
comment:6 Changed 8 years ago by
I should work on this ticket in the next days. I just need to install the newest sage version.
comment:7 Changed 8 years ago by
Salut Alex,
En fait, un patch de V. Delecroix et Stepan Starosta est en attente et mon ticket ne s'applique plus sur le leur... Je devrais écrire une nouvelle version au courant de la semaine prochaine si tout va bien... Donc, le review de ce ticket est en stand by pour l'instant.
Oups, I wrote in French sorry.
Sébastien
comment:8 Changed 8 years ago by
- Dependencies set to #12224
- Status changed from needs_review to needs_work
This ticket needs work to give the opportunity to #12224 to get into Sage first. Hoping it will not take forever.
comment:9 Changed 7 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:10 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:11 Changed 7 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:12 Changed 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4
I just updated the patch.