Question d'optimisation

TigrouMeow wrote:

Je veux faire un programme qui recherche plusieurs fois des mots (genre un
dictionnaire) dans un fichier texte assez conséquent.

Je dois plutot :
- mettre en mémoire le fichier dans son intégralité, avec un tableau de *
sur des char et ensuite rechercher en mémoire au fur et à mesure des
requêtes
- à chaque requête relire le fichier depuis le début

Nous sommes en C++: tu commences donc par faire une classe
qui encapsule le fichier, et qui ne présuppose pas de
l'implémentation. Ensuite tu peux
1) relire le fichier à chaque fois en espérant que les
méchanismes de cache de ton OS soient suffisant
2) si des problèmes de perf subsistent, tenter de tout
mettre en mémoire, et si tu n'as pas assez de mémoire,
en mettre autant que tu peux, et faire toi même ta
gestion de cache.

De façon algorithmique, si tu peux faire plusieurs
requêtes en un seul passage, c'est toujours mieux.

Marc Boyer
--
Lying for having sex or lying for making war? Trust US presidents :-(

Je dois plutot :
- mettre en mémoire le fichier dans son intégralité, avec un tableau de *
sur des char et ensuite rechercher en mémoire au fur et à mesure des
requêtes
- à chaque requête relire le fichier depuis le début

Si tu veux faire un dictionnaire (genre base de données), tu as interet à
commencer ton fichier par une table genre arbre binaire de recherche qui
indique où rechercher ton mot. Ensuite je pense que le plus efficace serait
de lire uniquement l'arbre, et ensuite l'utiliser pour diminuer la taille de
la recherche dans le fichier.

Evidemment, ca ne marche que si tu peux changer le format de ton fichier
(s'il est imposé c'est un autre probleme)

"TigrouMeow" <TigrouMeow-NOSPAM-@-NOSPAM-OnLine.Fr> a écrit dans le message
de news:3fb9f64a$0$235$636a55ce@news.free.fr...

Je veux faire un programme qui recherche plusieurs fois des mots (genre un
dictionnaire) dans un fichier texte assez conséquent.

Je dois plutot :
- mettre en mémoire le fichier dans son intégralité, avec un tableau de *
sur des char et ensuite rechercher en mémoire au fur et à mesure des
requêtes
- à chaque requête relire le fichier depuis le début

une SD qui peut s'avérer interessante pout ton problème : l'arbre lexial,
qui devrait te faire économiser pas mal de place en mémoire si tu veux y
stocker tout ton dico, et qui propose une recherche de mot en o(log(n))
(avec n nombre de lettres du mot)

.oO LGV Oo. wrote:

Je veux faire un programme qui recherche plusieurs fois des mots (genre un
dictionnaire) dans un fichier texte assez conséquent.

Je dois plutot :
- mettre en mémoire le fichier dans son intégralité, avec un tableau de *
sur des char et ensuite rechercher en mémoire au fur et à mesure des
requêtes
- à chaque requête relire le fichier depuis le début

une SD qui peut s'avérer interessante pout ton problème : l'arbre lexial,
qui devrait te faire économiser pas mal de place en mémoire si tu veux y
stocker tout ton dico, et qui propose une recherche de mot en o(log(n))
(avec n nombre de lettres du mot)

Oui sinon, des bases de données ("vraie" base: postgresql, mysql...;
dans le programme: sqlite; Berkeley Database).
Mais là ça sort du cadre de ce groupe :-)

"Fabien SK" <fabsk+news@free.fr> a écrit dans le message de
news:3fba35fc$0$14106$636a55ce@news.free.fr...

.oO LGV Oo. wrote:

Je veux faire un programme qui recherche plusieurs fois des mots (genre
un

dictionnaire) dans un fichier texte assez conséquent.

Je dois plutot :
- mettre en mémoire le fichier dans son intégralité, avec un tableau de
*

sur des char et ensuite rechercher en mémoire au fur et à mesure des
requêtes
- à chaque requête relire le fichier depuis le début

une SD qui peut s'avérer interessante pout ton problème : l'arbre
lexial,

qui devrait te faire économiser pas mal de place en mémoire si tu veux y
stocker tout ton dico, et qui propose une recherche de mot en o(log(n))
(avec n nombre de lettres du mot)

Oui sinon, des bases de données ("vraie" base: postgresql, mysql...;
dans le programme: sqlite; Berkeley Database).
Mais là ça sort du cadre de ce groupe :-)

