Anacycliques¶

Trouver tous les anacycliques dans une liste de mots (issue de lexique.org par exemple). Les palindromes sont des cas particuliers d'anacycliques.
Ex : 'été' est un palidrome
'vu' et 'uv', 'tort' et 'trot' sont des anacycliques

Tester si deux mots sont des anacycliques est très simple en Python. Pour cela on peut utiliser les slices avec le troisième argument pour le pas.
word[::-1] : un pas de -1 permet d'inverser la chaîne de caractères.

In [ ]:

def is_anacyclique(word1, word2):
    """
    Returns True if the given words are palindromes
    False if not
    """
    if word1 == word2[::-1]:
        return True
    else:
        return False

In [ ]:

is_anacyclique("tort", "trot")

In [19]:

words = []
with open('lexique381.ortho', 'r') as f:
    for line in f:
        line = line.rstrip()
        if len(line) != 1:
            words.append(line)
print("Nb de mots : {}".format(len(words)))

Nb de mots : 142641

Tester l'appartenance d'un élément à une liste de 142641 éléments est couteux en temps de traitement.
Le test d'appartenance d'un élément à une liste est de complexité 0(n) (voir TimeComplexity sur le wiki Python).
Ici comme la liste est déjà pas mal grande et que l'opération est répétée n fois, le temps de traitement est rhédibitoire.

Puisqu'on aime se compliquer la vie on peut essayer de réduite la taille de la liste en se limitant aux mots de même taille. Les anacycliques sont forcément de même taille.

In [ ]:

def words_by_length(words):
    """
    Receives a list of words sorted by length, returns a list of words for each length
    """
    for length in range(len(words[0]), len(words[-1]) + 1):
        yield [word for word in words if len(word) == length]

In [ ]:

res = set()
sorted_words = sorted(words, key = lambda x:len(x))
for words_n in words_by_length(sorted_words):
    for word in words_n:
        acyclique = word[::-1]
        if acyclique in words_n:
            res.add(tuple([word, acyclique]))
        
for match in sorted(res):
    print(match)

Malgré le découpage du lexique en mots de même taille et l'utilisation des générateurs, le temps de traitement reste important.
Essayons avec un dictionnaire.

In [12]:

from collections import defaultdict
words_d = defaultdict()
with open('lexique381.ortho', 'r') as f:
    for line in f:
        line = line.rstrip()
        if len(line) != 1:
            words_d[line] = ""
print("Nb de mots : {}".format(len(words_d.keys())))

Nb de mots : 125627

On a une différence de taille d'avec la liste parce que le dictionnaire supprime les doublons (125627 contre 142641). Mais ça ne change pas vraiment l'ordre du volume des données.

In [15]:

res = set()
for word in words_d.keys():
    acyclique = word[::-1]
    if acyclique in words:
        res.add(tuple([word, acyclique]))
        
for match in sorted(res)[:20]:
    print(match)

('aa', 'aa')
('ada', 'ada')
('ados', 'soda')
('adulé', 'éluda')
('aga', 'aga')
('agas', 'saga')
('ah', 'ha')
('ail', 'lia')
('ailé', 'élia')
('air', 'ria')
('ako', 'oka')
('alla', 'alla')
('alloc', 'colla')
('amis', 'sima')
('an', 'na')
('ana', 'ana')
('anas', 'sana')
('angor', 'rogna')
('annoté', 'étonna')
('ara', 'ara')

Là c'est tout de suite BEAUCOUP plus rapide (supprimez [:20] pour avoir tous les résultats). Mais pourquoi ?
Parce que le test d'appartenance pour un dictionnaire est estimé à O(1) en moyenne (O(n) dans le pire des cas).
idem pour les ensembles (set)

In [16]:

words_s = set()
with open('lexique381.ortho', 'r') as f:
    for line in f:
        line = line.rstrip()
        if len(line) != 1:
            words_s.add(line)
print("Nb de mots : {}".format(len(words_s)))

Nb de mots : 125627

In [17]:

res = set()
for word in words_s:
    acyclique = word[::-1]
    if acyclique in words:
        res.add(tuple([word, acyclique]))
        
for match in sorted(res)[:20]:
    print(match)

('aa', 'aa')
('ada', 'ada')
('ados', 'soda')
('adulé', 'éluda')
('aga', 'aga')
('agas', 'saga')
('ah', 'ha')
('ail', 'lia')
('ailé', 'élia')
('air', 'ria')
('ako', 'oka')
('alla', 'alla')
('alloc', 'colla')
('amis', 'sima')
('an', 'na')
('ana', 'ana')
('anas', 'sana')
('angor', 'rogna')
('annoté', 'étonna')
('ara', 'ara')

Allez on va s'amuser à mesurer ça :

In [25]:

%time "palindrome" in words
%time "palindrome" in words_d
%time "palindrome" in words_s

CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 3.02 ms
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 7.39 µs
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 8.82 µs

Out[25]:

True

Si vous êtes intéressés par l'implémentation des dictionnaires vous pourrez lire l'article suivant : [Python dictionary implementation] (http://www.laurentluce.com/posts/python-dictionary-implementation/)

In [ ]: