Implement faster iterator for Lyndon words

[tscrim]

Having an iterator for Lyndon words with a fixed length and alphabet size is useful that does not return elements (e.g., the free Lie algebra). Moreover, by having less transient objects, we can also improve the speed.

Current branch:

sage: LW = LyndonWords(11,6)
sage: %time for x in LW: pass
CPU times: user 2.17 s, sys: 40 ms, total: 2.21 s
Wall time: 2.17 s

sage: LW = LyndonWords(11,7)
sage: %time for x in LW: pass
CPU times: user 20.7 s, sys: 20 ms, total: 20.7 s
Wall time: 20.7 s

vs old version:

sage: LW = LyndonWords(11,6)
sage: %time for x in LW: pass
CPU times: user 2.86 s, sys: 12 ms, total: 2.87 s
Wall time: 2.85 s

sage: LW = LyndonWords(11,7)
sage: %time for x in LW: pass
CPU times: user 26.8 s, sys: 12 ms, total: 26.8 s
Wall time: 26.7 s

[tscrim]

New commits:

​fdb880b	Implementing "fast" iterator for Lyndon words of a fixed length and alphabet size.
​a17239b	Using new iterator in the free Lie algebra.

[mantepse]

Given #25262, it would be good to add a "long" doctest, so we can avoid performance regressions in future.

[mantepse]

Notes to myself:

There seem to be Gray codes available, eg:

• ​https://hal.inria.fr/hal-00966527/document
• ​http://www.cis.uoguelph.ca/~sawada/papers/bubble4.pdf

