Newsgroup: it.comp.java
Titolo: Algoritmo needed please... :)

Sto lavorando su un problema, forse e' un po' OT perche' non riguarda
Java in senso stretto, anche se sto cercando di risolverlo in Java.
Il problema e' questo: data una lista di parole, e associata ad ognuna
una frequenza, memorizzato il tutto in una qualsiasi struttura dati, un
programma accetta in input una sequenza di n caratteri. Devo trovare
piu' velocemente possibile quali siano le m parole piu' frequenti che
iniziano con questi n caratteri.
Idea che ho avuto (ma mi sembra un po' esagerata): struttura ad albero,
in ogni ramo un carattere, in ogni nodo una lista di m elementi (posso
chiamarli puntatori?) che rimandano alle parole. In totale un casino di
liste, un'occupazione di memoria esagerata, prestazioni sotto zero...
Seconda idea: stesso albero, in ogni nodo un solo puntatore, ogni parola
ha un puntatore alla successiva (ordinate per frequenza), piu' semplice,
ma non funziona (e ci ho messo anche un po' a capire perche'... siamo
alla frutta...)
Insomma, magari esiste un algoritmo "standard" e io sono qui a perdere
il sonno per cercare di inventarlo di nuovo?

 liste, un'occupazione di memoria esagerata, prestazioni sotto zero...
   In generale, le liste hanno il pregio di avere buone prestazioni sia
nella modifica della struttura dati che nell'accesso ai dati, al costo di un
maggiore utilizzo di memoria. Non capisco pero' perche' le tue prestazioni
sono "sotto zero". Forse per il thrashing dovuto a insufficienza di memoria.
   Se il tempo per costruire e modificare la struttura dati non e' da
ottimizzare (per esempio, perche' la struttura dati viene caricata al lancio
del programma e non viene piu' modificata per delle ore), l'uso di array e'
sempre piu' efficiente come memoria occupata, mentre come tempo di accesso
e' piu' efficiente per elaborare numeri, mentre con le stringhe non saprei.
   Comunque ti suggerisco il seguente algoritmo che e' abbastanza semplice
ed efficiente.
   Crea un array di riferimenti alle parole, inizializzato in modo che ogni
cella si riferisca a una parola diversa. Ordina l'array secondo un
ordinamento che e' quello alfabetico crescente per le parole che
differiscono per le prime n lettere, e per frequenza decrescente per le
parole che hanno le stesse prime n lettere. Ecco un esempio del risultato
dove n=1.
      milano 45
      mantova 12
      roma 89
      rovigo 17
      ragusa 4
      trieste 89
      torino  15
      trento 2
   Puoi cercare in questo array con l'algoritmo di ricerca binaria la prima
parola che inizia con la sequenza desiderata, e le altre m - 1 saranno
quelle seguenti.
   Questo algoritmo funziona anche con m variabile, mentre se ti serve poter
variare n dovresti avere tanti array quanti sono i valori possibili di n.
Chiaramente, se n puo' assumere tutti i valori compresi tra 1 e 20,
l'allocazione di 20 array non e' il modo migliore di far uso della memoria.
   Fammi sapere se il consiglio ti e' stato utile.
      Carlo Milanesi
http://digilander.iol.it/carlmila

    Fammi sapere se il consiglio ti e' stato utile.
Certo, ma se gli array non sono tutti della stessa lunghezza (le parole piu'
lunghe sono meno frequenti) allora si puo' trovare il compromesso
Terro' presente e ne parlero' al relatore. Grazie mille.
L'idea e' tua o e' un algoritmo documentato da qualche parte?