Speedup WordMorphism.growing_letters

[gh-mrejmon]

This patch changes the implementation of WordMorphism.growing_letters to be less sophisticated but faster.

sage: m = WordMorphism('a->aa,b->bc,c->def,d->fe,e->df,f->gh,g->hh,h->')
sage: %timeit m.growing_letters()
24.7 µs ± 74.3 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

vs.

sage: %timeit m.growing_letters()
7.89 ms ± 84 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

It also adds a method for returning "immortal" letters (letter a is mortal for a morphism s if there exists an integer k>0 such that s^k(a) = ε).

[vdelecroix]

You are not allowed to mutate self in

+        self._morph, new_morph = new_morph, self._morph
+        result = self.immortal_letters()
+        self._morph = new_morph

The code might be interrupted during the second line (an alaram, a keyboard interrupt, etc). In such situation you would end up with corrupted data.

[git]

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

​bd67035

31760: Don't modify self

[gh-mrejmon]

Replying to vdelecroix:

You are not allowed to mutate self in

+        self._morph, new_morph = new_morph, self._morph
+        result = self.immortal_letters()
+        self._morph = new_morph

The code might be interrupted during the second line (an alaram, a keyboard interrupt, etc). In such situation you would end up with corrupted data.

Fixed.

[tscrim]

I made a few trivial tweaks to the code to be a bit easier to read and follow our coding conventions. If my changes are good, then positive review unless Vincent has any more comments.

---

New commits:

​61c4f42	Merge branch 'u/gh-mrejmon/speedup_growing' of git://trac.sagemath.org/sage into public/combinat/growing_letters_speedup-31760
​24f3bf9	Small Python tweaks to immortal_letters().

[git]

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

​ce00ad6

improve growing letters, immortal letters

[vdelecroix]

I hope my last commit simplifies a bit the code. The ticket can be set to positive review if nobody thinks otherwise.

[git]

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

​a6fa7c6

do not build custom domain/codomain

[vdelecroix]

It is a pity that a6fa7c6 makes it faster in practice...

[git]

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

​2638908

31760: Add one set() call

[gh-mrejmon]

Thanks for improving the code, I did a last small change.

[git]

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

​5aab984

31760: Replace set with list in docs

[gh-mrejmon]

On second thought, what do you think about replacing:

if not self.is_endomorphism():

with something like:

if not set(self.codomain().alphabet()).issubset(self.domain().alphabet()):

so that one doesn't have to manually specify the codomain in cases like this:

WordMorphism('a->b,b->c,c->d,d->c', codomain=Words('abcd')).growing_letters()

[vdelecroix]

Replying to gh-mrejmon:

On second thought, what do you think about replacing:

if not self.is_endomorphism():

with something like:

if not set(self.codomain().alphabet()).issubset(self.domain().alphabet()):

so that one doesn't have to manually specify the codomain in cases like this:

WordMorphism('a->b,b->c,c->d,d->c', codomain=Words('abcd')).growing_letters()

Indeed. Is there a name for functions f: A -> B with B included in A?

[tscrim]

Replying to vdelecroix:

Indeed. Is there a name for functions f: A -> B with B included in A?

I would just call it an endomorphism as the only difference is a promise that the image is smaller than all of A.

Also, doctest failures from the patchbot:

**********************************************************************
File "src/sage/combinat/words/morphism.py", line 1981, in sage.combinat.words.morphism.WordMorphism.periodic_points
Failed example:
    for p in f.periodic_points():
        print("{} , {}".format(len(p), p[0]))
Expected:
    1 , ababaaababaaabaabaababaaababaaabaabaabab...
    1 , baaabaabaababaaabaababaaabaababaaababaaa...
Got:
    1 , baaabaabaababaaabaababaaabaababaaababaaa...
    1 , ababaaababaaabaabaababaaababaaabaabaabab...
**********************************************************************
File "src/sage/combinat/words/morphism.py", line 1987, in sage.combinat.words.morphism.WordMorphism.periodic_points
Failed example:
    for p in f.periodic_points():
        print("{} , {}".format(len(p), p[0]))
Expected:
    2 , aababaaaababaababbabaababaababbabaababaa...
Got:
    2 , babbabaababaababbabbabbabaababaababbabaa...
**********************************************************************

[vdelecroix]

Replying to tscrim:

Replying to vdelecroix:

Indeed. Is there a name for functions f: A -> B with B included in A?

I would just call it an endomorphism as the only difference is a promise that the image is smaller than all of A.

It is a bit like calling a matrix with more rows than column a square matrix :)

sage: WordMorphism('a->a,b->b,c->a').incidence_matrix()
[1 0 1]
[0 1 0]

Also, doctest failures from the patchbot:

I will see why this is not consistent.

[git]

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

​1400168

fix ordering in get_cycles

[vdelecroix]

Replying to vdelecroix:

Replying to gh-mrejmon:

On second thought, what do you think about replacing:

if not self.is_endomorphism():

with something like:

if not set(self.codomain().alphabet()).issubset(self.domain().alphabet()):

so that one doesn't have to manually specify the codomain in cases like this:

WordMorphism('a->b,b->c,c->d,d->c', codomain=Words('abcd')).growing_letters()

Indeed. Is there a name for functions f: A -> B with B included in A?

Alternatively, we can make WordMorphism construct so that if the codomain is included in the domain then the default is to set codomain=domain.

[git]

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

​35f617b