(Note that the very simple iterative algorithm on page 217 of Ruskey's book visits also the necklaces.)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​bbacc76

Added long test to lyndon_word.py.

[tscrim]

Replying to mantepse:

Given #25262, it would be good to add a "long" doctest, so we can avoid performance regressions in future.

That is not really how #25262 is suppose to work, and I don't believe is a better way to catch regressions (there will be less noise, but the noise will still be there). However, I've added it.

[mantepse]

Here is a naive implementation of the iterative FKM algorithm from Ruskey's book. I couldn't get ​http://puma.dimai.unifi.it/17_1_2/weston.pdf to work, and I haven't checked what it's advantage would be.

I won't steel the joy of timing this from you :-)

def FKM_iterativ(k, n):
    a = [0]*(n+1)
    if n == 1:
        yield a[:]
    i = n;
    while True:
        a[i] += 1
        for j in range(1, n-i+1):
            a[j + i] = a[j]
        if n == i:            
            yield a[:]
        i = n
        while a[i] == k-1:
            i -= 1
        if i == 0:
            break

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​ce2962b	restore richer doc tests
​ba08ff3	reviewer's comments
​95ce20f	provide iterators which return lists of lists
​d2e0e6e	inline a computation by reviewer's request
​947233c	Merge branch 'public/25462' of git://trac.sagemath.org/sage into public/combinat/speedup_set_partitions-25462
​a79e302	Reverted to an_element() and added some additional reviewer changes.
​87bf535	Cythonizing iterator.
​ba6a115	Fixing doctests due to ordering change.
​95d5d91	Merge branch 'public/combinat/speedup_set_partitions-25462' of git://trac.sagemath.org/sage into public/combinat/fast_lyndon_iter-26111
​8cc9d0e	Using a Cython version of FKM algorithm to generate Lyndon words.

[tscrim]

The "joy" of timing...sure...

Anyways...that was a good find. The FKM algorithm is much faster than what was previously there (approximately 4x times faster):

sage: %time for l in generate_lyndon_words(11,6): pass
CPU times: user 1.74 s, sys: 36 ms, total: 1.78 s
Wall time: 1.76 s
sage: %time for l in FKM_iterative(11,6): pass
CPU times: user 452 ms, sys: 32 ms, total: 484 ms
Wall time: 432 ms

sage: %time for l in generate_lyndon_words(11,7): pass
CPU times: user 16.7 s, sys: 28 ms, total: 16.7 s
Wall time: 16.7 s
sage: %time for l in FKM_iterative(11,7): pass
CPU times: user 3.75 s, sys: 28 ms, total: 3.78 s
Wall time: 3.74 s

With Cython (approximate another 10x speedup):

sage: %time for l in FKM_iterative_cython(11,6): pass
CPU times: user 36 ms, sys: 20 ms, total: 56 ms
Wall time: 40.7 ms
sage: %time for l in FKM_iterative_cython(11,7): pass
CPU times: user 340 ms, sys: 12 ms, total: 352 ms
Wall time: 322 ms

I have merged in #25462 and added the Cython code in such a way as to not (add) conflict with #25659.

[mantepse]

Great! (sorry, I actually did think that you would enjoy the timing)

One thing I do not yet understand: on my laptop, FKM is roughly 12 times faster than the original iterator (i.e., without this ticket).

I'll try this ticket now to check.

[mantepse]

Dear Travis!

The following cuts the time by a half, but I'm not sure whether it's correct... What do you think? (more precisely: should it really be FiniteWord_char?)

src/sage/combinat/lyndon_word.py

@@ -457 +457 @@
             sage: sum(1 for lw in LyndonWords(11, 6))  # long time
             295020
         """
+        from sage.combinat.words.word import FiniteWord_char
         for lw in generate_lyndon_words(self._n, self._k):
-            yield self._words([i+1 for i in lw], check=False)
+            yield FiniteWord_char(self._words, [i+1 for i in lw])
 
 def StandardBracketedLyndonWords(n, k):
     """

[vdelecroix]

To be nicer with the words code use

self._words.element_classes['char'](self._words, [i+1 for i in lw])

That should roughly be the same. And you can even keep a reference W = self._words.element_classes['char'] to save extra micro seconds.

[mantepse]

Thank you Vincent!

However, it turns out that "char" is probably incorrect:

sage: list(LyndonWords(1000,1))
OverflowError: value too large to convert to unsigned char

So it should be

src/sage/combinat/lyndon_word.py

@@ -457 +457 @@
             sage: sum(1 for lw in LyndonWords(11, 6))  # long time
             295020
         """
+        W = self._words._element_classes['list']
         for lw in generate_lyndon_words(self._n, self._k):
-            yield self._words([i+1 for i in lw], check=False)
+            yield W(self._words, [i+1 for i in lw])
 
 def StandardBracketedLyndonWords(n, k):
     """

This doesn't seem to be essentially slower than "char"...

[mantepse]

@Travis, a tiny thing:

src/sage/algebras/lie_algebras/free_lie_algebra.py

@@ -809 +809 @@
             n = len(self._indices)
             ret = []
             for lw in generate_lyndon_words(n, k):
-                b = self._standard_bracket(tuple([names[i] for i in lw]))
+                b = self._standard_bracket(tuple(names[i] for i in lw))
                 ret.append(self.element_class(self, {b: one}))
             return tuple(ret)

[mantepse]

Another one:

src/sage/algebras/lie_algebras/free_lie_algebra.py

@@ -774 +774 @@
                  [x0, [[x0, x1], x1]],
                  [x0, [x0, [x1, x2]]],
                  [x0, [[x0, x2], x1]],
-                 [[x0, x1], [x0, x2]],
                  [x0, [[x0, x2], x2]],
+                 [[x0, x1], [x0, x2]],
                  [[[x0, x1], x1], x1],
                  [x0, [x1, [x1, x2]]],
                  [[x0, [x1, x2]], x1],
-                 [[[x0, x2], x1], x1],
                  [x0, [[x1, x2], x2]],
+                 [[[x0, x2], x1], x1],
                  [[x0, x2], [x1, x2]],
                  [[[x0, x2], x2], x1],
                  [[[x0, x2], x2], x2],

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​7b25ddc

Using faster generator for LyndonWords and fixing doctest in free_lie_algebra.py.

[tscrim]

The change in comment:13 is actually slower in both Python and Cython. It has something to do with how Python constructs these things internally (but I agree that it is counter-intuitive).

With comment:12:

sage: LW = LyndonWords(11,6)
sage: %time for x in LW: pass
CPU times: user 200 ms, sys: 21.3 ms, total: 222 ms
Wall time: 201 ms
sage: LW = LyndonWords(11,7)
sage: %time for x in LW: pass
CPU times: user 1.85 s, sys: 8.12 ms, total: 1.85 s
Wall time: 1.84 s

vs old

sage: LW = LyndonWords(11,6)
sage: %time for x in LW: pass
CPU times: user 475 ms, sys: 42.2 ms, total: 518 ms
Wall time: 465 ms
sage: LW = LyndonWords(11,7)
sage: %time for x in LW: pass
CPU times: user 4.25 s, sys: 17.8 ms, total: 4.27 s
Wall time: 4.24 s

[mantepse]

One more doctest, a pyflakes thing, and a corner case:

sum(1 for lw in LyndonWords(1, 1000)) is stupid, but (with this patch) it kills my computer by filling up the memory really quickly. Without this patch, it hits the recursion limit, whereas it gives 0 (which is correct) up to and including length 988.

src/sage/combinat/combinat_cython.pyx

@@ -168 +168 @@
 
         sage: list(generate_lyndon_words(5, 0))
         []
+
+        sage: list(generate_lyndon_words(1, 1000))
+        []
     """
     cdef Py_ssize_t i, j
     if k == 0:
@@ -176 +179 @@
         for i in range(n):
             yield [i]
         return
+    if n == 1:
+        return
 
     cdef list a = [0] * (k+1)
     i = k

src/sage/combinat/lyndon_word.py

@@ -23 +23 @@
 from sage.misc.all import prod
 
 from . import necklace
-from sage.combinat.integer_vector import IntegerVectors, integer_vectors_nk_fast_iter
 from sage.combinat.words.words import FiniteWords
 from sage.combinat.combinat_cython import generate_lyndon_words
 
@@ -456 +455 @@
 
             sage: sum(1 for lw in LyndonWords(11, 6))  # long time
             295020
+
+            sage: sum(1 for lw in LyndonWords(1000, 1))
+            1000
+
+            sage: sum(1 for lw in LyndonWords(1, 1000))
+            0
         """
         W = self._words._element_classes['list']
         for lw in generate_lyndon_words(self._n, self._k):

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b9d8ee4

Corner case, pyflakes, and some extra doctests.

[tscrim]

Fixed and added. I also added more doctests for the other corner case of LyndonWords(1,1).

[mantepse]

Good catch! Funny that the # long disappeared :-)

I have a few hopefully final questions/requests:

• since it is very likely that more and more fundamental iterators are cythonized in a similar way (eg. #25864 would probably make a lot of sense), I think it would be good to create and stick to a good naming scheme. It might be a pain to do that later. In short, I think lyndon_word_iterator would be better.

• there is a typo in the docstring of the iterator, I propose the following instead:

  src/sage/combinat/combinat_cython.pyx

  @@ -144 +144 @@
   
   def generate_lyndon_words(Py_ssize_t n, Py_ssize_t k):
       """
  -    Generate all Lyndon words with of length ``k`` with ``n`` letters.
  +    Generate the Lyndon words of fixed length `k` over the alphabet `{0, 1, ..., n-1}`.
   
       The resulting Lyndon words will be words represented as lists
       whose alphabet is ``range(n)``.
   
       ALGORITHM:
   
  -    The FKM algorithm from *Combinatorial Generation* by Ruskey.
  +    The iterative FKM Algorithm 7.2 from *Combinatorial Generation* by Ruskey.
   
       EXAMPLES::

• in the documentation of the module lyndon_word.py, k and n are swapped in the docstrings class LyndonWords_nk and __init__ just thereafter. Should this be fixed in a separate ticket - I think it's easier to do it now.

Otherwise, I think it is ready to go.

[tscrim]

You can make and push changes too. :) I am going to bed now, but can do it in the morning.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​2b3f9d4

fix doc and rename iterator

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0b4c68b

A few more doc tweaks and making Ruskey a proper reference.

[tscrim]

Thank you. I made a few other small changes: I make Ruskey into an actual reference and the 1-line description of lyndon_word_iterator just use n as code because the alphabet description is given in the main body (and I prefer to use code format as much as possible in the 1-line descriptions for methods).

If my changes are good, then positive review.

[tscrim]

Thank you.