Partage

[exercice] La suite de Conway

1 -> 11-> 21 -> 1211 -> 111221 -> 312211 : suivant = ????

<< 1 2 3

9 août 2010 à 23:25:25

Là ou ca devient cool, c'est lorsqu'on essaye de donner le nombre de chiffres dans la n-eme chaine.

Moi j'ai 12.680.852 chiffres pour la 60e ligne et 894.810 pour n = 50.

L'objectif devient alors de gérer la mémoire de telle manière que tout ce qui est inutile est effacé.

A première vue, on a besoin que de trois caractères dans chaque chaine pour pouvoir travailler la suivante.

En mémoire on a alors (3*n) données à stoker.

théoriquement ca marche bien, en pratique je ne peux pas dépasser 60. Ça doit être un garbage collector qui ne fait pas son boulot.

Si vous avez des bonnes idées ?

bluestorm

9 août 2010 à 23:29:04

Une version en python, en mémoire linéaire à l'indice de la ligne demandée : si on demande la N-ième ligne générée à partir de la ligne [1] en appliquant la transformation décrite, on utilisera de la mémoire proportionnellement à N.

def init_conway():
    yield 1

def conway(input):
    last = input.next()
    count = 1
    for c in input:
        if c == last:
            count += 1
        else:
            yield count
            yield last
            last = c
            count = 1
    yield count
    yield last

def conway_n(n):
    input = init_conway()
    for i in range(1, n):
        input = conway(input)
    return input

for i in conway_n(20):
    print i

ordiclic

9 août 2010 à 23:41:52

Pour moi, c'est pour n=49 que le nombres de chiffres est de 12.680.852.
Je viens de réussir à monter à n=70 avec mon code (qui correspond pour toi à n=71), sans m'être fait manger par des petits hommes verts (j'ai quand même utilisé 600 MO de RAM), mais je manipule des chaines relativement courtes, donc ça aide. J'obtiens une longueur de la chaine de 234.241.786.

bluestorm : input est une fonction builtin de python, c'est méchant de s'en servir comme nom de variable.

Layus

10 août 2010 à 0:13:50

Je n'ai pas fait d'étude approfondie mais sur les 40 premières chaines, on a quand-même une jolie progression exponentielle de la taille.

Plus exactement chaque chaine est +/-31% plus longue que la précédente.

Je n'ai pas réussi à mettre en pratique ma théorie d'utilisation minimale de la mémoire...
L'inspiration vient en dormant dit-on !

Sur ce donc, bonne nuit !

[Edit]

Finalement, j'ai réussi, avec un langage paresseux... Bon évidement le temps de calcul s'allonge.

Moralité, on a pas d'omelettes sans casser des oeufs...

[/Edit]

Lord Casque Noir

10 août 2010 à 0:14:55

Il est vrai que ce type de problème se prête bien à l'utilisation d'une regexp.

time perl -E 'for ( $_=1;; ) { say; s/((.)\2*)/length($1).$2/xeg; }' | head -n 50 >/dev/null

real    0m2.377s
user    0m2.330s
sys     0m0.040s

Un algo classique en python :

def conway( n ):
	if n <= 1:
		return "1"
	s = conway( n-1 )
	
	result = []
	
	pred  = c = s[0]
	count = 1
	
	for c in s[1:]:
		if c == pred:
			count += 1
		else:
			result.append( str( count ))
			result.append( pred )
			pred  = c
			count = 1
			
	result.append( str( count ))
	result.append( c )
	
	result = "".join( result )
	
	return result

print conway(50)

time python conway.py >/dev/null

real    0m1.397s
user    0m1.370s
sys     0m0.020s

Autrement dit, l'algo "de base" auquel tout le monde a pensé sur ce topic est 2x plus rapide que perl dans son domaine de prédilection (les regexp). Je suppose que perl ne compile pas les regexp en langage machine, je me demande bien pourquoi.

Variante avec itertools.groupby :

import itertools

def conwayg( n ):
	if n <= 1:
		return "1"
		
	s = conway( n-1 )
	
	result = []
		
	for c, l in itertools.groupby( s ):
		result.append( str( len( tuple( l ))))
		result.append( c )
	
	result = "".join( result )
	
	return result

time python conway.py >/dev/null

real    0m2.309s
user    0m2.260s
sys     0m0.020s

Pas terrible !...

Mais bon, le langage de référence pour faire ce genre de truc, c'est encore et toujours le C. Donc on va faire du C en python, en utilisant pyrex, lol.

cdef cconway( int n ):
	if n <= 1:
		return "1"

	ss = conway( n-1 )
	cdef char* s 
	s = ss
	
	result = ' ' * (len(ss)*2)
	cdef char* rp
	rp   = result

	cdef int   count, rpos, spos, slen
	cdef char  c, pred

	rpos = 0
	pred  = c = s[0]
	count = 1
	
	spos = 1
	slen = len( ss )
	while( spos < slen ):
		c = s[spos]
		spos += 1
		if c == pred:
			count += 1
		else:
			rp[rpos]   = 48 + count
			rp[rpos+1] = pred
			rpos += 2
			pred  = c
			count = 1
			
	rp[rpos]   = 48 + count
	rp[rpos+1] = pred
	rpos += 2
	
	result = rp[0:rpos]
	
	#~ print n, repr( result )
	
	return result

def conway( n ):
	return cconway( n )

Code "un peu" laid (surtout le malloc), certes. Et le programme python :

import cconway

print cconway.conway( 50 )

pyrexc cconway.pyx && gcc -c -fPIC -O2 -I/usr/include/python2.6 cconway.c && gcc -shared cconway.o -o cconway.so && time python conway.py >/dev/null

real    0m0.046s
user    0m0.040s
sys     0m0.010s

Donc on passe de 1.4s à 40 ms, en rajoutant une boucle autour on voit que la fonction prend en fait 23 ms. Ce qui donne une petite accélération de 60x (lol).

Moralité de la chose :

- python est très lent (mais en général bien assez rapide)
- pour ce genre de truc rien ne vaut le C
- la facilité d'interfaçage d'un langage avec le C est donc un point non négligeable

