Discussion :

[momo_m]

Bonjour,

J'ai crée un algorithme de la recherche d'une chaine dans un fichier .

et pour l'exécuter j'utilise la fonction suivante :

Code caml :

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

1
2
3
 
let naif_algo texte nom_de_fichier =
 naif texte (lecture_fichier nom_de_fichier) 1;;

Tout marche très bien, maintenant je voulais faire le calcul de temps

d'exécution, mon prof m'as dis que le Sys.time ne donne pas une valeur exacte du resultat, il m'a dit de faire exécuter mon programme 100 fois et calculer le temps d'exécution et le diviser par 100.

Je veux savoir juste comment peut on exécuter un programme ocaml 100 fois, on utilise une boucle ou quoi ?

Merci d'avance,

[Cacophrene]

Bonsoir,

Il est en effet préférable d'exécuter plusieurs fois ton programme car la charge supportée par l'ordinateur à un instant donné peut rendre une exécution ponctuelle plus ou moins performante (mais j'imagine, sans en avoir la preuve, que les performances mesurées forment une gaussienne et que les cas de dégradation ou d'amélioration forte des performances sont rares). Tu as en effet juste besoin d'une boucle.

Je te propose ci-dessous une version plus compliquée qui utilise la fonction Unix.gettimeofday (documentation). La fonction à évaluée est ici appelée f et reçoit en entrée un argument x. Une fonction auxiliaire loop qui n'est autre qu'une boucle déguisée (c'est un cas de récursivité terminale, mais peu importe ici) effectue plusieurs fois le même calcul f x.

Code :

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

1
2
3
4
5
6
7
8
9
(* val eval_duration : ?repeats:int -> ('a -> 'b) -> 'a -> 'b * float *)
let eval_duration ?(repeats = 100) f x =
  let t1 = Unix.gettimeofday () in
  let rec loop res i =
    if i = 0 then (
      let t2 = Unix.gettimeofday () in
      (res, t2 -. t1)
    ) else loop (f x) (i - 1)
  in loop (f x) (repeats - 1)

La fonction renvoie le résultat de l'évaluation (il faut s'assurer que le programme donne bien le résultat attendu) ainsi qu'un flottant qui est la durée (en secondes) nécessaires à l'exécution des N répétitions.

Cordialement,
Cacophrène

[momo_m]

Merci beaucoup pour votre réponse,

J'ai encore des questions vu que je suis très doué en Ocaml, ar exemple moi j'ai ma fonction qui s'appelle naif et elle a deux paramètres texte et fichier, est ce que je vais citer dans la fonction si dessus

eval_duration ?(repeats = 100) naif texte fichier

et aussi je pense que Unix est une API alors dois je instancier quelque chose vu que moi je compile mon programme facilement en utilisant #use "nom_fichier.ml";;

Cordialement,

[momo_m]

Je l'ai testé comme je t'ai dis et il m'a envoyé un résultat comme ça :

- : unit * float = ((), 0.0123767852783203125)

mais à chaque exécution il me donne un chiffre différent !!

Merci d'avance,

[Cacophrene]

Bonjour,

je pense que Unix est une API alors dois je instancier quelque chose vu que moi je compile mon programme facilement en utilisant #use "nom_fichier.ml";;

Effectivement, j'ai oublié de préciser qu'il faut soit charger la bibliothèque unix directement dans l'interpréteur (#load "unix.cma"), soit la charger au démarrage (ocaml unix.cma). Pour compiler, ce sera la même chose (ocamlc unix.cma pour du bytecode et ocamlopt unix.cmxa pour du code natif).

ma fonction qui s'appelle naif (...) a deux paramètres texte et fichier

Avec les langages fonctionnels, ce n'est pas un problème, car on peut créer une fonction à N-1 paramètres à partir d'une fonction à N paramètres en effectuant ce que l'on appelle une application partielle. Regarde l'exemple ci-dessous :

Code :

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

1
2
3
let naif_texte = naif texte
let resultat = eval_duration naif_texte fichier

