SUITE DE CONWAY (LOOK AND SAY SEQUENCE) - GENERATEUR
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/39077-suite-de-conway-look-and-say-sequence-generateur
https://codes-sources.commentcamarche.net/source/39077-suite-de-conway-look-and-say-sequence-generateur
19 août 2006 à 19:50
Mais après faut convertir en string et là, je ne suis pas sûr que ce sera efficace (sauf si tu ne veux que la nième ligne).
Mais figure toi que j'y avais déjà pensé quand je disais "J'ai une autre méthode en vue [...]"
Tu codes, tu testes, et si ça marche, on dira que c'est grâce à moi, OK ???? ;-)
19 août 2006 à 19:25
le type string est trés lents.
si on code en hexa dans un byte array en exluant les 0 on pourrait non seulement raccourcirs la taille en octets et surrement gagner en vitesse.
en hexa ce la ferais donc :
01
11
21
12 11
11 12 21
31 22 11
13 11 22 21
11 13 21 32 11
31 13 12 11 13 12 21
13 21 13 11 12 31 13 11 22 11
11 13 12 21 13 31 12 13 21 13 21 22 21
31 13 11 22 21 23 21 12 11 13 12 21 13 12 11 32 11
en gros on as toujours une paire de chiffre et une longeur paire.
la ligne
1113213211
aurait pour valeur en char* :
31313133323133323131
soit deux fois plus longue (en memoire)
donc avec un array of byte ça devrait pouvoir passer.
ça te tente flo?
17 août 2006 à 23:21
Sinon:
Tmp := Format('%s%s', [Tmp, Line[j]]);
est peu performant.
On préfèrera la version "normale", à savoir : Tmp := Tmp + Line[j];
Ton code à l'avantage de pouvoir changer la ligne de départ, c'est déjà ça ^^ (n'essaye pas avec "22" lol).
Bon, vais me coucher moi ...
17 août 2006 à 22:51
Mon code est largué, mais alors très très loin derrière.
Je laisse à ceux qui ont des configs musclées le soin d'analyser finement.
Chez moi, à partir de 40 lignes, mon proc' est à deux doigts de l'infarctus...
17 août 2006 à 22:20
Ici : http://www.filefactory.com/file/00eef4/
17 août 2006 à 14:55
Avec un TListBox, c'est bien plus rapide, je comprend tes chiffres maintenant f0xi.
Sinon, j'ai (encore !) amélioré ma procédure, la voici :
---------------------------------------------------------------------
procedure FlorenthGenereEnigme(const S: TStrings; const Nbre: Word);
const
NUMBERS = '123';
var
D, N, DR, FR, Ne: PChar;
I, Size: Integer;
begin
S.Clear;
S.Add('1');
S.Add('11');
if Nbre < 40 then
Size := Ceil(Power(1.315, Nbre + 1))
else
Size := Ceil(Power(1.31, Nbre + 1));
GetMem(D, Size);
GetMem(N, Size);
D^ := '1';
PChar(D + 1)^ := '1';
PChar(D + 2)^ := #0;
for I := 3 to Nbre do
begin
DR := D;
FR := D;
Ne := N;
repeat
repeat
Inc(FR);
until (FR^ <> DR^);
Ne^ := NUMBERS[FR - DR];
Inc(Ne);
Ne^ := DR^;
Inc(Ne);
DR := FR;
until FR^ = #0;
Ne^:= #0;
S.Add(N);
D := D xor N;
N := N xor D;
D := D xor N;
end;
FreeMem(D, Size);
FreeMem(N, Size);
end;
---------------------------------------------------------------------
Changements par rapport à la dernière version :
- Encore plus rapide !
- Ajout d'une constante NUMBERS qui permet d'éviter une variable Char.
- Suivant le nombre de lignes à générer Size n'est pas le même. En fait, c'est une solution un peu (beaucoup ?) bricolée pour ajuster la taille des buffers au plus près du nombre de caractères de la dernière ligne. J'ai essayé les formules données sur Internet, elles renvoient des résultats inférieurs.
- Grâce au gain de mémoire (avant j'allouais 2*2^45 octets pour la 45ème ligne, maintenent 2*1.31^46 - gain très notable) je suis capable de calculer la soixantième ligne sans problèmes.
Voici un tableau très détaillé :
Nbr lignes | Taille texte (Ko) | Longueur dernière ligne | Temps (ms)
----------------------------------------------------------------------
5 | 0.02 | 6 | 0.13
10 | 0.09 | 20 | 0.23
15 | 0.34 | 78 | 0.33
20 | 1.27 | 302 | 0.46
25 | 4.89 | 1'182 | 0.76
30 | 18.6 | 4'462 | 1.40
35 | 70.32 | 16'774 | 4.31
40 | 264.7 | 63'138 | 13.69
45 | 996.9 | 237'746 | 42.85
50 | 3572 | 894'810 | 141
55 | 14127 | 3'369'156 | 561
60 | 53178 | 12'680'852 | 2381
C'est le maximum que ma mémoire vive peut supporter. Au delà, Windows utilise le swap (le fichier d'échange) à la place de la RAM. Alors évidemment, ça se ressent au niveau performances, un disque dur n'étant pas aussi rapide qu'une barrette DDR SDRAM !
J'ai quand même pu arriver à la 65ème ligne, mais ... lentement !
65 | 200178 | 47'736'936 | 3 min 30 sec !!!!! lol
Bon, forman, je n'ai pas pu tester non plus ta méthode à plus de 60 lignes mais en tout cas, la tienne, sur mon PC pour 60 lignes, met 3847ms c'est à dire une fois et demi plus long que la mienne. Si tu arrive à faire foncitonner la miene sur to nPC, tu pourrais me donner les résultats ?
Bon, je redémarre aussi mon PC, j'écris un caractère toutes les deux secondes tellment ça rame !
17 août 2006 à 12:16
- Processeur : Intel P4 2.8 GHz non HT
- Carte mère : ASUS P4P800 Deluxe
- Chipset : Intel Springdale i865PE
- Mémoire : 512 Mo DDR SDRAM
- OS : Windows XP Perso SP2
- Delphi 6 Perso
Je ne remarque pas trop de différence hors session Delphi (un petit plus mais pas grand chose)
Sinon, l'ordre de rapidité reste le même.
Point positif pour toi: pour 25 lignes, tu es plus rapide que Japee.
Bon je vais essayer de permettre à ma fonction de calculer plus que 30 lignes... A +
17 août 2006 à 04:52
version de Delphi ?
AMD ? Intel HyperThreadé ?
type de memoire ?
j'ai remarqué aussi une augmentation des temps quand on execute le prog hors session delphi ...
pour la verification des limites c'est etrange aussi car active sur ma session delphi ... etrange etrange ...
16 août 2006 à 20:46
And my dream comes true...
Y'en a qui vont penser que je suis pistonné, lol ;-)
Faudra aussi que je rajoute un BeginUpdate et EndUpdate à mon pauvre code poussif, ça améliore gravement la vitesse.
Même si ça n'était pas mon but initial, mais bon, il commence à avoir l'air minable, le pauvre...
16 août 2006 à 20:10
Que tes désirs soient réalisés. ;)
16 août 2006 à 19:07
- FlorenthGenereEnigme (moi) : 3.5 ms
- FastGenereEnigme (Forman) : 4.9 ms
- GenereEngime (Japee) : 5.7 ms
- MakeWakyStrings (f0xi) : 6.6 ms
J'ai fait des boucles de 100 (cent) tests, les valeurs ci-dessus sont les moyennes.
Tu noteras les différences de performances. C'est étrange.
En plus, pour s'executer comme il faut, ta procédure nécéssite que l'on désactive la vérification des limites (Projet > Options > Compilateur).
Bref, tout ça me parait bizarre. Je compte sur toi pour m'éclaircir.
16 août 2006 à 18:09
function GetNextWaky(const SFrom : string) : string;
var
PResult : PChar;
c, e : Char;
i : Cardinal;
begin
SetLength(Result,65536 shl 9);
PResult := PChar(Result);
i := 1;
c := SFrom[i];
repeat
e:='0';
repeat
Inc(i);
Inc(e);
until c <> SFrom[i];
PResult[0] := e;
PResult[1] := c;
inc(PResult,2);
c := SFrom[i];
until c = #0;
SetLength(Result,Integer(PResult)-Integer(PChar(Result)));
end;
var
n : Integer;
begin
if ACount > 60 then exit;
with AStrings do begin
Clear;
BeginUpdate;
//HPC := ExtSystem.GetHPClock;
Add('1');
for n := 0 to ACount-2 do begin
add(GetNextWaky(Strings[n]));
end;
//HPC := ExtSystem.GetHPClock - HPC;
EndUpdate;
//waket := 0;
//for n := 0 to Count-1 do
// if Length(Strings[n]) > Waket then Waket := Length(Strings[n]);
end;
end;
16 août 2006 à 18:03
TRichEdit : limité a 4095 octet par ligne
TListBox : illimités
avec la tlistbox, reglage de mon bug de compteur (variable i) qui etait en byte (donc rotation a 255 --> 0...255 --> 0) changé en cardinal.
je tiens a préciser que les temps donnés sont les temps mis pour calculer de la premiere (1) a la Neme solution et non en partant de celle d'avant (N-1).
>> buffer 1Mo
10 Wakygneuts / Temps : 0,11 ms / Taille : 0,09 Ko / Le plus long 20 caracteres
15 Wakygneuts / Temps : 0,15 ms / Taille : 0,34 Ko / Le plus long 78 caracteres
20 Wakygneuts / Temps : 0,23 ms / Taille : 1,27 Ko / Le plus long 302 caracteres
25 Wakygneuts / Temps : 0,36 ms / Taille : 4,89 Ko / Le plus long 1 182 caracteres
30 Wakygneuts / Temps : 0,96 ms / Taille : 18,60 Ko / Le plus long 4 462 caracteres
35 Wakygneuts / Temps : 3,69 ms / Taille : 70,32 Ko / Le plus long 16 774 caracteres
40 Wakygneuts / Temps : 16,26 ms / Taille : 264,79 Ko / Le plus long 63 138 caracteres
45 Wakygneuts / Temps : 56,70 ms / Taille : 996,99 Ko / Le plus long 237 746 caracteres
50 Wakygneuts / Temps : 217,97 ms / Taille : 3.75 Mo / Le plus long 894 810 caracteres
55 out of buffer...
>> up du buffer a 4Mo pour calculer le 55eme
55 Wakygneuts / Temps : 838,85 ms / Taille : 14.13 Mo / Le plus long 3 369 156 caracteres
>> up du buffer a 16Mo pour calculer le 60eme
60 Wakygneuts / Temps : 3.179 sec / Taille : 53.18 Mo / Le plus long 12 680 852 caracteres
- taille du processus en memoire : 109Mo!
juste pour le fun aprés j'arrete d'augmenter le buffer
>> up du buffer a 32Mo pour calculer le 70eme
mon dieu ça rame ... ça attaque carrement le swap disque ...
han ... erreur ... 32Mo ça suffit pas ...
buff a 64Mo ... out of resources ...
donc j'inscrit mon record du calcul de la 1ere a la 60eme solution avec TListBox et Buffer de 16Mo :
Temps : 3.179 sec / Taille (items.text) : 53.18 Mo / 12 680 852 caracteres
je dois redemarrer mon pc ... ça rame ...
16 août 2006 à 17:47
Mais comme tu peux le voir, la limite se trouve niveau nombre de lignes.
Le code peu compréhensible ? Oui mais j'ai enlevé les commentaires ! En fait, comme je commente chaque ligne (pour me souvenir), sans coloration syntaxique, c'est chaud à relire.
Sinon, la méthode de f0xi m'a l'air étrange, et en tout cas, elle ne fonctionne pas chez moi : j'ai une violation d'accès.
J'ai une autre méthode en vue mais elle m'a l'air encore moins lisible. En plus, comme il y aura aussi deux buffers, la limite sera la même.
16 août 2006 à 16:48
16 août 2006 à 15:46
------------------------------------------------------------------------
procedure FlorenthGenereEnigme(const S: TStrings; const Nbre: Word);
var
D, N, DR, FR, Ne: PChar;
O: Char;
I, Size: Integer;
begin
S.Clear;
S.Add('1');
S.Add('11');
Size := Trunc(Power(1.5, Nbre)) + 1;
GetMem(D, Size);
GetMem(N, Size);
D^ := '1';
PChar(D + 1)^ := '1';
PChar(D + 2)^ := #0;
for I := 3 to Nbre do
begin
DR := D;
FR := D;
Ne := N;
repeat
O := '0';
repeat
Inc(FR);
Inc(O);
until (FR^ <> DR^);
Ne^ := O;
Inc(Ne);
Ne^ := DR^;
Inc(Ne);
DR := FR;
until FR^ = #0;
Ne^:= #0;
S.Add(N);
D := D xor N;
N := N xor D;
D := D xor N;
end;
FreeMem(D, Size);
FreeMem(N, Size);
end;
------------------------------------------------------------------------
Bon, tout de suite, les avantages et inconvénients :
- Avantage: une seule allocation de mémoire pour toute la recherche. Utilisation de deux buffers que l'on inverse (technique xor, plus rapide de 0.05 ms ^^) à chaque ligne.
- Avantage: plus rapide que la méthode de Forman (pour 25 lignes je met 10.68 ms en moyenne, Forman en met 12.84 ms - procéssus actifs : Delphi, Firefox)
- Inconvénient: L'allocation massive de mémoire empèche la génération de plus de 30 lignes chez moi sinon "out of memory" (car 2 * 1.5^30 octets, c'est beaucoup)
- Inconvénient: le code est un peu plus long mais bon ...
Voila, je suis sûr qu'il reste des chose à revoir mais c'est déjà pas mal je trouve.
(@ f0xi: j'ai utilisé QueryPerformanceCounter()pour la mesure des temps)
A +
Florent
16 août 2006 à 12:23
http://www.math.temple.edu/~zeilberg/mamarim/mamarimPDF/horton.pdf
C'est une pure preuve informatique ;-)
16 août 2006 à 10:32
16 août 2006 à 09:05
Merci PINGU pour le lien :-)
16 août 2006 à 03:47
De nombreuse informations sont présente ici:
http://fr.wikipedia.org/wiki/Suite_de_Conway
15 août 2006 à 22:38
f(22)=22
f(111333)=3133
C'est pour ça que je disais que lorsqu'on restreint l'étude de cette fonction sur les termes de la suite, rien ne nous dit que la longueur de la suite est croissante (même si l'étude des 100 premiers termes semble le confirmer), ni même que la suite n'est pas périodique...
15 août 2006 à 17:00
Avec un TRichEdit, plus de problèmes.
15 août 2006 à 01:20
Il apparaît que la ligne 25 est tronquée, sans doute un problème de longueur, mon programme de test vérifiera ça quand il sera achevé :
ligne 25 : 13211321
"fausse" ligne 26 : 13112221
ligne 27 (en fait la ligne 26) : 111312211312
Pfff... en fait, je suis complètement paumé, je crois que je vais voir ça demain... ça a l'air moins simple que je ne le pensais au premier abord.
A +
15 août 2006 à 00:28
Mais je ne crois pas qu'il y ait de bug, enfin je vais vérifier, mais j'étais sur un autre coup, là, je balance un code qui traite de différence de dates, et je reviens.
14 août 2006 à 23:26
@ Japee: ton Raid action longue durée chez moi n'a pas l'air très puissant.
En fait, je suis toujours penché sur le défi de Forman et je remarque que ta fonction (comme celle de forman) donne au moins une ligne de plus que demandé.
Mais ce qui est le plus étrange, c'est que si tu demande au moins 25 lignes, la 26ème est buggée.
Voici le début des trois dernières lignes (j'ai mis 25 dans le spinedit)
1311222 ...
1113122 ...
1311222 ... (non je n'ai pas fait d'erreurs de recopiage, j'ai vérifié trois fois)
La dernière ne devrait-elle pas commencer par 31131122 ?
Le même phénomène se produit avec le code de Forman et le mien d'ailleurs :-(
Et en plus, la longueur de la ligne 26 est plus courte que les précédents (alors que normalement non je crois)
Bref, de quoi se tordre les neurones pour la nuit.
"Enfin, je râle, mais je suis bonne pâte, dans le fond. Oh, ils le savent bien va !"
=> Mais oui, tout le monde le sait.
14 août 2006 à 21:28
Mais bon, tu comprends, déjà ils rentrent sur la page, ils s'essuient même pas les pieds. Premièrement.
Et puis on fait la fête, tout ça, on rigole bien, mais je sais déjà qui va se taper le ménage, hein ?
Enfin, je râle, mais je suis bonne pâte, dans le fond. Oh, ils le savent bien va !
Et y'en a qui en profitent. Qui abusent, quoi...
14 août 2006 à 21:08
Eh oui ! Et il semble que l'algo de Foreman tienne la route plus que certains ne le souhaiteraient.
La vapeur est retombée ! (Mais Delphiprog doit être en train de bouillir quelque part)
Laisse donc la lumière allumée !
Ken@vo
14 août 2006 à 20:15
Ouais, bien vu : 111333 ne peut être valide ou je n'ai rien compris non plus...
Bon, on dirait que l'ambiance est un peu retombée depuis hier. Ils sont tous partis en laissant la lumière allumée. ;-)
14 août 2006 à 19:33
Bravo ! Vous profitez que j'ai le dos tourné pour jouer!
Amusant! Je ne sais pas combien de temps j'aurai cherché si Caribensila n'avait pas "donné" la solution !
@Foreman : 111333 que tu donnes en exemple n'est pas valide ! (tout du moins si j'ai bien compris)
@fOxi : 350 chiffres max, c'est par expérience ou par par calcul ?
Ken@vo
13 août 2006 à 19:51
non seulement ça ne compte que jusque 3,
mais en plus la taille des reponses ne peu pas depasser 350 chiffres.
ce qui permet d'ajuster mon buffer a 351 au lieu de 2048 ...
5000 Wakygneuts / Temps : 254,7406 ms / Taille : 1648,29 Ko
quelques diziemes de millisecondes en moins ...
procedure MakeWakyStrings(const AStrings : TStrings; const ACount : integer = 70);
function GetNextWaky(const SFrom : string) : string;
var
PResult : PChar;
c, e : Char;
i : byte;
begin
SetLength(Result,351);
PResult := PChar(Result);
i := 1;
c := SFrom[i];
repeat
e:='0';
repeat
Inc(i);
Inc(e);
until c <> SFrom[i];
PResult[0] := e;
PResult[1] := c;
inc(PResult,2);
c := SFrom[i];
until c = #0;
SetLength(Result,Integer(PResult)-Integer(PChar(Result)));
end;
var
i : Integer;
begin
with AStrings do begin
Clear;
BeginUpdate;
Add('1');
for i := 0 to ACount-2 do
add(GetNextWaky(Strings[i]));
EndUpdate;
end;
end;
13 août 2006 à 19:37
sinon tout les CPU de moins de 5 ans supporte PerformanceCounter au moins chez AMD et Intel, si je ne m'abuse.
13 août 2006 à 19:31
13 août 2006 à 19:23
13 août 2006 à 19:23
Delphi 7,
Atlhon XP 2700+ 2166Mhz (13x167) Thoroughbred-B,
MSI KT4VL chip VIA Apollo KT400,
DDR PC2700 @ 333Mhz 2.5-3-3-7 CR2T
Windows XP Pro SP1, 23 processus, CPU Load 0-2%, Avast/Firefox/Delphi 7
Compteur de temps : HPC millisecondes
Taille du buffer : 2048 bytes
40 Wakygneuts / Temps : 1,9776 ms / Taille : 7,87 Ko
70 Wakygneuts / Temps : 3,4915 ms / Taille : 17,79 Ko
140 Wakygneuts / Temps : 7,0836 ms / Taille : 40,95 Ko
280 Wakygneuts / Temps : 14,0205 ms / Taille : 87,24 Ko
560 Wakygneuts / Temps : 28,5095 ms / Taille : 179,86 Ko
1120 Wakygneuts / Temps : 56,6877 ms / Taille : 365,06 Ko
2240 Wakygneuts / Temps : 115,0914 ms / Taille : 735,48 Ko
13 août 2006 à 19:21
1CAFE, en hexadécimal...
Mais là, faut que je sorte la calculette microsoft, lol.
13 août 2006 à 19:17
Mais à mon goût, la progression est trop régulière et prévisible à des kilomètres... ;-)
13 août 2006 à 19:02
( j'espère que je ne dis pas trop de c..ies! :)
13 août 2006 à 18:49
truc
1t 1r 1u 1c
111t 111r 111u 111c
311t 311r 311u 311c
13211t 13211r 13211u 13211c
111312211t 111312211r 111312211u 111312211c
13 août 2006 à 18:42
Enfin, 'sais pas. Je ne me suis pas pencher sur le problème...
13 août 2006 à 18:38
- Les lettres t, r, u, et c apparaitron toujours une seule fois dans chaque ligne
- Et qu'elles seront toujours précédées du chiffre 1 !!!!!!
Et on peut aussi en coclure que ce qu'on pensiat être un simple "truc" se transforme souvent en un "111312211t111312211r111312211u111312211c" incompréhensible. ça peut peut être aider à plus penser pour programmer (ben quoi on ne sait jamais)
13 août 2006 à 18:17
truc
1t1r1u1c
111t111r111u111c
311t311r311u311c
13211t13211r13211u13211c
111312211t111312211r111312211u111312211c
Mathématiquement parlant, c'est rigolo...
'sais pas quoi en conclure, mais certains matheux y trouveront certainement du grain à moudre... ;)
13 août 2006 à 17:23
Bon, et vous en êtes où avec vos histoires d'optmisation ? (oui, j'essaye de remettre la discussion dans le bon chemin car si on commence à parler de vaches et de trains ...)
Perso, j'abandonne. Il faudrait enlever la stringlist pour augmente sensiblement les perfs (à quoi 4a sert de stocker toutes les lignes si on a besoin que de la 71ème ?)
13 août 2006 à 17:17
13 août 2006 à 17:14
En plus, tous les PC n'ont pas un copteur de perf pour utiliser QueryPerformanceCounter()
En attendant, chuuut car c'est grâce (entre autre) à moi que tu as découvert comment utiliser cette fonction pour chronométer les perfs des procédures.
# Cari: pas besoin, pas besoin. Prend du jus d'orange (qui d'ailleurs est orange grâce au E358 et E189 ^^)
13 août 2006 à 17:13
Ca a rapport avec la théorie relativité restreinte ? ptdr...
13 août 2006 à 17:13
Et que proposes-tu pour que la vache atteigne la cible? mdr
13 août 2006 à 17:09
en fait, chaque suite et le logarythme naturel exposant 4 au carré plus pi sinus 2 fois 16 divisé par 666.
ch'est pa cha ?
@florenth : gettickcount ça pue. c'est aussi précis qu'un lancé de vache avec un train qui roule a 120Km/h
13 août 2006 à 14:28
13 août 2006 à 14:21
Et maintenant je suis tourmenté par une profonde angoisse quant à mon age mental ou mon incurie en math.
Et même, par moment, une tragique question me hante: et si c'était les deux?!
mdr
En tout cas, c'est bien plus rigolo et plus beau que la suite de Steinhaus...
( Qui a demandé: "c'est quoi la beauté en math"? ;)
13 août 2006 à 13:30
13 août 2006 à 12:53
j'ai adoré...
13 août 2006 à 11:49
13 août 2006 à 11:43
Au vu des différences de performances, je suis curieux de savoir quelles sont les méthodes d'accès aux lignes de cette classe (eh non, je n'ai pas le code de l'unité ^^)
13 août 2006 à 11:26
J'étais justement en trin de faire des tests de vitesse entre le code de Japee et Forman et il y a quelque chose qui cloche.
Voila ma procédure :
procedure TForm1.BtnTestClick(Sender: TObject);
const
N = 40;
var
TcJ, TcF: Cardinal;
S: TStringList;
begin
S := TStringList.Create;
{ Japee }
TcJ := GetTickCount;
JapeeGenereEnigme(S, N);
TcJ := GetTickCount - TcJ;
S.Clear;
{ Forman }
TcF := GetTickCount;
FormanGenereEnigme(S, N);
TcF := GetTickCount - TcF;
S.Free;
ShowMessageFmt('Japee: %d ms - Forman: %d ms', [TcJ, TcF]);
end;
Si je remplace "S" par "Memo1.Lines" dans le sprocédure ***GenereEnigme, il faut moins d'une seconde chez moi pour calculer le 40è terme alors qu'avec la StringList, il faut environ 8 secondes.
Etrange, je n'ai toujours pas compris pourquoi.
13 août 2006 à 11:12
Il s'agit de la 71ème ligne ? Si oui, je ne comprend pas pourquoi l'algo metrait plus de 7sec pour y arriver.
13 août 2006 à 09:52
12 août 2006 à 23:03
Décidément, il est trop fort ce Forman.
Mais il y a encore au moins une possibilité pour améliorer et faire mieux que 7062 millisecondes.
Défi relevé...
12 août 2006 à 22:14
Lol, ça doit être une déformation professionnelle, à force de faire des maths...
12 août 2006 à 21:06
J'avais pas réfléchi à toutes les implications mathématiques, toutes ces interrogations (et les angoisses) que ça soulève. Wouah...
Je trouve que ton code est plus beau que le mien (bouh).
Merci d'avoir amené un peu de grain à moudre à notre réflexion à partir de cette simple petite énigme.
Alors, quelqu'un relève le défi ?
(moi, j'ai comme un gros coup de fatigue, lol)
12 août 2006 à 20:27
Mais étudier la suite ainsi définie est un vrai casse-tête:
je m'étais posé des questions dessus il y a quelques années: peut-on exprimer la longueur du n-ième terme de la suite en fonction de n? Ou au moins trouver un équivalent vers l'infini?
La conclusion est: je ne sais ni démontrer que la suite est de longueur croissante (en effet, sans rien dévoiler, on peut imaginer des termes tels qu'en calculant le terme suivant la longueur obtenue est strictement inférieure, par exemple 111333) ni même qu'elle n'est pas périodique (il existe en effet par exemple un mot de 2 caractères tel que le mot suivant est le même: 22). Et pourtant, j'y ai passé du temps, mdr...
Les seules choses que je sais démontrer sur cette suite (et c'est très facile à faire, ce sont des propriétés immédiates) c'est:
-elle ne contient que les 3 chiffres 1,2 et 3
-la longueur du n-ième terme est plus petite que (ou égale à) 2^n
J'ai réécrit l'algorithme pour calculer un des termes à partir du précédant, de façon à ce qu'il aille plus vite (moins de réallocation de mémoire):
function f(s:string):string;
var
p,q:PChar;
c,d,e:Char;
begin
SetLength(Result,2*Length(s));
p:=PChar(s);
q:=PChar(Result);
c:=p^;
repeat
e:='0';
repeat
Inc(p);
d:=p^;
Inc(e);
until d<>c;
q^:=e;
PChar(q+1)^:=c;
q:=q+2;
c:=d;
until c=#0;
SetLength(Result,Integer(q)-Integer(PChar(Result)));
end;
procedure FastGenereEnigme(const TS:TStrings;const n:Word=12);
var
a:Integer;
begin
TS.Clear;
TS.Add('1');
for a:=0 to n-1 do
TS.Add(f(TS[a]));
end;
Ca fonctionne si on considère que calculer le terme suivant de la suite va au plus doubler la longueur (d'où l'explication du SetLength(Result,2*Length(s))). Pour calculer le 50ième terme, GenerateEnigme met 25 secondes alors que FastGenereEnigme met 32 millisecondes... Ca démontre encore, s'il en était besoin, que les allocations de mémoire cachées rallentissent énormément le code: lorsqu'on écrit a+b (où a et b sont des chaînes de caractères) il y a une réallocation de mémoire pour stocker le résultat de la concaténation.
L'algorithme à optimiser est un bon exemple: je propose le challenge de celui qui donnera un algorithme (pour la fonction f) calculant le plus vite possible le 71ième terme de la suite (à partir du 72ème, le terme devient trop grand et provoque une exception EOutOfMemory chez moi). Record à battre: 7062 millisecondes pour calculer le 71ième terme de la suite. Bien sûr, pour que ça compte, il faut que les 2 algo soient lancés sur la même machine!
A vos claviers ;-)
12 août 2006 à 17:02
Florenth, bravo, mais c'est vrai que tu es un des plus jeunes d'entre nous (hormis moi, bien sûr, lol). J'ai lu ton MP, je vais étudier la question.
12 août 2006 à 16:34
Bon on me l'avais déjà fait :-)
mais c'est d'un "con"
si je ne suis pas trompé ce devrait être la ligne suivante :
11131221131211131231121113112221121321132132211331222113112211
bien :-)
@+
12 août 2006 à 16:22
J'ai mis à peine 1 minute pour trouver (sans lire le source) ^^ (ça veut dire que j'ai un esprit d'enfant - normal quoi !)
Par contre, pourque le programme ait plus d'utilité, j'aurais mis un peit bouton, qui quand on appuye dessus, afficherait l'explication (non pas de façon statique et mathématiques (mais est-ce bien des maths ?) mais de façon ... arrgh je ne peux pas le dire sans dévoiler la solution !
Surveille ton MP
Et il faurait aussi que ta fonction puisse faire varier le chiffre de début, ça aiderait certains à comprendre