Envoyé par
Cacophrene
Bref, ton message est à côté de la plaque.
Reprenons donc plus en détail ce que je veux dire par là.
On a deux codes, l'un de bluestorm, l'autre de toi, se reposant sur la même idée. (oui, chronologiquement, c'est dans l'autre sens).
Celui de bluestorm :
1
2
3
4
5
6
| let occurences t =
let occ = Array.make 256 0 in
String.iter (fun c -> let n = Char.code c in occ.(n) <- occ.(n) + 1) t;
occ
let anagramme x y = (occurences x = occurences y) |
Décortiquons le pour voir :
On défini une fonction occurences. La variable n'exprime malheureusement pas son type
let occ = Array.make 256 0 in
qui commence par définir un tableau (en anticipant, on peut même voir que c'est ce tableau qui sera retourné par la fonction)
String.iter (fun c -> let n = Char.code c in occ.(n) <- occ.(n) + 1) t;
String.iter ... t ==> t est une chaine, et on exécute une fonction sur chacun de ses caractères
(fun c -> let n = Char.code c in occ.(n) <- occ.(n) + 1) ==> la fonction récupère le code ascii du caractère et incrémente la case correspondante du tableau
On retourne le tableau
Résumé de la fonction occurences : pour chaque caractères de la chaine, on incrémente la case correspondante du tableau. Donc à la fin, le tableau contient à la case i le nombre d'occurrence du caractère i dans la chaine initiale
Et finalement
let anagramme x y = (occurences x = occurences y)
x et y sont anagramme l'un de l'autre si le nombre d'occurrence de chaque caractère est le même dans les deux chaines
Maintenant, passons au code de Cacophrene
1
2
3
4
5
6
| let apply tbl f chr = f tbl.(int_of_char chr)
let anagramme x y =
let tbl = Array.init 256 (fun _ -> ref 0) in
List.iter2 (fun f -> String.iter (apply tbl f)) [incr; decr] [x; y];
Array.fold_left (fun b r -> b && !r = 0) true tbl |
tentons de le décomposer
let apply tbl f chr = f tbl.(int_of_char chr)
Définition d'une fonction apply, qui prend un tableau, une fonction, et un caractère, et applique la fonction au contenu de la case du tableau correspondant au caractère. Pas de soucis
début de la définition de la fonction anagramme
let tbl = Array.init 256 (fun _ -> ref 0) in
On définit un tableau, qui contient des références initialement à 0. Contrairement à un bête tableau de 0, on doit passer par la fonction init et non make pour s'assurer que chaque référence est "fraîche", c'est à dire différente des autres
List.iter2 (fun f -> String.iter (apply tbl f)) [incr; decr] [x; y];
Décomposons lentement le code :
List.iter2 aux [incr; decr] [x; y] =>
iter2 prend successivement les premier éléments des deux listes, leur applique aux, puis les suivant, leur applique aux, etc. Très pratique quand on a deux listes inconnues. Ici, on a deux listes à deux éléments. Le code est donc équivalent à
1
2
3
| let aux f = String.iter (apply tbl f) in
aux incr x;
aux decr y; |
Pas beaucoup de caractères en plus, et on évite la création de deux listes qui n'ont aucune raison sémantique.
On constate au passage que List.iter2 attend une fonction à 2 arguments et qu'on lui passe une fonction qui a l'air de n'en avoir qu'un. Il y a en fait application partielle. On aurait pu écrire
(fun f str -> String.iter (apply tbl f) str)
qui fait un code plus lisible puisqu'on voit au premier coup d'oeil qu'il y a deux arguments et que le deuxième est une chaine.
Dans la version en trois lignes avec une fonction auxiliaire, incr et x sont cote à cote, ainsi que decr et y, alors que dans l'autre, incr et decr étaient regroupés, ainsi que x et y, obligeant à faire une gymnastique visuelle pour voir lequel est applique à qui.
Reprenons à
let aux f str = String.iter (apply tbl f) str in
aux "applique" donc f à chaque caractère de str, c'est à dire si on se souvient de la définition de apply, que pour chaque caractère, aux applique la fonction f au contenu de la case correspondante dans tbl.
donc, pour chaque caractère de x, on incrémente la référence contenue à la case correspondante de tbl
et pour chaque caractère de y, on *décrémente* la référence.
Array.fold_left (fun b r -> b && !r = 0) true tbl
finalement on fold sur le tableau une fonction qui vérifie que l'accumulateur est toujours à true et que le contenu de la référence contenue dans la case du tableau est bien à 0, le tout en partant avec un accumulateur initial à true. Dit autrement, on vérifie que chaque case du tableau contient bien une référence à 0. Vu l'absence de Array.forall dans la lib standard, on ne peut pas faire beaucoup plus simple.
Donc deux chaines sont anagrammes l'une de l'autre si quand on incrémente les références dans un tableau pour chaque caractère de l'une et qu'on décrémente les même références pour chaque caractère de l'autre, on obtient zéro à la fin. Si on obtient zéro, c'est qu'on a incrémenté autant de fois qu'on a décrémenté, donc que chaque caractère apparait autant de fois dans la première et la deuxième chaine.
Alors pourquoi je trouve que ton code est totalement absurde Cacophrene ?
Déjà, il est plus long que celui de bluestorm... 238 contre 190 caractères, si si..
Ensuite, il est *beaucoup* moins clair, puisqu'il faut décomposer des lignes d'applications partielles, et dérouler le code de List.iter2 sur deux listes de longueur 2.
Il est aussi beaucoup plus crade, puisque tu utilises des tableaux de références alors que les tableaux sont déjà mutables, pour éviter de définir incr_array et decr_array (qui auraient avantageusement remplacés la fonction apply)
Mais tout ça ne serait rien si il y avait un gain...
Et finalement, il est nettement plus lent !
Si on itère 1000 fois sur une chaine de taille 1 000 000, le code de bluestorm prend 11"80, le tiens prend 16"15. Mais là où ça devient drole, c'est que si on itère 1 000 000 de fois sur une chaine de taille 1000, le code de bluestorm passe à 15"30, et le tiens à 36"49 !
Moralité, un code plus long, incompréhensible, et plus lent, le tout en réponse à un débutant ocaml.
Je maintiens donc 
Ou est l'erreur?
Répondre avec citation
De plus j'ai aussi donné au PO des indications en français pour améliorer son code. Bref, ton message est à côté de la plaque.
Partager