Discussion :

[Cacophrene]

Bonsoir,

As-tu testé les performances contre la version qui ne hache rien du tout, et se passe complètement de mise en cache ?

Sous réserve que l'état final soit le même pour les deux programmes, ce que je n'ai pas vérifié, la différence est rapidement significative. Ainsi pour 1000 générations, j'obtiens ~400 ms pour la version sans mémorisation, et ~70 ms pour la version avec mémorisation. Pour 5000 générations, on est à ~3.7 s sans mémorisation, contre seulement ~100 ms avec mémorisation. C'est un élément important de l'algorithme et les performances s'en ressentent.

Je pense que la seule façon de faire plus rapide, en évitant les comparaisons en profondeur, est de faire du hash-consing propre dès le début. Cf. par exemple cet article.

Merci pour le partage. On va voir ce qu'en feront les PO.

Cordialement,
Cacophrène

[gasche]

La version rapide ne sert à rien si elle est fausse. En pratique je pense que tu as des collisions; tu peux facilement le vérifier en faisant tourner une fois le programme en ayant mis un "assert "dans la fonction de lookup pour vérifier que ce que tu as trouvé dans la table est bien structurellement égal à la nouvelle génération du tableau haché.

[Cacophrene]

Bonsoir,

La version rapide ne sert à rien si elle est fausse. En pratique je pense que tu as des collisions; tu peux facilement le vérifier en faisant tourner une fois le programme en ayant mis un "assert "dans la fonction de lookup pour vérifier que ce que tu as trouvé dans la table est bien structurellement égal à la nouvelle génération du tableau haché.

Nous sommes d'accord : un programme qui trouve remarquablement vite une solution remarquablement fausse est avant tout remarquablement mal conçu. Comme la raison d'être de l'algorithme Hashlife est de manipuler des univers immenses, la mise en cache des calculs est un passage obligé, de sorte qu'il faut chercher à résoudre le problème des collisions.

Après nos dernières interventions, je pense que c'est maintenant au PO de prendre la main, de décider ou non de suivre nos indications, et de réaliser les tests appropriés. Nous pourrons ensuite l'aider davantage. Cependant, si le sujet est intellectuellement plaisant, il me semble aussi que nous avons momentanément perdu les principaux intéressés...

Cordialement,
Cacophrène

[Uncaught_exception]

Bonsoir, et désolé pour l'absence de réponse, semaine chargée.

À la vue des résultats de Cacophrene il semble que la fonction de hachage soit le travail le plus urgent et les entiers une bonne solution. En manque d'idée, nous avons fouillé le code source de Golly, la référence pour Hashlife. Il semble qu'ils utilisent des entiers, qu'ils codent avec une structure Bigint. La fonction de hachage est la suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static g_uintptr_t nextprime(g_uintptr_t i) {
   g_uintptr_t j ;
   i |= 1 ;
   for (;; i+=2) {
      for (j=3; j*j<=i; j+=2)
         if (i % j == 0)
            break ;
      if (j*j > i)
         return i ;
   }
}
 
#define node_hash(a,b,c,d) (65537*(g_uintptr_t)(d)+257*(g_uintptr_t)(c)+17*(g_uintptr_t)(b)+5*(g_uintptr_t)(a))
#define leaf_hash(a,b,c,d) (65537*(d)+257*(c)+17*(b)+5*(a))

Cependant on a du mal à comprendre comment cela peut marcher. En effet, avec un espace de 1024 cellules de coté, il existe environ 6,73.10^315652 arbre possible pour le Jeu de la Vie, qui est un automate ne comportant que 2 états. Or Caml ne comprend que 2,14.10^9 ou 9,22.10^18 entiers selon l'architecture, ce qui rend quasi certain la présence d'un problème de recouvrement. Et si on utilise la structure Bigint dans l'espoir de couvrir tout les cas, ça commence à prendre pas mal de place, de part la taille et le nombre d'entiers à traiter. Or les développeurs de Golly disent utiliser des espaces de 10^50 cellules de coté. Bref, on reste perplexe.

On continue de creuser le code source, mais notre méconnaissance complète du C++ ne nous permet pas d'aller très vite. Et pour ce qui est de l'article de Gasche, la lecture est en cours !

[gasche]

Il y a toujours des conflits dans les tables de hachage et ça ne pose pas de problème de correction de l'application -- le code de la structure de donnée est prévue pour ça, chaque bucket de la table contient une liste d'éléments ayant le même hash et qui ne sont pas confondus. Ces éléments sont comparés entre eux (et pas seulement leur hash), et c'est cette comparaison qui est longue dans voter programme.

