Newsgroup: it.comp.programmare
Titolo: Paroliere

Buongiorno a tutti..
Vorrei sottoporVi un problema che mi sta assillando, nella speranza di
trovare uno spunto e andare avanti nello sviluppo.
Problema:
In una tabella sono inseriti tutti i vocaboli della lingua italiana.
Il campo è unico ed in chiave, ovviamente.
Data una serie di caratteri, devo estrarre su una seconda tabella le parole
formate da una o più lettere date (NB: SOLO dalle lettere proposte, senza
alcuna aggiunta).
Esempio pratico:
Lettere:
    g t r e l a m o
Estrazione:
    merlato
    merlot
    molare
    molate
    morale
    ago
    agore
    agre
    agro
Il linguaggio di programmazione è molto simile al pascal, ma mi basterebbe
scritto anche in pseudo - codice da adattare poi alla piattaforma.
Ringrazio in anticipo chi volesse collaborare.
Federico

     merlot
Te le devi passare tutte e controllare per ciascuna che tutti i suoi 
caratteri siano presenti nel set dato... 
-- 
Luc

 Luc
In questo modo, visto che la tabella contiene 700.000 records... penso ci
vogliano 2 giorni, no?
eehe!!
Federico

 vogliano 2 giorni, no?
Allora ti conviene creare qualche sorta di indice (es tutte le parole 
che contengono 'a','b',ecc). Più spazio occupato ma migliori 
performances... 
-- 
Luc

performances...
Il tempo di attraversamento di 25 indici non credo che sia molto più buono
che semplicemente guardarseli uno per uno.
Se deve farlo in maniera ripetitiva, gli conviene caricarsi il tutto in
memoria (mediamente con 7 mb circa se la cava, se programma in maniera
figa).
--- bye

 piattaforma.
Quindi il tuo problema e' levare dai 700000 vocaboli tutti quelli che
contengono lettere non scritte nel tuo esempio? Cioe'.. quelli che
contengono la b,c,d... eccetera?
Come devi comportarti se una lettera la ripeti 2 volte? Conta anche il
numero?
Saluti.

 proposte, senza alcuna aggiunta).
hai 21 (p.e.) indici con la posizione delle parole che NON [1]
contengono una lettera --- gli indici sono ordinati
hai m lettere, prendi le altre n=21-m, hai n lettere e n indici
prendi una coppia degli n indici che ti interessano, ne fai un merge e
sostituisci ai due indici usati quello calcolato --- ripeti
si tratta di usare strutture dei dati compatte e efficienti, capire se
esiste una strategia ottimale per la scelta delle coppie di indici
(penso di si), e infine fare molta attenzione all'algoritmo che
utilizzi per fare il merge
hth
[1] ho visto un post in cui ti si consigliava di precalcolare gli
    indici alle parole che CONTENGONO le lettere --- alla fine ti
    resterebbero delle parole che contengono ANCHE altre lettere
-- 
BOMBED BY SPACE-TIME VORTEX 122W 41N. SINKING. U-640.

 numero?
Le lettere non sono ripetibili.
Una volta usata infatti, la sego dalla stringa iniziale, cosě da non
incorrere in questo errorino.

 incorrere in questo errorino.
Hai risposto non esaurientemente...
prendiamo la parola casa.
Posso trovarla? E' valida la stringa aacs? basterebbe anche acs?
--- bye


Dicendo "Lettere non ripetibili" intendevo proprio questo discorso.
CASA la puoi formare con AACS ma NON con ACS.

 writes:

ok, variante degli anagrammi: se il tuo diz e' statico, o quasi, puoi
precompilare un bel databasone con, p.e., chiave "AANN" e valore (di
tipo lista) ["Anna" "nana"], caricarlo quando parte il paroliere e
ottenere una risposta immediata
hth
-- 
TORPEDOED BY IRC SERVER. EXPLODING. U-175.

 hth
Il problema è che la stringa in questione è di 8 caratteri...
Il database vocaboli è di 300.000 parole con lunghezza massima 8 caratteri.
il metodo + veloce trovato finora... trova una lista di parole nel giro di
10 secondi.

 10 secondi.
