Discussion :

[konitchua]

Salut,
je suis nouveau sur le forum, je suis etudiant en economie mais je programme a mes heures perdues, j'ai decouvert ocaml grace au site france-ioi qui m'a fournit les bases du langage.
je programme en ocaml parce que c'est un langage qui est repute pour sa simplicite, sa fiabilite et sa rapidite
Mon niveau en programmation est proche du zero et se limite a quelques scripts en bash
j'ai deja parcouru plusieurs sites pour m'affranchir de cette newbietitude mais je ne souheterais pas m'engager dans des solutions trop complexes pour resoudres des problemes simples alors j'ai besoin d'etre aiguiller alors je fais appel a vous pour m'aider.

voici mon probleme
je voudrais creer une fonction qui fasse une recherche dans un fichier texte basique.
Le programme fonctionne parfaitement pour des fichiers de 6000 lignes sans trop de probleme mais quand je le teste sur un fichier de 50 Mo, il met 27 minutes pour totalement lire les donnees.
Je voudrais savoir si le code est "optimal" ou si Ocaml n'aime pas les gros fichiers avec cette methode.
voici le 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
 
let cat_grep p a motif motif_2 motif_3 motif_4 motif_5 motif_6 c =
let ic = open_in a in
try 
while true do
          let obj=input_line ic in
          if ( obj <> "" && p = "-a" ) then
                   begin
                   if ( (cherche_string_char motif obj 1 0 0 0 0)> 0 && (cherche_string_char motif_2 obj 1 0 0 0 0)> 0 && (cherche_string_char motif_3 obj 1 0 0 0 0)> 0 && (cherche_string_char motif_4 obj 1 0 0 0 0)> 0 && (cherche_string_char motif_5 obj 1 0 0 0 0)> 0 && (cherche_string_char motif_6 obj 1 0 0 0 0)> 0) then
                              begin
                                       c := !c + 1; 
                              end;
                  end
          else if ( obj <> "" && p = "-o" ) then
                    begin
                    if ( (cherche_string_char motif obj 1 0 0 0 0)> 0 || (cherche_string_char motif_2 obj 1 0 0 0 0)> 0 || (cherche_string_char motif_3 obj 1 0 0 0 0)> 0 || (cherche_string_char motif_4 obj 1 0 0 0 0)> 0 || (cherche_string_char motif_5 obj 1 0 0 0 0)> 0 || (cherche_string_char motif_6 obj 1 0 0 0 0)> 0) then
                              begin
                                        c := !c + 1;                 
                              end;
                     end
          ;
done
;
with _->
  close_in_noerr ic;
in

voici la logique du code