Ce qui posait problème c'est l'utilisation qu'en faisait Cacophrène, qui consiste à stocker seulement un nœud possible pour chaque valeur de hash (dans un tableau), et donc à jeter toutes les autres. Dans ce cas un conflit (qui s'ensuit inévitablement) est un bug.

Je pense qu'il doit y avoir moyen de hacher bien et correctement, mais que c'est un peu subtil -- cf. le travail sur le Hash Consing. En attendant votre code avec arbres et sans hash est plus rapide que votre code avec chaînes et hash, donc c'est déjà ça.

[Uncaught_exception]

Ces éléments sont comparés entre eux (et pas seulement leur hash), et c'est cette comparaison qui est longue dans votre programme.

Mais dans ce cas, si on utilise la structure canonique du quadtree et que chaque nœud contient sa propre clef, ne peut on pas améliorer considérablement la recherche dans la table en faisant une comparaison récursive des arbres possédant une même clef ? On ne compare ainsi que les entiers hachant leurs sous nœuds, et les arbres ne seraient comparés entièrement seulement dans le cas où ils sont égaux.
De plus, il nous a semblé comprendre à la lecture du source de Golly qu'une bonne opération arithmétique pouvait accélérer la découverte d'une différence entre deux arbres. Mais c'est encore un peu flou, on espère éclaircir cela.

[gasche]

Bon en fait c'était trivial :-'

L'interface qu'on veut pour cacher des résultats intermédiaires:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
module type POOL = sig
  type pool
  val create : unit -> pool
  val get : pool -> int -> quadtree -> quadtree option
  val set : pool -> int -> quadtree -> quadtree -> unit
end

(Le paramètre `d` correspond au degré, je l'ai mis pour faire plaisir en fait il ne sert à rien car il n'évite aucune collision, toutes les tables en collision pour une fonction de hachage raisonnable étant de même degré de toute façon.)

La fonction h recodée pour utiliser un module `Pool` qui vérifie cette signature:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
let global_pool = Pool.create ()
 
(* ... *)
and h d arb =
  match Pool.get global_pool d arb with
    | Some result -> result
    | None -> 
      let a = traite arb in
      Pool.set global_pool d arb a;
      a

Différentes implémentations de POOL, à comparer (mais je sais laquelle est la plus rapide):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
(* arbres balancés: accès O(log n) *)
module AMap = Map.Make(struct type t = quadtree let compare = compare end)
 
module Pool : POOL = struct
  type pool = quadtree AMap.t ref
  let create () = ref AMap.empty
  let gebt p _d arb =
    try Some (AMap.find arb !p) with Not_found -> None
  let set p _d arb next =
    p := AMap.add arb next !p
end
 
module Pool : POOL = struct
  type pool = quadtree AMap.t array
  let pool_size = 100_000
  let create () = Array.make pool_size AMap.empty
  let index arb = Hashtbl.hash arb mod pool_size
  let get p _d arb =
    try Some (AMap.find arb p.(index arb)) with Not_found -> None
  let set p _d arb next =
    p.(index arb) <- AMap.add arb next p.(index arb)
end
 
module Pool : POOL = struct
  type pool = quadtree AMap.t array
  let pool_size = 100_000
  let create () = Array.make pool_size AMap.empty
  let index d arb = Hashtbl.hash (d, arb) mod pool_size
  let get p d arb =
    try Some (AMap.find arb p.(index d arb)) with Not_found -> None
  let set p d arb next =
    p.(index d arb) <- AMap.add arb next p.(index d arb)
end
 
module Pool : POOL = struct
  type pool = (quadtree, quadtree) Hashtbl.t
  let create () = Hashtbl.create 100_000
  let get p _d arb =
    try Some (Hashtbl.find p arb) with Not_found -> None
  let set p _d arb next =
    Hashtbl.add p arb next
end
 
module Pool : POOL = struct
  type pool = quadtree AMap.t array
  let pool_size = 100_000
  let create () = Array.make pool_size AMap.empty
  let get p d arb =
    try Some (AMap.find arb p.(d)) with Not_found -> None
  let set p d arb next =
    p.(d) <- AMap.add arb next p.(d)
end

[Uncaught_exception]

Bon en fait c'était trivial :-'

Pas pour nous... Ça nous arrangerait si tu pouvais éditer ton message précédent avec des commentaires descriptifs du code s'il te plaît. Par exemple, qu'est ce que AMap ? Caml ne semble pas le reconnaître nativement. Merci !

