Partage

[exercice] La suite de Conway

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

<< 1 2 3 >>

17 juillet 2010 à 12:54:30

Citation

Et je me dis alors : C (ou C++) + Python, c'est l'arme fatale (efficacité + simplicité) !!

EDIT néanmoins le C pur reste quand même beaucoup plus rapide que Python, par exemple ici l'équivalent de l'algo naïf en C tourne 5 à 8 fois plus vite.

Bien sûr, parce que même dans le code Python utilisant des fonctions standards, il reste des choses à interpréter. Mais il y a moyen d'aller encore plus vite qu'en C, en utilisant d'autres interpréteurs.

candide

17 juillet 2010 à 12:59:56

Citation : Maxibolt

Mais il y a moyen d'aller encore plus vite qu'en C, en utilisant d'autres interpréteurs.

Oui, c'est ce que j'avais lu, tu penses à PyPy ?

Maxibolt

17 juillet 2010 à 14:10:28

Entre autres, oui. J'ai entendu parler de Cython aussi.

sfsetwsg

18 juillet 2010 à 15:02:28

Pour écarter l'éventualité d'un 333, il faut déjà avoir montré qu'on n'a jamais 4 répétitions et à ce moment
http://www.yure.net

http://www.nike-tn-air.com

http://www.onlinedbiz.com
c'est immédiat à voir (un peu délicat à écrire pour qu'un interlocuteur comprenne bien).

JeanGervasi

6 août 2010 à 23:43:02

Bonjour,

