Discussion :

[pseudocode]

Et pourquoi ne pas utiliser une base de donnée externe. Meme en utilisant un truc simple comme HSQLDB ca te permet de t'affranchir des problèmes de place en mémoire et d'algorithme d'indexation.

[Jedai]

Et pourquoi ne pas utiliser une base de donnée externe. Meme en utilisant un truc simple comme HSQLDB ca te permet de t'affranchir des problèmes de place en mémoire et d'algorithme d'indexation.

Bonne idée. Mais je ne pense pas qu'une solution "purement DB" soit compétitive niveau performances, mieux vaudrait découper l'entrée en morceau de taille raisonnable pour l'algorithme en mémoire vive et réunir les résultats dans la DB après chaque morceau. En fait à partir de là il est aisé d'évoluer vers une solution type MapReduce en parallèle sur plusieurs ordinateurs.

--
Jedaï

[souviron34]

il est aisé d'évoluer vers une solution type MapReduce en parallèle sur plusieurs ordinateurs.

je sais pas pourquoi mais je crois pas que ce soit ça que le PO avait dans la tête

[pseudocode]

mieux vaudrait découper l'entrée en morceau de taille raisonnable pour l'algorithme en mémoire vive et réunir les résultats dans la DB après chaque morceau.

Bien sur, il faut utiliser un cache de 1er niveau pour booster les performances. Si le driver de la BD n'en dispose pas ou qu'il n'est pas efficace, une bonne vieille HashMap java fera l'affaire.

[souviron34]

