Newsgroup: it.comp.lang.c++
Titolo: Gestione wordlist

Salve a tutti.
Vorrei scrivere un'applicazione che gestisce una lunga lista di parole per
poi servirmene per diversi scopi linguistici (anagrammi e altro). La lista
di cui dispongo è di circa 3 MB e le parole sono ordinate alfabeticamente,
tipo:
a
abaco
...
zuzzurellone
Mi stavo chiedendo quali fossere le strutture dati più adeguate per accedere
al contenuto di tale lista in modo da poter realizzare, ad esempio, delle
ricerche binarie al suo interno. Mi interesserebbe soprattutto sapere se
nella STL (che mi sembra bellissima a prima vista, ma che conosco ancora
molto poco) ci sono delle strutture appropriate (per il resto uso il BCB3.1)
Come primo tentativo ho cercato di caricare tutte le parole in un vettore di
AnsiString, ossia, in modo un po' rozzo:
 fstream D; // File del dizionario
//....
 vector<AnsiString> V;
 char parola[100];
 while (D >> parola)
    {
        V.push_back(AnsiString(parola));
    }
La cosa funziona, ma il caricamento di tutte le parole nel vettore richiede
10 minuti buoni per un file di queste dimensioni.
Alternativamente posso gestire il file a basso livello e fare delle ricerche
binarie non tanto sulle parole, ma direttamente sui singoli byte - ma questa
soluzione è alquanto scomoda.
Che strada seguireste voi?
Grazie
/Martin



Che strada seguireste voi?
Fai un programma che le indicizza mettendo in un vettore di int il
puntatore al primo carattere di tutte le parole.
A questo punto potrai caricarlo in modo 'binario' e usare il vettore
per accedere alle varie parole.
Luc.

Ho provato a realizzare quanto suggerito in diversi modi. Purtroppo mi
sembrano tutti troppo lenti. Sono sicuro che si possa fare molto meglio di
cosě, anche con un computer vecchio come il mio.
Comunque eccoli qui.
Supponiamo che le parole siano separate da un carattere '\n' e che la
dimensione in byte del file sia Dim.
    fstream D; // File del dizionario
    vector<long> Ind;   // vettore di indici delle parole
    long Dim;   // dimensione del dizionario
// primo modo - ci mette 1 minuto (su circa 300000 parole)
    char c;
    long p=0L;
    while (p<Dim)
    {
        do { c=D.get(); p++; } while (c!='\n' && p<Dim);
        Ind.push_back(p);
    }
// secondo modo - sempre 1 minuto
 char parola[100];
 while (D >> parola) Ind.push_back(D.tellg());
// terzo modo - ci mette 45 secondi
    while (!D.eof()) { D.ignore(100,'\n'); Ind.push_back(D.tellg()); }
Idealmente il modo migliore č il secondo, ma in questo caso č perfettamente
inutile usare un "buffer" di 100 caratteri, perché tanto non li si deve
usare. Non si puň usare un buffer "fittizio", in modo da non dover neanche
stare a dichiarare l'array di caratteri parola?
Qualche consiglio?


 Che strada seguireste voi?
Se sei in un sistema con abbastanza memoria (anche virtuale) per non
lavorare su file, carica tutto in memoria.
Alcuni consigli sparsi:
Possibile miglioramento di prestazioni nell'input da file:
// aprire il file da leggere in modalita' binaria
// ottenere la dimensione del file e allocare un buffer di
// dimensione sufficiente a contenerlo tutto (o come array
// di char o come vector<char> (ricordati di settare le
// dimensioni nel costruttore o di usare resize. Non reserve.
// puoi anche creare una "mega" string
// leggere in un colpo solo tutto il file nel buffer con una read
// da qui in poi puoi chiudere il file quando vuoi
Alternative per la scansione dei dati. Hai vari scopi: separare
le stringhe, contarle, memorizzarle nella struttura da te scelta.
Nota che se le parole non le devi modificare in alcun modo l'uso di
string potrebbe non darti benefici. Puoi lasciarle nel megabuffer e
salvarti i puntatori (come fossi in C).
Devi pero' prima terminarle con lo \0 al posto del \n (o del \r\n se
sei in windows). Sta a te scegliere se fare una scansione
extra per contare le stringhe e essere piu' veloce nella
memorizzazione
o se far crescere il container manmano che aggiungi i dati. Il mio
consiglio e' di scandire due volte con l'algoritmo che vedi sotto.
// supponiamo che la prima fase abbia fornito quanto segue:
size_t siz; // lunghezza del buffer (e dei dati)
char *buf; // buffer allocato con new char[siz] e contenente i dati
// creo un container (per esempio un vector) e mi preparo a inserici
le
// parole facendo una prima scansione che conta il numero di parole
vector<const char*> words;
words.reserve( count(&buf[0],&buf[siz],'\n') );
// seconda scansione: memorizzo i puntatori nel container e setto
// i terminatori. do per scontato che il file termini con un a capo
// e che non sia vuoto
assert( siz!=0 && buf[siz-1]=='\n' );  // verifica precondizioni
words.push_back(buf);  // prima stringa
for ( char*p=buf; p!=&buf[siz]; p=find(p, &buf[siz], '\n') ) {
    p[-1]='\0'; // questa riga solo su sistemi windows, non in unix
    *(p++)='\0';
    words.push_back(p);
}
Un ultimo consiglio: non so cosa vuoi fare con le stringhe ma dai
un'occhiata (se ci capisci qualche cosa) a quella che secondo me e'
una delle piu' potenti infrastrutture della STL (nonche' la piu'
complessa, e quindi la meno conosciuta e meno usata): le classi e le
funzioni contenute nell'header valarray
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

 ricerche binarie al suo interno.
std::list garantisce un ordinamento stretto ed un tempo di accesso
O(N lnN); penso che sia la scelta migliore per te.
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it
The instructions said to use Windows 98 or better - so I installed FreeBSD.

 O(N lnN); penso che sia la scelta migliore per te.
Se l'operazione chiave e' una ricerca in un container ordinato (ovvero
una ricerca ordinata) allora una lista e' la scelta peggiore.
Sia un vettore che un albero (set) garantiscono un accesso O( log(n) )
quando la struttura e' ordinata. Se poi il set invece che con un
albero e' implementato con una hash table, ancora meglio!


 Qualche consiglio?
a - usa stringstream per leggere il file, che utilizza std::string. 
non uso il builder, non so quanto queste siano compatibili con 
AnsiString. VC++, ad es. non permette di usare std::string e CString 
insieme...
b - usa set< auto_ptr<AnsiString> >, o se ti trovi a tuo agio coi 
puntatori set<AnsiString *>, per aumentare le prestazioni (eviti la 
copia di un temporaneo, passando i valori al set). ancora meglio una 
hashtable, una implementazione in STL era disponibile sul sito della 
sgi qualche tempo fa.  ho perso il link, sorry.

 una ricerca ordinata) allora una lista e' la scelta peggiore.
Esatto; lapsus.  Volevo dire std::set.