Dans ce code, la fonction naif_texte est une application partielle de ta fonction naif dans laquelle un seul des deux paramètres est donné. La fonction naif_texte est ainsi une fonction à un seul paramètre (en l'occurrence fichier). Tout se passe comme si tu avais fixé la valeur du paramètre texte et créé ainsi une version spécialisée de la fonction naif. Tu peux aussi écrire plus simplement :

Code :

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

let resultat = eval_duration (naif texte) fichier

Maintenant, deux remarques :
Remarque 1 : le nom de paramètre fichier me donne à penser que ta fonction naif lit le contenu d'un fichier. Ce n'est pas très bien d'inclure la lecture d'un fichier dans l'évaluation des performances de ta fonction, parce que cela ne fait pas directement partie de l'algorithme. Serait-il possible de voir le code de la fonction naif ? Il me semble que tu cherches à évaluer le temps de calcul plutôt que le temps d'accès au fichier.
Remarque 2 : le premier terme de la valeur renvoyée par eval_duration est unit dans ton cas. Cela suggère que ta fonction naif ne retourne pas vraiment un résultat mais effectue plutôt des effets de bord : est-ce qu'elle affiche le résultat à l'écran ? dans un fichier ? Là encore, ce serait bien de voir le code pour mieux comprendre ce qui se passe. Le deuxième terme renvoyé est quant à lui toujours différent et c'est normal. Il s'agit du temps d'exécution (en secondes) de naif texte fichier et il n'y a aucune raison que ce soit rigoureusement le même à chaque exécution.

Cordialement,
Cacophrène

[momo_m]

Merci pour votre réponse très claire,

voilà mon code de la fonction naïf, elle fait une recherche d'une chaine de caractère dans un fichier texte :

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
let naif texte lines_list=
match lines_list with 
|[] -> print_string("Done!! ^_^");
print_newline()
|line::t -> 
let n=String.length texte in
let m =String.length line in
for s=0 to m-n do
if texte = (String.sub line s n) then
begin
print_string "occurence à la position n°: ";
print_int (s+1);
print_newline();
end
done;;

Donc pour la fonction eval_duration ne fonctionne pas bien dans mon cas ?
Est il possible de me donner une autre solution ?

Merci d'avance,

Cordialement,

[Cacophrene]

Bonjour,

Il y a beaucoup de choses à dire sur ce code et mon message est assez dense. J'ai essayé de le rendre clair malgré tout. N'hésite pas à demander si tu as d'autres questions. Je voudrais détailler quelques points qui pourront t'aider de façon plus générale dans ta pratique de la programmation (avec OCaml ou d'autres langages).

voilà mon code de la fonction naif, elle fait une recherche d'une chaine de caractère dans un fichier texte

En fait, ta fonction cherche la chaîne de caractères texte dans la liste lines_list (je suppose que c'est la liste des lignes du fichier). Cela signifie que la lecture du fichier a eu lieu en amont, ce qui est plutôt une bonne chose car tu souhaites probablement déterminer le temps d'exécution de la recherche de texte dans lines_list et non le temps de création de la liste lines_list.

Par ailleurs, tu sais sans doute qu'OCaml détermine automatiquement le type des variables et des fonctions à partir du contexte dans lequel elles sont utilisées. C'est un excellent moyen de réfléchir à ce que l'on fait. Regardons ensemble la signature de ta fonction naif :

Code :

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

val naif : string -> string list -> unit

La fonction naif reçoit bien deux paramètres, une chaîne de caractères à chercher (texte, type string) et une liste de lignes (lines_list, type string list). Jusqu'ici, tout va bien. En revanche, ta fonction ne renvoie rien ou, plus exactement, elle renvoie une valeur de type unit (il n'en existe qu'une, c'est ()). Or, on attend plutôt d'une fonction de ce genre qu'elle renvoie la liste des positions où le texte recherché a été trouvé. En regardant le code de la fonction naif, on comprend ce qui se passe : la fonction naif recherche les occurrences de texte dans lines_list et elle affiche directement les résultats sur la sortie standard. C'est aussi pour ça le premier élément des couples renvoyés par eval_duration est toujours une valeur de type unit (en vert dans le code).

Code :

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

- : unit * float = ((), 0.0123767852783203125)

De façon générale, on recommande de séparer le calcul et l'affichage des résultats. Ainsi, tu pourrais essayer de coder les fonctions naif2 et affiche qui dissocient les deux processus (parties importantes en vert) :

Code :

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

1
2
val naif2 : string -> string list -> int list
val affiche : int list -> unit

Concernant les choix d'implémentation, il faut faire attention à String.sub qui est très inefficace. En effet, si on regarde dans le code source du module String (avec tapant quelque chose comme gedit $(ocamlc -where)/string.ml dans un terminal), ou dans la documentation, on se rend compte que String.sub crée une nouvelle chaîne de caractères chaque fois qu'elle est utilisée, de sorte que ton programme va passer un temps considérable à gérer la mémoire. Pour contourner cette difficulté, je t'invite à essayer de te passer de String.sub et de voir ce que tu peux faire en manipulant seulement des entiers qui correspondent aux positions des caractères dans le texte recherché et les lignes du fichier.

Une autre considération à laquelle je t'invite à réfléchir : est-ce que ton programme fonctionne si le texte recherché est "ce\nmot" et que le fichier d'entrée est le suivant ?

Code :

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

1
2
3
 
Voici un texte sur deux lignes ; je me demande si ce
mot sera trouvé par la fonction naïf. Peut-être pas...

Ensuite, concernant la partie algorithmique proprement dite, tu as raison de dire qu'il s'agit d'un algorithme naïf. Je ne sais pas dans quel contexte tu es amené à coder ceci, mais tu peux aussi considérer des algorithmes non naïfs comme, par exemple, l'algorithme de Knuth-Morris-Pratt (KMP) ou encore l'algorithme de Boyer-Moore. Il en existe plusieurs et aucun d'entre eux n'est le meilleur en toute circonstance.

Passe quand même de bonnes fêtes :-)

Cordialement,
Cacophrène

[momo_m]

Bonjour,

Merci pour ta réponse assez claire une autre fois, j'ai bien compris ce que tu voulais dire avec tout ça, et je me suis bien convaincu pour la séparation de l'affichage au calcul, par contre dans ton message t'as que :

ta fonction ne renvoie rien ou, plus exactement, elle renvoie une valeur de type unit (il n'en existe qu'une, c'est ()). Or, on attend plutôt d'une fonction de ce genre qu'elle renvoie la liste des positions où le texte recherché a été trouvé

Mais par contre ma fonction renvoie très bien les résultats attendus, toutes correctes, mais juste elle m'affiche le eval_duration avec les deux parenthèses ().

J'ai essayé d'enlever la liste et ça marche aussi bien mais le même problème au niveau de l'affichage de eval_duration, voilà mon code :

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
 
let naif texte fichier =
let file = lecture_fichier fichier in
let motif = String.concat "" file in
let n=String.length texte in
let m =String.length motif in
for s=0 to m-n do
if texte = (String.sub motif s n) then
begin
print_string " la position n°: ";
print_int (s+1);
print_newline();
end
done;;
 
 
let test_naif texte fichier =
 naif texte fichier;;
 
let eval_duration ?(repeats = 100) test_naif texte fichier =
  let t1 = Unix.gettimeofday () in
  let rec loop res i =
    if i = 0 then (
      let t2 = Unix.gettimeofday () in
      (res, t2 -. t1)
    ) else loop (test_naif texte fichier) (i - 1)
  in loop (test_naif texte fichier) (repeats - 1);;

et pour la méthode naive je suis obligé de la faire.

Merci d'avance,

Bonne fêtes à toi aussi,

Cordialement,

[Cacophrene]

Bonjour,

ma fonction renvoie très bien les résultats attendus, toutes correctes, mais juste elle m'affiche le eval_duration avec les deux parenthèses ().

Non. Tu n'as pas compris ce que je t'explique. Ta fonction ne renvoie pas les résultats, elle les affiche à l'écran. La valeur renvoyée ou retournée par une fonction f appliquée à un paramètre x, c'est le résultat f x. Si la fonction f affiche des données à l'écran, elle effectue des effets de bord. En OCaml, les fonctions comme naif qui n'effectuent que des effets de bord renvoient une valeur de type unit qui se note (). À titre de comparaison, je te donne ci-dessous le code d'une fonction qui cherche toutes les occurrences d'un caractère chr dans une chaîne de caractères str et qui renvoie la liste des positions :

Code :

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

1
2
3
4
5
6
7
let find_char chr str =
  let len = String.length str in
  let rec loop i =
    if i = len then []
    else if str.[i] = chr then i :: loop (i + 1)
    else loop (i + 1)
  in loop 0

Si tu regardes la signature de cette fonction, tu verras qu'elle renvoie bien une liste de valeurs (partie en vert) :

Code :

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

val find_char : char -> string -> int list

Je t'invite à comparer cette signature avec la signature de ta fonction naif. Tu verras que ta fonction renvoie une valeur de type unit et non une liste de positions. Donc, comme je disais, ta fonction ne renvoie pas de résultat. En vert tous les effets de bord :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
let naif texte fichier =
  let file = lecture_fichier fichier in
  let motif = String.concat "" file in
  let n=String.length texte in
  let m =String.length motif in
  for s=0 to m-n do
    if texte = (String.sub motif s n) then
    begin
    print_string " la position n°: ";
    print_int (s+1);
    print_newline();
    end
  done

Nous en sommes donc toujours au point soulevé dans mon précédent message. Ta fonction comporte toujours des String.sub, il n'y a toujours pas de séparation entre la recherche des occurrences et leur affichage à l'écran et, maintenant, la lecture du fichier se trouve dans la fonction naif. De plus, je ne vois pas bien à quoi peut servir une lecture sous forme de liste (lecture_fichier) si c'est pour la transformer ensuite en chaîne de caractères (String.concat).

Bref, maintenant que tu as eu de conseils, à toi de les appliquer à ton code !

Cordialement,
Cacophrène