voila ma version qui est bcq plus facile que la votre (que j'ai pas compris) et elle vas assez vite 3sec pour 50 lignes (le plus rapide je crois )

#CopyRight Jean Gervasi (TecknoPlay)
# gervasi-jean@hotmail.com
from time import clock
import sys

cptgenerale=5
cptligne=0
cptnombre=0
cptg1=int(raw_input("cb de ligne"))
cptg2=0

#print "1"

ligneprec="1"+" "*3
cpt=0
start = clock()
while cptg2 != cptg1:
	cpt=0
	ligne=""
	lignepreclst=""
	while cpt !=len(ligneprec)-3:
		
		lignepreclst=lignepreclst
		if ligneprec[cpt] == ligneprec[cpt+1] and ligneprec[cpt+1] == ligneprec[cpt+2]:
			#print "3 %s"%(ligneprec[cpt]),
			lignepreclst=lignepreclst+"3%s"%(ligneprec[cpt])
			cpt+=3
			
			
		elif ligneprec[cpt] == ligneprec[cpt+1]:
			#print "2 %s"%(ligneprec[cpt]),
			lignepreclst=lignepreclst+"2%s"%(ligneprec[cpt])
			cpt+=2
			
			
		else:
			#print "1 %s"%(ligneprec[cpt]),
			lignepreclst=lignepreclst+"1%s"%(ligneprec[cpt])
			cpt+=1
		
	ligneprec=lignepreclst+" "*3	
		
	#print ""
	cptg2+=1
		
stop = clock()

print >> sys.stderr, 'Execution time :', stop-start, 's'

cb de ligne :50
Execution time : 2.8545728963 s

candide

7 août 2010 à 3:34:45

Citation : JeanGervasi

voila ma version qui est bcq plus facile

facile dans quel sens ?

Citation : JeanGervasi

la votre

tu parles à qui ?

Citation : JeanGervasi

elle vas assez vite 3sec pour 50 lignes (le plus rapide je crois )

Ben pour tester tes dires, j'attends que tu proposes un programme complet qui l'affiche la ligne n° N (donnée en entrée) et n'affiche que cela. Ce n'est pas le cas même si on décommente tes print. Maintenant, j'ai quand même un doute que ton code soit plus rapide que celui d'ordiclic.

Abraxasz

7 août 2010 à 8:52:20

import time                                                                                                                                                                          
                                                                                                                                                                                     
def conway(n):                                                                                                                                                                       
    current_line = [1]                                                                                                                                                               
    for i in xrange(n):                                                                                                                                                              
        oldchar = ''                                                                                                                                                                 
        count = 0                                                                                                                                                                    
        new_line = []                                                                                                                                                                
        for j in range(len(current_line)):                                                                                                                                           
            if current_line[j] != oldchar:                                                                                                                                           
                if oldchar != '':                                                                                                                                                    
                    new_line += [count,oldchar]                                                                                                                                      
                oldchar = current_line[j]                                                                                                                                            
                count=1                                                                                                                                                              
            else:                                                                                                                                                                    
                count+=1                                                                                                                                                             
        new_line += [count,current_line[-1]]                                                                                                                                         
        current_line = new_line                                                                                                                                                      
    return current_line                                                                                                                                                              
                                                                                                                                                                                     
conway(50)                                                                                                                                                                           
print (time.clock())

Voici une version brute, sans astuces.
Elle tourne en 2.10 sec CPU, ce qui n'est pas trop mal (bon c'est pas encore du niveau des versions d'Ordicic mais bon...).

candide

7 août 2010 à 11:35:34

Citation : Abraxasz

Elle tourne en 2.10 sec CPU, ce qui n'est pas trop mal (bon c'est pas encore du niveau des versions d'Ordicic mais bon...).

Un temps absolu comme ça ne veut rien dire mais ton temps est plus que correct.
chez moi, pour n=50 :

ordiclic : 0.240s
Abraxasz : 1.220s
maxibolt, candide : 1.5s
wikipedia itertools : 6.6s
deux codes sur le site de sloane : > 30s

rks`

7 août 2010 à 12:41:51

Si j'ai bien compris, le but de l'atelier est d'implémenter un RLE ?
Si oui, ça a déjà été fait sur le topic « Différents algorithmes de compressions ».

Abraxasz

7 août 2010 à 14:16:12

Citation : Dark-Side

Si j'ai bien compris, le but de l'atelier est d'implémenter un RLE ?

Pas vraiment non. Lis au moins le premier post.

rks`

7 août 2010 à 15:11:05

Citation : Abraxasz

Pas vraiment non. Lis au moins le premier post.

Hum ouais ok, il peut y avoir des doublons dans la liste finale ici.
Mes excuses.

Edit: Quoi qu'il en soit, c'est dommage de vous limiter à un langage pour vos ateliers, et je salue l'initiative de Yohan d'essayer de montrer d'autres langages (même si il vient nous montrer du perl :/ )
D'ailleurs, voici deux versions faites rapidement en haskell:

import Char ( intToDigit)
import List ( group )

conway (x:xs) = helper (x, 1) xs
  where helper (last, nb) [] = intToDigit nb:[last]
        helper (c,nb) (x:xs) | c == x    = helper (c, succ nb) xs
                             | otherwise = intToDigit nb:c:helper (x,1) xs

conway' = concat . map (\lst -> (intToDigit $ length lst):[head lst]) . group

La première faite à la main, la deuxième utilisant la stdlib.

Je suis d'ailleurs étonné par la longueur des versions python qui ont été montrées.
Il y'a sûrement moyen de faire plus concis (Zopieux, Maxibolt, vous attendez quoi ?)

Abraxasz

7 août 2010 à 16:21:24

Citation : Dark-Side

Hum ouais ok, il peut y avoir des doublons dans la liste finale ici.
Mes excuses.

Acceptées

Pour ce qui est de la concision, tu n'as pas tort. J'ai été moi même surpris en écrivant ma version de voir qu'aucune solution concise et élégante ne me venait à l'esprit. Le problème, c'est que les suites de Conway ne se prêtent pas vraiment à un algorithme récursif, ni à l'utilisation de List Comprehensions (qui en générale raccourcissent beaucoup le code). Ceci dit, j'admire encore une fois l'élégance d'Haskell qui, bien qu'à mon sens moins lisible que Python, permet des solutions esthétiquement plaisantes.

Jette quand même un coup d'œil aux solutions de Maxibolt et ordiclic qui sont relativement courtes.

rks`

7 août 2010 à 16:54:34

Citation : Abraxasz

Le problème, c'est que les suites de Conway ne se prêtent pas vraiment à un algorithme récursif, ni à l'utilisation de List Comprehensions (qui en générale raccourcissent beaucoup le code).

C'est là où tu te trompes. Mes deux fonctions précédentes traduisent un même algorithme purement récursif.

Et pour ce qui est de l'utilisation de compréhension de listes, tu aurais du passer sur le lien wikipedia donné au début du topic, c'est ce que je viens de faire et on y trouve une solution (en haskell) à base de compréhension de listes qui donne les n premiers termes de la suite.
Cette solution s'adapte d'ailleurs facile pour donner la ligne n+1 en fonction de la ligne n.

import Char ( intToDigit, digitToInt)
import List ( group )

conway = map intToDigit . helper . map digitToInt
  where helper l = [f x | x <- group l, f <- [length, head]]

Regarde juste la fonction helper, qui fait tout le boulot. conway permet juste de transformer la string en liste de nombres puis de retransformer en string après l'appel à helper.

Je ne fais pas de python, mais ça doit quand même s'adapter relativement facilement. Par contre, on y perdrait probablement au niveau des performances, python n'effectuant a priori pas (mais j'en sais rien au fond) les optimisations (de haut niveau) faites par ghc.

EPonix

7 août 2010 à 17:06:09

Oui il est possible de faire un code utilisant les compréhension de liste en python ainsi que le module itertool qui permet de regrouper par paquet les éléments d'une liste (donc la traduction de ton code Haskell en Python).

Et je n'avais jamais remarqué la ressemblance entre la suite de conway et la compression RLE.

Tsp

7 août 2010 à 19:57:05

J'ai codé une version en OCaml

let rec suivant c l e = match l with
    | [] -> [c; e]
    | t::q when t = e -> suivant (c + 1) q t
    | t::q -> c::e::(suivant 1 q t)
    
let conway n =
    let rec aux n l = 
        if n <= 1 then List.iter print_int l
        else aux (n - 1) (suivant 1 (List.tl l) (List.hd l)) in
    aux n [1]; print_newline ()

let _ = conway (int_of_string Sys.argv.(1))

$ ocamlopt conway.ml -o conway
$ time ./conway 50 > fichier

real        0m1.965s
user        0m1.940s
sys        0m0.016s

candide

8 août 2010 à 19:08:05

Une petite amélioration de mon temps (0.45s au lieu de 1.50s pour n=50) mais sans battre le temps d'ordiclic (0.25s).

L'idée : quand on considère les sous-chaînes ne contenant pas le chiffre 3, on voit qu'elles sont très peu nombreuses et donc qu'elles se répètent beaucoup. Donc, on calcule leur transformé (par une fonction conway implémentée basiquement) et on stocke ça dans un dictionnaire ce qui permet une réutilisation à chaque fois que la sous-chaîne réapparait.

Le code (Python 2.6) :

def conwayBase(z):
    (zz, old, c) = ([], z[0], 0)
    for i in range(len(z)):
        if z[i] != old:
            zz += [str(c)] + [old]
            (old, c) = (z[i], 1)
        else:
            c += 1
    return ''.join(zz + [str(c)] + [old])

d = {'': ''}

def conwayDico(z):
    global d
    zz = z.split('3')
    debut = 0
    while zz[debut] == '':
        debut += 1
    r = ''
    i = debut
    for ch in zz[debut:]:
        if ch != '':
            r += str(i) + '3'
            i = 1
            if ch not in d:
                d[ch] = conwayBase(ch)
            r += d[ch]
        else:
            i += 1

    if i > 1:
        r += str(i - 1) + '3'
    if debut == 0:
        r = r[2:]
    return r

def conway(n):
    z = '1'
    for _ in range(n - 1):
        z = conwayDico(z)
    return z

n = 50
z = conway(n)
print z

ordiclic

8 août 2010 à 20:30:33

Il existe un système d'atomes pour les éléments de la suite de Conway ; il y en a une soixantaine, dont je n'arrive pas à trouver la liste.
Si je les trouve, je vous ferai une jolie implémentation, pour me rattraper de mon premier code, qui nécessite plus de commentaires que de code.

candide

8 août 2010 à 23:00:26

Citation : ordiclic

Il existe un système d'atomes pour les éléments de la suite de Conway ; il y en a une soixantaine, dont je n'arrive pas à trouver la liste.

Je suppose que tu as regardé cet article (format pdf)

Look-and-Say Biochemistry:Exponential RNA and Multistranded DNA

qui donne 92 atomes (?).

Sinon, je pensais vraiment que l'idée suivante aller donner un code très rapide. Pour expliquer, soit par exemple

11131221133112132113212221

Pour calculer la séquence suivante, il suffit de séparer la chaîne suivant les groupes formés de deux ou trois chiffres contigus et identiques, ici ça donne

111 31 22 11 33 11 2132 11 321 222 1

L'intérêt c'est qu'il suffit de calculer les transformés des blocs indépendamment les uns des autres.

Pour les blocs comme 222 ou 33 (chiffres identiques), c'est immédiat. Et les autres groupes (pas de répétition de chiffres contigus) sont, comme une petite expérience le confirme, très peu nombreux et on peut les stocker dynamiquement dans un dictionnaire.

Hélas, l'implémentation est plus lente que je ne croyais (0.8s pour n=50 au lieu de 0.25s pour le temps d'ordiclic) alors que j'ai essayé d'utiliser au maximum les types, fonctions ou méthodes builtin. Bon, je donne quand même le code :

def conwayBase(z):
    (zz, old, c) = ([], z[0], 0)
    for i in range(len(z)):
        if z[i] != old:
            zz += [str(c)] + [old]
            (old, c) = (z[i], 1)
        else:
            c += 1
    return ''.join(zz + [str(c)] + [old])

# astuce d'ordiclic !
repet=[('111','tu'),('222','td'), ('333','tt'),
        ('11','du'),('22','dd'),('33','dt')]
        
repet_inv=dict((b,a) for a,b in repet)
d={}

def conwaySplit(z):
    global d
    for chiffres,lettres in repet :
        z=z.replace(chiffres,'-'+lettres+'-')
    zz=[(k if k.isdigit() else repet_inv[k]) for k in z.split('-') if k]
    for p in set(zz)-set(d):
        d[p]=conwayBase(p)
    return ''.join([d[k] for k in zz])


def conway(n):
    z = '1'
    for _ in range(n - 1):
        z = conwaySplit(z)
    return z

n = 50
z = conway(n)
print z

-------
EDIT
En partageant juste suivant 111, on obtient un temps légèrement meilleur que celui d'ordiclic, j'y croyais plus !
Voici le code (à peine modifié du précédent) :

# --- Dernier code de candide ------------

def conwayBase(z):
    (zz, old, c) = ([], z[0], 0)
    for i in range(len(z)):
        if z[i] != old:
            zz += [str(c)] + [old]
            (old, c) = (z[i], 1)
        else:
            c += 1
    return ''.join(zz + [str(c)] + [old])

d={}

def conwaySplit(z):
    global d
    z=z.replace('111','-'+'111'+'-')
    zz=[(k if k.isdigit() else repet_inv[k]) for k in z.split('-') if k]
    for p in set(zz)-set(d):
        d[p]=conwayBase(p)
    return ''.join([d[k] for k in zz])

def conway(n):
    z = '1'
    for _ in range(n - 1):
        z = conwaySplit(z)
    return z


# --- Code d'ordiclic ------------

def ordiclic(nbr=50): #Variante 1 de conway2
    n = "A"
    l=[('AAA','31'),('BBB','32'),('AA','21'),('BB','22'),('CC','23'),('A','11'),('B','12'),('C','13')]
    l2=[('111','CA'),('222','CB'),('11','BA'),('22','BB'),('33','BC'),('1','AA'),('2','AB'),('3','AC')]
    for i in xrange(nbr):
        for old,new in (l if not i%2 else l2):
            n=n.replace(old,new)
    if nbr%2==0:
        n=n.replace('A','1')
        n=n.replace('B','2')
        n=n.replace('C','3')
    return n

# ------------------ Test -----------------
from time import *
n = 65

start = clock()
z = conway(n)
print "%.2fs" % (clock()-start)


start = clock()
zz = ordiclic(n-1)
print "%.2fs" % (clock()-start)

print z==zz

10.18s
13.43s
True

Par contre, mon programme consomme beaucoup de mémoire (177 Mo) et nettement moins celui d'ordiclic (61 Mo) pour n=65.

EMC1

8 août 2010 à 23:50:36

Un détail candide: ton code calcule la ligne donnée exacte tandis que celui d'ordiclic calcul la ligne d'après.
Chez moi le code d'ordiclic est plus rapide à traiter conway(59) que le tiens à traiter conway(60) (calcul de la même ligne, là).

candide

9 août 2010 à 0:08:15

Citation : EMC1

Un détail candide: ton code calcule la ligne donnée exacte tandis que celui d'ordiclic calcul la ligne d'après.
Chez moi le code d'ordiclic est plus rapide à traiter conway(59) que le tiens à traiter conway(60) (calcul de la même ligne, là).

Oui, j'ai bien sûr tenu compte du décalage. D'abord, je confirme que ma dernière version est plus rapide (légèrement) que celle d'ordiclic.

[EDIT : le point suivant a été réglé, voir réponse plus loin dans le fil]
Mais plus embêtant et très curieux, j'ai l'impression que le code d'ordiclic donne un résultat faux à partir de n=55 (les notations sont celles de l'énoncé que j'ai donné, autrement dit n=1 est la première suite, ie la chaîne '1'). J'ai fait une comparaison avec

*) mon premier code,
*) le code de maxibolt,
*) celui d'Abraxasz

à chaque fois le résultat d'ordiclic diffère de celui des autres à n=55 (mais à n=54 on trouve tous pareil). Voici le code

# --- Premier code de candide ------------
def lookAndSay(n):
    def conway(z):
        zz, old, c =[], z[0], 0 # c = compteur
        for i in range(len(z)):
            if z[i]!=old:
                zz+=[c]+[old]
                old, c = z[i], 1
            else :
                c+=1
        return zz+[c]+[old]
    z=[1]
    for _ in range(n-1):
        z=conway(z)
    return ''.join(str(i) for i in z)

# --- Dernier code de candide ------------

def conwayBase(z):
    (zz, old, c) = ([], z[0], 0)
    for i in range(len(z)):
        if z[i] != old:
            zz += [str(c)] + [old]
            (old, c) = (z[i], 1)
        else:
            c += 1
    return ''.join(zz + [str(c)] + [old])

d={}

def conwaySplit(z):
    global d
    z=z.replace('111','-'+'111'+'-')
    zz=[(k if k.isdigit() else repet_inv[k]) for k in z.split('-') if k]
    for p in set(zz)-set(d):
        d[p]=conwayBase(p)
    return ''.join([d[k] for k in zz])

def conway(n):
    z = '1'
    for _ in range(n - 1):
        z = conwaySplit(z)
    return z


# --- Code d'ordiclic  ------------

def ordiclic(nbr): #Variante 1 de conway2
    n = "A"
    l=[('AAA','31'),('BBB','32'),('AA','21'),('BB','22'),('CC','23'),('A','11'),('B','12'),('C','13')]
    l2=[('111','CA'),('222','CB'),('11','BA'),('22','BB'),('33','BC'),('1','AA'),('2','AB'),('3','AC')]
    for i in xrange(nbr):
        for old,new in (l if not i%2 else l2):
            n=n.replace(old,new)
    return n

# --- Code d'Abraxasz ------------
def abraxasz(n):
    current_line = [1]
    for i in xrange(n):
        oldchar = ''
        count = 0
        new_line = []
        for j in range(len(current_line)):
            if current_line[j] != oldchar:
                if oldchar != '':
                    new_line += [count,oldchar]
                oldchar = current_line[j]
                count=1
            else:
                count+=1
        new_line += [count,current_line[-1]]
        current_line = new_line
    return ''.join(str(z) for z in current_line)

# --- Code de Maxibolt ------------

def ligne_suivante(ligne):
    suivante = []
    chiffre_actuel = ligne[0]
    compteur = 0
    for chiffre in ligne:
        if chiffre == chiffre_actuel:
            compteur += 1
        else:
            suivante.append(str(compteur))
            suivante.append(chiffre_actuel)
            chiffre_actuel = chiffre
            compteur = 1
    suivante.append(str(compteur))
    suivante.append(chiffre_actuel)
    return "".join(suivante)


def maxibolt(n):
    "Iterateur sur les n premiers termes de la suite"
    ligne = "1"
    for i in xrange(n):
        yield ligne
        ligne = ligne_suivante(ligne)

def maxib(n):
    for i,z in enumerate(maxibolt(n)):
        if i==n-1:
            return z

# --- Comparaison des 5 codes ------------

n = 55
candide1 = conway(n)
candide2=lookAndSay(n)
ordi = ordiclic(n-1)
abra=abraxasz(n-1)
maxi=maxib(n)

print candide1==candide2


print candide1==abra
print candide2==abra

print candide1==maxi
print candide2==maxi
print abra==maxi

print maxi==ordi
print abra==ordi
print candide1==ordi
print candide2==ordi

True
True                                                                                      
True
True
True
True
False
False
False
False

Si quelqu'un pouvait tester

ordiclic

9 août 2010 à 0:26:43

Rapide ton code, candide ! Et merci pour le PDF, je ne me rappelais plus du nombre exact d'atomes. Je vais tenter d'implémenter cette méthode, ça donnera ce que ça donnera.

Pour le fait que mon code retourne quelque chose de faux, ça me parait bizarre, surtout si tu as retransformé les lettres en chiffres, parce que quand n = 55, alors n%2=1... Certain qu'on atterrit sur des lettres à la fin ; ceci dit, le netbook prend cher avec ces calculs, donc je testerai plus tard.

candide

9 août 2010 à 0:53:39

Citation : ordiclic

Rapide ton code, candide !

J'ai fait beaucoup de contorsions pour un temps équivalent au tien donc la bonne méthode c'est vraiment la tienne.

Citation : ordiclic

Je vais tenter d'implémenter cette méthode, ça donnera ce que ça donnera.

Bon là c'est plus de la rando, c'est de l'escalade

Citation : ordiclic

Pour le fait que mon code retourne quelque chose de faux, ça me parait bizarre, surtout si tu as retransformé les lettres en chiffres, parce que quand n = 55, alors n%2=1.

Oui, une fois sur deux ton code donne le résultat avec des chiffres, l'autre fois avec des lettres (le prix des astuces !)
Une fois ce point rectifié, aucun problème.

Je donne une version fixée de ton code au cas où ça serait utile à certains :

def conway(nbr=50): #Variante 1 de conway2
    n = "A"
    l=[('AAA','31'),('BBB','32'),('AA','21'),('BB','22'),('CC','23'),('A','11'),('B','12'),('C','13')]
    l2=[('111','CA'),('222','CB'),('11','BA'),('22','BB'),('33','BC'),('1','AA'),('2','AB'),('3','AC')]
    for i in xrange(nbr):
        for old,new in (l if not i%2 else l2):
            n=n.replace(old,new)
    if nbr%2==0:
        n=n.replace('A','1')
        n=n.replace('B','2')
        n=n.replace('C','3')
    return n


n=60
suite = conway(n-1)

ordiclic

9 août 2010 à 1:18:11

J'ai pu trouver un autre document sur Internet à cette adresse : http://www.btinternet.com/~se16/mhi/Part1.htm et je pense qu'il ne sera pas trop difficile d'implémenter l'algorithme. Il sera sûrement fait à coups de str.replace, mais j'utiliserai le nom des éléments, ce qui sera beaucoup moins lourd à manipuler, même par centaines, que les dizaines de milliers de chiffres de la suite elle-même ; de plus, certains de ces éléments, bout à bout, s'écrivent comme un seul élément. Avec une bonne table pour gérer tout ça, je pense qu'il y a de quoi s'amuser encore un bout de temps.

candide

9 août 2010 à 2:37:17

Citation : EMC1

Chez moi le code d'ordiclic est plus rapide à traiter conway(59) que le tiens à traiter conway(60) (calcul de la même ligne, là).

Ça peut dépendre de l'implémentation. Mais si tu prends le pattern '222' [au lieu de toutes les possibilités de chiffres identiques], mon code devient 2 fois plus rapide que celui d'ordiclic. Bien sûr ce genre de choix de pattern est un peu aléatoire car tu ne sais pas à l'avance si tu fais des recopies assez rentables ou au contraire si ton dictionnaire va exploser. D'ailleurs, c'est ce qui se passe avec le pattern '333' qui n'aboutit pas. Pour '222', le dictionnaire a une taille très raisonnable (167). Le code est ici :

# --- Dernier code de candide ------------

def conwayBase(z):
    (zz, old, c) = ([], z[0], 0)
    for i in range(len(z)):
        if z[i] != old:
            zz += [str(c)] + [old]
            (old, c) = (z[i], 1)
        else:
            c += 1
    return ''.join(zz + [str(c)] + [old])

d={}

def conwaySplit(z):
    global d
    m='222'
    z=z.replace(m,'-'+m+'-')
    zz=[k for k in z.split('-') if k]
    for p in set(zz)-set(d):
        d[p]=conwayBase(p)
    return ''.join([d[k] for k in zz])



def conway(n):
    z = '1'
    for _ in range(n - 1):
        z = conwaySplit(z)
    return z


# --- Code d'ordiclic ------------

def ordiclic(nbr=50): #Variante 1 de conway2
    n = "A"
    l=[('AAA','31'),('BBB','32'),('AA','21'),('BB','22'),('CC','23'),('A','11'),('B','12'),('C','13')]
    l2=[('111','CA'),('222','CB'),('11','BA'),('22','BB'),('33','BC'),('1','AA'),('2','AB'),('3','AC')]
    for i in xrange(nbr):
        for old,new in (l if not i%2 else l2):
            n=n.replace(old,new)
    if nbr%2==0:
        n=n.replace('A','1')
        n=n.replace('B','2')
        n=n.replace('C','3')
    return n

# ------------------ Test -----------------
from time import *
n = 65

start = clock()
z = conway(n)
print "%.2fs" % (clock()-start)


start = clock()
zz = ordiclic(n-1)
print "%.2fs" % (clock()-start)

print z==zz
print len(d)

6.02s
13.45s
True
167

Citation : ordiclic

J'ai pu trouver un autre document sur Internet à cette adresse : http://www.btinternet.com/~se16/mhi/Part1.htm et je pense qu'il ne sera pas trop difficile d'implémenter l'algorithme.

Ben bon courage quand même

De toute façon, autour de n=75, ta chaîne fera 1Go de mémoire donc enbrute on peut aller très loin. Par contre, est-ce que ton code va pouvoir nous dire quelle est le 2010ème chiffre avant la fin de la chaîne n°2010 (genre Simon Plouffe pour pi)

ordiclic

9 août 2010 à 9:41:53

Hum, il ne sera quand même pas aussi puissant, je serai déjà content si j'arrive à n=70 sans faire exploser le netbook. Le tout sera de trouver des tables optimisées.
Bon, je me mets au boulot !

Pour ton code, effectivement il se retrouve à être de 30 à 50% plus rapide que le mien.

Yohan88

9 août 2010 à 13:22:35

Vous voulez un défi ? Essayer de faire cet algorithme en assembleur

ordiclic

9 août 2010 à 13:37:23

Je posterai bientôt les tables que je vais utiliser pour passer d'un atome aux autres d'une itération à l'autre, pour que vous puissiez les réutiliser au besoin, que vous n'ayiez pas à les refaire. Avec 92 atomes et deux tables à faire, c'est long !

Edit : Bon, j'ai presque réussi à faire quelque chose de correct, juste des erreurs dans les tables que j'ai faites. Les premiers tests montrent que c'est beaucoup plus rapide (~2 fois), qu'avec le remplacement de strings brut.

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

#!/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(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 conway2(nbr=50): #Variante 1 de conway2
    n = "A"
    l=[('AAA','31'),('BBB','32'),('AA','21'),('BB','22'),\
         ('CC','23'),('A','11'),('B','12'),('C','13')]
    l2=[('111','CA'),('222','CB'),('11','BA'),('22','BB'),\
        ('33','BC'),('1','AA'),('2','AB'),('3','AC')]
    for i in range(nbr):
        for old,new in (l if not i%2 else l2):
            n=n.replace(old,new)
    if nbr%2==0:
        n=n.replace('A','1')
        n=n.replace('B','2')
        n=n.replace('C','3')
    return n


import time
t=time.clock()
a=conway(65)
print(time.clock()-t)
t=time.clock()
b=conway2(65)
print(time.clock()-t)
print(a==b)

C'est terriblement efficace, voilà ce que j'obtiens sur mon netbook avec 65 itérations à calculer :

Citation

29.6736973554
62.8442251739
True
>>>

Je sais qu'il est possible de faire encore des optimisations qui accélèreraient considérablement le programme, mais il va falloir que je fasse un bruteforce pour déterminer quels atomes, accolés, correspondent à quel autre atome, et ainsi regrouper directement des atomes, ce qui allègera la chaine à traiter et fera gagner peut-être 10% de temps.

bluestorm

9 août 2010 à 22:46:08

Citation : candide

Citation : Yohan88
Rien ne vaut le Perl
for ( $_=1;; ) { say; s/((.)\2*)/length($1).$2/xeg; }
Citation : zen de Python
Readability counts

Très honnêtement, le coeur de cet algorithme est plus lisible que la plupart de vos codes python, et je pense même que c'est le plus lisible du topic.

s/((.)\2*)/length($1).$2/xeg;

Pour tout groupe de caractères identiques ((.)\2* : un caractère, puis la même chose répété autant de fois), le remplacer par ce même groupe avec sa taille devant.

Il faut avoir déjà lu des regexp avec parenthèses capturantes pour le comprendre, mais à part ça il est plutôt clair et concis. Il se rapproche beaucoup du code de drk-sd :

conway' = concat . map (\lst -> (intToDigit $ length lst):[head lst]) . group

Elle est cependant préférable car :
- le groupage des caractères est défini déclarativement par la regexp, plutôt que par un appel à une fonction d'une bibliothèque (dont il faut vérifier la documentation, etc.)
- la concaténation de la taille au groupe est exprimée plus lisiblement

PS : 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.
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. 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.

EMC1

9 août 2010 à 23:00:38

Le but a la base n'était pas de générer le plus rapidement possible le n-ième élément de la suite de Conway, ni de concevoir un algorithme performant pour résolution du problème, ni de rayer Perl, ni même de lancer un quelconque débat.

En fait, à la base, il était juste question de proposer un entraînement aux débutants.
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é.

ordiclic

9 août 2010 à 23:21:17

On s'amuse comme on peut, hein.
C'est justement parce que je trouvais un peu lourd d'utiliser l'implémentation moche avec le remplacement bête de chaines que j'ai tenté d'implémenter une méthode qui utilise directement les propriétés de la suite, à savoir les atomes. Et c'est plus rapide que de parcourir bêtement la chaîne, et ceci pour deux raisons : la première est que maintenant je ne parcours la chaine qu'une fois par itération, car il me suffit de remplacer caractère par caractère par les éléments de la table à chaque itération ; la deuxième raison est que je travaille sur des chaines beaucoup plus courtes (env. 20 fois) que si j'utilisais directement les termes de la suite.

Je pense néanmoins que je peux encore pas mal améliorer mon implémentation.

<< 1 2 3 >>