Ricerca rapida di una stringa in una lista

di
ninjo
il
12 risposte
N
ninjo
Pochi posts
Iscritto da
mag, 2014
Messaggi:
37

Ricerca rapida di una stringa in una lista

Salve a tutti ragazzi
Espongo rapidamente il mio problema:
ho una serie di stringhe salvate in varie liste

lista[0]={casa, mela}
lista[1]={auto}
lista[2]={banana}
lista[3]={ciao,come,stai}

queste liste sono salvate in un vettore[4]={lista[0],lista[1],lista[2],lista[3]}

quindi vector<list<string> > coda;

e ho la possibilità di spostare la stringhe da una lista ad un altra, in base all'input.
es: input: casa mela -> sposta mela in casa

Il problema è che la ricerca delle suddette è estremamente lento, ovviamente i test li faccio con input di mooolte stringhe e mooolto più lunghe, quindi mi serve un metodo più veloce di ricerca e confronto e a quanto ho capito dovrei utilizzare una tabella hash, solo che non ho ancora capito bene come funziona e come evitare le collisioni o se è il metodo migliore.

Suggerimenti? consigli?

12 Risposte

  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Ricerca rapida di una stringa in una lista

    Io direi di usare un unordered_set di string invece che le liste. Così la ricerca è nel ordine di O(1) caso standard oppure O(n) caso peggiore.
    Attenzione allo spazio in meoria però. unordered_set ne chiede di più.
  • N
    ninjo
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    37

    Re: Ricerca rapida di una stringa in una lista

    Unordered_set è' per c++11 e non va bene. Ma usare una tabella hash mi ridurrebbe i tempi di ricerca di molto? La sto studiando ma non ho capito bene se è quello che mi servirebbe.
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Ricerca rapida di una stringa in una lista

    Unordered_set é una tabella di hash. Poi non ho capito perché non va bene.
  • N
    ninjo
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    37

    Re: Ricerca rapida di una stringa in una lista

    Non ti riferisci a questa http://www.cplusplus.com/reference/unordered_set/unordered_set/? Non uso c++11, ho pure provato ad inserirla come libreria e non la trova, ma non so se mi sbaglio, magari tu ti riferisci a qualcosa altro.
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Ricerca rapida di una stringa in una lista

    Unorderet_set fa parte del C++11 e deve essere incluso nel tuo compilatore. Se così non fosse aggiornalo. All'interno implementa una tabella di hash ma tu sei all'oscuro perche l'interfaccia te lo presenta come un set.
  • N
    ninjo
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    37

    Re: Ricerca rapida di una stringa in una lista

    Ti ringrazio del suggerimento ma purtroppo devo farlo andare su c++ senza aggiornarmenti al compilatore.
    Altri consigli? Pure in linea teorica...
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Ricerca rapida di una stringa in una lista

    Che funzione usi per il confronto delle stringhe?
  • N
    ninjo
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    37

    Re: Ricerca rapida di una stringa in una lista

    Per ora sto usando semplicemente un for che mi scorre tutte le liste di tutta la coda e gli faccio fare un controllo dapprima solo sulla prima lettera in modo da scremare un pò di confronti inutili 
    if(   (*it)[0] == parola1[0]  || (*it)[0] == parola2[0]   )

    Se la prima lettere è uguale confronta 
    if (*it == parola1) o if (*it == parola2)
    inserisci 
    coda[Xparola1].erase(posIterParola1); 
coda[Xparola2].push_back(parola1);
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Ricerca rapida di una stringa in una lista

    Inizia intanto ad usare un std::set invece che list. il set ha la funzione find con complessità log(n) invece che lineare e vedrai che acceleri. Poi per la ricerca lineare puoi usare std::find applicata ai vector se proprio ti serve farla.
  • N
    ninjo
    Pochi posts
    Iscritto da
    mag, 2014
    Messaggi:
    37

    Re: Ricerca rapida di una stringa in una lista

    Se volessi usare il set dovrei impostare la lista come 
    set<vector<string > >
    ma ho un po di problemi a capire come ridimensionarla (serve?) in quanto non ha la funzione resize(), prima infatti facevo 
    coda.resize(dimCoda,vector<string>());
    In effetti ne guadagnerei nella ricerca ma non siamo ancora nel grado di ottimizzazione in cui mi farebbe arrivare, credo, un hastable. Quello che non riesco a capire è come gestire una collisione, esempio, se un hash(string) % ecc.. mi restituisce un valore già presente, anche se riuscissi ad inserirlo nella spazio successivo non occupato, poi come faccio a capire quante posizioni dopo l'ho inserito, dovrei procedere con una scansione lineare?
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Ricerca rapida di una stringa in una lista

    No ti serve: 
    vector<set<string>>
    questo per accelerare la ricerca delle stringhe. 
    std::set<std::string> mySet;
std::set<std::string>::iterator it;
mySet.insert("pippo");
it = mySet.find("pippo");

if(it != mySet.end())
    std::cout << "trovato";
    Non c'è bisogno di resize. Non so quanti elementi inserisci e se questi siano ripetuti o meno.
    Se ripetuti devi usare il std::multiset
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Ricerca rapida di una stringa in una lista

    Se proprio ti piace reinventare la ruota leggi anche qua:
    http://www.cplusplus.com/forum/general/107756
Devi accedere o registrarti per scrivere nel forum
12 risposte