Discussion :

[topgun1223]

Bonjour à tous,

je cherche à écrire dans un fichier texte des infos récupérées lors de l'execution de ma fonction, mais je ne vois pas du tout comment faire. J'ai regardé du coté du module Sdl vu que je l'utilise également dans ma fonction mais sans succès...
Pour le fichier texte, soit je peux le créer dans ma fonction ce qui serait parfait, soit j'en remplit un créé manuellement.

Merci d'avance de vos réponse!

[kulssaka]

hello !

alors voila un lien bien utile qui m'a beaucoup servi l'annee derniere sur l'ecriture dans un fichier en caml

www.ensiie.fr/~dubois/IAP1/PROJETS/impression_fichiers.pdf

ce pdf t'explique comment on ouvre un fichier, comment on y ecrit et comment on le quitte correctement

[topgun1223]

Waou, j'ai regardé en vitesse ton document, et c'est exactement ce dont j'avais besoin ! Je te remercie kulssaka
J'étudierai ça plus en détail demain.
Encore merci !

[kulssaka]

Euh bah il n'y a pas de quoi ^^

[topgun1223]

Hey,

j'ai une autre petite question, j'arrive à lire et à écrire dans un fichier texte à l'aide de "output_string" et "input_line" mais séparément !
J'aimerais bien pouvoir lire et écrire dans un même fichier texte en même temps. Parce que là, au début de mon code je dois préciser :

Code :

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

1
2
let texte = open_in "monfichier.txt"
(* pour ouvrir mon fichier en lecture *)

Ou

Code :

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

1
2
let texte = open_out "monfichier.txt"
(* pour ouvrir mon fichier en écriture *)

Vous voyez une solution ?
Merci d'avance !

[Cacophrene]

Bonjour !

Peut-être quelque chose comme ceci :

Code :

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

1
2
 
Unix.openfile "foo.txt" Unix.O_RDWR 0o644

À utiliser avec Unix.read, Unix.write et Unix.close.

Cordialement,
Cacophrène

[topgun1223]

Okok, j'ai regardé un peu du coté du module Unix mais je ne vois pas comment faire ce que je veux faire ; je dois écrire dans un fichier mais aussi lire dans ce même fichier pour voir si ce que je vais écrire n'est pas déjà écrit
Or la fonction Unix.read renvoit le nombre de caractère lu si j'ai bien compris, donc comment faire un truc du style "ce que je lis" <> "ce que je vais écrire" ?
Merci!

[Cacophrene]

Re !

Peut-être qu'il faut changer d'approche... est-ce que le fichier est volumineux ? Peut-on d'abord tout lire, puis se servir des données lues pour retirer ce qui figure déjà dans le fichier, et effectuer ensuite les ajouts en une seule fois ? Il y a plein de manières de procéder...

Cordialement,
Cacophrène

[topgun1223]

Hey,

Non mon fichier n'est pas volumineux, avec les informations de trop il fait environ 280 Kio, par contre il y pas mal de lignes à l'intérieur mais elles sont très courtes...
Sinon, pour le moment j'arrive à tout écrire dans mon fichier donc il y pas mal de lignes qui sont en double, maintenant oui bien sûr ce serait une méthode de tout lire et de se servir des données lues pour supprimer ce qu'il faut.
C'est faisable ?
Parce que moi chaque solution que je trouve y inclus une lecture et une écriture en même temps !

[Cacophrene]

Salut !

Il existe des types de données qui permettent de ne pas avoir de doublons. Regarde du côté de Set.

Une piste : charger les lignes dans un set, puis y ajouter tout ce que tu veux écrire en plus dans le fichier. À ce stade, les doublons seront tout simplement écartés. Il n'y a plus ensuite qu'à enregistrer tout le set dans le fichier...

Cordialement,
Cacophrène

[topgun1223]

Hi,

désolé de ma réponse tardive, j'ai eu pas mal de boulot ce week-end.
Sinon j'ai pensé à quelque chose de plus simple pour mon problème : créer un tableau avec pour chaque case de ce tableau trois composantes R,G,B qui représente les infos lues. Et avant d'écrire dans mon fichier texte je parcours mon tableau pour savoir si elle n'existe pas déjà ! Je pense que c'est faisable et que ça peut marcher.
Sauf que je ne vois pas comment créer un tableau à trois composantes par case. Il faut sûrement commencer par "Array.make" mais après

