~rom1v/blog { un blog libre }

Résoudre le cube-serpent en Python

cube-serpent

Je me suis amusé à écrire un petit programme en Python qui résout le cube-serpent (ainsi nous pouvons dire qu’un serpent en résout un autre).

Mon but était surtout d’apprendre le langage Python, avec un problème intéressant, pas trop compliqué (c’est de la force brute). Il m’a permis de découvrir différents aspects de Python.

EDIT : Je l’ai également implémenté en C.

L’algorithme proposé résout un cube-serpent généralisé. En effet, il sait trouver des solutions pour obtenir un cube de 3×3×3, mais également d’autres tailles, comme 2×2×2 ou 4×4×4. Il sait également résoudre des volumes non cubiques, comme 2×3×4. Et pour être totalement générique, il fonctionne pour un nombre quelconque de dimensions (2×2, 3×5×4×2, 2×3×2×2×4). Comme ça, vous saurez replier un serpent en hypercube

Je vais d’abord présenter le problème et décrire l’algorithme de résolution et survoler l’implémentation, puis je vais m’attarder sur certaines fonctionnalités de Python qui m’ont semblé très intéressantes.

Résolution

Problème

Le but est de replier la structure du serpent pour qu’elle forme un volume, par exemple un cube.

La structure peut être vue comme une liste de vecteurs orthogonaux consécutifs, ayant chacun une norme (une longueur). Elle peut donc être caractérisée par la liste des normes de ces vecteurs. Ainsi, la structure du serpent présenté sur Wikipedia est la suivante :

snake

[2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2]

Le volume cible peut être représenté par un graphe, un ensemble de sommets reliés par des arêtes, auquel on ajoute la notion d’orientation dans l’espace (il est important de distinguer les arêtes orthogonales entre elles). En clair, chaque sommet représente une position dans le cube : il y a donc 27 sommets pour un cube 3×3×3.

L’objectif est de trouver dans le graphe ainsi formé par le cube un chemin hamiltonien (un chemin qui passe par tous les sommets une fois et une seule) qui respecte la contrainte de la structure du serpent.

Principe

Pour trouver les solutions, il suffit de partir d’un sommet et tenter de placer les vecteurs de la structure consécutivement un à un, en respectant trois contraintes :

  • rester dans le volume (évidemment) ;
  • le nième vecteur doit être orthogonal au (n-1)ième vecteur (cette règle ne s’applique pas pour le tout premier vecteur) ;
  • le vecteur “placé” dans le cube ne doit pas passer par une position déjà occupée (physiquement, il n’est pas possible de faire passer une partie du serpent à travers une autre).

Il faut donc placer récursivement tous les vecteurs possibles, c’est-à-dire tous les vecteurs orthogonaux au précédent, qui ne sortent pas du cube et qui ne passent pas par une position déjà occupée. Jusqu’à arriver soit à une impossibilité (plus aucun vecteur ne respecte ces 3 contraintes), soit à une solution (tous les vecteurs sont placés).

Pour ne manquer aucune solution, il faut répéter cet algorithme en démarrant avec chacun des points de départ (donc les 27 sommets pour un cube 3×3×3).

Limites

Cet algorithme ne détecte pas les symétries ni les rotations, il donne alors plusieurs solutions “identiques”. Une amélioration serait de les détecter “au plus tôt” et de ne pas les construire.

EDIT : La version 0.2 gère les symétries et les rotations, pour éviter de calculer plusieurs solutions identiques. Plus d’explications dans ce commentaire et le suivant.

Implémentation

Voici une explication succincte des différentes parties du programme (pour plus d’informations, lire les commentaires dans le code).

Vector

Nous avons besoins de vecteurs, mais pas n’importe lesquels : seulement ceux qui ont une et une seule composante non-nulle, c’est-à-dire des multiples des vecteurs de la base. En effet, par exemple en 3 dimensions, la direction de chacun des vecteurs sera soit droite-gauche, soit dans haut-bas, soit avant-arrière, mais jamais en diagonale avant-droite vers arrière-gauche.

Ainsi, au lieu de stocker toutes les composantes, le Vector ne contient que la valeur de la composante non-nulle ainsi que sa position (plus facile à manipuler):

Vector(position, value)

VolumeHelper

Cette classe définit l’outil que va utiliser le solveur pour noter tout ce qu’il fait : le chemin emprunté et les sommets déjà visités. À chaque fois qu’il place un vecteur dans le volume, il “allume les petites lumières” associées aux sommets visités, et quand il revient en arrière (pour chercher d’autres solutions), il éteint ces petites lumières (par lumières, comprenez booléens).

SymmetryHelper

Cette classe a été ajoutée dans la version 0.2. Elle définit l’outil que va utiliser le solveur pour n’explorer que les solutions nécessaires, en ignorant les symétries et les rotations.

Solver

Le solveur place récursivement les vecteurs de la structure dans toutes les positions possibles (en s’aidant du VolumeHelper) afin de trouver toutes les solutions.

Solutions

Lors de l’exécution du script, les solutions s’affichent au fur et à mesure :

$ ./snakesolver.py
([0, 0, 0], [2x, y, -x, 2z, y, -2z, x, z, -2y, -2x, y, -z, y, 2z, -2y, 2x, 2y])
([0, 0, 0], [2x, z, -x, 2y, z, -2y, x, y, -2z, -2x, z, -y, z, 2y, -2z, 2x, 2z])
([0, 0, 0], [2y, x, -y, 2z, x, -2z, y, z, -2x, -2y, x, -z, x, 2z, -2x, 2y, 2x])
...

Considérons la première solution :

([0, 0, 0], [2x, y, -x, 2z, y, -2z, x, z, -2y, -2x, y, -z, y, 2z, -2y, 2x, 2y])

Le point de départ est [0, 0, 0]. On se déplace d’abord de 2 sur l’axe x, puis de 1 sur l’axe y, de -1 sur l’axe x, etc.

Voici la représentation graphique de cette solution :

solution-cube-serpent

Fonctionnalités de Python

Maintenant, voici quelques éléments essentiels du langage Python dont je me suis servi pour ce programme.

Compréhension de liste

La compréhension de liste (ou liste en compréhension) est très pratique. Je l’ai utilisée plusieurs fois dans l’algorithme. Je vais détailler deux exemples.

D’abord, dans la classe VolumeHelper :

def all_points(self, index=0):
    if index == len(self.dimensions):
        return [[]]
    return ([h] + t for h in xrange(self.dimensions[index])
            for t in self.all_points(index + 1))

Ce qui est retourné à la fin signifie :

tous les éléments de la forme [h] + t (l’élément h en tête de liste suivie de la queue de la liste) pour h compris entre 0 et self.dimensions[index] (un entier) et pour tout t compris dans les résultats de l’appel récursif

Ça ne vous éclaire pas ? Dit plus simplement :

le résultat de la concaténation de chacun des nombres de 0 à n (avec n = self.dimensions[index]) à chacune des listes fournies par l’appel récursif

En fait, cette fonction fournit tous les points possibles pour les dimensions données. Par exemple, si dimensions = [2, 2], alors le résultat sera :

[[0, 0], [0, 1], [1, 0], [1, 1]]

Pour dimensions = [2, 2, 3], le résultat sera :

[[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 1, 0], [0, 1, 1], [0, 1, 2], [1, 0, 0],
[1, 0, 1], [1, 0, 2], [1, 1, 0], [1, 1, 1], [1, 1, 2]]

Sans compréhension de liste, il serait difficile d’écrire le corps de cette fonction en 3 lignes !

Remarque : la compréhension de liste retourne une liste si elle est définie entre [], alors qu’elle retourne un générateur (un _itérateur) si elle est définie entre ()._

Second exemple, dans Solver.__solve_rec(…) :

for possible_vector in ( Vector(i, v)
                         for v in [ norm, -norm ]
                         for i in xrange(len(self.dimensions))
                         if i != previous_position ):

Cette partie fournit un ensemble de Vector(i, v), pour toutes les combinaisons de i et de v dans leurs domaines respectifs, qui vérifient la condition (qui ici ne porte que sur i).

En clair, ici nous récupérons tous les vecteurs possibles, c’est-à-dire orthogonaux au précédent et avec la norme (la longueur) imposée par la structure.

Itérateur

La notion d’itérateur est présente dans beaucoup d’autres langages. Un itérateur retourne un nouvel élément à chaque appel à la méthode next(). En pratique, il est souvent utilisé de manière transparente dans une boucle for _variable_ in _iterator_ :

for i in xrange(10):
    print i

xrange(…) retourne un itérateur et fournit les valeurs au fur et à mesure, alors que range(…) crée la liste de toutes les valeurs, qui est ensuite parcourue.

Yield

Les expressions yield permettent de créer un itérateur très simplement.

Pour résoudre le cube-serpent, il est préférable d’une part de fournir les solutions au fur et à mesure qu’elles sont trouvées, et d’autre part de pouvoir ne calculer que les k premières solutions.

La première contrainte est souvent résolue grâce à des callbacks : la fonction de calcul prend en paramètre une fonction, qui sera appelée à chaque résultat trouvé, le passant alors en paramètre.

La seconde est plus délicate : elle implique que l’algorithme s’arrête dès qu’il trouve une solution, et que lors d’un prochain appel il reprenne le calcul là où il s’était arrêté, afin calculer les solutions suivantes. Cela nécessite de conserver un état. Pour un itérateur simple comme celui d’une liste, il suffit de stocker l’index courant de parcours, et de l’incrémenter à chaque appel à next(). Gérer manuellement l’itération sur les solutions du cube-serpent semble beaucoup plus complexe, d’autant plus que les solutions sont trouvées dans des appels récursifs.

C’est là qu’interviennent les expressions yield, qui répondent aux deux besoins en même temps. Utiliser une expression yield dans le corps d’une fonction suffit à transformer cette fonction en un générateur. Il n’est donc plus possible de retourner de valeur grâce à return.

Dès que l’expression yield est rencontrée, la valeur est transmise et l’exécution de la fonction s’arrête. Elle reprendra lors du prochain appel.

Afin d’utiliser ce principe pour la génération des solutions, les fonctions SnakeCubeSolver.solve() et SnakeCubeSolver.__solve_rec(…) ne sont donc pas des fonctions ordinaires, mais des générateurs :

if step == len(self.structure):
    yield init_cursor, self.volume_helper.path[:]

Grâce à cette implémentation, il est possible de parcourir toutes les solutions :

for solution in solver.solve():
    print solution

ou alors de ne générer que les k premières :

max_solutions = 5
solutions = solver.solve()
for i in xrange(max_solutions):
    try:
        print solutions.next()
    except StopIteration:
        break

Lambdas

Python supporte aussi les expressions lambda, issues du lambda-calcul, qui permettent d’écrire des fonctions anonymes simplement.

J’utilise cette fonctionnalité une fois dans le programme :

needed_length = reduce(lambda x, y: x * y, self.dimensions) - 1

Il s’agit de la déclaration d’une fonction avec deux arguments, qui retourne leur produit.

La fonction reduce(function, iterable, …) permet d’appliquer cumulativement la fonction aux éléments de l’iterable, de gauche à droite, de manière à réduire l’iterable en une seule valeur.

Même si “ce qui se conçoit bien s’énonce clairement”, la fonction reduce est bien plus facile à comprendre qu’à expliquer en quelques mots…

Ici, donc, needed_length contient le produit de tous les éléments de la liste self.dimensions.

Conclusion

La résolution du cube-serpent est intéressante, tout comme sa généralisation à n’importe quel volume de dimensions quelconque. Je me suis arrêté là (EDIT : finalement, non), mais la détection des symétries et des rotations “au plus tôt” serait une amélioration non négligeable (et pas si évidente).

Débutant tout juste en Python, ce micro-projet m’a permis de beaucoup apprendre, et de découvrir quelques bonnes surprises comme les expressions yield que je ne connaissais pas.

J’espère que ça vous a amusé aussi.

Script

Le code source est disponible sur ce dépôt git : snakesolver.

Commentaires

Fred

Hello,

Sympa ton challenge perso :)

Pour info, un 3x3x3, tu le résous en combien de temps ?

Par ailleurs, tu connais la complexité de ton algo ?

®om

@Fred

Pour info, un 3x3x3, tu le résous en combien de temps ?

Pour trouver les 48 solutions (symétries et rotations incluses), il met moins d’une seconde.

@Fred

Par ailleurs, tu connais la complexité de ton algo ?

Je dirais que la complexité max est de (2d)n, avec d le nombre de dimensions (dans l’exemple 3), et n le nombre de vecteurs dans la structure du serpent (dans l’exemple 17) : on tente les combinaisons de toutes les directions (et sens) (2d) pour chacun des vecteurs (n).

La complexité réelle est bien moins importante, car les branches de l’arbre de résolution sont vite coupées (dès qu’un vecteur sort du cube ou qu’il ne peut pas être placé).

La première expression en gras n’est pas une compréhension de liste, puisqu’elle n’est pas entre crochets:

[f(elem) for elem in truc]

Elle est entre parenthèses, c’est donc un générateur. Mais ça revient (presque) au même si c’est créé pour itérer dessus (la seule différence, c’est que le générateur ne contient pas tous les éléments en mémoire en même temps).

®om

@EdEd

Que le résultat soit une liste ou un générateur, je pense qu’il s’agit d’une compréhension de liste.

J’ai d’ailleurs précisé :

Remarque : la compréhension de liste retourne une liste si elle est définie entre [], alors qu’elle retourne un générateur (un itérateur) si elle est définie entre ().

Pour moi, quelque soit la manière dont les éléments sont produits, il s’agit bien de compréhension de liste, car son contenu est défini par compréhension et non par énumération.

EDIT : Je viens de comprendre ce que tu voulais dire. D’après toi ça ne peut pas être une liste en compréhension car ce n’est pas une liste (mais un générateur). En fait, il s’agit bien une liste en compréhension, liste étant à comprendre dans le sens général (une suite d’éléments). Par contre, cette liste n’est pas forcément implémentée sous forme de liste python (dont tous les éléments sont en mémoire).

®om

Bon, par contre, le 4×4×4 c’est beaucoup plus long, en partie parce qu’il teste toutes les combinaisons alors qu’en supprimant les rotations et symétries, on diviserait pas mal les combinaisons à tester.

Par exemple, si en partant de [0, 0, 0], il n’y a pas de solution, ça ne sert à rien de tester en partant [0, 0, 3]. De même, toujours en partant de [0, 0, 0], s’il n’y a pas de solution en partant sur l’axe x, alors il n’y en aura pas non plus si l’on part sur les axes y ou z.

Concrètement, pour le cube-serpent 4×4×4 suivant :

SNAKE_STRUCTURE = [1, 1, 2, 1, 1, 3, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1 ,1, 2, 2, 1, 1, 1, 1, 1, 2, 3, 1, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3]
VOLUME_DIMENSIONS = [4, 4, 4]

il trouve la première solution en 20 heures et 23 minutes sur mon PC :

([0, 1, 1], [-y, x, 2z, -x, -z, 3y, z, -2y, x, 2y, -z, -2y, -z, y, -x, y, x, -z, -y, x, y, x, -2y, 2z, y, -z, -x, y, x, 2z, -3y, -z, -x, z, 3y, -z, -2y, -z, -y, x, -z, -x, y, -x, -y, -x, 3y])
nico

Merci,

Grâce à toi je viens enfin de résoudre mon serpent de 64 (cube de 4x4x4) sur lequel je séchais depuis des années!

®om

@nico Tu as exécuté le programme pour trouver la solution ? Si oui tu as eu le résultat en combien de temps ?

Ou alors tu as utilisé la solution que je viens de poster en commentaire… 6 minutes avant ton message (auquel cas tu es très rapide) ?

nico

Ca a pris environ 5mn chez moi.

Pour info, voila mon serpent:

[ 2, 1, 2, 1, 1, 3, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 2, 3, 1, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1 ]

et la solution:

([0, 0, 0], [2x, y, -2x, z, -y, 3x, -z, 2y, -x, 2z, -x, -2z, -x, y, x, z, x, -z, x, z, -2y, -2x, z, -x, y, -z, y, 2z, -3y, -z, x, z, 3y, -z, 2x, -y, z, -y, -z, -x, -y, x, z, -x, 3y, x])
®om

@nico

Ah ok, tu as une structure qui a une solution avec le premier point testé ([0, 0, 0]), forcément ça prend moins de temps ;-)

Ywen

Salut !

Pour l’histoire des points testés, en fait c’est pas compliqué, il suffit de supprimer ceux qui sont identiques à une rotation près. Exemple, pour un 3x3x3, il ne faut tester qu’une face et sur cette face, qu’un corner (*), un edge (*) et un center (*), autrement dit :

. . .
. C .
O E .

O = cOrner, E = Edge, C = Center

Ca plus le core (le milieu du cube), on n’a donc que 4 positions initales à tester (au lieu de 27).

(*) Termes du Rubik’s Cube.

Doit bien y avoir moyen de déduire une règle pour les configurations autres que 3x3x3…

De plus, si je ne me trompe pas, tu génères bien la liste de TOUTES les solutions possibles à partir d’un coin, indépendamment de la structure de ton serpent ?

Par exemple, si ton serpent commence ainsi :

[2, 2, 1, 2....]

Alors tu est sûr dès le moment ou tu vas commencer à établir une solution du type

[2x, -y...]

Qu’elle sera forcément fausse, car la deuxième partie du corps de ton serpent a une taille de 2. (tu devrais donc avoir 2y ou -2y pour continuer à investiguer cette solution).

Or (j’ai lu rapidement ton code et donc il est possible que je me trompe) il me semble que si tu génères tes solutions à la demande (via un generator), ce n’est pas le cas des éléments de chaque solutions. Cela te permettrait de tuer dans l’oeuf des solutions qui seront forcément fausses.

®om

Merci de ta réponse de fond, qui s’attaque aux limites de mon algo.

@Ywen

Pour l’histoire des points testés, en fait c’est pas compliqué, il suffit de supprimer ceux qui sont identiques à une rotation près.

Il est effectivement assez facile de supprimer dès le départ tous ceux qui sont “équivalents”. Mais ce n’est pas suffisant pour supprimer toutes les symétries et les rotations : si tu pars de [0, 0, 0], tu peux encore diviser par 3 le nombre de chemins à tester, car les solutions commençant par x, y et z sont équivalentes. Et une fois que tu as choisi de commencer par x, les chemins [x, y] et [x, z] sont encore équivalents.

<je_pense_à_voix_haute>

Je suis convaincu que les règles de détection sont les mêmes pour les points d’origine et pour les chemins.

Pour les points, elle est la suivante : deux points p1 et p2 sont équivalents si et seulement si en permutant entre elles les dimensions de même grandeur de p1, éventuellement en les “inversant”, on peut obtenir p2.