en effet, selon la taille du dico, ce serait interessant d'avoir une vraie
base de données à côté ; et ensuite peut-être en charger sélectivement une
partie seulement dans une SD adaptée... à voir, on ne sait pas tres bien les
finalités de la choses...

Marc Boyer wrote:

TigrouMeow wrote:

Je veux faire un programme qui recherche plusieurs fois des mots (genre un
dictionnaire) dans un fichier texte assez conséquent.

Je dois plutot :
- mettre en mémoire le fichier dans son intégralité, avec un tableau de *
sur des char et ensuite rechercher en mémoire au fur et à mesure des
requêtes
- à chaque requête relire le fichier depuis le début

Nous sommes en C++: tu commences donc par faire une classe
qui encapsule le fichier, et qui ne présuppose pas de
l'implémentation. Ensuite tu peux
1) relire le fichier à chaque fois en espérant que les
méchanismes de cache de ton OS soient suffisant
2) si des problèmes de perf subsistent, tenter de tout
mettre en mémoire, et si tu n'as pas assez de mémoire,
en mettre autant que tu peux, et faire toi même ta
gestion de cache.

3) Si le cas d'utilisation le permet, lire une première fois le document
pour générer un index qui contient déjà les résultats des recherches
possibles.

--
Loïc

TigrouMeow <TigrouMeow-NOSPAM-@-nospam-online.fr> wrote:

- mettre en m?moire le fichier dans son int?gralit?, avec un tableau de *
sur des char et ensuite rechercher en m?moire au fur et ? mesure des
requ?tes
- ? chaque requ?te relire le fichier depuis le d?but

Peut-etre tu as besoin de quelque chose comme mmap(). Ce n'est pas du
C++, mais il existe sous la plupart des UNIX et (je crois) sous Windows
aussi.

-Gerhard
--
| voice: +43 (0)662 642934 *** web: http://www.cosy.sbg.ac.at/~gwesp/
|
| If emailing to gwesp@cosy.sbg.ac.at doesn't work, please try gcw@gmx.at!

une SD qui peut s'avérer interessante pout ton problème : l'arbre lexial,
qui devrait te faire économiser pas mal de place en mémoire si tu veux y
stocker tout ton dico, et qui propose une recherche de mot en o(log(n))
(avec n nombre de lettres du mot)