Sinon, à propos d'une de tes remarques précédentes :

Il y a toujours des conflits dans les tables de hachage et ça ne pose pas de problème de correction de l'application -- le code de la structure de donnée est prévue pour ça, chaque bucket de la table contient une liste d'éléments ayant le même hash et qui ne sont pas confondus. Ces éléments sont comparés entre eux (et pas seulement leur hash), et c'est cette comparaison qui est longue dans voter programme.

Cependant l'implémentation de la fonction Hashtbl.find est la suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
rec find_rec key = function
    Empty ->
      raise Not_found
  | Cons(k, d, rest) ->
      if compare key k = 0 then d else find_rec key rest
 
let find h key =
  match h.data.((hash key) mod (Array.length h.data)) with
    Empty -> raise Not_found
  | Cons(k1, d1, rest1) ->
      if compare key k1 = 0 then d1 else
      match rest1 with
        Empty -> raise Not_found
      | Cons(k2, d2, rest2) ->
          if compare key k2 = 0 then d2 else
          match rest2 with
            Empty -> raise Not_found
          | Cons(k3, d3, rest3) ->
              if compare key k3 = 0 then d3 else find_rec key rest3

Il semble bien ici que si les clefs sont identiques, il renvoie directement la valeur associer à la clef. Après, on fait peut être une confusion...

[gasche]

Attention, le smiley (:-') est ironique !

AMap est un module de table associative indexée par des quadtree, obtenue par instantiation du foncteur Map.Make de la bibliothèque standard (première ligne "module AMap = .."), implémentée avec des arbres binaires équilibrés. A pour Arbre, mais je reconnais que c'était peu clair.
L'utilisation des foncteurs dans ce cadre est décrite dans ce chapitre du livre DA-OCaml.

Il semble bien ici que si les clefs sont identiques, il renvoie directement la valeur associer à la clef. Après, on fait peut être une confusion...

Oui, OCaml vérifie bien que les *clefs* sont identiques, et non seulement que leur *hash* est identique (condition nécessaire mais pas suffisante). Donc il fait un test d'égalité sur les clés, ici des quadtree, ce qui est long.

La table de hachage implémentée par Hashtbl stocke les ensembles d'éléments ayant le même hash (et qui doivent donc être comparés directement) dans des listes chaînées. C'est le plus efficace quand il y a peu de conflits et que la comparaison des éléments est relativement rapide. Par contre quand il y a beaucoup de conflit et que la comparaison est lente, comme ici, le nombre linéaire de comparaison dans ces listes tue les performances.

Une de mes structures Pool, reprenant l'idée de Cacophrène, utilise le hash de l'arbre pour aller le placer dans un tableau de tables associatives AMap, au lieu d'un tableau de listes -- comme fait Hashtbl. Donc en cas de conflit on compare avec un nombre logarithmique, plutôt que linéaire, d'éléments. Ça va beaucoup plus vite.

[Cacophrene]

Bonsoir,

Une de mes structures Pool, reprenant l'idée de Cacophrène, utilise le hash de l'arbre pour aller le placer dans un tableau de tables associatives AMap, au lieu d'un tableau de listes -- comme fait Hashtbl. Donc en cas de conflit on compare avec un nombre logarithmique, plutôt que linéaire, d'éléments. Ça va beaucoup plus vite.

Bon, c'est pas très bien d'avoir vendu la mèche aussi vite quand même. Cette idée de remplacer un (int, quadtree) Hashtbl.t par un (int, quadtree AMap.t) Hashtbl.t, c'était précisément là où je ne voulais pas aller parce que le PO aurait pu trouver tout seul à partir de l'implémentation OCaml des tables de hachage et de quelques indices judicieusement choisis... Mais tu as bien fait de proposer plusieurs solutions à "comparer". Je note et j'apprécie la valeur pédagogique de cette façon de présenter les choses !

Ne nous arrêtons pas en si bon chemin, on compare avec du hash consing soigneux ?

Cordialement,
Cacophrène

[Uncaught_exception]

Un jeu de piste ? Pourquoi pas. Mais là on commence à s'éloigner sérieusement de nos connaissances ! Et le temps commence à jouer contre nous...

Si je comprends bien, le fait d'utiliser AMap va faire qu'au lieu que tout les arbres possédant un même hash seront classés dans une sorte d'arbre de recherche (parlons avec des mots que l'on connait), ce qui améliorera la vitesse à laquelle on les retrouve ou pas. Question donc, doit-on intervenir dans la méthode de classement ? De plus nous venons de modifier notre type quadtree pour que chaque nœuds contiennent sa valeur de hash, déterminer par la formule trouvé dans Golly valable sur des Bigint :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
type quadtree =
* | Base of int * int * int array array
* | Node of int * int * quadnode
* and quadnode = quadtree array;;
 