Che metodo hai usato?


Suggerito da G. Resta:
Ci sono diversi approcci per risolverlo. Consideriamo il
piu' semplice, che si basa sulla possibilita' di rispondere
a questa domanda:
data una parola e un insieme di lettere determinare se la
parola data puo' essere formata con le lettere date.
Per determinare la lista delle parole che e' possibile
formare con le lettere date bastera' iterare questo test
su tutte le parole del vocabolario.
Come fare a determinare se una parola si puo' costruire
con un insieme di lettere date ?
Facilissimo:
Data la serie di lettere, io conto quante A ci sono, quante B
ci sono, quante C ci sono e cosi' via.
Quindi formo un array di 26 numeri interi che mi dicono
quante lettere ci sono di ogni tipo.
Faccio la stessa operazione sulla parola "candidata"
ottenendo un altro array di 26 interi.
Se, elemento per elemento, questo secondo array e' minore
o uguale al primo significa che posso formare la parola.
Esempio:
parola = BACCA
vettore 1  = {2,1,2,0,0,0,0......}
lettere = CCBADDABAEEEG
vettore 2  = {3,2,2,2,3,0,1,0,0,....}
E quindi la parola BACCA si puo' fare con le lettere CCBADDABAEEEG

Il metodo in effetti mi sembra veloce... Ora devi solo lavorare su come
implementarlo al meglio.
La cosa più semplice è che ti tieni nella RAM tutto il dizionario e anche
gli indici delle lettere. Diciamo 20 lettere + 26 chars per i contatori = 46
caratteri per parola. Moltiplicato per 300.000 = 14mb. Fattibile!
Non è che magari tu conti i 10 secondi perchè solo per mostrare l'output ci
mette 10 secondi? (pagine pagine e pagine di risultati sono lenti a essere
visualizzati)
--- bye

 visualizzati)
I risultati sono visualizzati su un form, e di solito non ci sono + di 80
records filtrati, quindi escluderei quel problema. Il tempo è proprio quello
necessario all'esecuzione dei controlli, niente di più.
Bye

Uno screenshot dell'ambiente di sviluppo...
www.nodev.net/verbatron.jpg

