Ho un vettore di stringhe e devo controllare se ogni elemento in vettoriale è presente in una data lista di 5000 parole. Oltre al metodo banale di due cicli annidati, c'è un modo più veloce per farlo in C++?Ricerca stringa veloce?
È necessario inserire l'elenco di stringhe in un std::set. È una struttura dati ottimizzata per la ricerca. Trovare se un dato elemento è nell'insieme o no è un'operazione che è molto più veloce di iterare tutte le voci.
Quando si utilizza già C++ 11, è anche possibile utilizzare std::unordered_set che è ancora più veloce per la ricerca, poiché è implementato come tabella hash.
In questo caso per scuola/università: Prepararsi a spiegare come queste strutture di dati riescono ad essere più veloci. Quando il tuo istruttore ti chiede di spiegare perché li hai usati, "alcuni ragazzi su internet mi hanno detto" è improbabile che ti guadagnino un adesivo nel class book.
haha, no, lo avrei menzionato se fosse per la scuola. questo era parte del mio codice per un problema di usaco. – ofey
È possibile inserire l'elenco di parole in un std::unordered_set. Quindi, per ogni elemento nel vettore, devi solo testare se si trova in unordered_set in O (1). Avresti una complessità prevista di O (n) (guarda il commento per capire perché è solo previsto).
Non è proprio la verità. L'hash di ogni stringa deve essere calcolato e le stringhe devono essere confrontate almeno una volta. Ognuno di questi è indipendente dal numero totale di stringhe (nel caso previsto), ma vale la pena menzionarlo. E mentre il caso peggiore è estremamente improbabile, è bene mantenere lo stile corretto e dire che il tempo * previsto * è O (1). – delnan
Hai perfettamente ragione. Ho cambiato la mia risposta di conseguenza. Grazie. –
È possibile ordinare il vettore, quindi è possibile risolverlo con un "ciclo" (considerato che anche il dizionario è stato ordinato), il che significa che O (n) non sta contando nel costo dell'ordinamento.
Quindi hai un vettore di stringhe, ogni stringa ha una o più parole e hai un vettore che è un dizionario e devi determinare quali parole nel vettore di stringhe sono anche nel dizionario? Il vettore delle stringhe è un fastidio, dal momento che è necessario guardare ogni parola. Comincerei creando un nuovo vettore, dividendo ogni stringa in parole e spingendo ogni parola nel nuovo vettore. Quindi ordina il nuovo vettore ed eseguilo attraverso l'algoritmo std::unique per eliminare i duplicati. Quindi ordina il dizionario. Quindi, esegui entrambi gli intervalli attraverso std::set_intersection per scrivere il risultato.
È un'opzione per popolare un contenitore associativo in primo luogo piuttosto che una lista? –
È possibile ordinare l'elenco di 5000 parole? Se sì, sulla lista ordinata è possibile effettuare una ricerca binaria per le stringhe nel vettore. – Satyajit
Vuoi che la stringa corrisponda all'intera * * di una nel tuo set, o è sufficiente che quella del set * contenga * quella che stai cercando? –