[Ocaml] lecture d'un fichier texte de

Marsh Posté le 17-05-2007 à 07:21:03

Salut,
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
voici le code

Code :

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.

j'ai essaye de voir comment d'autres ont fait et dans la documentation du module Agrep, la construction est semblable (testagrep.ml).
Jai 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).
par contre bash le fais en 27 sec sur la meme machine
Alors je me demande si je dois persister ou rendre les armes.
merci pour vos reponses et votre lecture :hello:

Message édité par poli le 19-05-2007 à 13:35:10

Reply

Marsh Posté le 17-05-2007 à 07:21:03

Reply

Marsh Posté le 17-05-2007 à 16:57:20

C'est sans doute parce que cherche_string_char est récursive que c'est très lent et que ça plante. Tu fais péter la pile.
D'ailleurs je me demande ce qu'elle fait pour que tu aies besoin de l'écrire en récursif. Réécris-la en non récursif.

Reply

Marsh Posté le 17-05-2007 à 19:24:56

je pouvais faire une fonction non recursive mais je croyais que Ocaml en tant que langage fonctionnel preferait la recursivite a l'imperatif (while,for) mais tu as raison la simple lecture est tres rapide.
je vais la modifier alors, merci de m'aider

Code :

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

Message cité 1 fois
Message édité par poli le 17-05-2007 à 20:01:04

Reply

Marsh Posté le 17-05-2007 à 21:38:11

je l'ai modifiee et c'est tombe a 1 minutes 27

Code :

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
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

Message édité par poli le 17-05-2007 à 21:45:04

Reply

Marsh Posté le 17-05-2007 à 22:23:20

poli a écrit :

je pouvais faire une fonction non recursive mais je croyais que Ocaml en tant que langage fonctionnel preferait la recursivite a l'imperatif (while,for) mais tu as raison la simple lecture est tres rapide.
je vais la modifier alors, merci de m'aider

La recursivite, ca n'est pas miraculeux, il faut avoir une idee de comment ca fonctionne. C'est bien quand on est certains qu'il ne va pas y avoir une profondeur trop grande, cad pas plus de quelques dizaines de niveaux de recursivite. Au-dela, sauf dans le cas particulier ou la fonction est dite "tail-recursive", cas ou la pile ne conserve que le dernier contexte, il faut ecrire sous forme de boucle.
Honnetement, je n'ai pas le courage d'etudier ton code, mais je suis sur qu'il y a moyen de faire bcp mieux que bash. Tu a compile avec le compilateur natif ocamlc ou en bytecode ?
J'ai un doute sur l'utilisation de String.lowercase. Ocaml en deduit que rtab est un String geant. Il faudrait verifier dans la doc qu'il n'y a pas des limitations sur ce type, du style recopie en memoire de toute la chaine.
Si rtab est long, je pense que ce n'est pas la bonne structure de donnees pour ce que tu veux faire.

Perso, j'aurais commence par jeter un coup d'oeil aux flots d'Ocaml pour une telle application.
http://www.pps.jussieu.fr/Livres/o [...] ra040.html
http://caml.inria.fr/pub/docs/manu [...] tream.html

Il y a aussi la possibilite d'une liste chainee de caracteres, mais a priori, les flots me semblent appropries.

Message édité par el muchacho le 17-05-2007 à 23:11:56

Reply

Marsh Posté le 18-05-2007 à 00:28:46

je ne savais meme pas que les flots existaient, mais c'est vraiment interessant car je souhaite le code le plus optimal possible meme si rtab contient au maximum 300 caracteres.
j'ai passe le code en bytes-code avec ocamlrun, je vais essayer d'ameliorer la fonction avec les flots.

Merci

Reply

Marsh Posté le 18-05-2007 à 05:32:01

Code :

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';

la recherche est moins rapide 1min37 et je ne recherchais qu'un seul caractere

Reply

Marsh Posté le 18-05-2007 à 09:49:07

J'ai verifie si Ocaml n'avait pas une faiblesse au niveau des fichiers, mais a priori, ca n'est pas le cas.

Tu as encore plusieurs pistes a suivre:
1. utiliser le moteur de regexp.
Inspire-toi des techniques utilisees dans ce programme:
http://shootout.alioth.debian.org/ [...] ocaml&id=2
a savoir utilisation de regexp_string et Buffer-isation en RAM du fichier.
La description de ce que fait ce programme est donnee en bas de la page http://shootout.alioth.debian.org/ [...] =all#about
En gros il recherche les occurences de patterns d'ADN dans un fichier de 100ko et les remplace par des patterns inverses.
Le programme Ocaml (compile en natif) met 5s pour faire cela, ce qui laisse a penser que tu as une marge de progression encore importante.

2. compiler en natif plutot qu'en bytecode

Message édité par el muchacho le 18-05-2007 à 09:59:23

Reply

Marsh Posté le 18-05-2007 à 16:11:21

Je vais essayer de modifier leur code merci pour tes conseils el muchacho

