Ricerca binaria in std :: vector

Question

Sto cercando di cercare la posizione degli elementi vettoriali in un altro vettore. Qui mi interessa utilizzare un'implementazione veloce come binary search. Ho diversi vettori di lunghezza 1 milione o più, quindi sto cercando di ottenere qualcosa di più veloce.

seguenti situazioni nel mio caso:

1)vector in cui sto cercando è ordinato.

2) L'elemento Cerco sarà sempre lì cioè non ho un caso di not found, e vorrei per ottenere l'indice di elementi vettoriali in un modo più veloce.

Ho provato il seguente codice per ottenere l'indice degli elementi vettoriali.

#include <iostream> 
#include <vector> 
#include <algorithm> 

template<class Iter, class T> 
Iter binary_find(Iter begin, Iter end, T val) 
{ 
    Iter i = std::lower_bound(begin, end, val); 
    return i; 
} 

int main() { 
    std::vector<std::string> values = {"AAAAAA","AB", "AD" ,"BCD","CD", "DD" }; 
    std::vector<std::string> tests = {"AB", "CD","AD", "DD"}; 
    for(int i=0 ; i < tests.size(); i++) { 
     int pos = binary_find(values.begin(), values.end(), tests.at(i))- values.begin(); 
    std::cout << tests.at(i) << " found at: " << pos <<std::endl; 
    } 
    return 0; 
} 

Vorrei sapere se il codice corrisponde con l'implementazione ricerca binaria. ??

C'è un modo più rapido per ottenere l'indice degli elementi vettoriali?

Eventuali ulteriori suggerimenti per migliorare questo codice.

Answer 1

binary_find non restituisce nulla pur non dichiarato di tornare void, così è indefinito comportamento.

Dopo averlo corretto e supponendo che non si disponga di conoscenze specifiche sul contenuto del vettore diverso da quello ordinato, la ricerca binaria è praticamente ottimale.

Esistono tuttavia altre strutture di dati più veloci per la ricerca basata su predicato rispetto a un vettore. Se le prestazioni sono critiche, dovresti dare un'occhiata agli alberi di ricerca e alle mappe di hash. Dal momento che le tue chiavi sono stringhe, i tentativi e il grafico della parola aciclica in particolare possono essere efficaci. Puoi decidere quale sia il migliore per il tuo caso d'uso.

Answer 2

Q1: Vorrei sapere se il codice corrisponde all'implementazione della ricerca binaria. ??

Sì, è (almost) è. Controllare std::lower_bound, in cui si afferma:

Complessità:

In media, logaritmica nella distanza tra il primo e ultimo : esegue circa log2 (N) +1 confronti elemento (dove N è questa distanza). Negli iteratori non a accesso casuale, l'iteratore avanza producendo una complessità lineare aggiuntiva in N in media.

---

Q2: C'è un modo più veloce per ottenere l'indice di elementi vettoriali ??.

Questa è una domanda piuttosto ampia.

---

Q3: eventuali ulteriori suggerimenti per migliorare questo codice.

Ciao mondo, Code Review!

---

PS - Hai compilato il codice?Dà diversi messaggi, come:

warning: no return statement in function returning non-void [-Wreturn-type] 

Compilare con avvisi attivato, in questo modo:

g++ -Wall main.cpp 

Answer 3

http://www.cpluplus.com dice che il comportamento di binary_search è equivalente a:

template <class ForwardIterator, class T> 
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val) { 
    first = std::lower_bound(first, last, val); 
    return (first != last && !(val < *first)); 
} 

Quindi sì, lower_bound è la vostra arma di scelta. Ma quando fai la differenza dovresti usare distance. Perché, se c'è un modo più veloce per acquisire la posizione, verrà trasferito in quella funzione.

quanto riguarda gli altri miglioramenti, suggerirei usando C++ 14 di begin e end e non chiamare una funzione che serve solo per avvolgere una lower_bound (e non riescono a restituire correttamente un valore.) Quindi il modo che avevo scrivere questo codice sarà simile a:

auto pos = distance(lower_bound(begin(values), end(values), tests[i]), begin(values));