Pour 10 Mo de texte pur, issue du Projet Gutenberg anglais (donc représentatif d'un langage naturel), cette solution finit en 9s chez moi et prend 125 Mo de mémoire vive.

Quel bouquin, qu'on regarde des choses comparables ?

[Jedai]

Quel bouquin, qu'on regarde des choses comparables ?

10 Mo, en supposant que le mot fasse en moyenne 6 caractères, rajoutant 1 caractère pour l'espace... Ca fait environ 1_500_000 mots. Beaucoup pour un livre unique, non ?

En fait j'ai dû récupérer 22 livres, un total de 1_760_000 mots pour pouvoir faire ce test.

C'est à se demander d'où peuvent bien venir les 300 Mo de texte pur du test de Tidus...

Je te place l'archive sur Rapidshare.

--
Jedaï

[Tidus159]

d'abord il faut être précis dans l'exposé du problème..

Tu démarres par parler d'un fichier de 80 Mo, puis 250, puis 300... Les problématiques ne sont pas forcément les mêmes..

Oui, je me suis trompé, désolé. (300 => approximation quand j'ai écrit... des 250)

Il faut tester progressivement. Ton truc de 30h tu peux arrêter tout de suite.

500 ko, 4 Mo, 10 Mo, 20, 40, 80, 160..

Ce que je n'ai pa fait c'est vrai -> du fichier de 100 Ko je suis passé a celui de 250.

Ensuite, on pourrait (si c'est possible) avoir un exemple de ton fichier (80 déjà ça irait) ?

Je suis en train d'uploader cela, j'édite avec le lien quand c'est fini.

solution en Haskell

C'est quoi ce langage :-) ! C'est plutôt illisible ;p

Bien sur, il faut utiliser un cache de 1er niveau pour booster les performances. Si le driver de la BD n'en dispose pas ou qu'il n'est pas efficace, une bonne vieille HashMap java fera l'affaire.

Tiens, au début j'ai commencé avec un TreeMap (ça n'a pas l'air d'être très loin du hashmap...), je n'ai pas du l'utiliser correctement...

@+,
Tid.

[EDIT]

C'est à se demander d'où peuvent bien venir les 300 Mo de texte pur du test de Tidus...

Notre prof, nous a présenté ce fichier comme étant un corpus "Le monde"... Il l'a ensuite codé (chaque mot devient un nombre) car il n'avait pas le droit d'envoyer la vraie version aux étudiants (d'après lui...)

[EDIT2]
Voyant que je rencontrais des problèmes en suivant petit à petit vos solutions, j'ai envoyé un mail à mon prof (au sujet de la solution tableau de string pour les mots et tableau de trigramme)... Je vous en fais part pour peut être nous aider dans notre recherche...

Si non, en combien de temps environ, estimez vous le temps d'exécution du programme ?
Aussi, si cette proposition d'algo ne peut pas être considéré comme solution, auriez
vous une piste à me donner ?

Le problème semble être, dans cette proposition, le stockage des mots dans un tableau,
mais comment l'éviter ? Il faut bien garder une trace, rien que pour l'écriture dans un
fichier, des trigrammes et de leur nombre d'occurrences dans le texte.
Si il faut bien sûr indéxer les mots (vous faites bien une recherche dichotomique ?)

Pour votre tableau de trigrammes : vous êtes en train de remplir la structure et de
rechercher les trigrammes déjà rencontrés pour mettre à jour l'occurrence.

Les opération importantes sont donc la recherche et l'insertion. Un tableau est-il la
meilleure structure pur cela ?

[EDIT3]

Voici le lien pour les fichiers de test : http://www.megaupload.com/?d=TLF0N0YZ

[souviron34]

C'est quoi ce langage :-) ! C'est plutôt illisible ;p

arrête, tu vas le vexer


tu vois ce que je disais, Jedai ?

[Jedai]

arrête, tu vas le vexer


tu vois ce que je disais, Jedai ?

J'ai eu la même réaction la première fois que j'ai lu du Haskell... et la première fois que j'ai lu du C... et la première fois que j'ai lu du ....

Si tu crois que le C est lisible intuitivement par quelqu'un qui n'y a jamais été exposé.

Haskell est un langage très différent du C ou du Java niveau syntaxe, il est donc naturel qu'un programmeur qui n'a connu que des langages à la syntaxe inspirée du Algol ait du mal.

En plus, j'ai utilisé pas mal de style pointfree (orienté composition de fonctions), qui est un style difficile à utiliser dans la plupart des langages non fonctionnel (et même dans la plupart des langages fonctionnels), il est inévitable que Tidus soit désorienté.

Pour une petite explication du code Haskell :

Code :

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

let trigramsMap = fromListWith' (+) . map (flip (,) 1) . trigrams . map (toAtom . toStrictBS) . BL.words $ input

ça se lit de droite à gauche : je prends l'entrée (input)
, je commence par la découper en mots (BL.words, BL est un raccourci pour le module Data.ByteString.Lazy.Char8 de la liste d'import)
, ensuite je traduis cette liste de mot en une liste d'entiers (un entier correspond à un mot unique du dictionnaire) (map toAtom, map est une fonction d'ordre supérieur : elle prend une fonction (toAtom) en paramètre et l'applique à chaque élément de la liste qu'on lui passe)
, puis je passe d'une liste d'entier à une liste de trigrammes (trigrams)
, je transforme chaque trigramme en une paire dont le premier élément est le trigramme et le second élément est 1 (map (flip (,) 1))
et je transforme cette liste associative en une Map de (trigrammes => entier), quand une clé est rencontrée une seconde fois, les valeurs correspondantes sont additionées (fromListWith' (+)).

Le (.) est l'opérateur de composition de fonctions commun en mathématique, le ($) est juste l'application de fonction mais avec des priorités telles que "f . g . h bla $ truc machin" est équivalent à "(f . g . (h bla)) (truc machin)", ce qui est pratique pour éviter des profusions de parenthèses comme en Lisp.

Est-ce un peu plus clair ?

--
Jedaï

[Jedai]

J'ai donc effectué le test sur notre fichier de 260Mo, ma solution a mis 376s (6min 16s) et a pris 1773 Mo en mémoire vive (j'ai 2Go de RAM). J'en conclus donc que ma solution est viable, surtout si je prend la peine de personnaliser un peu la Map pour utiliser une structure moins gourmande. Néanmoins on atteint les limites du raisonnable, découper les fichiers en portions de 50 Mo et utiliser une BDD est sûrement plus approprié.

(NB: Ma solution m'a pris dans les 10min à écrire... Si c'était un assignement, je prendrais sans doute la peine de personnaliser un peu la structure de donnée et d'écrire une déclinaison en parallèle type MapReduce, il y a des framework simple pour faire ça en Haskell)

--
Jedaï

[Tidus159]

(Re)bonjour,

pour ta solution en Haskell, t'as réussi quelque chose de fort...j'espère un temps comme ça à la fin.

Je vais relire plusieurs fois ton explication, mais c'est vraiment dur :p !

Sinon pour en revenir à ma solution, j'ai modifié une petite chose : plutôt que de stocker les trigrammes d'index dans un tableau, je les stocke dans un arbre trié par index avec comme valeur le nombre d'occurrence.

Je suis en train de tester ton fichier de 10 Mo pour voir déjà le temps que ça prend (c'est vrai que multiplier les tests en augmentant c'est quand même plus intelligent que de passer directement de 100 Ko à 250Mo...)
J'éditerai pour donner le résultat, on pourra évaluer si ça passe pour le fichier de 250 Mo.

J'ai juste une question : pourquoi mon prof me fait il une remarque sur une recherche dichotomique dans le tableau de mots ?
En suivant vos conseils, l'intérêt était de stocker les index, mais si je trie le tableau tous mes index vont être modifié au fur et a mesure, c'est gênant !

Mais apriori le vrai soucis c'est l'insertion des mots dans le tableau et la recherche...
Tiens au fait, j'ai utilisé un arrayList pour ce stockage.

Y'a-t-il un moyen d'amélioration de ce coté ?
Car avec l'arbre trié du coté trigramme, ça semble être optimal.

@+,
Tid.

[EDIT]
Résultat : 10 mins pour afficher tous les trigrammes dans ce style (dans un fichier) ->
0 | 1 | 2 =54, 0 | 1 | 18150 =2, 0 | 8 | 203 =1, 0 | 8 | 283 =2, 0 | 8 | 5986 =1, 0 | 16 | 30 =1, 0 | 19 | 4 =2, 0 | 24 | 4 =3
pour le fichier de 10 Mo...
ça va faire beaucoup sur le fichier de 250 Mo !

[Jedai]

En suivant vos conseils, l'intérêt était de stocker les index, mais si je trie le tableau tous mes index vont être modifié au fur et a mesure, c'est gênant !

En fait ce qu'on veut c'est une fonction qui transforme un mot en entier de façon réversible. Attention je parle ici de fonction au sens mathématique, c'est-à-dire qui étant donné une même entrée renvoie toujours la même sortie. Autrement dit tu veux une bijection entre ton ensemble de mots dans le fichier et l'ensemble des entiers (de 32 bits). C'est exactement la sémantique toAtom et fromAtom de StringTable.Atom.

Ce genre de bijection n'existe pas en général (l'ensemble des mots possible étant infini) mais elle peut être construite dans un cas particulier où l'ensemble des mots est suffisamment petit. C'est ce que fait StringTable.Atom en sous main avec une table de hachage. Il y a probablement des solutions toute faite en Java également.

--
Jedaï

[souviron34]

mais sur quelle machine tournes-tu ? il faudrait comparer des choses comparable, quand on parle de temps..

Pour la mémoire, OK. Mais pour le temps ?

[Jedai]

Je tourne sur un portable avec 2Go de RAM DDR2 et un Centrino T8100 (2.1GHz, 2 Core bien que mon programme n'en utilise qu'un).

Néanmoins il faut noter une grande différence entre mon test et celui de Tidus : je n'écris pas l'ensemble des trigrammes dans un fichier, ceci est susceptible d'être couteux (pas au point d'expliquer la différence entre 9s et 10min toutefois... 2 ordres de grandeur de différence), je ne fais qu'afficher les 10 trigrammes les plus fréquents (avec leur nombre d'occurences).