Reply

Marsh Posté le 19-05-2007 à 18:21:02

je te remercie El muchacho
La compilation native apporte un gain tres impressionnant c'est quasiment 10 fois plus rapide
j'ai fait apel aux moins 15 fois au fichier et le tout prend seulement 1m19
Pour ne pas le consulter trop souvent je l'ai mis dans un tableau c'est 1 bonne idee?

Reply

Marsh Posté le 19-05-2007 à 18:21:02

Reply

Marsh Posté le 20-05-2007 à 00:50:56

tu ne veux pas plutot sortir un profiler ? Parce que bon, mettre en cache le fichier c'est le boulot du noyau. La bibli entre les deux doit faire tampons pour minimiser les appels systèmes. Vu les temps que tu annonces, ton programme est clairement bridé par le CPU, et pas par les E/S. Donc vraiment, sort un profiler et cherche qui crame des cycles.

Reply

Marsh Posté le 21-05-2007 à 06:30:04

voici le profiling en code-octect j'ai essaye en native j'ai bien le fichier gmon.out mais je parviens a le lire avec gprof

Code :

let cherche_string_char rmotif rtab =
(* 2796115 *) let motif = (String.lowercase rmotif) in
let tab = (String.lowercase rtab) in
let p = ref 0 in
let u = ref 0 in
let d = ref 0 in
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 (* 66716289 *)
begin (* 11235 *)
u := 0
end
;
let trouve = motif.[!u] in
let trouve_2 = tab.[i] in
if ( trouve = trouve_2) then
begin (* 234910 *)
p := !p + 1;
if ( !p = fin_2) then
begin (* 11235 *)
d := !d + 1;
p := 0;
u := !u + 1;
end
else
begin (* 223675 *)
u := !u + 1;
end
;
end
else
begin (* 66481379 *)
p := 0;
u := 0;
end
;
done;
!d
in
let cat_grep p a motif motif_2 motif_3 motif_4 motif_5 motif_6 =
let c = ref 0 in (* 1 *)
let cat_grep_corps p a motif motif_2 motif_3 motif_4 motif_5 motif_6 c =
let ic = open_in a in (* 1 *)
try
while true do
let obj=input_line ic in(* 2784896 *)
if ( obj <> "" && p = "-a" ) then
begin (* 2784890 *)
if ( (cherche_string_char motif obj)> 0 && (cherche_string_char motif_2 obj )> 0 && (cherche_string_char motif_3 obj )> 0 &&
(cherche_string_char motif_4 obj )> 0 && (cherche_string_char motif_5 obj )> 0 && (cherche_string_char motif_6 obj )> 0) then
begin (* 0 *)
c := !c + 1;
end;
end
else
begin (* 5 *)
if ( obj <> "" && p = "-o" ) then
begin (* 0 *)
if ( (cherche_string_char motif obj )> 0 || (cherche_string_char motif_2 obj )> 0 || (cherche_string_char motif_3 obj )> 0 ||
(cherche_string_char motif_4 obj )> 0 || (cherche_string_char motif_5 obj )> 0 || (cherche_string_char motif_6 obj)> 0)
then
begin (* 0 *)
c := !c + 1;
end;
end
;
end
;
done;
with _->
close_in_noerr ic; (* 1 *)
in
cat_grep_corps p a motif motif_2 motif_3 motif_4 motif_5 motif_6 c;
!c ;
in
cat_grep "-a" "monfichier" "fichier" "fichier" "fichier" "fichier" "fichier" "probleme";

Message édité par poli le 21-05-2007 à 15:11:27

Reply

Marsh Posté le 21-05-2007 à 09:14:25

c'est illisible comme truc. (ton algo aussi d'ailleurs)

Reply

Marsh Posté le 21-05-2007 à 14:57:53

pourquoi les seuls commentaires proviennent de ocamlprof.il y a 3 fonctions, la premiere evalue la correspondance entre les string au niveau des caracteres, la deuxieme(cat_grep) englobe la troisieme (cat_grep_corps) (c'est pour eviter eviter le warning This fonction should be unit).je vais mieux l'indenter!

Reply

Marsh Posté le 26-05-2007 à 22:42:56

Salut, je n'ai pas lu ce topic depuis longtemps, désolé de ne pas avoir répondu.

Niveau perfs, ça n'est pas suffisant ?
Dans ton profiling, il est clair que le prog passe son temps à faire les tests des lignes 10 et 17. De toute façon, j'ai bien peur que ton algo de recherche de motifs soit loin d'être optimal, alors que les algos classiques type grep de regexp_string sont sans doute performants, quitte à le passer sur des morceaux d'un Mo chacun.

ps: Je trouve que tu abuses des fonctions définies les unes au sein des autres, ça rend ton code excessivement difficile à lire.

Message édité par el muchacho le 26-05-2007 à 22:45:50

Reply

[Ocaml] lecture d'un fichier texte de > 50 Mo (resolu)

Sujets relatifs:

Leave a Replay