PS : si cette solution ne marche pas, j'irais voir du coté de Set, merci pour ton aide Cacophrène !

[Cacophrene]

Salut !

Sinon j'ai pensé à quelque chose de plus simple pour mon problème : créer un tableau avec pour chaque case de ce tableau trois composantes R,G,B qui représente les infos lues. Et avant d'écrire dans mon fichier texte je parcours mon tableau pour savoir si elle n'existe pas déjà !

Sauf que dans un tableau la recherche d'un élément est en O(n) dans le pire des cas (n désigne la taille du tableau). Avec un ensemble (Set) tu es en O(log n). Ce n'est pas négligeable si tu as beaucoup de lignes. Mais tu peux très bien commencer par un tableau et envisager ensuite de passer à un ensemble si les performances sont mauvaises.

je ne vois pas comment créer un tableau à trois composantes par case

Pour t'aider, il faudrait que tu me donnes quelques précisions supplémentaires sur la nature des données que tu souhaites manipuler (d'après les notations que tu utilises, des triplets d'entiers codant des couleurs ?).

Cordialement,
Cacophrène

[topgun1223]

Justement je pense que cela devrait aller avec un tableau car mon but est d'ananlyser une carte topographique et d'en différencier les couleurs. Donc je ne pense pas dépasser les 4 ou 5 couleurs différentes. C'est juste qu'il y a pas mal de fois la même couleur qui réapparait et donc il faudra parcourir le tableau pas mal de fois, mais s'il n'est pas très grand je pense que ça devrait aller.
Sinon c'est sûr qu'au niveau de la complexité c'est pas terrible

Bref, il faudrait donc que dans chaque case de mon tableau j'ai trois champs et que je puisse y accéder comme ceci :

Code :

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

1
2
3
tab.(i).r
tab.(i).g
tab.(i).b

Il faut sûrement définir un enregistrement mais je ne vois pas trop comment le définir...

Code :

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