let hash qn = match qn with
* * | [|Base (dno, hno, ano); Base (dne, hne, ane); Base (dso, hso, aso); Base (dse, hse, ase)|] -> (hno lsl 12) lor (hne lsl 8) lor (hso lsl 4) lor hse
* * | [|Node (dno, hno, ano); Node (dne, hne, ane); Node (dso, hso, aso); Node (dse, hse, ase)|] -> (hno lsl 16 lor hno) + (hne lsl 8 lor hne) + (hso lsl 4 lor hso) + (hse lsl 2 lor hse)
* * | _ -> failwith "Hash";;

L'utilisation de cette fonction de hash relativement facile à calculer combiner avec les AMap est-elle intéressante ou bien inutile voir nuisible ? Structurellement, comment fonctionne t-elle exactement ? Les arbres codés de cette manière sont-ils des successions de pointeurs ? C'est, si l'on a à peu près compris le source de Golly la manière optimal de programmer Hashlife.

Ne nous arrêtons pas en si bon chemin, on compare avec du hash consing soigneux ?

Pour ce qui est du hash consing, la lecture du document n'est pas vraiment simple. On verra ça une fois le reste implémenter ! C'est la première fois qu'on entend parler de « lambda-termes » et d'« indices de Bruijn », et c'est un peu abrupte comme entrée en matière.*

Et enfin une question qui vous semblera peut être bête mais, que sont les fonctions Some et None ? On a cru comprendre que c'était lié aux options. Mais qu'est ce ?

[gasche]

Un jeu de piste ? Pourquoi pas. Mais là on commence à s'éloigner sérieusement de nos connaissances ! Et le temps commence à jouer contre nous...

Oui enfin les connaissances, tu es là pour les acquérir (si tu ne voulais pas entendre parler de hashing et de perfs, il ne fallait pas choisir ce sujet, ou au moins ne pas te concentrer autant sur les performances), et c'est un peu normal que ce soit à vous de bosser.

Enfin je ne critique pas du tout votre démarche, au contraire je trouve que vous vous en sortez bien sur un sujet qui n'est pas facile, mais c'est normal qu'au final on ne vous donne pas tout cru non plus.

Si je comprends bien, le fait d'utiliser AMap va faire qu'au lieu que tout les arbres possédant un même hash seront classés dans une sorte d'arbre de recherche (parlons avec des mots que l'on connait), ce qui améliorera la vitesse à laquelle on les retrouve ou pas.

C'est exactement ça. Si l'ensemble des arbres ayant le même hash a taille N sur un cas donné, AMap va y trouver un élément de cette classe d'équivalence en temps O(log N) au lieu de O(N) pour le module Hashtbl classique. C'est un facteur qui n'est pas si important d'habitude, mais le devient sur les applications où il y a beaucoup de conflits, ce qui semble être le cas ici (... au vu des perfs de la version classique).

De plus nous venons de modifier notre type quadtree pour que chaque nœuds contiennent sa valeur de hash [...] L'utilisation de cette fonction de hash relativement facile à calculer combiner avec les AMap est-elle intéressante ou bien inutile voir nuisible ?