je passe à la fonction le parametre p (-a ou -o), le repertoire (a) suivi des motifs recherches jusqu'a 6 (motif...) et enfin la reference c.
il ouvre un channel sur le fichier
continue la boucle et ferme le channel a toutes les exceptions rencontrees
dans cette boucle si la ligne tiree du fichier est non-"nulle"(c'est a dire <> '\n') et que et que la presence de tout les motifs est simultanee alors la reference est augmentee d'1 unite
ou si la ligne tiree du fichier est non-"nulle" et que et que la presence d' un des motifs est decelee alors la reference est augmente d'1 unite
la fonction cherche_string_char est recursive elle compare caractere par caractere le texte recherche.

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
54
55
 
let rec cherche_string_char rmotif rtab v k l m u_2=
      let motif = (String.lowercase rmotif) in
      let tab = (String.lowercase rtab) in
      let w = ref v in (*w le nbre de boucle effectue*)
      let p = ref k in (*p indique le nbre de char egaux*)
      let u = ref l in  (*u c char observe de motif*)
      let r = ref m in (*r c char observe de tab*)
      let d = ref u_2 in (*d le nbre de boucle reussie effectuee*)
      let fin = (String.length tab) in
      let fin_2 = (String.length motif) in
      if ( fin_2 = !u) then
          begin
                   u := 0 
          end
      ;
      let trouve =   motif.[!u] in
      let trouve_2 =  tab.[!r] in
      if ( trouve = trouve_2) then
               begin
               p := !p + 1;
               if ( !p = fin_2) then
                         begin 
                         d := !d + 1;
                         p := 0;
                         u := !u + 1;
                         r := !r + 1;
                         w := !w + 1;
                         end
               else
                         begin
                         u := !u + 1;
                         r := !r + 1;
                         w := !w + 1;
                         end
               ;
              end                   
      else
                    begin
                    p := 0;
                    u := 0;
                    r := !r + 1;
                    w := !w + 1;
                    end
      ;
      if ( !r < fin) then
          begin
          cherche_string_char motif tab !w !p !u !r !d;
          end
      else
          begin
                 !d
          end
      ;
in

la logique est la suivante
la fonction recursive prend en parametre le motif recherche, la mot dans lequel on souhaite recherche, v donne le nomvre de boucle effectue, k le nombre de fois le motif a ete trouve, l le nombre de caractere semblable, m le nombre de caratere deja lu du texte ou l'on recherche
on transforme tous en minuscule
les reference w,p,u,r,d s'initialise a vec les valeurs entieres v,k,l,m,u_2
on integre la limite du motif et du texte cible
si la fin du motif est atteinte on continue avec le 1er caractere
on choisit un caratere dans le motif et la cible grace au reference
on effectue une comparaison
on cas de reussite
on incremente la reference qui memorise les reussites au niveau des caracteres
si elle est egale au nbre de terme du motif
alors on incremente
on incremente la reference qui comptabilise les boucles reussie
on reset la comptabilisation des caracteres egaux
on incremente la ref qui fait tourner le motif et celle de la cible
on incremente la ref qui comptabilise les boucles effectuees
sinon
on incremente que u r w
si parcontre un des caracteres du motif n'est pas trouve dans la cible alors on increment que les reference qui comptabilise les boucles effectuees et celle qui choisit les caracteres de la cible
on reset les reference qui note la reussite d'une suite de caracteres trouves et celle qui choisit le caractere du motif a comparer
enfin on verifie que le numero du caractere soit infereieur a la teille de la cible pour empecher un out of bounds si c'est inferieur on recommence les nouvelle valeur.
sinon on lache en pature la valeur le nombre de boucles reussies






je n'ai pas utlise agrep car je connaissais pas encore la methode pour utliser le module
j'ai essaye de voir comment d'autres ont fait et dans la documentation du module Agrep, la construction est semblable (testagrep.ml).
J ai teste la fonction en code interprete et en bytes-code.Je travaille sur un ordinateur que les jeunes de moins de 20 ne peuvent pas connaitre (1ghz,~700mo de ram,dd=100Go,debian;Ocaml 3.09.2).
par contre bash le fais en 27 sec sur la meme machine
il y a quelques sujets qui en parlent et qui m'ont beaucoup aides avant que je m'inscrive (lire un fichier, lexing).
je voudrais savoir si la taille du fichier m'oblige a passer par des buffers (chose que je ne maitrise pas) ou si c'est ma fonction qui est trop lourde.
je parle de buffer car en recherchant sur le web j'ai vu qu'il y avait une histoire de taille des buffers (8192) sur ce lien (http://cristal.inria.fr/~remy/poly/s.../vitesse-copie)
et aussi dans le message sur ocamlex
merci pour vos reponses et le temps passe a me lire

[Strab]

Je ne connais rien à la manipulation de fichiers en Caml, mais je peux deviner deux causes. Soit ta fonction a une complexité beaucoup trop grande (ça veut dire que ton algorithme fait trop de fois la même chose ou fait des choses inutiles), soit c'est effectivement un problème de buffer.

A vue de nez, c'est plutôt un problème avec ta fonction, car vu la quantité de mémoire que tu as (qui n'est pas si faible que tu le dis), tu as largement de quoi charger le fichier entier en mémoire.

Désolé de ne pouvoir t'aider plus, je n'ai vraiment pas à la tête à me plonger dans ton code pour t'en dire plus. Peut-être plus tard

[konitchua]

merci Strab
le probleme vient bien de la fonction de recherche qui est bien trop lourde, je l'ai modifie et la recherche est bien plus rapide.
avant
27min
apres
1min
c'est completement fou
la voici

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
 
let rec cherche_string_char rmotif rtab =
      let motif = (String.lowercase rmotif) in
      let tab = (String.lowercase rtab) in
      let p = ref 0 in (*p indique le nbre de char egaux*)
      let u = ref 0 in  (*u c char observe de motif*)
      let d = ref 0 in (*d le nbre de boucle reussie effectuee*)
      let fin = (String.length tab) in
      let fin_2 = (String.length motif) in
      for i = 0 to (fin - 1) do
           if ( fin_2 = !u) then
                    begin
                        u := 0 
                    end
          ;
          let trouve =   motif.[!u] in
          let trouve_2 =  tab.[i] in
(*           Printf.printf "trouve=%c trouve_2=%c  p=%d u=%d d=%d%c" trouve  trouve_2 !p !u !d '\n'; *)
          if ( trouve = trouve_2) then
               begin
                    p := !p + 1;
                    if ( !p = fin_2) then
                         begin 
                              d := !d + 1;
                              p := 0;
                              u := !u + 1;
                         end
                    else
                         begin
                              u := !u + 1;
                         end
                    ;
              end                   
          else
                    begin
                              p := 0;
                              u := 0;
                    end
          ;
      done;
!d
in

[Jedai]

Une tentative un peu plus fonctionnelle dans le même objectif :

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
54
55
56
57
58
59
60
61
62
63
let same_str string pattern from len =
  let ok = ref true
  and offset = ref 0
  in begin
    while !ok && !offset < len do
      if pattern.[!offset] <> string.[from + !offset]
      then ok := false
      else incr offset
    done;
    !ok;
  end
 
let count_str_in_str string pattern =
  let ifrom = ref 0 
  and pat = String.lowercase pattern
  and str = String.lowercase string
  and lpat = String.length pattern
  and lstr = String.length string
  and count = ref 0
  in try
      ifrom := String.index_from str !ifrom pat.[0];
    while !ifrom <= lstr - lpat do
      if same_str str pat !ifrom lpat
      then incr count;
      incr ifrom;
      ifrom := String.index_from str !ifrom pat.[0];
    done;
    !count;
    with 
      | Not_found -> !count 
 
 
let foldl_on_lines f init filename =
  let file = open_in filename
  and computed = ref init
  in try
      while true do
	computed := f !computed (input_line file);
      done;
    !computed;
    with 
      | End_of_file ->
	  begin
	    close_in_noerr file;
	    !computed;
	  end 
      | Sys_error(ex) -> failwith ("problem with " ^ filename ^ " : " ^ ex)
 
let count_strings_in_file strlist =
  let aux count_until_here line =
    List.fold_left (+) count_until_here 
      (List.rev_map (count_str_in_str line) strlist)
  in foldl_on_lines aux 0
 
let count_lines_with_patterns patlist f =
  let bool_of_int = function | true -> 1 | false -> 0 in
  let positive = (<) 0 in
  let is_in string pattern = positive (count_str_in_str string pattern) in
  let aux count line = match patlist with
    | [] -> count
    | h::t -> count + bool_of_int (List.fold_left f (is_in line h) 
				      (List.rev_map (is_in line) t))
  in foldl_on_lines aux 0

Au passage on gagne un outil intéressant (foldl_on_lines).
Mais OCaml est décidemment complètement inadapté à la manipulation des strings. La même chose en Perl :

Code Perl :

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
#!/usr/bin/env perl
use strict; use warnings;
use List::Util qw(reduce);
 
sub count_lines_with_patterns {
  my ($filename, $mode, @patterns)= @_;
  open my($file), '<', $filename or die "$filename : $!\n";
  return unless @patterns;
  @patterns = map { qr/\Q$_\E/i } @patterns;
  my $count = 0;
  while( my $line = <$file> ) {
    my @results = map { $line =~ m/$_/ } @patterns;
    if( $mode eq 'and' ){
      $count++ if reduce { $a and $b } @results;
    } elsif( $mode eq 'or' ){
      $count++ if reduce { $a or $b } @results;
    } else {
      $count++ if reduce { $mode->($a,$b) } @results;
    }
  }
  return $count;
}

(J'imagine qu'on peut faire mieux pour le OCaml, par exemple raccourcir ou rendre plus fonctionnel la fonction de compte du nombre d'occurence dans une string, mais c'est tout de même spécial que cette fonction n'existe pas en standard dans OCaml, ou au moins un "index_str()". On peut utiliser Str.quote puis Str.search_forward, mais on sort du "core")

--
Jedaï

[Jedai]

Version Haskell :

Code :

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

1
2
3
4
5
6
import Data.List
import Data.Char
 
count_lines patterns f filename = do
	content <- readFile filename
	return $ (foldl (+) 0 (map (\line -> fromEnum (f (map ((flip isInfixOf) (map toLower line)) (map (map toLower) patterns)))) (lines content)))

Version mieux indentée :

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
import Data.List
import Data.Char
 
count_lines patterns f filename =
	readFile filename >>=
	(\content -> 
	return $ 
	(foldl (+) 0 
		(map 
			(\line -> fromEnum 
				(f (map 
					((flip isInfixOf) (map toLower line)) 
					(map (map toLower) patterns))
				)
			) (lines content)
		)
	))

Bienvenue dans le monde merveilleux du tout fonctionnel...
(Pour f, on peut utiliser les fonctions and ou or, elles sont dans le prélude)

--
Jedaï

[konitchua]

c'est vraiment impressionnant !!!!
j'ai l'impression de faire joujou dans le bac a sable loin, loin, loin de la cour des grands
je te remercie pour ton accueil et ton aide

[InOCamlWeTrust]

Les fonctions de recherche de motifs sont déjà implantées dans la librairie standard et non standard. Cherche du côté des expressions rationnelles et du module String (voire Buffer) de la librairie standard.

http://caml.inria.fr/pub/docs/manual...manual037.html
http://caml.inria.fr/pub/docs/manual...manual034.html

La racine du document est ici :

http://caml.inria.fr/pub/docs/manual-ocaml/index.html

Si tu veux optimiser le chargement de ton fichier en mémoire, tu peux :

- soit utiliser des flots, structures de données optimisées par le compilateur et le préprocesseur
- soit faire un Unix.read violent et charger en une seule fois tout ton fichier en mémoire
- soit utiliser les fonctions de Pervasives pour charger aussi le ficheir en une seule fois
- soit utiliser le module Genlex conjointement avec des flots pour parcourir et reconnaître les chaînes de caractères plus facilement

Mais dans tous les cas, fais bien attention à l'algorithme que tu implantes, car dès que l'on joue avec des fichiers, on peut se brûler les ailes !

Regarde aussi dans le manuel pour voir si ce que tu veux faire n'est pas déjà implanté dans la librairie standard.

[Jedai]

Ce n'est pas implémenté dans la librairie standard, ni dans Buffer, ni dans String. Tu dois utiliser Str avec regex_string_case_fold et search_forward, si tu veux faire ça pas tout à fait à la main :

Code :

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

1
2
3
4
5
6
7
8
9
let count_occurence string pattern = 
  let pat = Str.regexp_string_case_fold pattern in
  let rec aux count pos =
    try 
      let newpos = Str.search_forward pat string pos
      in aux (count + 1) (newpos + 1);
    with
      | Not_found -> count
  in aux 0 0

Evidemment, les fold_on_file et tutti quanti ne sont pas implémenté, non plus qu'une fonction renvoyant une liste de lignes à partir d'un fichier par exemple... Franchement la librairie standard d'OCaml est déficiente dans ce domaine, OCaml n'est pas adapté à un traitement "quick_and_dirty" de document texte, pas sans utiliser des librairies supplémentaires. (Ce n'est pas un défaut du langage lui-même, juste de sa librairie standard).

Bon j'admet qu'avec la fonction ci-dessus, on réduit de 30% le code que j'avais commis. Mais pour coder fast_and_dirty, utiliser une librairie qui n'est pas lié à la boucle interactive standard, c'est pas l'idéal (je suppose que si on fait ça souvent, on se compile sa propre boucle). De plus les regexs en OCaml...

--
Jedaï

[InOCamlWeTrust]

String implante certaines fonctions de recherche et je parlais de Buffer au cas où on souhaitait utiliser une structure de données extensible et un peu plus optimisée que la bête chaîne de caractères.

D'un autre côté, ce que je ferais, moi, ce serait d'extraire du fichier un flot grâce à Stream.from_channel, puis le découper en unités lexicales avec Genlex et cherhcer dans ce merdier ce qui m'intéresse, si ce qui m'intéresse est bien un mot et non un motif plus général... on pultrude alors le nombre de lignes de code et la complexité de la chose.

[konitchua]

je vais tenter le violent Unix.read, j'ai essayer avec les streams ce n'etait pas plus rapide avec ce 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
 
let ic = open_in "monfichier" in
let b = Stream.of_channel ic in
let d = ref 0 in
try
while true do
      let a = Stream.next b in
      let rtab = 'a' in
      let d = ref 0 in 
      if ( a = rtab) 
      then
          begin     
                    d := !d + 1;
          end
      ;
done
with _->
  close_in_noerr ic;
Printf.printf "%d%c" !d '\n';

je vais essaye le code avec Str.regexp_case_fold
merci les gars

[Jedai]

String implante certaines fonctions de recherche

Uniquement de caractères malheureusement... Je me suis d'ailleurs servi d'index_from dans ma première version dans l'espoir d'améliorer un peu l'efficacité de l'algorithme naïf employé (je rappelle tout de même qu'il y a des algorithmes spécialisés de recherche de sous-chaîne nettement plus efficaces que pour les regexs, surtout si elles sont implémentées avec un backtracing engine, ce qui est le plus courant aujourd'hui (?)).

D'un autre côté, ce que je ferais, moi, ce serait d'extraire du fichier un flot grâce à Stream.from_channel, puis le découper en unités lexicales avec Genlex et cherhcer dans ce merdier ce qui m'intéresse, si ce qui m'intéresse est bien un mot et non un motif plus général... on pultrude alors le nombre de lignes de code et la complexité de la chose.

Je ne connaissais pas "pultrude", cela veut-il dire "multiplier par vingt au moins" ?
Parce que franchement je ne suis pas convaincu de l'utilité d'optimiser à mort ce programme en OCaml quand on peut écrire un programme équivalent et très efficace en 10 fois moins de lignes et 40 fois moins de temps de réflexion dans un autre langage... Autant faire un appel système dans ce cas, ce n'est pas la légère pénalité de la création de processus qui compensera le gain obtenu ainsi.
J'aime beaucoup la version Haskell pour ma part, d'autant que dans ce cas, la nature paresseuse de l'évaluation en Haskell permet de profiter sans effort d'optimisations longues à mettre en oeuvre en OCaml, par exemple la lecture bufferisée avec readFile, les and et or ne calculant pas forcément pour tous les patterns, etc...

--
Jedaï

[InOCamlWeTrust]

Ouh la... on ne manipule pas les flots comme ça, sauf en de rares cas. Moi, je pensais plutôt à autre chose, beaucoup plus simple à mettre en place... d'ailleurs, ton code ne devrait pas compiler, je crois...

[Jedai]

Après test, sur un fichier de test de 40 Mo, clwp étant la solution avec ma propre fonction de compte d'occurence d'un pattern dans une string et clwp' étant la solution utilisant Str.

Avec ocamlc :
clwp = 20s
clwp' = 5s

Avec ocamlopt :
clwp = 1,9s
clwp' = 1,3s

En conclusion oublie les optimisations, utilise mon code avec ocamlopt et basta ! (Ton propre code devrait lui-même être suffisamment rapide avec ocamlopt à mon avis)

--
Jedaï

[konitchua]

Je pense aussi que si on atteint ces temps avec la compilation ce sera suffisant
Je ne savait qu'il y avait une telle difference entre le code compile et le le code interprete, desole!
En tout cas je vous remercie tous pour votre aide et votre accueil

[gasche]

Voici la version Ocaml de la version Haskell de Jedai :p

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
module A = Array
module L = List
module S = String
 
let model line pattern = try
  let pat_list = A.to_list (A.init (S.length pattern) (S.get pattern)) in
  let lookup = S.index_from line in
  let rec model pos begin_pos locked = function
    [] -> true
  | hd::tl ->
      let new_pos = lookup pos hd in
      if not locked || new_pos = pos + 1 then model new_pos begin_pos true tl
      else model begin_pos (begin_pos + 1) false pat_list
  in
  model 0 1 false pat_list
with Not_found -> false
 
let count_lines patterns disjonctive inchan = 
  let get_line () = try Some (input_line inchan) with End_of_file -> None in
  let rec count_lines nb =
  match get_line () with
    None -> nb
  | Some line ->
      let check = (if disjonctive then L.exists else L.for_all)
	(model line) patterns
      in count_lines (nb + (if check then 1 else 0))
  in count_lines 0

La fonction "model" ne compte pas, il triche avec sa fonction "isInfixOf" :-°

[konitchua]

je te remercie bluestorm, mais tu m'as perdu a hd::tl, je sais que ca concerne les listes mais je ne sais pas ce que ca fait!!

Edit hd::tl -> head et tail du 1er au dernier element de la liste

[InOCamlWeTrust]

On a un élément, que l'on note hd, et une liste notée tl : quand on veut former la liste contenant hd en premier élément et tl en tant que queue de liste (c'est-à-dire ceux qui suivent), on écrit : hd :: tl.