Per darti un'idea di cosa significhi velocità:
Questo è un programmino scritto in C++, usando costrutti C++ nella maniera
più stupida possibile. Non bufferizzo niente (lascio che ci pensi lui), uso
le string, uso list (con il risultato di chissà quanti cache miss) ecc.
Ho creato un dizionario di 300.000 parole (circa 2,6mb), unendo un
dizionario italiano, un francese e un altro paio di dizionari trovati in
Internet. Il file si chiama listaparole.txt. Ogni parola occupa una riga e
dopo si va a capo. Io ho un 1700 mhz mi sembra (forse sono 1600, forse
1800). Per caricare il file ci mette 0.671 secondi, per ricercarlo 0.07
secondi (questo in versione Release. La versione Debug è veramente lenta!).
Mi segna che in memoria occupa 21 mb.
Calcola che tipo se lo facessi per windows probabilmente lo potrei fare il
doppio più veloce. Userei un po' di trucchetti per rendere più locali i dati
(in maniera che la cache non abbia difficoltà) e per leggere il file lo
memmapperei in memoria. Poi magari userei un algoritmo di sort più
ottimizzato (il qsort credo sia più veloce del sort delle STL), farei grandi
allocazioni singole di memoria ecc.
// TrovaLettere.cpp : Defines the entry point for the console application.
//
#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <list>
#include <string>
#include <time.h>
using namespace std;
class ParolaLettere {
public:
   string strParola;
   string strLettere;
};
bool operator < (const ParolaLettere& left, const ParolaLettere& right)
{
   return (left.strParola < right.strParola);
}
int main(int /*argc*/, char* /*argv[]*/)
{
   string strLettere;
   cout << "Inserisci le lettere da cercare: ";
   getline(cin, strLettere);
   transform(strLettere.begin(), strLettere.end(), strLettere.begin(),
tolower);
   sort(strLettere.begin(), strLettere.end());
   cout << endl << "Lettere inserite: " << strLettere << endl;
   cout << "Carico File! ";
   clock_t ctCaricoFile = clock();
   list<ParolaLettere> lista;
   ParolaLettere pl;
   string strParola;
   ifstream input("listaparole.txt");
   if (!input.is_open()) {
      cout << "Impossibile aprire il file" << endl;
      return 0;
   }
   while (!input.eof()) {
      getline(input, strParola);
      transform(strParola.begin(), strParola.end(), strParola.begin(),
tolower);
      pl.strParola = strParola;
      sort(strParola.begin(), strParola.end());
      pl.strLettere = strParola;
      lista.push_back(pl);
   }
   cout << endl;
   clock_t ctFineCaricoFile = clock();
   cout << "Fine Carico File! ";
   cout << "Inizio Ricerca! ";
   clock_t ctInizioRicerca = clock();
   list<string> listaTrovati;
   bool bFound = true;
   for (list<ParolaLettere>::iterator i = lista.begin(); i != lista.end();
++i) {
      const char *p1 = &i->strParola[0];
      const char *p2 = &i->strLettere[0];
      const char *p3 = &strLettere[0];
      for (size_t j = 0, k = 0; j < i->strLettere.length() && k <
strLettere.length(); j++, k++) {
         const char *c1 = &i->strLettere[j];
         do {
            const char *c2 = &strLettere[k];
            if (*c1 == *c2)
               break;
            if (*c1 < *c2) {
               bFound = false;
               break;
            }
            k++;
         } while (k < strLettere.length());
         if (k == strLettere.length()) {
            bFound = false;
            break;
         }
      }
      if (j != i->strLettere.length() && k == strLettere.length()) {
         bFound = false;
      }
      if (bFound) {
         listaTrovati.push_back(i->strParola);
      } else {
         bFound = true;
      }
   }
   clock_t ctFineRicerca = clock();
   cout << "Fine Ricerca!" << endl << endl;
   double dCaricoFile = (double)(ctFineCaricoFile - ctCaricoFile) /
(double)CLOCKS_PER_SEC;
   double dRicerca = (double)(ctFineRicerca - ctInizioRicerca) /
(double)CLOCKS_PER_SEC;
   cout << "Per caricare il file (sec): " << dCaricoFile << endl;
   cout << "Per ricercare (sec): " << dRicerca << endl;
   cout << "Premi <ENTER> per continuare!";
   string str;
   getline(cin, str);
   cout << endl << endl << "-- Trovati:" << endl;
   for (list<string>::iterator i = listaTrovati.begin(); i !=
listaTrovati.end(); ++i) {
      cout << " " << *i << endl;
   }
   return 0;
}

Dimenticavo... L'algoritmo.
Dunque... Prendo tutte le parole del "dizionario", le faccio diventare
minuscole e poi ordino le loro lettere (amico = acimo)
Prendo le lettere scritte dall'utente, le rendo minuscole e poi le riordino
(stessa maniera).
Definizione: str1 = stringa dal dizionario riordinata, str2 = stringa
inserita dall'utente riordinata
Poi confronto le due stringhe. Se i due caratteri sono uguali, passo ai due
caratteri successivi. Se il carattere di str1 è minore del carattere di str2
faccio avanzare str2. Se il carattere di str1 è maggiore del carattere di
str2 allora str1 non va bene, e passo alla successiva parola. Se esaurisco
str2 senza aver esaurito str1 allora non va bene, e passo alla successiva
parola.
Se K è la dimensione del dizionario, questo algoritmo ha bisogno
teoricamente di 2K di RAM (infatti di ogni parola tengo due copie: la copia
non ordinata e la copia ordinata).
--- bye

Dando un'occhiata solo alla schermata che hai postato, ho già visto un paio
di possibili migliorie :-)
Vettore fallo di 26 caratteri, e poi fa qualcosa del tipo
if Lettera >= "a" and Lettera <= "z" then
    Vettore[asc(Lettera) - 97] += 1