(il m'a fallu 20 minutes pour pondre cette petite crotte, je ne savais pas utiliser pyrex avant).

ordiclic

10 août 2010 à 0:34:58

En effet, c'est rapide , avec pyrex. Merci d'avoir montré ça !
Je verrai ce que donne mon code avec pyrex, vu que la stratégie avec les atomes est plus rapide, par nature, que le comptage simple, vu que les chaînes manipulées sont moins lourdes, et un seul parcours de la chaîne suffit.

candide

10 août 2010 à 3:33:38

Citation : ordiclic

Edit 2 : j'ai réussi ! et le résultat est largement à la hauteur de ce qui était attendu :

Bravo ordiclic, super boulot, fallait oser s'y attaquer ! Et la vitesse d'exécution c'est ... une bombe atomique :lol:

J'avais déjà vu des articles sur cette suite de Conway (cf. par exemple le livre Jeux mathématiques et Mathématiques des jeux) et son théorème "cosmologique" mais je n'avais jamais osé y regarder vraiment tant ça me paraissait compliqué. Grâce à ton code, les choses m'apparaissent ultra-simples, et donc merci pour ce travail de clarification.

Citation : bluestorm

Très honnêtement, le coeur de cet algorithme est plus lisible que la plupart de vos codes python,

Oui quand on a ton expérience des langages de programmation. Bon pour moi c'est totalement cryptique. Il semblerait qu'on puisse faire la même chose en Python (en moins concis et aussi cryptique), voici le code que j'ai trouvé sur rosettacode (qui propose d'ailleurs d'autres codes en Python) :

import re

def lookandsay(z):
    return re.sub(r'(.)\1*', lambda m: str(len(m.group(0))) + m.group(1),z)

n=50
num = "1"
for i in range(n-1):
    num = lookandsay(num)

print num

Hélas l'exécution est assez lente (pour n=50, le temps est de 2.8s alors qu'ordiclic dans sa version 1 fait 0.25s et que la version naïve est entre 1s et 1.5s).

Quelqu'un connait-il assez bien les re de Python pour donner quelque chose de plus efficace ?

Citation : bluestorm

sans vouloir diminuer l'astuce d'ordiclic, s'émerveiller de ses performances comparé à vos codes python donne une impression de ridicule. L'implémentation la plus populaire de votre langage fait qu'un code moche, illisible et algorithmiquement stupide (de nombreux parcours de la même chaîne alors qu'on peut faire ça en mémoire constante) est plus rapide qu'une implémentation correcte à plusieurs ordres de grandeur près.

Je pense que le vocabulaire employé ("ridicule", "stupide") est excessif. Mais il est vrai qu'un tel décalage entre un hack et un code "naturel" est surprenant.

Citation : bluestorm

Ce que disent les mesures de performance, ce n'est pas que sa méthode est rapide, mais plutôt que vous utilisez des outils inadaptés.

Comprends pas. Tu veux dire que Python n'est pas adapté pour coder la suite de Conway ?

Citation : bluestorm

Qu'est-ce que le choix du langage a apporté à vos codes pour résoudre ce problème ? Il me semble que la seule valeur ajoutée de Python par rapport à C ici, c'est que vous n'avez pas à vous soucier de l'allocation dynamique.

Oui mais en dehors de ça, pour le passage d'une chaîne à sa suivante, je trouve que, pour le coup, le code est vraiment plus naturel en C : à cause des chaines fermées par une sentinelle, à cause de la boucle for très différente et plus souple que la boucle for de Python.

Citation : EMC1

Je pense aussi que tout le monde ici a parfaitement conscience qu'on ne cherche pas en Python à se contorsionner pour que le programme s'exécute vite, mais qu'on privilégie la simplicité et la lisibilité.

C'est vrai mais ici je trouve quand même que l'algo naturel (utiliser une boucle for) ne donne pas un code super lisible. À l'usage, je trouve assez contraignant qu'on travaille avec un itérateur. En pratique il arrive fréquemment qu'on ait besoin d'une boucle for car on doit parcourir un objet de son début à sa fin mais on doit faire des sauts en cours de parcours (c'est typiquement le cas pour Conway) et avec un itérateur comme for c in mot , tu peux pas passer certains élément (ou revenir en arrière). Tu me diras qu'on peut utiliser while mais c'est beaucoup moins pratique et les performances vont s'en ressentir.

Citation : bluestorm

Une version en python, en mémoire linéaire à l'indice de la ligne demandée : si on demande la N-ième ligne générée à partir de la ligne [1] en appliquant la transformation décrite, on utilisera de la mémoire proportionnellement à N.

Pas mal du tout et plutôt efficace. J'ai pas compris tous les détails de l'algo mais cela revient-il à parcourir nos chaines par exemple

11
11
21
311
111221
312211
13112221
1113213211
31131211131221

non pas dans le sens gauche droite puis haut vers bas comme on la fait usuellement mais plutôt haut vers bas puis droite vers gauche (par exemple le 13 de la dernière ligne ne dépend que du 3 au-dessus qui lui-même ne dépend que de 222 au-dessus encore, etc) ?

Citation : ordiclic

J'obtiens une longueur de la chaine de 234.241.786.

Exact, cf. ce site.

Citation : Lord Casque Noir

Un algo classique en python :

def conway( n ):
	if n <= 1:
		return "1"
	s = conway( n-1 )
	
	result = []
	
	pred  = c = s[0]
	count = 1
	
	for c in s[1:]:
		if c == pred:
			count += 1
		else:
			result.append( str( count ))
			result.append( pred )
			pred  = c
			count = 1
			
	result.append( str( count ))
	result.append( c )
	
	result = "".join( result )
	
	return result

print conway(50)

Je trouve que c'est un des meilleurs algo naïf du fil, disons un des plus naturels (mis-à-part la récursivité un peu factice) et en plus plutôt assez rapide (1.2s pour n=50 alors que mon code met 1.5s). Mais ce n'est pas encore exactement l'algo de Monsieur toutlemonde. En pratique je fais quoi pour trouver le suivant de z=111221 ?

Rép : je compte directement le nombre de 1 (je vois 3, par une recherche séquentielle) et une fois que je l'ai, alors
a) j'écris 31 dans ma nouvelle chaîne
b) j'incrémente directement dans z vers la nouvelle position en décalant du 3 que j'ai trouvé

et ainsi de suite.

Donc, moi ce que je souhaite, c'est un code qui colle exactement à ça. Or aucun code ne l'a fait jusqu'à présent. Et pourquoi ? Parce qu'on ne peut pas facilement et directement trouver le nombre d'occurrences identiques à partir d'une position donnée. Alors si, il y a bien un moyen avec le module re mais c'est cryptique et en plus il faut gérer une exception ce que je vois ici comme une verrue :

from re import match

def conway(z):
    zz=""
    try: #moche
        while True: # moche
            r=match("%s+"%z[0], z).end(0) # repetition du caractere, assez moche
            zz+=str(r)+z[0]
            z=z[r:]
    except IndexError: pass # moche
    return zz

