Limites de temps bougrement trop restrictives

@yosh :
> non mais voilà prends 5s et soumets un truc dans un langage un
> minimum "sérieux", je sais pas soumets le en assembleur par exemple
> et optimise tout à fond
Je soumettrai en Ook! histoire de bien me faire comprendre par les orgas. (pas taper)

@agranger36 : Merci de te soucier de ma santé mant++[>+-----.>++[>---.

@serialk : Mouais bon… il faut voir aussi qu'une addition c'est au mieux en O(log(N)) (avec optimisations et des cells de 8 bits).

@yosh :
> Perso j'ai du mal à imaginer un algo de 5 lignes trop lent mais bon c'est pas grave ..
Mon programme (sans commentaires) ne fais qu'une seule ligne… de 5286 caractères.
> anyway avec un simple compilo to asm peu de chances que ça rame
C.f. ma note à serialk. L'interpréteur utilisé a des cellules de 8 bits (c'est le plus commun), ce qui est trop petit pour les contraintes de l'exercice 3. Personnellement, je représente le nombre en base 10, ce qui évite des conversions au début de l'algorithme et facilite l'affichage. Cela signifie toutefois que mes additions nécessitent autour de log_10(N) opérations brainfuck. Je te laisse imaginer les modulos et divisions…

@Equinoxe :
> Bon, je suis en train de coder le compilo, et je me demande : vous avez besoin du wrapping ou pas ?
> Parce que sans, le code irait sûrement beaucoup plus rapidement. Et vu qu'il n'y a pas de spécification explicite
J'abuse fortement du wrapping. Il y a des compétitions où c'est interdit (mais dans ce cas là, c'est plus comme une conduct nethack).
Et je ne vois pas en quoi c'est plus lent… si tu utilises des unsigned char, en pratique ça wrap tout seul (en théorie, dans le standard, c'est un undefined behavior).

@yosh :
> @epsilon012 retourne faire du xhtml
6, je te pris. Du XHTML6.
> @Equinoxe & @epsilon012 J'aurais dû me douter que ce concours serait aussi un meeting de trolls, autant pour moi
Je pense que tu veux dire "au temps pour moi", quoi, si cela te conviens et que c'est "autant pour toi", pas besoin de traiter des gens que tu ne connais pas de "pauvre type".
> en même temps vu le niveau de ce qcm ya pas à s'étonner
Le fait est que tout mes messages jusqu'à celui ci étaient complétement dépourvu de sérieux. Tu trouves les sélections faciles ? Tu crois que tu es bien meilleur ? Et bien deux notes là dessus :

• Ce sont des sélections, un grand nombre de gens les trouvent facile, mais le but du concours c'est de réunir des passionnés d'informatique aussi. Faire des sélections trop difficiles, c'est fermé la porte à de nombreuses personnes. De toute façon il y a deux autres étapes à Prologin : les régionales et la finale.
• Si tu trouves cela trop facile, tu peux essayer de le faire dans un langage ésotérique… type brainfuck.

Cordialement

@Megra : good \o/

Sinon… 42.

yosh : effectivement, je pense qu'on va s'arrêter là, merci.

@LLB:
"Je ne sais pas quel compilo est utilisé, mais je conseille d'essayer celui-là : http://code.google.com/p/esotope-bfc/
Je doute que tu arrives à faire mieux (sans y passer 3 mois)."

Je n'arriverai probablement pas à faire mieux. Mais j'essaierai. Quand même, son utilisation reste sûrement préférable pour Prologin ! (En fait, à part un tout petit bug -- cf. developpez.net "[C++11][lambda] Variable qui se modifie toute seule", j'ai fini la propagation de constantes de leur wiki -- et j'ai déjà fait la conversion vers le C.)

@epsilon: mEntalE * (Désolé, je suis incapable de m'en empêcher !)
"J'abuse fortement du wrapping. Il y a des compétitions où c'est interdit (mais dans ce cas là, c'est plus comme une conduct nethack).
Et je ne vois pas en quoi c'est plus lent… si tu utilises des unsigned char, en pratique ça wrap tout seul (en théorie, dans le standard, c'est un undefined behavior)."

Si je prends unsigned char memory[30000]; unsigned char *ptr = memory;, à chaque déplacement de ptr je dois faire ptr = (ptr - memory + DEPL + 30000) % 30000 + memory; (+30000 pour éviter les négatifs)
Si je prends unsigned char memory[30000]; unsigned int pos = 0; je dois faire pos = (pos + DEPL + 30000) % 30000; et ça coute une addition supplémentaire à chaque accès mémoire.

Donc dans tous les cas ça coûte au moins un modulo et une addition de plus par déplacement de pointeur. Ce qui me semble être relativement lourd, comparé à une seule addition sinon !

Et le wrap automatique, je ne vois pas de quoi tu parles ... ?

Sinon, le code actuel de mon compilo est ici : https://github.com/Ekinox/BFC
Et le lien vers le topic du bug ici : http://www.developpez.net/forums/d1170319/c-cpp/cpp/cpp11-lambda-variable-change-toute-seule/

Il y a quiproquo, je parlais du wrapping des cells (est ce que le code "-" est un undefined behavior ou est ce qu'il change la valeur de la première cell en 255 ?).
Sur le wrapping mémoire, ça ne sert à rien sachant que pour être portable un code ne doit pas l'utiliser (d'ailleurs mes codes brainfuck commencent souvent par une dizaine de >). En plus imho, c'est plus simple pour déboguer, c'est rarement volontaire d'avoir un pointeur en -100.
Un code brainfuck portable… marrant comme expression.

Ah, le wrapping des cells ! Du coup, mon message ne servait à rien.

Bon, sinon, mon bug était simplement idiot : c'est dans la passe d'optimisation qui exécute le programme "à froid", pour déterminer les constantes, que j'avais oublié un '+' ...
Du coup, je vais bientôt retourner à l'optimisation.

Edit : D'ailleurs, tu peux poster ton code BF ? Ce serait une bonne occasion pour vérifier les performances des optimisations !

Equinoxe: http://www.prologin.org/node/997

@alex3er: J'étais en train de lire le topic, et de me dire que je devrais revenir éditer mon message ... ="(

Arf, alors désolé pour ma réactivité.

@Equinoxe : Une petite note sur ton code.
treeoptimizer.cpp:46 : unsigned char memory[30000];
FDIS §8.5 ¶6 (ton tableau est default-initialized )
FDIS §23.3.2 (et Dieu créa std::array).

Je sais, j'ai remarqué hier. Vu que ça marchait, je ne m'en étais pas préoccupé.
Sauf qu'après réflexion, vu que prologin a trouvé un autre compilateur capable, j'ai changé d'idée. Je vais voir pour développer une extension à GCC (qui s'appellera gbf ! =D).
L'avantage, c'est que ça permet d'utiliser la structure de GCC pour développer les optimisations, plutôt que d'avoir un pseudo-arbre qui ne gère que peu de choses.

Je reviendrai sur les forums prologin quand j'aurai un peu avancé et uploadé le code sur github. ;)

On a parlé de la même chose mardi dernier d'ailleurs, tu pourras laisser toutes les optimisations au compilateur, et il va simplifier un grand nombre d'opérations à mon avis.

Une question : pourquoi GCC et pas LLVM ?

ven, 06/01/2012 - 15:31 — Megra
> Une question : pourquoi GCC et pas LLVM ?
+1

Parce que je n'y avais pas pensé. De toute façon, je n'avais pas encore commencé. Vu que je n'ai encore jamais développé d'extension au aucun des deux, je vais examiner avant de commencer, merci !

@epsilon012:
Le compilateur est en place :)

Bon ...
Si ça tente quelqu'un d'essayer de comprendre pourquoi ça bug, j'abandonne.
https://github.com/Ekleog/EBC
(cmake . -DLLVM_DIR=[la ou vous avez le fichier LLVMConfig.cmake dispo] && make && bin/ebc [monfichier].bf)
Le souci, c'est que ça marche pour les programmes simples (hello world, cat), mais que l'exécutable généré segfaulte au lancement pour les programmes plus compliqués ...