Discussion :

[Cacophrene]

Bonjour,

Cette discussion est ouverte pour recueillir vos avis sur l'article de Edouard Evangelisti Implémentation d'un lexique avec Objective Caml.

Merci de lire : http://www.developpez.net/forums/d65...avis-articles/ avant de poster.

Cordialement,
Cacophrène

[LLB]

Je trouve la remarque suivante bizarre :

les lexiques que nous allons manipuler sont très volumineux : ils comportent entre 300 et 600 000 mots. C'est suffisant pour déclencher une erreur de débordement de pile (Stack_overflow). En effet, la pile d'OCaml est limitée, par défaut, à un peu plus de 260 000 appels.

D'une part, qui s'amuserait à faire autant d'appels récursifs non terminaux que de mots ? Même s'il y en avait 100 000, je ne m'amuserais pas à le faire.
D'autre part, d'où sort cette limite de 260 000 ? A priori, c'est dépendant du système et des valeurs que tu mets sur la pile.

Préciser à quoi correspond flag, au moment de la définition du record (on devine avec la suite, mais ce n'est pas explicite).

En lisant l'article, je m'attendais à voir un benchmark à la fin ou une comparaison avec les autres structures de données (en terme de rapidité de recherche, de temps de construction et d'utilisation mémoire), ne serait-ce que pour justifier l'intérêt de la chose. Juste pour voir si ça vaut le coup par rapport à une table de hachage classique.

J'ai survolé le code et j'ai vu l'utilisation de la fonction input_value. Ca m'a toujours fait peur, ce truc. Le dictionnaire inclus dans l'archive est sous format binaire, j'imagine qu'on peut avoir des problèmes si on n'utilise pas la bonne version de Caml (note en passant, je crois qu'il faut l'ouvrir avec open_in_bin plutôt qu'open_in).

[Cacophrene]

Bonjour !

D'abord merci de t'être penché sur mon article.

D'une part, qui s'amuserait à faire autant d'appels récursifs non terminaux que de mots ? Même s'il y en avait 100 000, je ne m'amuserais pas à le faire.

Cette remarque « bizarre » s'adresse à ceux qui essaieraient d'implémenter un lexique (idem pour un dictionnaire) à l'aide d'une liste triée de mots. La fonction utilisée pour ajouter un mot serait alors :

Code :

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

1
2
3
4
5
6
7
8
9
10
let add word dic =
  let rec loop = function
    | [] -> [str]
    | x :: t as y ->
      match String.compare word x with
      | 0 -> y (* Mot déjà inséré *)
      | 1 -> x :: loop t
      | _ -> word :: y
  in loop dic

Cette fonction conserve l'ordre des mots dans la liste triée et garantit leur unicité. Seul problème, la complexité dans le pire des cas de cette fonction est O(n) où n désigne bien sûr la longueur de la liste, c.-à-d. la taille du lexique. Et comme elle n'est pas récursive terminale... Il s'agit d'une solution naïve mais simple qui séduit régulièrement (pas qu'en OCaml) des débutants non sensibilisés aux problèmes de complexité, de pile, etc., ou tout simplement qui ne savent pas qu'on peut utiliser d'autres structures ou n'ont pas le courage de s'y attaquer. Tu n'en fais bien évidemment pas partie, et je comprends très bien que tu n'essaies pas de le faire.

D'autre part, d'où sort cette limite de 260 000 ? A priori, c'est
dépendant du système et des valeurs que tu mets sur la pile.

La limite dépend effectivement du système et des options définies dans la variable d'environnement OCAMLRUNPARAM. Il me semble cependant que sur la plupart des systèmes (au moins Windows et GNU/Linux), avec une installation standard, un test à la con (vraiment con) comme celui-ci lève l'exception Stack_overflow vers i = 260 000 :

Code :

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

1
2
3
4
5
let rec loop i =
  Printf.printf "%d\n" i;
  loop (i + 1);
  ()

Si ce n'est pas le cas, bien entendu, je modifierai le passage en conséquence.

En lisant l'article, je m'attendais à voir un benchmark à la fin ou une comparaison avec les autres structures de données (en terme de rapidité de recherche, de temps de construction et d'utilisation mémoire), ne serait-ce que pour justifier l'intérêt de la chose. Juste pour voir si ça vaut le coup par rapport à une table de hachage classique.

Inutile de faire un benchmark, même si on pourrait effectivement le faire, car il y a de nombreux avantages par rapport à une table de hachage. Peut-être qu'il aurait été judicieux de faire un tableau pour comparer ces deux types de données. Voici quelques spécificités des lexiques par rapport aux tables de hachage :

• Un lexique (un dictionnaire) est une structure ordonnée. Sur ce point la comparaison est peut-être plus judicieuse avec Map que Hashtbl.
• Une clef ne possède qu'une seule valeur associée (ce n'est pas le cas dans l'implémentation actuelle des tables de hachage d'OCaml, où les clefs précédentes sont seulement masquées et réapparaissent après suppression de la clef visible).
• Il est très facile d'extraire un sous-dictionnaire constitué des mots qui possèdent le préfixe X. Opération en O(len(X)) avec un trie contre O(n) pour la table de hachage.
• Il est très facile de trouver le premier mot de préfixe X (selon des critères à choisir) pour l'auto-complétion (un exemple d'application des dictionnaires).

Préciser à quoi correspond flag, au moment de la définition du record (on devine avec la suite, mais ce n'est pas explicite)

Je vais l'ajouter. J'en parle un peu avec la fonction d'ajout, mais c'est effectivement trop succinct.

J'ai survolé le code et j'ai vu l'utilisation de la fonction input_value. Ca m'a toujours fait peur, ce truc. Le dictionnaire inclus dans l'archive est sous format binaire, j'imagine qu'on peut avoir des problèmes si on n'utilise pas la bonne version de Caml (note en passant, je crois qu'il faut l'ouvrir avec open_in_bin plutôt qu'open_in).

En fait cela dépend du système d'exploitation qui distingue ou non les fichiers texte et les fichiers binaires. C'est le cas de Microsoft Windows (donc open_in_bin ne se comporte pas de la même façon que open_in) mais pas de GNU/Linux (donc open_in_bin se comporte de la même façon que open_in). Il faudrait donc que j'écrive open_in_in pour éviter tout problème... une mauvaise habitude liée à la pratique exclusive d'un OS. Merci pour la remarque.

À propos des problèmes liés au fichier et input_value : je suis bien conscient des problèmes que cela pose. Pour avoir utilisé quelquefois ce logiciel hors de la phase de tests, le chargement est très rapide (< 300 ms environ) et sans difficulté. Avec un fichier texte contenant les 600 000 entrées, c'est vraiment long (4-6 s environ ). Bref, tout n'est que compromis.

Une solution plus robuste serait d'inclure dans l'installation l'exécution d'un script qui recrée le binaire à partir de la version d'OCaml utilisée et de la liste de mots.

En tout cas merci pour ces remarques constructives.
Je vais essayer de modifier l'article dans des délais raisonnables.

Cordialement,
Cacophrène

[LLB]

Je viens de tester (Freebsd) :
Je peux faire 8382000 appels récursifs avec ocamlopt et 65400 avec ocamlc. Mais si, au lieu de passer un int en argument, j'en passe quatre, ça tombe à 4183600 et 32700. J'imagine qu'il y aussi des variations entre machines 32 et 64 bits.

C'est bien d'avoir un ordre de grandeur sur le nombre de récursions que l'on peut faire avec son environnement (sinon, on a des surprises quand on passe à Python/Ruby), mais donner un chiffre précis me semble peu pertinent, voire dangereux.

[Cacophrene]

Salut !

Je peux faire 8382000 appels récursifs avec ocamlopt et 65400 avec ocamlc. Mais si, au lieu de passer un int en argument, j'en passe quatre, ça tombe à 4183600 et 32700. J'imagine qu'il y aussi des variations entre machines 32 et 64 bits.

C'est bien d'avoir un ordre de grandeur sur le nombre de récursions que l'on peut faire avec son environnement (sinon, on a des surprises quand on passe à Python/Ruby), mais donner un chiffre précis me semble peu pertinent, voire dangereux.

J'en prends note, merci bien.

Cordialement,
Cacophrène

[Cacophrene]

Re !

Quelques mises à jour de l'article.

- Débordement de pile : j'ai réécrit le paragraphe sans citer de valeur, et ajouté la fonction d'insertion dans le cas d'une implémentation naïve pour illustrer le problème posé par la complexité temporelle en O(n).
- OCamlBoggle : Le dépôt SVN a été mis à jour. Désormais le chargement du dictionnaire s'effectue avec open_in_bin.
- Edit : le générateur de fichier binaire est prêt. Un fichier de script bash est fourni pour automatiser la construction du fichier binaire et la compilation du logiciel.

Cordialement,
Cacophrène