Par exemple, sur un 3×3×3, les points [ 1, 0, 2 ] et [ 2, 1, 0 ] sont équivalents, car il s’agit d’une simple permutation de dimensions. Par contre, ces points ne sont pas équivalents sur un 2×3×4, car un tel volume n’a pas de symétries diagonales (il ne faut permuter entre elles que les dimensions dans lequel le volume a la même taille).

Mais ce n’est pas tout, les points [ 0, 0, 1 ] et [ 2, 0, 1 ] sont aussi équivalents (symétrie par rapport l’axe des x), tout comme les points [ 0, 0, 1 ] et [ 2, 2, 1 ] (symétries par rapport aux axes x et y, donc rotation de 180° autour de l’axe z). Ainsi, il faut également considérer comme équivalents les points avec des dimensions “inversées” (c’est-à-dire, pour la dimension i, avec p1[i] + p2[i] + 1 = dimensions[i]).

Et il faut aussi prendre en compte les permutations de ces dimensions “inversées”.

En supprimant tous les points équivalents, on trouve bien les 4 solutions initiales dont tu parlais :

[ 0, 0, 0 ]
[ 0, 0, 1 ]
[ 0, 1, 1 ]
[ 1, 1, 1 ]

Toutes les autres sont “équivalentes” au sens de la règle énoncée.

Et ce qui est bien, c’est qu’on remarque qu’on peut trouver tous les points “minimaux” très facilement, car ils ont une forme très simple qu’on peut généraliser (comme tu l’intuitais). De cette façon, on sait les générer bien plus simplement qu’en appliquant la règle complexe.

Maintenant, pour “tuer dans l’œuf” les chemins équivalents à ceux déjà calculés, il “suffit” d’appliquer une généralisation de la règle : deux chemins c1 et c2 sont équivalents si et seulement si en appliquant la même permutation des dimensions de même grandeur de chacun des points par lesquels passe c1, et en appliquant la même “inversion”, on peut obtenir chacun des points par lesquels passe c2. En clair, en appliquant la même règle à chacun des points, si on parvient à obtenir un chemin déjà parcouru, c’est un chemin équivalent.

Je pense que comme pour les points, il y a un algorithme simple de génération qui applique cette règle pour couper les branches de l’arbre de résolution. Je laisse tourner un processus démon dans ma tête avant de l’implémenter…

</je_pense_à_voix_haute>

@Ywen

De plus, si je ne me trompe pas, tu génères bien la liste de TOUTES les solutions possibles à partir d’un coin, indépendamment de la structure de ton serpent ?

Par exemple, si ton serpent commence ainsi :

[2, 2, 1, 2....]

Alors tu est sûr dès le moment ou tu vas commencer à établir une solution du type

[2x, -y...]

Qu’elle sera forcément fausse, car la deuxième partie du corps de ton serpent a une taille de 2. (tu devrais donc avoir 2y ou -2y pour continuer à investiguer cette solution).

Or (j’ai lu rapidement ton code et donc il est possible que je me trompe) il me semble que si tu génères tes solutions à la demande (via un generator), ce n’est pas le cas des éléments de chaque solutions. Cela te permettrait de tuer dans l’oeuf des solutions qui seront forcément fausses.

C’est déjà ce que fait l’algo, il ne testera jamais [ 2x, -y, … ] si la structure est [ 2, 2, … ].

Tout est dans cette portion de code :

for possible_vector in ( Vector(i, v)
                         for v in [ norm, -norm ]
                         for i in xrange(len(self.dimensions))
                         if i != previous_position ):

Les vecteurs possibles sont ceux concernant les dimensions autres que celles du vecteur précédent (donc orthogonal), dont la composante vaut norm ou -norm. Sur ton exemple, norm vaut 2, donc les vecteurs possibles seront 2y, -2y, 2z et -2z.

®om