Dove asc è la funzione che, a partire da una lettera, ti dà il suo codice
ascii (osserva... a = 97, b = 98, c = 99...)
Inoltre vedo che tu fa la strlen(lettereeee). Se sei fortunato il computer
calcola la strlen una sola volta, se no per ogni passaggio del ciclo, il
computer quando arriva al for si ricalcola la lunghezza della stringa.
Prova a postare i sorgenti... Probabilmente ci saranno altri problemi del
genere :-)
(c'è un motivo per cui aver programmato in C e in ASM rende programmatori
migliori :-) )
--- bye

 genere :-)
Ecco il sorgente della funzione FiltroAvanzato:
===============================================================
FiltroAvanzato(lettereeee : Text[30])
// Azzero il vettore
FOR Contatore := 1 TO 21 DO
  Vettore[Contatore] := 0;
// Converto in vettore le lettere passate
FOR Contatore := 1 TO STRLEN(lettereeee) DO
BEGIN
  Lettera := COPYSTR(lettereeee,Contatore,1);
  CASE Lettera OF
    'a': Vettore[1]+=1;
    'b': Vettore[2]+=1;
    'c': Vettore[3]+=1;
    'd': Vettore[4]+=1;
    'e': Vettore[5]+=1;
    'f': Vettore[6]+=1;
    'g': Vettore[7]+=1;
    'h': Vettore[8]+=1;
    'i': Vettore[9]+=1;
    'l': Vettore[10]+=1;
    'm': Vettore[11]+=1;
    'n': Vettore[12]+=1;
    'o': Vettore[13]+=1;
    'p': Vettore[14]+=1;
    'q': Vettore[15]+=1;
    'r': Vettore[16]+=1;
    's': Vettore[17]+=1;
    't': Vettore[18]+=1;
    'u': Vettore[19]+=1;
    'v': Vettore[20]+=1;
    'z': Vettore[21]+=1;
   END;
END;
// Elimino la tabella su cui estrarre
Estrazione.DELETEALL;
Parole.RESET;
Parole.FIND('-');
REPEAT
  // carico vettore parola del dizionario
  Vettore2[1] := Parole.a;
  Vettore2[2] := Parole.b;
  Vettore2[3] := Parole.c;
  Vettore2[4] := Parole.d;
  Vettore2[5] := Parole.e;
  Vettore2[6] := Parole.f;
  Vettore2[7] := Parole.g;
  Vettore2[8] := Parole.h;
  Vettore2[9] := Parole.i;
  Vettore2[10] := Parole.l;
  Vettore2[11] := Parole.m;
  Vettore2[12] := Parole.n;
  Vettore2[13] := Parole.o;
  Vettore2[14] := Parole.p;
  Vettore2[15] := Parole.q;
  Vettore2[16] := Parole.r;
  Vettore2[17] := Parole.s;
  Vettore2[18] := Parole.t;
  Vettore2[19] := Parole.u;
  Vettore2[20] := Parole.v;
  Vettore2[21] := Parole.z;
  trovalettera := TRUE;
  Contatore := 1;
  WHILE (Contatore < 22) AND (trovalettera) DO
  BEGIN
    IF Vettore2[Contatore] > Vettore[Contatore] THEN
      trovalettera := FALSE
    ELSE
      Contatore += 1;
  END;
  IF trovalettera THEN
    BEGIN
      Estrazione.INIT;
      Estrazione.Parola := Parole.Vocabolo;
      Estrazione.Punteggio := Parole.Punteggio;
      Estrazione.INSERT;
    END;
UNTIL Parole.NEXT = 0;
NB: Il campo Punteggio del recordset Parole indica semplicemente la somma
del valore dei punti di ogni lettera, ed è già calcolato e "storato" nel db.

   Vettore2[2] := Parole.b;
--- bye

Oggi pomeriggio non avevo un tubo da fare... E quindi l'ho fatto "un po' più
serio" in C++ per Windows :-)
Risultato: per caricare 0,39 secondi, per ricercare 0,03 (contro i 0,671 e
0,07). E occupa 12 mb quando viene eseguito :-) (contro i 22 di prima). In
pratica ho raddoppiato la velocità e dimezzato l'occupazione (anche l'exe si
è dimezzato) :-) Se fosse mission-critical potrei accellerarlo ancora di un
minimo (più nel caricamento del file che nella ricerca. In questo momento
alloco la memoria a blocchettini. Allocandola a pezzettoni accellererei di
sicuro.).
Se vuoi ti spedisco i sorgenti (sono abbastanza incomprensibili... La
programmazione ottimizzata non va molto a braccetto con la programmazione
"esteticamente bella" :-)
--- bye

 "esteticamente bella" :-)