--
Jedaï

[Tidus159]

Je travaille sur windows ([EDIT] vista), avec eclipse.

J'ai un portable avec un T8100, et 3 Go de ram.

Mais eclipse est bridé a 1 Go et le programme aussi.

[Jedai]

Je travaille sur windows, avec eclipse.

J'ai un portable avec un T8100, et 3 Go de ram.

Mais eclipse est bridé a 1 Go et le programme aussi.

Ca peut sans doute se configurer, non ?

(Par ailleurs je suis sous Linux/Gnome/XMonad, c'est probablement plus léger que ton Windows (Vista non ?) comme environnement).

--
Jedaï

[pseudocode]

En reprennant mon idée du post #12:

- 192 secondes pour splitter les trigrammes dans 256 fichiers selon leur hashcode
- 158 secondes pour compter les occurences dans chaque fichier (via une hashmap) et creer le gros fichier trigramme+occurence (non trié).

donc 350 secondes pour faire le tout en Java sur mon PC (P4 3.0Ghz / 1Go Ram).

[Tidus159]

pseudocode
ton résultat a été obtenu sur quel fichier ? celui de Jedai ? Ou le mien ?

[pseudocode]

pseudocode
ton résultat a été obtenu sur quel fichier ? celui de Jedai ? Ou le mien ?

celui qui s'appelle "le_monde_identifiants" avec un mot (enfin un nombre) par ligne.

[Tidus159]

Bonsoir,

arf c'est reparti, bien que sur le fichier de 10 Mo de Jedai, mon programme a mis 10 mins, j'ai tenté de lancer le_monde_identifiants, fichier de 250 Mo.
Lancé a 20h30, il a levé une exception "Exception in thread "main" java.lang.OutOfMemoryError: Java heap space" à 00h30...

Je n'ai pas trouvé la structure en java pour stocker tous les mots pour remplacer mon tableau... (j'ai donc créé un topic sur le forum java : http://www.developpez.net/forums/d72...e/#post4196190) mais j'ai peur que ça ne fonctionne toujours pas après...

Ca peut sans doute se configurer, non ?

(Par ailleurs je suis sous Linux/Gnome/XMonad, c'est probablement plus léger que ton Windows (Vista non ?) comme environnement).

Et bien je l'ai configuré, si je lui mets plus de 1200 Mo, eclipse met un message d'erreur, donc je vais le mettre a 1190...

- 192 secondes pour splitter les trigrammes dans 256 fichiers selon leur hashcode

je n'ai pas compris pourquoi tu splittais les trigrammes en 256 fichiers ? Et ce que tu appelles un hashcode ? (après une recherche, cela semble être un identifiant d'un objet ?)

Tiens tu as codé en java, tu sais peut être quel est l'objet qui pourrait remplacer mon tableau pour stocker les mots ? (ce que tu ne fais pas je crois...)
Sinon je vais me rediriger vers ta solution... le stockage d'index de souviron et bretus semblait tellement bien vu !

@+,
Tid.