def lookAndSay(n):
    z="1"
    for _ in range(n-1):
        z=conway(z)
    return z


n=35
z=lookAndSay(n)
print z

Et en plus, il met un temps infini pour faire n=50.

Citation : Lord Casque Noir

rpos += 2
</secret>

Oui mais là tu triches un peu car tu n'est pas censé savoir que la répétition sera un nombre à un seul chiffre.

Citation : Lord Casque Noir

Donc on passe de 1.4s à 40 ms, en rajoutant une boucle autour on voit que la fonction prend en fait 23 ms. Ce qui donne une petite accélération de 60x (lol).

Moralité de la chose :

- python est très lent (mais en général bien assez rapide)
- pour ce genre de truc rien ne vaut le C
- la facilité d'interfaçage d'un langage avec le C est donc un point non négligeable

(il m'a fallu 20 minutes pour pondre cette petite crotte, je ne savais pas utiliser pyrex avant).

Merci de cette démo fort intéressante. Et en plus on a même pas besoin de connaitre le C (ou à peine).

Lord Casque Noir

10 août 2010 à 8:41:36

En fait pyrex c'est sympa mais c'est très limité. Le langage ressemble à python mais c'est intéressant que si tu prends un bout de python et que t'as envie de l'accélérer sans trop le modifier. Et surtout tu n'as pas à écrire le code d'interface entre python et C, ça simplifie énormément les choses.

Tout repose sur les déclarations de types d'argument (cdef). A chaque fois que tu remplaces un type python par un type c, les performances augmentent (normal, si tu déclares un int, il remplace des dispatch de méthodes python "operator+" par une instruction genre "add" par exemple).

Sinon, vous avez pensé à faire la concaténation avec un CStringIO au lieu d'une liste ?

ordiclic

10 août 2010 à 9:54:28

Personnellement, j'utilise un générateur pour faire la concaténation sur une chaine ; j'ai essayé d'utiliser les StringIO, mais ça n'accélère rien du tout.

Je pense que les seules optimisations possibles sont l'utilisation de pyrex, et peut-être une structure de données plus adaptée, si je trouve.

bluestorm

10 août 2010 à 10:28:01

Citation : candide

Citation : bluestorm
Une version en python, en mémoire linéaire à l'indice de la ligne demandée : si on demande la N-ième ligne générée à partir de la ligne [1] en appliquant la transformation décrite, on utilisera de la mémoire proportionnellement à N.
def conway(input):
    last = input.next()
    count = 1
    for c in input:
        if c == last:
            count += 1
        else:
            yield count
            yield last
            last = c
            count = 1
    yield count
    yield last
Pas mal du tout et plutôt efficace. J'ai pas compris tous les détails de l'algo [..]
Citation : Lord Casque Noir
Un algo classique en python :
def conway( s ):
	result = []
	
	pred  = c = s[0]
	count = 1
	
	for c in s[1:]:
		if c == pred:
			count += 1
		else:
			result.append( str( count ))
			result.append( pred )
			pred  = c
			count = 1
			
	result.append( str( count ))
	result.append( c )
	
	result = "".join( result )
	
	return result
Je trouve que c'est un des meilleurs algo naïf du fil, disons un des plus naturels (mis-à-part la récursivité un peu factice) [..]

C'est drôle, tu trouves mon algorithme difficile à comprendre et celui de Lord Casque Noir naturel. Regarde les un peu mieux; pour aider la comparaison j'ai isolé des deux côté la partie importante, qui passe d'une ligne de la suite à la suivante.
C'est exactement le même code, à part que j'utilise yield là où lui utilise str.append.

Citation : candide

J'ai pas compris tous les détails de l'algo mais cela revient-il à parcourir nos chaines par exemple [..] non pas dans le sens gauche droite puis haut vers bas comme on la fait usuellement mais plutôt haut vers bas puis droite vers gauche

Je n'en sais rien. J'ai juste pris l'algorithme classique, et utilisé des primitives paresseuses plutôt que strictes. Aucune chaîne n'est stockée, elles sont construites au vol, et il n'y a donc aucun coût en mémoire à part le stockage des N itérateurs successifs. Si on veut une vision précise de la dynamique de l'algorithme, il faut retracer les dépendances à la main comme tu fais et c'est compliqué; mais il n'y en a pas besoin pour comprendre l'algorithme (je pense qu'en pratique, il fait haut bas puis gauche droite plutôt que l'algorithme gauche droite puis haut bas classique).

Une version paresseuse similaire (faible consommation mémoire) de l'algorithme d'ordiclic :

def conway(nbr=50):
    if nbr > 7:
        #les atomes ne sont visibles qu'à partir de 7 itérations...
        #et à la 7è itération on a la chaine :
        c = ['\x58', '\x42'].__iter__()
        def reiter(seq, table):
            for x in seq:
                for t in table[x]:
                    yield t
        for i in range(nbr-7):
            c = reiter(c, trans)
        return reiter(c, trad)
    else : #je le gèrerai plus tard, la flemme
        pass

ordiclic

10 août 2010 à 11:03:18

Ton code est rapide bluestorm, mais il ne retourne pas le bon résultat... C'est pour du python2.x ?

Lord Casque Noir

10 août 2010 à 11:13:01

> C'est drôle, tu trouves mon algorithme difficile à comprendre et celui de Lord Casque Noir naturel.

Je préfère aussi celui avec les générateurs. J'ai utilisé une liste parce que c'était plus simple à transposer en pyrex ensuite.

bluestorm

10 août 2010 à 11:18:19

J'ai viré un -1 quelque part qui me semblait louche. En fait, je pense que nos deux codes sont faux, il faudrait mettre un +1 ici.

Dans tous les cas, moi que conway(k) renvoie la k-ième, la k+1-ième ou la k-1-ième itération ça m'est complètement égal, alors si tu veux un code équivalent au tien :

def conway(nbr=50):
    if nbr > 7:
        #les atomes ne sont visibles qu'à partir de 7 itérations...
        #et à la 7è itération on a la chaine :
        c = ['\x58', '\x42'].__iter__()
        def reiter(seq, table):
            for x in seq:
                for t in table[x]:
                    yield t
        for i in range(nbr-7-1):
            c = reiter(c, trans)
        return reiter(c, trad)
    else : #je le gèrerai plus tard, la flemme
        pass

Du reste, à priori, mon code n'a aucune raison d'être particulièrement "rapide", à mon avis il est même un peu plus lent que la version stricte puisque yield et les itérations ne sont sans doute pas terriblement optimisées en Python (contrairement à un langage où la paresse est très présente comme Haskell). Son intérêt c'est qu'il ne consomme pas de mémoire.

ordiclic

10 août 2010 à 11:24:55

En effet, il est plus lent, mais est clair. Je n'avais pas vu qu'il retournait un générateur, c'est pour ça qu'il me paraissait si rapide, en prenant 2 ms.
J'essaye actuellement de faire un code où j'imbrique les générateurs pour économiser le passage vers une string.

Et effectiement, j'ai toujours 2-3 problèmes avec le n° du terme que je calcule.

bluestorm

10 août 2010 à 11:47:06

Citation

J'essaye actuellement de faire un code où j'imbrique les générateurs pour économiser le passage vers une string.

Quelle serait la différence avec ma version de ton code ?

Si tu parles des chaînes dans les tables, jhe pense que les remplacer par une liste suffirait. Tu pourrais aussi nommer tes états avec des entiers plutôt que des caractères, mais ça ne change pas grand chose. S'il y avait des "symboles" (à la lisp/erlang/Ruby) en Python, ils seraient agréables à utiliser ici.

Edit : une définition plus sucrée de la fonction clé, reiter :

def reiter(seq, table):
    return (t for x in seq for t in table[x])

ordiclic

10 août 2010 à 14:49:37

Voilà ce que je cherchais à faire, en gros ; en effet, il n'y a pas de différence majeure avec ton code.
Par contre, comme tu le soupçonnais, les générateurs sont lents en python : en effet, j'ai essayé d'utiliser des list comprehensions à la place des generator expressions, et le programme est sensiblement plus rapide, même si en réalité, c'est la traduction de la chaîne qui prend le plus de temps.
Je vais essayer d'installer pyrex sur windows, et sortir un algo correct.

bluestorm

11 août 2010 à 11:43:43

En étudiant, comme a commencé à le faire candide, le flot de contrôle des solutions paresseuses (avec "yield"), je suis arrivé à l'algorithme suivant, complètement itératif mais avec le même comportement que l'algorithme paresseux.

from collections import deque

def count_conway(nbr=50):
    if nbr < 7: #les atomes ne sont visibles qu'à partir de 7 itérations...
        return None
    result_len = 0
    nb_lines = nbr - 7
    maxlen = max(len(s) for s in trans.values())
    # print "maxlen", maxlen
    lines = [deque(maxlen=maxlen) for i in range(nb_lines)]

    # def debug(c): return hex(ord(c))

    def extend(i, li):
        # print "extend", i, [debug(c) for c in li]
        lines[i].extend(li)
    index = 0
    extend(index, "\x58\x42")
    while True:
        while True:
            # print "ascending", index, len(lines[index]), debug(lines[index][0])
            elem = lines[index].popleft()
            index += 1
            if index == nb_lines:
                # print "traduction", trad[elem]
                result_len += len(trad[elem])
                break
            extend(index, [c for c in trans[elem]])


        while True:
            index -= 1
            # print "descending", index, len(lines[index])
            if index < 0:
                return result_len
            if len(lines[index]) > 0:
                break

Il calcule ici la taille de la ligne résultat, mais on peut facilement l'adapter pour n'importe quoi d'autre. Ci-dessous, une version où c'est juste un générateur :

def conway(nbr=50):
    if nbr < 7: #les atomes ne sont visibles qu'à partir de 7 itérations...
        raise Error
    nb_lines = nbr - 7
    maxlen = max(len(s) for s in trans.values())
    # print "maxlen", maxlen
    lines = [deque(maxlen=maxlen) for i in range(nb_lines)]

    # def debug(c): return hex(ord(c))
    def extend(i, li):
        # print "extend", i, [debug(c) for c in li]
        lines[i].extend(li)
    index = 0
    extend(index, '\x58\x42')
    while True:
        while True:
            # print "ascending", index, len(lines[index]), debug(lines[index][0])
            elem = lines[index].popleft()
            index += 1
            if index == nb_lines:
                # print "traduction", trad[elem]
                for t in trad[elem]:
                    yield t
                break
            extend(index, [c for c in trans[elem]])

        while True:
            index -= 1
            # print "descending", index, len(lines[index])
            if index < 0:
                raise StopIteration
            if len(lines[index]) > 0:
                break

La grosse déception, c'est que l'algorithme est plus lent que la simple version avec yield : la version directe est environ deux fois plus lente sur mes tests, et la version avec un générateurs quatre fois plus lente.

Je ne sais pas exactement à quoi est due cette lenteur : normalement (si je ne me suis pas planté), l'algorithme est équivalent, et la formulation impérative devrait améliorer ses performances. Je soupçonne que la lenteur est liée à la lenteur du flot de contrôle en Python, et qu'on ne puisse pas y faire grand chose (à part passer à un autre langage ou essayer de changer d'implémentation du langage avec pyrex ou autres).

ordiclic

11 août 2010 à 12:16:25

J'ai réussi à pondre un truc qui ne fait pas des erreurs de partout, ne segfault pas sans cesse et est plus rapide que la version en python pure du programme, mais je suis assez déçu du résultat, parce qu'elle n'est que deux fois plus rapide. Le problème est dû à des problèmes de typage, qui remplacent mes char* par des str sans que je ne le demande.
Dès que j'ai trouvé une solution pour imposer un typage statique, je retravaille et posterai mon code.

bluestorm

11 août 2010 à 12:58:43

Comme personne n'a posté depuis longtemps, il y a dans ce post le contenu d'un post, puis de deux edits successifs, qui auraient dû être des messages à part.

Message initial : Une formulation comme un DFS

En continuant à travailler sur le flot de contrôle, on aboutit à une version particulièrement simple de mon algorithme. La clé est de se rendre compte qu'il s'agit en fait d'un parcours en profondeur sur l'ensemble des lignes à la fois.

Si ça intéresse quelqu'un, je mets la version intermédiaire (avant que je m'en rende compte), où j'ai juste ajouté une pile comme astuce pour éviter la boucle While "décrémentation" de l'algorithme :

def conway_restricted_stack(nbr=50):
    if nbr < 7: #les atomes ne sont visibles qu'à partir de 7 itérations...
        return None
    result_len = 0
    nb_lines = nbr - 7
    maxlen = max(len(s) for s in trans.values())
    # print "maxlen", maxlen
    lines = [deque(maxlen=maxlen) for i in range(nb_lines)]
    stack = []

    # def debug(c): return hex(ord(c))
    def extend(i, li):
        # print "extend", i, [debug(c) for c in li]
        lines[i].extend(li)
        stack.extend([index] * (len(li) - 1))
    index = 0
    extend(index, "\x58\x42")
    while True:
        while True:
            # print "ascending", index, len(lines[index]), debug(lines[index][0])
            elem = lines[index].popleft()
            index += 1
            if index == nb_lines:
                # print "traduction", trad[elem]
                result_len += len(trad[elem])
                break
            extend(index, trans[elem])

        if stack == []:
            return result_len
        index = stack.pop()

La version simple (une fois qu'on se rend compte qu'on peut utiliser la pile pour tout) :

def conway_stack(nbr=50):
    if nbr < 7: #les atomes ne sont visibles qu'à partir de 7 itérations...
        return None
    result_len = 0
    nb_lines = nbr - 7
    stack = []
    def extend(i, li):
        # reversed(li) : item in the stack are popped in reverse order
        stack.extend([(i, v) for v in reversed(li)])
    extend(0, "\x58\x42")
    while stack != []:
        index, elem = stack.pop()
        if index + 1 == nb_lines:
            result_len += len(trad[elem])
        else:
            extend(index + 1, trans[elem])
    return result_len

Au niveau des perfs, c'est en gros toujours équivalent à ma première « version stricte de l'algorithme paresseux ». Bref, c'est sensiblement plus lent que la version stricte d'ordiclic, mais la consommation mémoire est extrêmement faible (proportionnelle au nombre de lignes qu'on veut).

Comme toutes ces versions sont construites sur le code de base d'ordiclic (en particulier ses tables), qui commence à se perdre en milieu de topic, voici une version complète du code :

#!/usr/bin/python3
# -*- coding:utf-8 -*-
#cette table permet de passer d'un élément a un autre au cours des itérations
trans = {
    '\x01':'\x01',
    '\x02':'\x58\x6b\x01\x14\x03',
    '\x03':'\x02',
    '\x04':'\x20\x14\x03',
    '\x05':'\x04',
    '\x06':'\x05',
    '\x07':'\x06',
    '\x08':'\x07',
    '\x09':'\x08',
    '\x0a':'\x09',
    '\x0b':'\x0a',
    '\x0c':'\x4d\x0b',
    '\x0d':'\x0c',
    '\x0e':'\x0d',
    '\x0f':'\x53\x0e',
    '\x10':'\x0f',
    '\x11':'\x10',
    '\x12':'\x11',
    '\x13':'\x12',
    '\x14':'\x13',
    '\x15':'\x53\x6b\x01\x14\x1b',
    '\x16':'\x15',
    '\x17':'\x16',
    '\x18':'\x17',
    '\x19':'\x18\x0e',
    '\x1a':'\x19',
    '\x1b':'\x1a',
    '\x1c':'\x1e\x1b',
    '\x1d':'\x1c',
    '\x1e':'\x1d',
    '\x1f':'\x4f\x14\x69\x01\x14\x1e',
    '\x20':'\x53\x1f',
    '\x21':'\x20\x0b',
    '\x22':'\x21',
    '\x23':'\x22',
    '\x24':'\x23',
    '\x25':'\x24',
    '\x26':'\x25',
    '\x27':'\x26\x6c',
    '\x28':'\x27\x01\x14\x2b',
    '\x29':'\x54\x28',
    '\x2a':'\x29',
    '\x2b':'\x2a',
    '\x2c':'\x4f\x14\x2b',
    '\x2d':'\x53\x2c',
    '\x2e':'\x2d',
    '\x2f':'\x2e',
    '\x40':'\x2f',
    '\x41':'\x40',
    '\x42':'\x41',
    '\x43':'\x4d\x42',
    '\x44':'\x4f\x14\x43',
    '\x45':'\x53\x44',
    '\x46':'\x45',
    '\x47':'\x46',
    '\x48':'\x47',
    '\x49':'\x48',
    '\x4a':'\x49\x01\x14\x1b',
    '\x4b':'\x4a',
    '\x4c':'\x4b',
    '\x4d':'\x4c',
    '\x4e':'\x4d\x14\x1e',
    '\x4f':'\x4e',
    '\x50':'\x4f\x14\x1b',
    '\x51':'\x53\x50',
    '\x52':'\x51',
    '\x53':'\x52',
    '\x54':'\x53\x4d',
    '\x55':'\x54\x14\x1b',
    '\x56':'\x55',
    '\x57':'\x56',
    '\x58':'\x57',
    '\x59':'\x58\x6b\x01\x14\x5a',
    '\x5a':'\x59',
    '\x5b':'\x20\x14\x5a',
    '\x5c':'\x5b',
    '\x5d':'\x5c',
    '\x5e':'\x5d',
    '\x5f':'\x5e',
    '\x60':'\x5f',
    '\x61':'\x60',
    '\x62':'\x61',
    '\x63':'\x4d\x62',
    '\x64':'\x63',
    '\x65':'\x64',
    '\x66':'\x53\x65',
    '\x67':'\x66',
    '\x68':'\x67',
    '\x69':'\x68',
    '\x6a':'\x69',
    '\x6b':'\x6a',
    '\x6c':'\x6b'
    }

#C'est la table de traduction employée pour la derniere itération ;
#une itération a lieu pendant la traduction avec cette table.
#Pourquoi j'utilise des\x** ? Parce que c'est court !
#La non-utilisation des\x3* est volontaire : en effet, ces caractères sont, de
#\x30 à \x39, des chiffres, et c'est plus simple pour suivre de ne pas mettre
#les caractères de \x3a à \x3f.
trad = {
    '\x01':'22',
    '\x02':'11132132212312211322212221121123222112',
    '\x03':'13112221133211322112211213322112',
    '\x04':'3113112221131112211322212312211322212221121123222112',
    '\x05':'111312211312113221133211322112211213322112',
    '\x06':'1321132122211322212221121123222112',
    '\x07':'3113112211322112211213322112',
    '\x08':'111312212221121123222112',
    '\x09':'132112211213322112',
    '\x0a':'31121123222112',
    '\x0b':'111213322112',
    '\x0c':'132123222112',
    '\x0d':'3113322112',
    '\x0e':'1113222112',
    '\x0f':'13211321322112',
    '\x10':'311311222112',
    '\x11':'1113122112',
    '\x12':'132112',
    '\x13':'3112',
    '\x14':'1112',
    '\x15':'132113213221232112',
    '\x16':'3113112221133112',
    '\x17':'11131221131112',
    '\x18':'13211312',
    '\x19':'311321322112',
    '\x1a':'111311222112',
    '\x1b':'13122112',
    '\x1c':'31232112',
    '\x1d':'11133112',
    '\x1e':'131112',
    '\x1f':'11132221231132212312',
    '\x20':'132113213221133122211332',
    '\x21':'31131122211311122113222123222112',
    '\x22':'11131221131211322113322112',
    '\x23':'13211321222113222112',
    '\x24':'3113112211322112',
    '\x25':'11131221222112',
    '\x26':'1321122112',
    '\x27':'31121123',
    '\x28':'11121332212311322113212221',
    '\x29':'31131122212322211331222113112211',
    '\x2a':'1113122113322113111221131221',
    '\x2b':'13211322211312113211',
    '\x2c':'111322212311322113212221',
    '\x2d':'1321132132211331222113112211',
    '\x2e':'311311222113111221131221',
    '\x2f':'111312211312113211',
    '\x40':'132113212221',
    '\x41':'3113112211',
    '\x42':'11131221',
    '\x43':'13213211',
    '\x44':'1113222123112221',
    '\x45':'13211321322113312211',
    '\x46':'311311222113111221',
    '\x47':'11131221131211',
    '\x48':'13211321',
    '\x49':'311311',
    '\x4a':'11131221232112',
    '\x4b':'1321133112',
    '\x4c':'31131112',
    '\x4d':'111312',
    '\x4e':'13212312',
    '\x4f':'311332',
    '\x50':'11132221232112',
    '\x51':'132113213221133112',
    '\x52':'3113112221131112',
    '\x53':'111312211312',
    '\x54':'1321132132',
    '\x55':'3113112221232112',
    '\x56':'11131221133112',
    '\x57':'1321131112',
    '\x58':'311312',
    '\x59':'11132132212312211322212221121123222113',
    '\x5a':'13112221133211322112211213322113',
    '\x5b':'3113112221131112211322212312211322212221121123222113',
    '\x5c':'111312211312113221133211322112211213322113',
    '\x5d':'1321132122211322212221121123222113',
    '\x5e':'3113112211322112211213322113',
    '\x5f':'111312212221121123222113',
    '\x60':'132112211213322113',
    '\x61':'31121123222113',
    '\x62':'111213322113',
    '\x63':'132123222113',
    '\x64':'3113322113',
    '\x65':'1113222113',
    '\x66':'13211321322113',
    '\x67':'311311222113',
    '\x68':'1113122113',
    '\x69':'132113',
    '\x6a':'3113',
    '\x6b':'1113',
    '\x6c':'13',
    }

def conway_strict(nbr=50):
    if nbr > 7:
        #les atomes ne sont visibles qu'à partir de 7 itérations...
        #et à la 7è itération on a la chaine :
        c = '\x58\x42'
        for i in range(nbr-7-1):
            c = ''.join((trans[j] for j in c))
#        print([hex(ord(j)) for j in c])
        return ''.join((trad[j] for j in c))
    else : #je le gèrerai plus tard, la flemme
        pass

def conway_lazy(nbr=50):
    if nbr > 7:
        #les atomes ne sont visibles qu'à partir de 7 itérations...
        #et à la 7è itération on a la chaine :
        c = ['\x58', '\x42'].__iter__()
        def reiter(seq, table):
            return (t for x in seq for t in table[x])
        for i in range(nbr-7-1):
            c = reiter(c, trans)
        return reiter(c, trad)
    else : #je le gèrerai plus tard, la flemme
        pass

    

from collections import deque

def conway_restricted(nbr=50):
    if nbr < 7: #les atomes ne sont visibles qu'à partir de 7 itérations...
        return None
    result_len = 0
    nb_lines = nbr - 7
    maxlen = max(len(s) for s in trans.values())
    # print "maxlen", maxlen
    lines = [deque(maxlen=maxlen) for i in range(nb_lines)]

    # def debug(c): return hex(ord(c))

    def extend(i, li):
        # print "extend", i, [debug(c) for c in li]
        lines[i].extend(li)
    index = 0
    extend(index, "\x58\x42")
    while True:
        while True:
            # print "ascending", index, len(lines[index]), debug(lines[index][0])
            elem = lines[index].popleft()
            index += 1
            if index == nb_lines:
                # print "traduction", trad[elem]
                result_len += len(trad[elem])
                break
            extend(index, [c for c in trans[elem]])

        while True:
            index -= 1
            # print "descending", index, len(lines[index])
            if index < 0:
                return result_len
            if len(lines[index]) > 0:
                break


def conway_restricted_stack(nbr=50):
    if nbr < 7: #les atomes ne sont visibles qu'à partir de 7 itérations...
        return None
    result_len = 0
    nb_lines = nbr - 7
    maxlen = max(len(s) for s in trans.values())
    # print "maxlen", maxlen
    lines = [deque(maxlen=maxlen) for i in range(nb_lines)]
    stack = []

    # def debug(c): return hex(ord(c))
    def extend(i, li):
        # print "extend", i, [debug(c) for c in li]
        lines[i].extend(li)
        stack.extend([index] * (len(li) - 1))
    index = 0
    extend(index, "\x58\x42")
    while True:
        while True:
            # print "ascending", index, len(lines[index]), debug(lines[index][0])
            elem = lines[index].popleft()
            index += 1
            if index == nb_lines:
                # print "traduction", trad[elem]
                result_len += len(trad[elem])
                break
            extend(index, trans[elem])

        if stack == []:
            return result_len
        index = stack.pop()

def conway_dfs(nbr=50):
    if nbr < 7: #les atomes ne sont visibles qu'à partir de 7 itérations...
        return None
    result_len = 0
    nb_lines = nbr - 7
    stack = []
    def extend(i, li):
        # reversed(li) : item in the stack are popped in reverse order
        stack.extend([(i, v) for v in reversed(li)])
    extend(0, "\x58\x42")
    while stack != []:
        result_len = max(result_len, len(stack))
        index, elem = stack.pop()
        if index + 1 == nb_lines:
            # result_len += len(trad[elem])
            pass
        else:
            extend(index + 1, trans[elem])
    return result_len

Version DFS en OCaml

J'ai codé une version en Caml du dernier algorithme.

let conway n init f =
  if n < 7 then invalid_arg "conway"
  else
    let state = ref init in
    let nb_lines = n - 7 in
    let rec dfs i elem =
      let i' = i + 1 in
      if i' = nb_lines then
        state := f !state trad_table.(elem)
      else List.iter (dfs i') trans_table.(elem) in
    dfs 0 0x58; dfs 0 0x42;
    !state

let count_conway n =
  conway n 0 (fun i str -> i + String.length str)

Les performances sont excellentes : pour n=65, la version stricte d'ordiclic met 15 secondes, la version caml compilée en bytecode en met 7, et la version native 0.8s.

En 3.3s et en mémoire quasi-constante, je confirme la taille mesurée par ordiclic pour n=70. Pour n=75 (12s) elle est de 881 752 750. Pour n=80 (53s) elle est de 3 319 186 080.

Les tables de transition en Caml (code généré automatiquement à partir des tables Python) :

let trans_assoc = [
0x4, [0x20;0x14;0x3];
0x8, [0x7];
0xc, [0x4d;0xb];
0x10, [0xf];
0x14, [0x13];
0x18, [0x17];
0x1c, [0x1e;0x1b];
0x20, [0x53;0x1f];
0x24, [0x23];
0x28, [0x27;0x1;0x14;0x2b];
0x2c, [0x4f;0x14;0x2b];
0x40, [0x2f];
0x44, [0x4f;0x14;0x43];
0x48, [0x47];
0x4c, [0x4b];
0x50, [0x4f;0x14;0x1b];
0x54, [0x53;0x4d];
0x58, [0x57];
0x5c, [0x5b];
0x60, [0x5f];
0x64, [0x63];
0x68, [0x67];
0x6c, [0x6b];
0x3, [0x2];
0x7, [0x6];
0xb, [0xa];
0xf, [0x53;0xe];
0x13, [0x12];
0x17, [0x16];
0x1b, [0x1a];
0x1f, [0x4f;0x14;0x69;0x1;0x14;0x1e];
0x23, [0x22];
0x27, [0x26;0x6c];
0x2b, [0x2a];
0x2f, [0x2e];
0x43, [0x4d;0x42];
0x47, [0x46];
0x4b, [0x4a];
0x4f, [0x4e];
0x53, [0x52];
0x57, [0x56];
0x5b, [0x20;0x14;0x5a];
0x5f, [0x5e];
0x63, [0x4d;0x62];
0x67, [0x66];
0x6b, [0x6a];
0x2, [0x58;0x6b;0x1;0x14;0x3];
0x6, [0x5];
0xa, [0x9];
0xe, [0xd];
0x12, [0x11];
0x16, [0x15];
0x1a, [0x19];
0x1e, [0x1d];
0x22, [0x21];
0x26, [0x25];
0x2a, [0x29];
0x2e, [0x2d];
0x42, [0x41];
0x46, [0x45];
0x4a, [0x49;0x1;0x14;0x1b];
0x4e, [0x4d;0x14;0x1e];
0x52, [0x51];
0x56, [0x55];
0x5a, [0x59];
0x5e, [0x5d];
0x62, [0x61];
0x66, [0x53;0x65];
0x6a, [0x69];
0x1, [0x1];
0x5, [0x4];
0x9, [0x8];
0xd, [0xc];
0x11, [0x10];
0x15, [0x53;0x6b;0x1;0x14;0x1b];
0x19, [0x18;0xe];
0x1d, [0x1c];
0x21, [0x20;0xb];
0x25, [0x24];
0x29, [0x54;0x28];
0x2d, [0x53;0x2c];
0x41, [0x40];
0x45, [0x53;0x44];
0x49, [0x48];
0x4d, [0x4c];
0x51, [0x53;0x50];
0x55, [0x54;0x14;0x1b];
0x59, [0x58;0x6b;0x1;0x14;0x5a];
0x5d, [0x5c];
0x61, [0x60];
0x65, [0x64];
0x69, [0x68];
] ;;
let trad_assoc = [
0x4, "3113112221131112211322212312211322212221121123222112";
0x8, "111312212221121123222112";
0xc, "132123222112";
0x10, "311311222112";
0x14, "1112";
0x18, "13211312";
0x1c, "31232112";
0x20, "132113213221133122211332";
0x24, "3113112211322112";
0x28, "11121332212311322113212221";
0x2c, "111322212311322113212221";
0x40, "132113212221";
0x44, "1113222123112221";
0x48, "13211321";
0x4c, "31131112";
0x50, "11132221232112";
0x54, "1321132132";
0x58, "311312";
0x5c, "111312211312113221133211322112211213322113";
0x60, "132112211213322113";
0x64, "3113322113";
0x68, "1113122113";
0x6c, "13";
0x3, "13112221133211322112211213322112";
0x7, "3113112211322112211213322112";
0xb, "111213322112";
0xf, "13211321322112";
0x13, "3112";
0x17, "11131221131112";
0x1b, "13122112";
0x1f, "11132221231132212312";
0x23, "13211321222113222112";
0x27, "31121123";
0x2b, "13211322211312113211";
0x2f, "111312211312113211";
0x43, "13213211";
0x47, "11131221131211";
0x4b, "1321133112";
0x4f, "311332";
0x53, "111312211312";
0x57, "1321131112";
0x5b, "3113112221131112211322212312211322212221121123222113";
0x5f, "111312212221121123222113";
0x63, "132123222113";
0x67, "311311222113";
0x6b, "1113";
0x2, "11132132212312211322212221121123222112";
0x6, "1321132122211322212221121123222112";
0xa, "31121123222112";
0xe, "1113222112";
0x12, "132112";
0x16, "3113112221133112";
0x1a, "111311222112";
0x1e, "131112";
0x22, "11131221131211322113322112";
0x26, "1321122112";
0x2a, "1113122113322113111221131221";
0x2e, "311311222113111221131221";
0x42, "11131221";
0x46, "311311222113111221";
0x4a, "11131221232112";
0x4e, "13212312";
0x52, "3113112221131112";
0x56, "11131221133112";
0x5a, "13112221133211322112211213322113";
0x5e, "3113112211322112211213322113";
0x62, "111213322113";
0x66, "13211321322113";
0x6a, "3113";
0x1, "22";
0x5, "111312211312113221133211322112211213322112";
0x9, "132112211213322112";
0xd, "3113322112";
0x11, "1113122112";
0x15, "132113213221232112";
0x19, "311321322112";
0x1d, "11133112";
0x21, "31131122211311122113222123222112";
0x25, "11131221222112";
0x29, "31131122212322211331222113112211";
0x2d, "1321132132211331222113112211";
0x41, "3113112211";
0x45, "13211321322113312211";
0x49, "311311";
0x4d, "111312";
0x51, "132113213221133112";
0x55, "3113112221232112";
0x59, "11132132212312211322212221121123222113";
0x5d, "1321132122211322212221121123222113";
0x61, "31121123222113";
0x65, "1113222113";
0x69, "132113";
] ;;

let table default assoc =
  let maxi = List.fold_left max 0 (List.map fst assoc) in
  let table = Array.make (maxi + 1) default in
  List.iter (fun (k, v) -> table.(k) <- v) assoc;
  table


let trans_table = table [] trans_assoc
let trad_table = table "" trad_assoc

Deuxième edit : une formulation dynamique

Quand on regarde bien le code de parcours DFS, on voit que le comportement de l'algorithme est déterminé par ses deux entrées :
- le numéro de ligne dans lequel on se trouve
- l'atome qu'on est en train d'examiner

Cette formulation se prête bien à un algorithme dynamique. Le problème c'est : quel est l'état qu'on enregistre pour chaque appel ? Avec la formulation actuelle (parcours itératif de la liste des résultats), on ne peut pas faire grand chose : on peut envisager de stocker pour chaque appel la séquence traduite correspondante, mais vu sa taille ça couterait très cher en mémoire (autant que l'algorithme de départ) en n'apportant pas grand chose.

Pour avoir un état à sauvegarder pour chaque appel, il faut passer de la version "séquentielle" actuelle (accumulation d'un état, d'une liste de résultats) à une version "monoïdale", où chaque appel renvoie un résultat indépendant des autres et où on "réunit" (merge) les résultats des appels.

Toujours en Caml :

let conway_monoid n proj merge =
  if n < 7 then invalid_arg "conway"
  else
    let nb_lines = n - 7 in
    let rec dfs i elem =
      let i' = i + 1 in
      if i' = nb_lines then
        proj trad_table.(elem)
      else
        let fold acc t = merge acc (dfs i' t) in
        let hd::tl = trans_table.(elem) in
        List.fold_left fold (dfs i' hd) tl in
    let a = dfs 0 0x58 in
    let b = dfs 0 0x42 in
    merge a b

let count_monoid n =
  conway_monoid n String.length (+)

Maintenant, on sait quoi stocker pour un dynamique : l'état monoïdal associé à l'appel.

let conway_dyna n proj merge =
  if n < 7 then invalid_arg "conway"
  else
    let nb_lines = n - 7 in
    let table =
      Array.make_matrix nb_lines (Array.length trans_table) None in
    let rec dfs i elem =
      match table.(i).(elem) with
      | Some result -> result
      | None ->
          let result =
            let i' = i + 1 in
            if i' = nb_lines then
              proj trad_table.(elem)
            else
              let fold acc t = merge acc (dfs i' t) in
              let hd::tl = trans_table.(elem) in
              List.fold_left fold (dfs i' hd) tl in
          table.(i).(elem) <- Some result;
          result in
    let a = dfs 0 0x58 in
    let b = dfs 0 0x42 in
    merge a b

let count_dyna n =
  conway_dyna n String.length (+)

Cette version est particulièrement efficace pour toutes les opérations de parcours qui se prêtent à un traitement "par réunion". Par exemple, on peut calculer les tailles des chaînes résultantes quasi-instantanément. Par exemple, la taille de la ligne numéro 1000 est :

Citation

27981351371113001020436934044969543281325518064547027161534027713608590019465423516313818830989981757685809308236276

La complexité en temps et en mémoire du code est O(N*S), où N est le numéro de la ligne demandée, et S le nombre d'états des tables d'ordiclic. En gros, on ne peut pas faire mieux.

Remarque : ce n'est pas forcément une solution miracle, au sens où si on choisit mal les opérations de réunion à faire sur les résultats, on doit faire le travail pour les produire. Par exemple si on essaie d'afficher la ligne résultat, la bonne complexité de l'algorithme de calcul sera éclipsée par les temps énormes de réunion et d'affichage de la chaîne.

ordiclic

11 août 2010 à 17:52:33

Ouch, terriblement efficace. Il me semblait qu'une approche fonctionnelle était possible avec ce code, mais là je vois qu'effectivement, ça aide beaucoup.

Quand je maitriserai un petit peu mieux cython, je posterai le code utilisé.

bluestorm

11 août 2010 à 20:08:01

Une version Python de l'algorithme dynamique. Comme j'ai dû contourner l'absence de récursion dans CPython, le code est nettement moins clair, mais les résultats sont là :

def conway_dyna(nbr, proj, merge):
    if nbr < 7: #les atomes ne sont visibles qu'à partir de 7 itérations...
        return None
    nb_lines = nbr - 7
    stack = []
    cache = dict()
    def extend(i, li):
        # reversed(li) : item in the stack are popped in reverse order
        stack.extend([(i, v, 'up') for v in reversed(li)])
    def result(i, li):
        acc = cache[i, li[0]]
        for k in li[1:]:
            acc = merge(acc, cache[i, k])
        return acc
    init = "\x58\x42"
    extend(0, init)
    while stack != []:
        index, elem, direction = stack.pop()
        if direction == 'down':
            cache[index, elem] = result(index + 1, trans[elem])
        elif direction == 'up':
            if (index, elem) in cache:
                continue
            if index + 1 == nb_lines:
                cache[index, elem] = proj(trad[elem])
            else:
                stack.append((index, elem, 'down'))
                extend(index + 1, trans[elem])
    return result(0, init)

>>> conway_dyna(17, (lambda s:s), lambda x,y : x+y)
'31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211'
>>> conway_dyna(100, len, lambda x,y : x+y)
666450031706L

Edit : une version dynamique "directe", où on remplit le cache sans passer par les requêtes. C'est nettement plus lisible, mais cette version fait un peu de calculs inutiles, puisqu'il y a des combinaisons (ligne, atomes) qui ne sont calculées mais ne seront jamais demandées en pratique (par exemple toutes les combinaisons de la ligne 1, à part les deux initiales) :

def conway_dyna_direct(nbr, proj, merge):
    if nbr < 7: #les atomes ne sont visibles qu'à partir de 7 itérations...
        return None
    nb_lines = nbr - 7
    cache = dict()
    for (e, v) in trad.items():
        cache[nb_lines, e] = proj(v)
    for i in range(nb_lines-1, 0, -1):
        for e, li in trans.items():
            val = cache[i+1, li[0]]
            for v in li[1:]:
                val = merge(val, cache[i+1, v])
            cache[i, e] = val
    return merge(cache[1, '\x58'], cache[1, '\x42'])

ordiclic

12 août 2010 à 0:45:42

Je m'incline devant le code, que j'ai du mal à comprendre à cause de l'algo utilisé.
J'essaierai de l'examiner plus tard, à tête reposée.

Edit : l'absence de récursion, wut ?

FrançoisHouessou

23 octobre 2023 à 13:02:17 - Message modéré pour le motif suivant : Merci d’utiliser le bouton code pour insérer un code sur le forum

<< 1 2 3