Ça y’est, j’ai trouvé comment éviter les symétries et les rotations : il faut garder la liste des classes d’équivalence associées à la relation de symétrie/rotation, et ne choisir à chaque étape qu’un vecteur par classe (en ignorant les autres, car ils sont équivalents). Ces classes d’équivalence se diviseront lors du placement d’un nouveau vecteur.

Je l’ai implémenté dans une version v0.2, et j’ai mis à jour le billet.

J’ai ajouté une classe SymmetryHelper qui gère ça, et son utilisation par le solveur. Le code est commenté pour comprendre comment ça fonctionne.

Pour les points de départ, la fonction get_useful_points() remplace la fonction all_points().

Pour la résolution du cube de nico (en s’arrêtant à la première solution), il n’y a aucun gain de temps, car la solution était déjà trouvée sans explorer de symétries inutiles. Par contre, il n’y a aucune perte de temps non plus, ce qui montre que le code servant à gérer la détection des symétries prend un temps négligeable.

Pour se donner une idée du temps gagné, on peut comparer le calcul de toutes les solutions du 3×3×3 :

  • snakesolver-0.1.py : 412ms ;
  • snakesolver-0.2.py : 50ms

Et il ne trouve plus qu’une seule solution, au lieu de 48 (qui étaient donc 48 solutions identiques).

J’ai démarré la résolution du cube 4×4×4 qui avait pris plus de 20 heures. J’éditerai ce commentaire quand le programme aura trouvé la solution.

EDIT : Il a trouvé en 3 heures 53 minutes.

Pas mal du tout!!

Mais pourquoi pas du C++ par exemple?

En gros pourquoi de l interprété plutôt que du compilé?

®om

@FTG

C’est un choix arbitraire. Ici, je voulais apprendre Python, plus haut niveau.

Il serait intéressant de comparer les performances d’un tel algo écrit en Python et en C++ (si tu as quelques heures à perdre pour l’écrire en C++ ^^).

Il existe aussi des (au moins un) compilateurs JIT pour Python comme Psyco, mais je n’ai jamais testé.

Ywen

@FTG :

Parce qu’en C++ le code aurait peut-être été 2 fois plus long. Il ne s’agit pas d’interprété VS compilé, simplement d’expressivité (®om utilise beaucoup de list-comprehensions et de fonctions lambda).

A titre d’exemple, je suis en train d’essayer de refaire le solver en Haskell, je suis parti pour avoir un code 4 fois plus court qu’en Python.

Plus rapide ? Comme a dit ®om, ça se teste, mais visiblement Python commence à se défendre.

@®om:

Mmmh… Psyco n’apporte pas toujours des gros boosts de vitesse, ça dépend vraiment de ton algo (je n’en sais pas plus). Mieux vaut se pencher sur Pypy, une autre implantation de Python.

®om

Dans la version 0.2, la fonction get_useful_points() ne fonctionnait pas si toutes les dimensions n’étaient pas égales (par exemple 2×3×4).

Il faut d’une part ne créer que les vecteurs dont les coordonnées sont à la moitié ou moins de la taille du volume dans cette dimension (pour éviter les symétries suivant les axes des vecteurs de base), et uniquement ceux dont les coordonnées sont dans l’ordre (pour éviter les permutations de dimensions).

Mais il ne faut éviter les permutations de dimensions que pour celles qui sont de même taille (commencer à [0, 1] ou à [1, 0], c’est équivalent sur un 2×2, mais pas sur un 2×3). Du coup, il faut faire cette opération à l’intérieur de chaque classe d’équivalence, ce que ne faisait pas la version 0.2.

C’est ce que j’ai implémenté dans la version 0.2.1.

@Ywen Poste ton code en Haskell quand tu auras terminé ;-)

Ywen

Yep, je le posterai (enfin là ça fait 5 jours que j’y ai pas touché), j’essaie de comprendre tes optimisations pour la symétrie et la rotation.

Les commentaires sont fermés.