type TabRGB = { tab : 'a array; r : int; g : int; b : int}

Mais là, tab et r par exemple ne sont pas "reliés"... C'est à ce niveau là que je bloque.

[Cacophrene]

Salut !

Je pense que cela devrait aller avec un tableau car mon but est d'analyser une carte topographique et d'en différencier les couleurs. Donc je ne pense pas dépasser les 4 ou 5 couleurs différentes. C'est juste qu'il y a pas mal de fois la même couleur qui réapparait et donc il faudra parcourir le tableau pas mal de fois, mais s'il n'est pas très grand je pense que ça devrait aller.

Si j'ai bien compris, tu souhaites stocker des couleurs puis tester leur présence un grand nombre de fois. Dans ce cas, un ensemble à la Set convient mieux qu'un tableau, comme déjà dit. En particulier, les tableaux d'OCaml sont conçus pour avoir une taille fixe, même si on peut les concaténer. À la rigueur une liste conviendrait mieux puisque l'insertion d'une nouvelle couleur est immédiate avec le cons ( :: ). Mais dans tous les cas, les listes et les tableaux ont une moins bonne complexité en temps pour la fonction mem que les Set.

Ceci dit, tu n'as peut-être pas envie d'avoir à définir une relation d'ordre comme l'exige Set (le foncteur a besoin d'une fonction de comparaison). On peut simuler efficacement une sorte de Set sans relation d'ordre avec une table de hachage dont les clefs sont les couleurs; les valeurs valent unit :

Code :

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

1
2
3
4
5
6
7
8
9
module Color =
  struct
    let htbl = Hashtbl.create 7
    let of_rgb r g b = r lsl 16 + g lsl 8 + b
    let add ~red:r ~green:g ~blue:b = Hashtbl.add htbl (of_rgb r g b) ()
    let mem ~red:r ~green:g ~blue:b = Hashtbl.mem htbl (of_rgb r g b)
    let rem ~red:r ~green:g ~blue:b = Hashtbl.remove htbl (of_rgb r g b)
  end

et la signature associée :

Code :

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

1
2
3
4
5
6
7
module Color :
  sig
    val add : red:int -> green:int -> blue:int -> unit
    val mem : red:int -> green:int -> blue:int -> bool
    val rem : red:int -> green:int -> blue:int -> unit
  end

De cette façon tu peux ajouter facilement de nouvelles couleurs et tester efficacement leur existence (modulo la qualité de la fonction de hachage et les collisions que cela entraîne, mais pour 5 valeurs ça ne doit pas poser problème).

Si tu tiens quand même à utiliser un type record, ce que tu as écrit est quasiment la solution :

Code :

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

1
2
3
type color = { red : int; green : int; blue : int }
let array r g b = Array.make 1 { red = r; green = g; blue = b }

Cordialement,
Cacophrène

[topgun1223]

Bon après avoir regardé et testé ton module color utilisant hashtbl, c'est clair que c'est beaucoup plus simple parce qu'avec un tableau j'aurais en plus de créer mon tableau et de rentrer les valeurs, faire une boucle à chaque fois pour vérifier ce qu'il y a dedans. Bref, c'est ce que tu m'expliquais dans ton précédant post

Sinon j'ai regardé un peu du coté du module hashtbl et il n'est pas très dur à comprendre, on utilise une table de hachage en gros. Par contre, j'aimerais bien vérifier les collisions, ce serait plus rigoureux, même si je peux très bien faire une table de 10 éléments en sachant pertinemment qu'ils ne seront jamais atteint. Je ne vois pas comment comment connaitre la place de l'élément dans ma table.

Ah oui, et si tu pouvais me donner une rapide explication sur "lsl" que tu utilises dans ta fonction of_rgb. Ca me fait penser aux puissances de deux et donc à l'ordre de r, g et b mais pas sûr...

Merci encore de ton aide !

[Cacophrene]

Salut !

on utilise une table de hachage en gros

Tout à fait. On la détourne juste un peu de sa fonction première dans la mesure où seules les clefs nous intéressent.

j'aimerais bien vérifier les collisions, ce serait plus rigoureux

Franchement, hormis le fun ou la curiosité, quel intérêt ? Si tu avais des millions d'éléments à stocker, ce serait vraiment une question sensible. Ici j'en doute beaucoup. Ceci dit, si tu veux vraiment avoir un contrôle là-dessus, il faut passer par le foncteur Hashtbl.Make et jouer sur les paramètres de la fonction Hashtbl.hash_param. Je te laisse consulter la documentation si tu veux en savoir plus. Naturellement si tu as des questions à ce propos, n'hésite pas à les poser ici.

une rapide explication sur "lsl" que tu utilises dans ta fonction of_rgb

Je suis parti du principe que tu codais les couleurs sous la forme RRGGBB (8 bits par composante), donc RR lsl 16 est un shift de 16 bits vers la gauche pour la composante rouge (équivalent d'une multiplication par 2^16), et GG lsl 8 un shift de 8 bits vers la gauche pour la composante verte. Ça n'a pas grand intérêt si la fonction of_rgb est appelée de façon modérée.

Cordialement,
Cacophrène

[topgun1223]

Okok, merci pour les détails
Bon vu que ça marche nickel comme ça, je ne vais pas aller titiller inutilement la module Hashtbl ! Je vais juste mettre une valeur avec une certaine marge lors de la création et ça fera l'affaire.
Merci Cacophrène pour ton aide

[adtunum]

Bonjour,

J'aurais quelques remarques a faire.
En general en informatique on conseille d'ecrire un programme
de la maniere la plus simple possible dans un premier temps.
Et ensuite si on constate des problemes de performances alors
on essaie d'optimiser.
A cela plusieurs raisons, d'abord la plupard du temps on se
rend compte qu'il n'y a pas besoin d'optimiser, donc il aurait
ete contre-productif de le faire. Ensuite souvent si on se rend
compte qu'il faut optimiser, on se rend souvent compte que la
partie a optimiser n'etait pas celle qu'on aurait cru au depart.
Et surtout dans tout les cas il est tres important d'essayer de
garder le programme le plus simple possible pour de mutliples
raisons la encore, parmi lesquelles, plus un programme est
simple et moins on risque d'y inclure des bugs, plus un programme
est simple et plus il est facile et rapide a ecrire, plus un
programme est simple et plus il sera facile a relire, a comprendre,
et a modifier.

Pour me rendre compte tres concretement j'ai utilise le script
suivant pour creer un fichier correspondant a la description
de topgun1223 d'environ 280K:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
let () =
  let n = 5 in
  Random.self_init();
  let ar = Array.init n (fun _ -> Random.int 255, Random.int 255, Random.int 255) in
  let oc = open_out "foo.txt" in
  for i = 1 to 28000 do
    let d = Random.int n in
    let r, g, b = ar.(d) in
    Printf.fprintf oc "%d %d %d\n" r g b;
  done;
  close_out oc;
;;

Puis j'ai ecris le script suivant pour lire ces donnees:

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
 
let parse str =
  Scanf.sscanf str "%d %d %d" (fun r g b -> (r,g,b)) ;;
 
let input_line ic =
  try Some(input_line ic)
  with End_of_file -> None
 
let () =
  let ic = open_in "foo.txt" in
 
  let rec read_loop acc =
    match input_line ic with
    | Some color ->
        if List.mem color acc
        then read_loop acc
        else read_loop (color::acc)
    | None ->
        close_in ic;
        (acc)
  in
 
  let colors_list = read_loop [] in
 
  let colors_list = List.map parse colors_list in
 
  List.iter (fun (r,g,b) -> Printf.printf "%d %d %d\n" r g b) colors_list;
;;

Dans notre cas la facon la plus simple de proceder est d'utiliser
une bete liste toute simple, comme on le voit dans la boucle
"read_loop".

En testant ce script on se rend compte que l'operation prend
moins d'un dixieme de seconde (sur un P3).
A partir de la utiliser d'autres solutions plus compliquees
revient un peu a ecraser une mouche avec un bazooka

On a deplus un tres bon exemple d'optimisation faite a priori
et qui se revele non pertinente dans les exemples precedants
avec le module Color. Voici ci-dessous l'equivalent qui utilise
ce module Color, et surprise, le resultat est moins performant !

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
 
module Color =
  struct
    let htbl = Hashtbl.create 7
    let of_rgb (r, g, b) = r lsl 16 + g lsl 8 + b
    let to_rgb d = (d lsr 16, (d lsr 8) land 0xFF, d land 0xFF)
    let add color = Hashtbl.add htbl (of_rgb color) ()
    let mem color = Hashtbl.mem htbl (of_rgb color)
    let results() = Hashtbl.fold (fun color _ acc -> (to_rgb color)::acc) htbl []
  end
 
let parse str =
  Scanf.sscanf str "%d %d %d" (fun r g b -> (r,g,b)) ;;
 
let input_line ic =
  try Some(input_line ic)
  with End_of_file -> None
 
let () =
  let ic = open_in "foo.txt" in
 
  let rec read_loop () =
    match input_line ic with
    | Some line ->
        let color = parse line in
        if not(Color.mem color) then Color.add color;
        read_loop ()
    | None ->
        close_in ic;
        (Color.results())
  in
 
  let colors_list = read_loop () in
 
  List.iter (fun (r,g,b) -> Printf.printf "%d %d %d\n" r g b) colors_list;
;;

Pourquoi ? C'est tres simple, en depis de l'effort louable pour
optimiser le hachage avec la fonction "of_rgb" on a totalement
oublie de regarder ou le script perdait du temps, or la ou il en
perd c'est en parsant chaque ligne pour obtenir 3 ints.

Sinon pour repondre a topgun concernant la verification des collisions
d'une table de hashage, tu ne peux pas vraiement le faire directement,
pour le faire tu dois appliquer la fonction Hashtbl.hash a toutes tes
clefs modulo la taille de la table et verifier si tous les resultats
sont differents ou s'il y a des resultats similaires. (Attention la taille
d'une table de hachage peut varier en cours de route).
Les resultats similaires sont appeles des collisions. Pour les grandes
tables de hachage il y en a toujours un petit peu ce qui n'est pas
vraiement genant, s'il y en a beaucoup il faut changer de fonction de
hachage. Et en fait quand on parle de beaucoup de collision on devrait
peut-etre plutot parler de grandes collisions, car si on a 10 mille
collisions mais qu'a chaque collision il n'y a que 3 ou 4 valeurs
qui collisionnent ce n'est pas bien genant, mais s'il n'y a que 3 ou 4
collisions mais que ces collisions comprennent 10 milles valeurs,
la l'acces a ces valeurs sera penalise, car a cet endrois il y aura
un bucket contenant une liste de 10 milles elements.

C'est aussi pour reduire le risque de collisions qu'on utilise un nombre
premier lorsqu'on invoque Hashtbl.create car la valeur de hachage est
prise modulo la taille de la table (ou plutot la taille du tableau de
buckets). Il est aussi recommande que le nombre qu'on passe a Hashtbl.create
soit legerement superieur au nombre d'elements qu'on prevoit qu'il y aura
dans la table pour eviter le redimentionnement de la table.

Pour l'autre question concernant lsl et of_rgb, lsl est un decalage de bit
qui permet de compacter les trois valeurs de r, g et b dans un seul
entier. Ceci repose sur la supposition (souvent exacte) que tes valeurs
seront entre 0 et 255 inclus, ce qui represente un octet, donc of_rgb
place chaque octet cote a cote dans un seul entier puisque un entier
ocaml est d'au moins 31 bits, or pour stocker 3 octets il faut
3 * 8 = 24 bits donc ca tient. Le but de cette manipulation est
d'avoir un element plus simple a hacher et donc que le hachage soit
plus rapide. Experimentalement je viens de verifier que ca rend
l'operation 2 fois plus rapide. Cependant ca ne permet pas de ratraper
le fait que parser chaque ligne plutot que de les comparer directement
rend le travail beaucoup plus lent que la methode immediate utilise
dans le premier bout de code donne dans ce poste.

[Cacophrene]

Bonjour !

Les choses sont beaucoup plus simples : c'est le contexte d'utilisation qui détermine quel est le meilleur code. Je suggère des solutions variées et c'est au PO de choisir la plus appropriée. Il n'a jamais été question de dire "voilà le bon code à la bonne place". Ce n'est pas l'état d'esprit de mes précédents messages.

Ceci étant, j'ai lu comme toi que topgun1223 ne comptait pas dépasser 4 ou 5 couleurs... seulement d'autres personnes peuvent lire ce fil de discussion en ayant d'autres contraintes, le PO peut faire évoluer son code dans un autre sens après coup, et il est toujours intéressant de découvrir d'autres manières de procéder même si elles ne collent pas forcément avec le détail du moment. Souvent, donc, mes réponses (je crois que je ne suis pas le seul à faire ça ici) sortent un peu du cadre strict de la question posée. Je crois que c'est plus enrichissant, mais ça demande de ne pas faire de copier/coller... il est indispensable de tester son code et de le profiler régulièrement pour choisir la méthode la plus adaptée (balance efficacité/lisibilité dont tu parlais dans ton message).

En testant ce script on se rend compte que l'operation prend moins d'un dixieme de seconde (sur un P3). A partir de la utiliser d'autres solutions plus compliquees revient un peu a ecraser une mouche avec un bazooka

en dépit de l'effort louable pour optimiser le hachage avec la fonction "of_rgb" on a totalement oublie de regarder ou le script perdait du temps, or la ou il en perd c'est en parsant chaque ligne pour obtenir 3 ints.

Ton test est biaisé parce que tu pars du principe qu'il y a 5 couleurs seulement (cf le paragraphe précédent, je suis conscient que c'est ce que voulait topgun1223). Pour n = 5, List.mem est sans conteste plus efficace qu'une table de hachage. En revanche, s'il y a une couleur différente par ligne, que se passe-t-il ? Chez moi, pour 26 000 couleurs (donc peu de doublons dans le fichier foo.txt), ta solution à base de liste demande près de 34 s contre 1.2 s pour la solution à base de table de hachage (dans l'interpréteur). Ce n'est plus du tout la même chose : le parsing limitant pour n = 5 devient largement négligeable devant le temps passé à chercher la couleur dans la liste pour de grandes valeurs de n ! D'ailleurs ce comportement est le reflet des complexités associées : List.mem est en O(n) et Hashtbl.find le plus souvent en O(1).

Regarde la comparaison des données de profilage (natif + gprof) avec les listes :

Code :

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

1
2
3
4
5
6
7
8
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 51.82      7.98     7.98 358124358     0.00     0.00  compare_val
 15.94     10.44     2.46 358124354     0.00     0.00  caml_compare
 10.91     12.12     1.68 716405670     0.00     0.00  caml_string_length
  9.87     13.63     1.52     28000     0.00     0.00  camlList__mem_189

et avec une table de hachage :

Code :

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

1
2
3
4
5
6
7
8
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total   
 time   seconds   seconds    calls  ms/call  ms/call  name    
 18.18      0.02     0.02      397     0.05     0.05  sweep_slice
  9.09      0.03     0.01   314726     0.00     0.00  invert_pointer_at
  9.09      0.04     0.01   299726     0.00     0.00  parse_digit
  9.09      0.05     0.01   162481     0.00     0.00  camlPrintf__incr_ac_215

Avec les tables de hachage, le parsing reste limitant même pour n grand. Avec les listes, il devient largement négligeable. Et d'ailleurs on peut probablement l'optimiser un peu avec Scanf.Scanning.from_file ou des streams (là encore, c'est une suggestion, je n'ai pas testé).

Pour finir, je tiens quand même à dire qu'une table de hachage n'est pas foncièrement plus compliquée qu'une liste dans la mesure où il ne faut pas beaucoup d'effort pour comprendre son fonctionnement quand on connaît le principe d'un tableau. On est quand même loin de la haute voltige, question algorithme...

Cordialement,
Cacophrène

[adtunum]

Ceci étant, j'ai lu comme toi que topgun1223 ne comptait pas dépasser 4 ou 5 couleurs... seulement d'autres personnes peuvent lire ce fil de discussion en ayant d'autres contraintes, le PO peut faire évoluer son code dans un autre sens après coup, et il est toujours intéressant de découvrir d'autres manières de procéder même si elles ne collent pas forcément avec le détail du moment. Souvent, donc, mes réponses (je crois que je ne suis pas le seul à faire ça ici) sortent un peu du cadre strict de la question posée. Je crois que c'est plus enrichissant, mais ça demande de ne pas faire de copier/coller... il est indispensable de tester son code et de le profiler régulièrement pour choisir la méthode la plus adaptée (balance efficacité/lisibilité dont tu parlais dans ton message).

Je suis d'accord, étant dans un contexte d'apprentissage il est intéressant de voir différentes façons de faire, et voir comment on peut optimiser les choses, mais ce que je cherchais à mettre en valeur dans mon poste, c'est qu'il faut partir du point de départ qui est la solution la plus simple, avant de chercher d'autres solutions plus rafinées, lorsque l'on s'adresse à une personne débutante comme c'est le cas.

Ton test est biaisé parce que tu pars du principe qu'il y a 5 couleurs seulement (cf le paragraphe précédent, je suis conscient que c'est ce que voulait topgun1223). Pour n = 5, List.mem est sans conteste plus efficace qu'une table de hachage. En revanche, s'il y a une couleur différente par ligne, que se passe-t-il ? Chez moi, pour 26 000 couleurs (donc peu de doublons dans le fichier foo.txt), ta solution à base de liste demande près de 34 s contre 1.2 s pour la solution à base de table de hachage (dans l'interpréteur). Ce n'est plus du tout la même chose : le parsing limitant pour n = 5 devient largement négligeable devant le temps passé à chercher la couleur dans la liste pour de grandes valeurs de n ! D'ailleurs ce comportement est le reflet des complexités associées : List.mem est en O(n) et Hashtbl.find le plus souvent en O(1).

Regarde la comparaison des données de profilage (natif + gprof) avec les listes :

1) Non le test n'est pas biaisé, il s'agit de l'énoncé du problème.
2) Je n'ai jamais remis en cause le fait qu'une table de hachage soit plus rapide, je voulais juste pointer du doigt le fait qu'on ne commencait pas par le bon bout pour optimiser, car ici l'escenciel du temps perdu n'est pas perdu au niveau de la structure de stockage utilisée, mais au niveau du parsing. Donc en toute logique c'est par là qu'il faudrait commencer.

Avec les tables de hachage, le parsing reste limitant même pour n grand. Avec les listes, il devient largement négligeable. Et d'ailleurs on peut probablement l'optimiser un peu avec Scanf.Scanning.from_file ou des streams (là encore, c'est une suggestion, je n'ai pas testé).

Les chaines contenant un triplet d'entier entre 0 et 255 on une longueur moyenne de 9.7
Pour hacher 100000 de ces chaines, ca prend environ 0.3 sec sur un P3
C'est peu. Même en optimisant le parsing je ne pense pas que l'on puise descendre en dessous. Mais il faudrait tester pour en être sur.

Pour finir, je tiens quand même à dire qu'une table de hachage n'est pas foncièrement plus compliquée qu'une liste dans la mesure où il ne faut pas beaucoup d'effort pour comprendre son fonctionnement quand on connaît le principe d'un tableau. On est quand même loin de la haute voltige, question algorithme...

Oui je suis tout à fait d'accord avec toi, j'avais d'ailleur hésité à poster, cependant ce qui m'avait décidé c'est de voir toutes ces solutions proposées à topgun qui avait l'air d'avoir bien du mal avec ces solutions alors qu'on aurait dut commencer par le point de départ qui est une solution toute simple et facile à appréhender pour un tout jeune débutant.