Excuse moi mais c'est quoi une SD ?
Quand à l'arbe lexial, j'ai rien truové là dessus sur google, c'est pas
plutôt lexical ? Enfin il y a rien non plus :(
Je n'ai jamais fait d'arbres en plus alors c'est compliqué pour moi encore..

"TigrouMeow" <TigrouMeow-NOSPAM-@-NOSPAM-OnLine.Fr> a écrit dans le message
de news:3fbb6ec8$0$27573$626a54ce@news.free.fr...

une SD qui peut s'avérer interessante pout ton problème : l'arbre
lexial,

qui devrait te faire économiser pas mal de place en mémoire si tu veux y
stocker tout ton dico, et qui propose une recherche de mot en o(log(n))
(avec n nombre de lettres du mot)

Excuse moi mais c'est quoi une SD ?
Quand à l'arbe lexial, j'ai rien truové là dessus sur google, c'est pas
plutôt lexical ? Enfin il y a rien non plus :(
Je n'ai jamais fait d'arbres en plus alors c'est compliqué pour moi
encore..

oui, en effet, c'est bien ARBRE LEXICAL, et non pas lexial... désolé pour
cette faute de frappe qui t'as surement valu qq recherches infructueuses :(
une SD n'est rien d'autres qu'une Structure de Données

sur le principe, un arbre lexical est relativement simple : c'est un arbre
binaire organisé en frère/fils ; les mots y sont stockés dans l'ordre
lexicographique (exactement comme dans un dictionnaire quoi). Pour que
l'arbre soit fonctionnel, chaque noeud possède donc les élements suivants :

- une lettre (ou chiffre, etc.)
- un lien vers un frère (lettre ou chiffre suivant)
- un lien vers un fils (lettre ou chiffre, qui correspond à la continuation
du mot actuel)
- un flag indiquant si le noeud est terminal (ie la lettre en cours est la
dernière lettre d'un mot reconnu)
- une lien vers une donnée (si c'est utile d'associer une donnée aux mots
reconnus)

un petit diagramme pour expliciter tout ça :

| relation fils
- relation frere
* lettre terminale

root -
|
A --------------------------- C-
| |
R- H-
| |
B- A-
| |
R--------U- U-
| | |
E*- S- D*-
| | |
S*- T- I-
| | |
E* E-
| |
R-
|
E*-
|

en partant de la racine et en explorant les branches de l'arbre, on voit
que les mots reconnus par celui-ci sont :

arbre, arbres, arbuste, chaud, chaudière

on noteraque ceux-ci sont évidemment classés par ordre lexicographique
puisque c'est le but...

voilà, l'idée c'est donc de partir d'un arbre vide, et d'y insérer les mots
de ton dico, la méthode d'insertion devra se charger d'effectuer l'insertion
en respectant l'ordre ; ensuite, une recherche est des plus triviale, on
peut tres facilement se demander par ex. "le mot xxx est-il reconnu ?"
on notera également une grande économie mémoire étant donné que seuls les
mots les plus longs sont en fait stockés, les autres étants préfixes de ces
derniers, il ne sont reconnu par l'arbre que par la présence de lettre dite
terminale.
voilà, en espérant que ça t'éclaire...

une petite implémentation pour terminer : (attention, je déconseille
fortement de la reprendre telle quelle dans la mesure où c'est plus du C que
du C++ , qu'on y manipule des void *, etc. - cette implémentation avait été
réalisée dans un cadre et but bien spécifique de console... bref - le mieux
est donc de bien comprendre le fonctionnement, et de pondre une jolie classe
qui fait ça bien comme il faut :) ) :

#ifndef __ADVANCEDDS_H
#define __ADVANCEDDS_H

typedef struct LEXICALTREE
{
CHAR c;
VOID *ptr;
LEXICALTREE *pBrother;
LEXICALTREE *pSon;
} LEXICALTREE, *LPLEXICALTREE;

/**
* @brief returns a valid pointer to a lexical tree
*/
LEXICALTREE *NewLexicalTree(CHAR, VOID *);

/**
* @brief deletes a lexical tree using a specific function
*/
VOID Delete(LPLEXICALTREE *, VOID (*)(VOID *));

/**
* @brief adds a word linked to data to a lexical tree
*/
VOID AddBinding(LPLEXICALTREE *, CHAR *, VOID *);

/**
* @brief returns data/function linked to a word in a lexical tree
*/
VOID *SearchBinding(LEXICALTREE *, CHAR *);

/**
* @brief returns all words linked to data/function of a lexical tree
*/
vector<CHAR *> ListAll(LEXICALTREE *);

#endif // __ADVANCEDDS_H


--------------------------------------------------------------


#include "velvet.h"

/**
* @param c character to be placed in the tree node
* @param ptr pointer to data/function to be linked to the tree node (NULL
if none)
* @return a pointer to a lexical tree
* @warning data/function should not be mixed in the same lexical tree
*/
LEXICALTREE *NewLexicalTree(CHAR c, VOID *ptr)
{
LEXICALTREE *pLt = reinterpret_cast<LEXICALTREE
*>(malloc(sizeof(LEXICALTREE)));
pLt->c = c;
pLt->ptr = ptr;
pLt->pBrother = NULL;
pLt->pSon = NULL;
return pLt;
}

/**
* @param pLt pointer to the lexical tree to be deleted
* @param pFunc pointer to the function to be called to delete lexical
tree's linked data/function
* @warning the pFunc should match the linked data and properly deletes it
*/
VOID Delete(LPLEXICALTREE *pLt, VOID (*pFunc)(VOID *))
{
if (*pLt)
{
if ((*pLt)->pSon)
Delete(&(*pLt)->pSon, pFunc);

if ((*pLt)->pBrother)
Delete(&(*pLt)->pBrother, pFunc);

if (pFunc)
(*pFunc)(*pLt);

free(*pLt);
*pLt = NULL;
}
}

/**
* @param pLt pointer to the lexical tree to be modified
* @param pointer to characters representing the word to add to the lexical
tree
* @param ptr pointer to data/function to be linked to the word
* @warning this function should not be used to link different data/function
to the same word
*/
VOID AddBinding(LPLEXICALTREE *pLt, CHAR *pName, VOID *ptr)
{
// last letter of the word, and it already exists: only updates data
pointer
if (!*(pName + 1) && *pLt && (*pLt)->c == *pName)
{
(*pLt)->ptr = ptr;
return;
}

// the lexical tree is empty
if (!*pLt)
{
// one letter left: performs linkage to data
if (!*(pName + 1))
*pLt = NewLexicalTree(*pName, ptr);
// more than one letter left: adds next one and recursive call
else
{
*pLt = NewLexicalTree(*pName, NULL);
AddBinding(&(*pLt)->pSon, ++pName, ptr);
}
}
// the lexical tree is not empty
else
{
// the word should be inserted before the current lexical tree to keep it
sorted
if ((*pLt)->c > *pName)
{
LEXICALTREE *pSave = *pLt;
*pLt = NewLexicalTree(*pName, NULL);
AddBinding(pLt, pName, ptr);
(*pLt)->pBrother = pSave;
}
// browse the tree to next insertion point
else
{
// the fisrt letter of the word does not exists: adds a new brother
if ((*pLt)->c != *pName)
AddBinding(&(*pLt)->pBrother, pName, ptr);
// the first letter of the word exists: contiue width son and updated
word
else
AddBinding(&(*pLt)->pSon, ++pName, ptr);
}
}
}

/**
* @param pLt pointer to the lexical tree to search in
* @param pName pointer to characters representing the word to search
* @return data/function linked to the word (NULL if none or word not found)
*/
VOID *SearchBinding(LEXICALTREE *pLt, CHAR *pName)
{
if (!pLt)
return NULL;

// last letter matches (word found): returns the linked data
if (!*(pName + 1) && pLt->c == *pName)
return pLt->ptr;

if (pLt->c == *pName)
return SearchBinding(pLt->pSon, ++pName);
else
return SearchBinding(pLt->pBrother, pName);
}

/**
* @param pLt pointer to the lexical tree to be browsed
* @return a vector containing all words found
*/
vector<CHAR *> ListAll(LEXICALTREE *pLt)
{
vector<CHAR *> words;

// lexical tree is empty: it does not contain any word
if (!pLt)
return words;

// data is linked to current lexical tree: add the letter as a recognized
word
if (pLt->ptr)
{
CHAR *pBuffer = reinterpret_cast<CHAR *>(malloc(2*sizeof(CHAR)));
pBuffer[0] = pLt->c;
pBuffer[1] = 0;
words.push_back(pBuffer);
}

// browse the son
vector<CHAR *> s_words = ListAll(pLt->pSon);
// if found any words, concatain them to current lexical tree's letter
if (s_words.size())
{
vector<CHAR *>::const_iterator end = s_words.end();
for (vector<CHAR *>::const_iterator it = s_words.begin(); it != end; ++it)
{
CHAR *pBuffer = reinterpret_cast<CHAR *>(malloc(256*sizeof(CHAR)));
ZeroMemory(pBuffer, 256*sizeof(CHAR));
pBuffer[0] = pLt->c;
strcat(pBuffer, *it);
free(*it);
words.push_back(pBuffer);
}
}

// browse the brother
vector<CHAR *> b_words = ListAll(pLt->pBrother);
// if found any words, add them to current lexical tree's recognized words
if (b_words.size())
{
vector<CHAR *>::const_iterator end = b_words.end();
for (vector<CHAR *>::const_iterator it = b_words.begin(); it != end; ++it)
words.push_back(*it);
}

return words;
}



le copy/paste passe moyen... un bon coup de formattage dans votre IDE favori
et ce sera mieux :)

"TigrouMeow" <TigrouMeow-NOSPAM-@-NOSPAM-OnLine.Fr> a écrit dans le message
de news:3fb9f64a$0$235$636a55ce@news.free.fr...

Je veux faire un programme qui recherche plusieurs fois des mots (genre un
dictionnaire) dans un fichier texte assez conséquent.

Qu'entends-tu par "assez" ? 1 MO ? 100 MO ? 45 GO ?

Je dois plutot :
- mettre en mémoire le fichier dans son intégralité, avec un tableau de *
sur des char et ensuite rechercher en mémoire au fur et à mesure des
requêtes

Une taille raisonnable actuellement en mémoire vive c'est 128 MO. La moitié
bouffée d'office. Donc reste 64 MO. On en laisse un peu pour le reste, je
dirais qu'avec 40-50 MO, tu peux te permettre de tout stocker en RAM. Au
dessus, il vaut mieux laisser sur disque.
De toutes façons, si tu lis souvent, tu liras en fait en RAM (cache disque
du système), et si c'est en mémoire mais gros, tu liras sur le disque (swap
du système)....

- à chaque requête relire le fichier depuis le début