Ti ringrazio, ma di C non ne capisco un H purtroppo...
mi sarebbe molto + utile in VB, ma non vorrei rompere + di quanto abbia
fatto finora. Il tempo penso sia prezioso per tutti.. se ne trovi altro da
"buttare", avrei piacere...
;)
bye

Dunque, senti... Se lo vuoi fare in Visual Basic... Circa fallo come
quell'altro :-) E non farlo con un DB Access... Solo per connetterti al DB e
leggere record per record ci perdi un marasma di tempo. Piuttosto apri
direttamente un file .txt e usa quello (come ho fatto io)
--- bye


Ehehe, troppo tardi...
l'ho fatto all'incirca come quell'altro..
e sono riuscito a tirar giu' i tempi a 5 secondi, sempre con db access e
sempre con 130mila records.
ora lo velocizzo un altro po' poi.. al massimo ti passo io i sorgenti..
eheh!
bye, buona serata!

 parole nel giro di 10 secondi.
A TITOLO DI ESEMPIO, con ~120000 parole, un processore forse + veloce,
% dmesg  | grep processor
Detected 2290.823 MHz processor.
ma scritto in awk (anzi, in gawk, che e' leeento, ma ha asort())
% time gawk -v test="complementati" '
BEGIN {
  TEST=toupper(test);
  n=split(TEST,AR,"");
  asort(AR);
  TEST="";
  for(i=1;i<n+1;i++) TEST=TEST AR[i];}
length($0)==n {
  A=toupper($1);
  split(A,AR,"");
  asort(AR);
  A="";
  for(i=1;i<n+1;i++) A=A AR[i];
  if(TEST==A) print $1;}' < /usr/share/dict/italian    
complementati
completamenti
real    0m0.251s
user    0m0.250s
sys     0m0.000s
% 
hth

Oggi ho finalmente capito perchè non bisogna mai lasciare che un
programmatore si diverta ad ottimizzare il codice... Il gioco non vale la
candela :-) (però il programmatore si diverte tantissimo!)
Continuando a non sapere cosa fare, ho proceduto ad altre due
ottimizzazioni.
(1° colonna: lettura dei dati e loro organizzazione, 2° colonna ricerca di
un insieme di lettere, 3° colonna memoria occupata secondo Task Manager, 4°
colonna dimensione del file exe)
0,691s-0,050s-21000kb-100kb   Programma scritto in C++ generico, 130 righe
0,337s-0,025s-12.000kb-53kb   Programma scritto in Visual C++ per windows
(C++ + API), 240 righe
0,265s-0,020s-9.000kb-53kb   come sopra, più allocatore della memoria
personalizzato, 385 righe
0,165s-0,020s-9.000kb-53kb   come sopra, più sort ottimizzata per i
caratteri, 370 righe + 380 righe copiate dai sorgenti delle librerie di
runtime MS (distribuiti insieme al VC++) con poche modifiche (10 minuti di
lavoro circa)
Se qualcuno vuole i sorgenti, glie li passo senza problemi... Io il mio
esperimento l'ho fatto :-)
(ed ho imparato cose interessanti sull'allocazione di memoria e sul qsort)

 (ed ho imparato cose interessanti sull'allocazione di memoria e sul qsort)
Bella lě, vedi che allora a qualcosa č servito il mio progettino?
Peccato che non capisco un'h di C++ ne' tanto meno di Visual...
In vb no eh?
eheh... dato che ci siamo, magari...
poi ci mettiamo a venderlo!
Saluti...
Nodev

 "Anassimandro" ha chiave AAADIMNNORSS
Grazie, ma non ho bisogno di una lezione di italiano...
Cmq mi interessava scritto su un linguaggio windows.. e non linux, sorry..
Non mi ero spiegato!
Nodev