Pour information j'avais fait cette modification dans le code de base, utilisant toujours Hashtbl, et je n'avais pas observé de différnece : le goulot d'étranglement en temps était bien au sein d'un même "bucket" (la classe d'équivalence des quadtree ayant le même hash) et pas sur le calcul du hash comme je l'avais pensé au départ.

Maintenant peut-être qu'une fois que tu es passé à AMap, le temps de calcul du hash devient à nouveau important et on peut avoir des gains avec cette autre technique de Hash. Impossible de le dire sans essayer, mais j'ai un peu des doutes (surtout si tu mémorises le hash de toute façon).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Structurellement, comment fonctionne t-elle exactement ?

Dans le cas de base il construit un entier correspondant à une représentation en binaire de la carte, et dans les cas évolués il fait des joyeux mélange de bit un peu arbitraires. Ça a l'air d'être une très mauvaise fonction de hachage dans l'absolu (pour une fonction de hash on veut que les entrées soient réparties très uniformément, donc ça ressemble à des générateurs de nombres pseudo-aléatoires) mais ça marche peut-être bien dans ce cas particulier.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Les arbres codés de cette manière sont-ils des successions de pointeurs ? C'est, si l'on a à peu près compris le source de Golly la manière optimal de programmer Hashlife.

Ça c'est une question de représentation mémoire qui n'a rien à voir avec la question des hash. En OCaml tout est stocké avec des pointeurs un peu partout de toute façon. Mais jecrois que vous vous arrêtez sur des détails assez accessoires : est-ce que l'impl. que vous avez est assez rapide pour votre usage, et sinon pourquoi ?

déterminer par la formule trouvé dans Golly valable sur des Bigint

Drapeau rouge ! Si tu utilises le type Bigint de Caml, qui n'est pas du tout fait pour ça, les performances vont se traîner. Il faut utiliser les entiers machines de votre architecture (bref le type "int" de Caml) ou ce sera l'horreur. Je pense que tu n'as rien à gagner à passer de Hashtbl.hash à cette fonction de hash si en même temps tu utilises des représentations des entiers plus lourdes en mémoire.

Et enfin une question qui vous semblera peut être bête mais, que sont les fonctions Some et None ? On a cru comprendre que c'était lié aux options. Mais qu'est ce ?

Le type option est défini ainsi:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
type 'a option =
  | None
  | Some of 'a

[Cacophrene]

Bonsoir,

Pour ajouter mon grain de sel au sujet des performances, avant de vous lancer dans quelque chose de très compliqué, il faut répondre à la question suivante : programmer hashlife, dans quel but ?

Si vous voulez programmer un hashlife propre et efficace sur des arbres de taille moyenne (disons une profondeur maximale de 8 ou 9), alors le code que vous avez obtenu me semble déjà bien abouti. Il y a des choses qui peuvent être améliorées, mais l'essentiel du code est bon. Il me semble que c'est une bonne idée pour un TIPE.

Si vous voulez programmer un hashlife applicable sur des motifs immenses et toujours performant sur des arbres très gros (disons une profondeur au moins égale à 10 ou 12), il va falloir pousser plus loin l'analyse des goulots d'étranglement, mais le code final ne sera probablement pas aussi limpide...

La question du nombre de générations envisagé a aussi son importance. Clairement, Golly est conçu pour faire tourner des motifs de plusieurs milliards de cellules sur plusieurs millions de générations... pour un TIPE, hashlife vous permet d'aborder des notions variées. Si vous montrez que vous maîtrisez la manipulation des arbres, le filtrage, l'évaluation de la complexité de vos fonctions, la récursivité, les tables de hachage et la mise en cache des valeurs, sans oublier une certaine dose d'abstraction du code... c'est plutôt pas mal !

Cordialement,
Cacophrène

[Uncaught_exception]

Bonjour,

Dans le cas de base il construit un entier correspondant à une représentation en binaire de la carte, et dans les cas évolués il fait des joyeux mélange de bit un peu arbitraires. Ça a l'air d'être une très mauvaise fonction de hachage dans l'absolu (pour une fonction de hachage on veut que les entrées soient réparties très uniformément, donc ça ressemble à des générateurs de nombres pseudo-aléatoires) mais ça marche peut-être bien dans ce cas particulier.

Je pense qu'il y a quiproquo. Nous parlions de la structure des Amap, et pas de la fonction de hachage de Caml.

Drapeau rouge ! Si tu utilises le type Bigint de Caml, qui n'est pas du tout fait pour ça, les performances vont se traîner. Il faut utiliser les entiers machines de votre architecture (bref le type "int" de Caml) ou ce sera l'horreur. Je pense que tu n'as rien à gagner à passer de Hashtbl.hash à cette fonction de hachage si en même temps tu utilises des représentations des entiers plus lourdes en mémoire.

Ne pourrait-on pas utiliser une structure du type int vect pour obtenir un équivalent plus léger de Bigint ?

Sinon pour répondre à Cacophrene, effectivement on ne cherche pas à le faire fonctionner sur des espaces immenses. Cependant on aimerait pouvoir le faire tourner sur des arbres de degré 12. Le but originel étant d'essayer de simuler des phénomènes physiques avec des automates, cela nous permettrait d'avoir une densité de cellule suffisante pour avoir des approximations correctes. On va essayer la méthode avec les Amap et voir ce que cela donne. On va commencer par examiner les diverse propositions de Gasche. Mais on ne comprends pas très bien le fonctionnement de Amap, d'où notre question sur la structure des arbres balancés. Quelques questions d'ordre syntaxique et structurelle :

• Pourquoi les modules Pool commence par module pool : POOL = struct et pas simplement module pool = struct ? Car pour nous seule la deuxième syntaxe fonctionne.
• Est-ce que l'emploie de Some et None dans les modules sert à les définir de façon polymorphe, en opposition avec nos Base et Node déjà typées ?
• Pourquoi utiliser des références dans la première proposition (qui, à défaut d'avoir trouvé la plus rapide, nous sert d'exemple) ?
• Un intérêt à utiliser certaine fois _d et d'autres d ?

[Cacophrene]

Bonjour,

Pourquoi les modules Pool commence par module pool : POOL = struct et pas simplement module pool = struct ? Car pour nous seule la deuxième syntaxe fonctionne.

La signature POOL permet de masquer les éléments qui ne doivent pas être visibles à l'extérieur du module Pool.

Est-ce que l'emploie de Some et None dans les modules sert à les définir de façon polymorphe, en opposition avec nos Base et Node déjà typées ?

Je ne suis pas sûr d'avoir bien compris. Le type 'a option fait partie des types de base comme int ou unit.

Pourquoi utiliser des références dans la première proposition (qui, à défaut d'avoir trouvé la plus rapide, nous sert d'exemple) ?

Contrairement aux tableaux et aux tables de hachage, les valeurs de type map ne sont pas modifiables en place. Ça veut dire que si on modifie une valeur de type map, on obtient en retour une nouvelle valeur de type map, et pas unit. Comparez les signatures suivantes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
val Hashtbl.add : ('a, 'b) Hashtbl.t -> 'a -> 'b -> unit
val Array.set : 'a array -> int -> 'a -> unit
val Map.add : Map.key -> 'a -> 'a Map.t -> 'a Map.t

Un intérêt à utiliser certaine fois _d et d'autres d ?

Je suppose que gasche a voulu indiquer par là que dans certains cas le paramètre d est inutile... et pas dans d'autres.

Sinon pour répondre à Cacophrene, effectivement on ne cherche pas à le faire fonctionner sur des espaces immenses. Cependant on aimerait pouvoir le faire tourner sur des arbres de degré 12. Le but originel étant d'essayer de simuler des phénomènes physiques avec des automates, cela nous permettrait d'avoir une densité de cellule suffisante pour avoir des approximations correctes. On va essayer la méthode avec les Amap et voir ce que cela donne. On va commencer par examiner les diverse propositions de Gasche

Oui, voyez d'abord si le code que vous avez entre les mains est assez rapide pour vos besoins. Si ce n'est pas le cas, et seulement si c'est rédhibitoire, vous devrez envisager de regarder d'autres siouxieries...

Cordialement,
Cacophrène

[Uncaught_exception]

Bonjour,

On a essayé de se pencher sur les propositions de Gashe pour le type Pool, et voici nos premières suppositions.

• La première semble créer une liste chainée de AMap, et la fonction find les compare un par un.
• La deuxième crée un tableau dans lequel les AMap sont rangés selon leur valeur de hachage. Cela fait une sorte de près tri, mais la taille du tableau semble petite.
• La troisième fait de même mais intègre le paramètre d.
• La quatrième réutilise la table de hachage et n'utilise pas les AMap. On ne voit pas trop de différence avec la méthode des tables seules. Elle est excessivement lente !
• La dernière est semblable à la première, mais utilise le degré au lieu de la valeur de hachage.

On suppute que la deuxième est la plus rapide ce que les tests semblent confirmer.


De plus, le jury aime les images. Avec les chaines de caractère, il était aisé d'obtenir une sortie jolie. Mais maintenant, cela semble plus ardu. Existe-t-il une méthode rapide pour imprimer un AMap ou va-t-on devoir les parcourir un par un en entier ? On ne cherche pas à faire de l'impression en direct, on crée un BMP par génération et on balance le tout dans PhotoShop.

[Cacophrene]

Bonjour,

Quelques éléments de réponse :

Solution 1 de proposée par gasche

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
module Pool : POOL = struct
  type pool = quadtree AMap.t ref
  let create () = ref AMap.empty
  let gebt p _d arb =
    try Some (AMap.find arb !p) with Not_found -> None
  let set p _d arb next =
    p := AMap.add arb next !p
end

Avez-vous lu mon précédent message au sujet des fonctions Array.set, Hashtbl.add et Map.add ? Ici ce n'est pas une liste chaînée de map mais une seule et unique map stockée dans une référence.

Solution 2 proposée par gasche

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
module Pool : POOL = struct
  type pool = quadtree AMap.t array
  let pool_size = 100_000
  let create () = Array.make pool_size AMap.empty
  let index arb = Hashtbl.hash arb mod pool_size
  let get p _d arb =
    try Some (AMap.find arb p.(index arb)) with Not_found -> None
  let set p _d arb next =
    p.(index arb) <- AMap.add arb next p.(index arb)
end

Là vous avez vu juste. La taille du tableau n'a pas besoin d'être immense mais il faut sans doute la déterminer de façon empirique (ou mieux : en fonction de la taille de l'univers) étant donné que chaque élément est une map. L'ensemble forme donc une forêt de map qui sont des valeurs pour lesquelles la fonction index donne le même résultat.

Solution 3 proposée par gasche

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
module Pool : POOL = struct
  type pool = quadtree AMap.t array
  let pool_size = 100_000
  let create () = Array.make pool_size AMap.empty
  let index d arb = Hashtbl.hash (d, arb) mod pool_size
  let get p d arb =
    try Some (AMap.find arb p.(index d arb)) with Not_found -> None
  let set p d arb next =
    p.(index d arb) <- AMap.add arb next p.(index d arb)
end

Vous avez tout bon également.

Solution 4 proposée par gasche

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
module Pool : POOL = struct
  type pool = (quadtree, quadtree) Hashtbl.t
  let create () = Hashtbl.create 100_000
  let get p _d arb =
    try Some (Hashtbl.find p arb) with Not_found -> None
  let set p _d arb next =
    Hashtbl.add p arb next
end

Justement... c'est la méthode des tables de hachage seules, sans tenir compte du paramètre d. On vous a expliqué les raisons de sa lenteur. Dans l'implémentation des tables de hachage en OCaml, quand plusieurs valeurs x, y, z, etc. donnent la même valeur de hachage, elles sont stockées dans une liste chaînée. Cette méthode est efficace lorsque la comparaison de deux valeurs est une opération rapide. En revanche, dans le cas des quadtree, la comparaison est très coûteuse. On a donc intérêt à les minimiser. C'est pourquoi gasche propose de remplacer une liste chaînée où la recherche s'effectue en O(N) (N la longueur de la liste, soit N comparaisons dans le pire des cas) par une map où la recherche s'effectue en O(log N), ce qui est beaucoup plus rapide... surtout quand les collisions sont nombreuses !

Solution 5 proposée par gasche

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
module Pool : POOL = struct
  type pool = quadtree AMap.t array
  let pool_size = 100_000
  let create () = Array.make pool_size AMap.empty
  let get p d arb =
    try Some (AMap.find arb p.(d)) with Not_found -> None
  let set p d arb next =
    p.(d) <- AMap.add arb next p.(d)
end

Vous avez tout bon.

Le classement a priori de ces cinq propositions s'effectue sur la base de l'évaluation du nombre de comparaisons à effectuer pour retrouver une valeur avec la fonction get, sachant qu'en général la fonction set elle-même est assez rapide :

• La solution 4 est la plus lente à cause du stockage des éléments ayant la même clef de hachage sous forme de liste chaînée.
• Déjà plus rapide, la solution 1 stocke tous les quadtree dans une seule map, ce qui implique un nombre de comparaisons assez élevé. Ce n'est donc pas une forêt mais un arbre unique dans le style d'un grand séquoia d'un parc américain.
• La solution 5 stocke tous les quadtree de même degré d dans une même map. C'est déjà mieux que la solution 1, mais la « forêt » comporte peu d'arbres relativement gros (disons dans le genre d'un paysage de baobabs)
• Les solutions 1 et 2 stockent dans une même map tous les quadtree qui ont la même clef de hachage. La forêt est beaucoup plus étendue et constituée d'arbres de taille plus modeste, ce qui allège les opérations de recherche. Pour reprendre les comparaisons imagées de tout à l'heure, on passe des baobabs à la forêt de conifères, plus dense et de taille modérée.

De plus, le jury aime les images. Avec les chaines de caractère, il était aisé d'obtenir une sortie jolie. Mais maintenant, cela semble plus ardu. Existe-t-il une méthode rapide pour imprimer un AMap ou va-t-on devoir les parcourir un par un en entier ? On ne cherche pas à faire de l'impression en direct, on crée un BMP par génération et on balance le tout dans PhotoShop.

Le pretty printing c'est une autre histoire et il faut bien penser à séparer cette partie du code du reste de votre programme. Une idée comme ça qui est généralement assez adaptée aux structures arborescentes : graphviz. Son principal intérêt : vous avez à disposition un langage assez souple et de syntaxe simple que vous pouvez obtenir automatiquement à partir de vos structures de données. Ensuite, il suffit de lancer l'une des applications de la suite Graphviz pour produire une image. Si ça vous intéresse je peux vous donner plus d'infos.



Cordialement,
Cacophrène

[Uncaught_exception]

Voici donc le code utilisant la deuxième fonction de Gasche. On a augmenté la taille du baquet jusqu'au plus grand entier premier pouvant servir de taille de tableau. Cependant comme dit plus haut, on aimerait pouvoir faire tourner notre programme sur des arbres de degré 12. Or notre code n'est pas encore assez performant pour cela. Il va donc nous falloir de nouvelles "siouxeries" ! (En toute honnêteté, pour l'instant une programmation naïve du Jeu de la Vie est bien plus rapide que notre programme...)
On pourrait utiliser un tableau de tableaux pour diminuer le nombre d'élément à comparer dans chaque AMap. Mais cela augmenterait le nombre d'accès. Une chose qui pourrait être source de ralentissement : les AMAp ne contiennent-ils pas les arbres en entier au lieu de pointeurs amenant à des arbres de degré inférieurs ? Si c'était le cas cela pourrait expliquer en partie les faibles vitesses. Il faudrait pouvoir combiner la structure AMap avec l'idée qu'un arbre n'est qu'un ensemble de pointeurs.

De plus pour voir où notre programme ralentit, on aimerait utiliser gprof. Comment installer et utiliser celui-ci ? Enfin on est en train de se renseigner sur l'utilisation de Graphviz. D'après ce que l'on a vu, c'est pour représenter graphiquement la structure d'un programme. Rien que l'on ne peut pas faire en LaTeX ; sauf si Graphviz est capable interpréter (dans une certaine mesure) un code quelconque, ce qui dans ce cas représenterai un gros gain de temps. Se méprend-t-on ? On va fouiller la librairie de programmes proposée pour voir si l'on peut l'intégrer à notre code.

[Cacophrene]

Bonsoir,

D'après ce que l'on a vu, c'est pour représenter graphiquement la structure d'un programme. Rien que l'on ne peut pas faire en LaTeX ; sauf si Graphviz est capable interpréter (dans une certaine mesure) un code quelconque, ce qui dans ce cas représenterai un gros gain de temps. Se méprend-t-on ? On va fouiller la librairie de programmes proposée pour voir si l'on peut l'intégrer à notre code.

Pas seulement la structure d'un programme (mais il y a un exemple d'automate fini). Les outils de GraphViz permettent de représenter presque toute structure arborescente, même très compliquée, à partir d'un fichier .dot. Les fichiers se présentent généralement sous la forme suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
graph foo{
  node n0, n1;
  n0 -> n1;
  n1 -> n0;
}

On peut y ajouter des informations de mise en forme (couleur, taille, etc.) et des imbrications plus ou moins complexes. On compile avec l'un des logiciels de la suite (neato, twopi, dot, etc.) pour produire une image PNG. Ces logiciels appliquent des algorithmes différents et produisent des arbres dont les dispositions diffèrent aussi. Le choix du programme le plus adapté dépend de la structure de l'arbre à représenter.

Un exemple : l'image du lexique dans cet article a été obtenu avec Graphviz.

Cordialement,
Cacophrène

[Uncaught_exception]

Ok, merci pour ces infos sur GraphViz. Ça pourrait nous être très utile pour l'élaboration du dossier qui accompagne le TIPE.

Mais ça ne rentre pas tout à fait dans le cadre de ce que nous voulions faire à la base, à savoir trouver un moyen efficace d'afficher ce que sort notre programme, pour vérifier que le résultat est correct. Sauf s'il existe un moyen assez simple de convertir nos structures OCaml en .dot pour qu'elles soit lisibles par GraphViz, mais j'en doute. Non, nous pensons vraiment à une fonction à coté ou mieux en parallèle du programme qui affiche l'évolution de l'arbre au cours de son exécution.

De plus, pourriez vous revenir sur une petite présentation de gprof ? Cela pourrai nous permettre d'avoir des données intéressantes tant pour l'optimisation du programme que pour la présentation du TIPE, mais nous n'avons pas vraiment compris son utilisation et son fonctionnement.

Il faut avouer que nous faisons un peu du surplace, à défaut d'avoir de nouvelles idées pour le programme. Avoir découvert que la version naïve et bourine est bien plus rapide ne nous a pas vraiment rassuré...