clarify get_cycles

[tscrim]

Replying to vdelecroix:

Replying to tscrim:

Replying to vdelecroix:

Indeed. Is there a name for functions f: A -> B with B included in A?

I would just call it an endomorphism as the only difference is a promise that the image is smaller than all of A.

It is a bit like calling a matrix with more rows than column a square matrix :)

sage: WordMorphism('a->a,b->b,c->a').incidence_matrix()
[1 0 1]
[0 1 0]

I agree fundamentally with your point, but not a generic example. I would argue that if there is a canonical way of embedding the image, I think we can allow the abuse. ;)

[tscrim]

Replying to vdelecroix:

Alternatively, we can make WordMorphism construct so that if the codomain is included in the domain then the default is to set codomain=domain.

-1 on this. This would break the composition f: A -> B and g: B -> C if A < B but C is some other unrelated set of words that is not defined on all of A.

[gh-mrejmon]

Replying to tscrim:

Replying to vdelecroix:

Alternatively, we can make WordMorphism construct so that if the codomain is included in the domain then the default is to set codomain=domain.

-1 on this. This would break the composition f: A -> B and g: B -> C if A < B but C is some other unrelated set of words that is not defined on all of A.

I don't think it would in practice due to the way __mul__ is implemented:

def __mul__(self, other):
    r"""
    Returns the morphism ``self``\*``other``.
    ...
    """
return WordMorphism(dict((key, self(w)) for key, w in other._morph.items()), codomain=self.codomain())

and for example:

sage: f = WordMorphism('a->a,b->a', codomain=FiniteWords('ab'))
sage: g = WordMorphism('a->0')
sage: g * f
WordMorphism: a->0, b->0

All in all, I don't mind either of these approaches. I also noticed that in the docs of is_endomorphism there already is:

Returns ``True`` if the codomain is a subset of the domain.

And hence that is_endormophism did work with subsets in some point, but this was changed in #8920 due to not being mathematically accurate.

[vdelecroix]

Replying to tscrim:

Replying to vdelecroix:

Alternatively, we can make WordMorphism construct so that if the codomain is included in the domain then the default is to set codomain=domain.

-1 on this. This would break the composition f: A -> B and g: B -> C if A < B but C is some other unrelated set of words that is not defined on all of A.

Maybe I was unclear. What I suggested is to change

sage: WordMorphism('a->a,b->a').codomain()
Finite words over {'a'}

to

sage: WordMorphism('a->a,b->a').codomain()
Finite words over {'a', 'b'}

The keyword codomain will not disappear and still allows you to build any kind of morphism you want

sage: WordMorphism('a->a,b->a', codomain=FiniteWords('a')).codomain()
Finite words over {'a'}

[vdelecroix]

This discussion is not exactly in the scope of the ticket and I suggest that we conclude here and talk about what is an endomorphism elsewhere. What do you think?

[tscrim]

I think it is still somewhat relevant to the ticket at hand, so we should see if we can come to a consensus.

That is what I understood your proposal to be, but I am thinking of the following situation:

sage: I = WordMorphism('a->a,b->b')  # The identity map
sage: f = WordMorphism('a->x')                                                            
sage: I.domain()
Finite words over {'a', 'b'}
sage: I.codomain()
Finite words over {'a', 'b'}
sage: f.domain()
Finite words over {'a'}
sage: f.codomain()
Finite words over {'x'}
sage: f * I  # This should not be a valid composition
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-7-dc18bb6a87ea> in <module>
----> 1 f * I

~/sage-build/local/lib/python3.9/site-packages/sage/combinat/words/morphism.py in __mul__(self, other)
    976             WordMorphism:
    977         """
--> 978         return WordMorphism(dict((key, self(w)) for key, w in other._morph.items()), codomain=self.codomain())
    979 
    980     def __pow__(self, exp):

~/sage-build/local/lib/python3.9/site-packages/sage/combinat/words/morphism.py in <genexpr>(.0)
    976             WordMorphism:
    977         """
--> 978         return WordMorphism(dict((key, self(w)) for key, w in other._morph.items()), codomain=self.codomain())
    979 
    980     def __pow__(self, exp):

~/sage-build/local/lib/python3.9/site-packages/sage/combinat/words/morphism.py in __call__(self, w, order, datatype)
    794                 im = C()
    795                 for a in w:
--> 796                     im += self._morph[a]
    797                 if datatype is not None:
    798                     return C(im, datatype=datatype)

KeyError: 'b'

Now this is failing, as it should, but not in a meaningful way IMO. The error message is somewhat cryptic, It all works without explicit consideration of the domain/codomain matching because of how it is coded, but it feels a bit fragile to me.

[vdelecroix]

Replying to tscrim:

I think it is still somewhat relevant to the ticket at hand, so we should see if we can come to a consensus.

That is what I understood your proposal to be, but I am thinking of the following situation:

SNIP

Now this is failing, as it should, but not in a meaningful way IMO. The error message is somewhat cryptic, It all works without explicit consideration of the domain/codomain matching because of how it is coded, but it feels a bit fragile to me.

It looks fragile to me as well but also unrelated to this ticket which is about improving growing_letters. comment:14 which is the starting point of the discussion about is_endomorphism was complaining about the fact that growing_letters (and many other methods) remains valid under the more general assumption that you can iterate the morphism. I opened #31797 for the latter.

[tscrim]

Alright, then let's set this to a positive review. Thanks.