Quale contenitore per memorizzare valori univoci?

Question

Ho il seguente problema. Ho un gioco che esegue in media 60 fotogrammi al secondo. Ogni frame ho bisogno di memorizzare valori in un contenitore e non ci devono essere duplicati.

Probabilmente deve memorizzare meno di 100 elementi per fotogramma, ma il numero di chiamate da inserire sarà molto più (e molti rifiutati a causa di esso devono essere unici). Solo alla fine del frame devo attraversare il container. Quindi circa 60 iterazioni del contenitore per fotogramma, ma molti più inserimenti.

Ricordare che gli elementi da memorizzare sono numeri interi semplici.

Ci sono un sacco di contenitori che posso usare per questo ma non riesco a decidermi cosa scegliere. Le prestazioni sono il problema chiave per questo.

Alcuni pro/contro che ho raccolto:

---

vettore

• (PRO): di memoria contigui, un fattore enorme.
• (PRO): La memoria può essere prenotata prima, pochissimi Accantonamenti/deallocazioni dopo
• (CON): No alternativa che attraversare il contenitore (std :: trovare) ciascun inserto() per trovare le chiavi uniche? Il confronto è semplice anche se (interi) e l'intero contenitore può probabilmente in forma cache

impostato

• (PRO): semplice, significava chiaramente per questo
• (CON): Non tempo di inserimento costante
• (CON): un sacco di allocazioni/deallocazioni per frame
• (CON): memoria non contigua. Attraversare un insieme di centinaia di oggetti significa saltare in giro in memoria.

unordered_set

• (PRO): semplice, significava chiaramente per questo
• (PRO): caso medio costante di tempo inserire
• (CON): Visto che devo conservare interi, operazione di hash è probabilmente molto più costosa di qualsiasi altra
• (CON): un sacco di allocazioni/deallocazioni per frame
• (CON): memoria non contigua. Attraversare un insieme di centinaia di oggetti significa saltare in giro in memoria.

---

che sto appoggiato in corso il vettore di rotta a causa dei modelli di accesso di memoria, anche se insieme è chiaramente inteso per questo problema. Il grosso problema che non mi è chiaro è se attraversare il vettore per ogni inserto sia più costoso delle allocazioni/deallocazioni (specialmente considerando quanto spesso questo deve essere fatto) e le ricerche di memoria del set.

So che alla fine tutto si riduce alla profilazione di ogni caso, ma se non altro come un vantaggio iniziale o solo teorico, quale sarebbe probabilmente la cosa migliore in questo scenario? Ci sono pro/contro che potrei aver perso?

EDIT: Come non ho citato, il contenitore viene cancellato() alla fine di ogni frame

Answer 1

ho intenzione di mettere il mio collo sul ceppo qui e suggeriscono che il percorso vettore è probabilmente il più efficiente quando la dimensione è 100 e gli oggetti da memorizzare sono valori interi. Il semplice motivo per questo è che set e unordered_set allocano memoria per ogni inserto mentre il vettore non ha bisogno di più di una volta.

È possibile aumentare notevolmente le prestazioni di ricerca mantenendo il vettore ordinato, poiché tutte le ricerche possono essere ricerche binarie e quindi completare in tempo log2N.

Lo svantaggio è che gli inserti richiederanno una piccola frazione più lunga a causa delle mosse di memoria, ma sembra che ci saranno molte più ricerche rispetto agli inserti e lo spostamento (medio) di 50 parole contigue di memoria è un'operazione quasi istantanea .

Ultima parola: Scrivere la logica corretta ora. Preoccupati delle prestazioni quando gli utenti si lamentano.

EDIT: Perché io non potevo aiutare, ecco un'implementazione ragionevolmente completo:

template<typename T> 
struct vector_set 
{ 
    using vec_type = std::vector<T>; 
    using const_iterator = typename vec_type::const_iterator; 
    using iterator = typename vec_type::iterator; 

    vector_set(size_t max_size) 
    : _max_size { max_size } 
    { 
     _v.reserve(_max_size); 
    } 

    /// @returns: pair of iterator, bool 
    /// If the value has been inserted, the bool will be true 
    /// the iterator will point to the value, or end if it wasn't 
    /// inserted due to space exhaustion 
    auto insert(const T& elem) 
    -> std::pair<iterator, bool> 
    { 
     if (_v.size() < _max_size) { 
      auto it = std::lower_bound(_v.begin(), _v.end(), elem); 
      if (_v.end() == it || *it != elem) { 
       return make_pair(_v.insert(it, elem), true); 
      } 
      return make_pair(it, false); 
     } 
     else { 
      return make_pair(_v.end(), false); 
     } 
    } 

    auto find(const T& elem) const 
    -> const_iterator 
    { 
     auto vend = _v.end(); 
     auto it = std::lower_bound(_v.begin(), vend, elem); 
     if (it != vend && *it != elem) 
      it = vend; 
     return it; 
    } 

    bool contains(const T& elem) const { 
     return find(elem) != _v.end(); 
    } 

    const_iterator begin() const { 
     return _v.begin(); 
    } 

    const_iterator end() const { 
     return _v.end(); 
    } 


private: 
    vec_type _v; 
    size_t _max_size; 
}; 

using namespace std; 


BOOST_AUTO_TEST_CASE(play_unique_vector) 
{ 
    vector_set<int> v(100); 

    for (size_t i = 0 ; i < 1000000 ; ++i) { 
     v.insert(int(random() % 200)); 
    } 

    cout << "unique integers:" << endl; 
    copy(begin(v), end(v), ostream_iterator<int>(cout, ",")); 
    cout << endl; 

    cout << "contains 100: " << v.contains(100) << endl; 
    cout << "contains 101: " << v.contains(101) << endl; 
    cout << "contains 102: " << v.contains(102) << endl; 
    cout << "contains 103: " << v.contains(103) << endl; 
} 

Answer 2

come hai detto di avere molti inserimenti ed un solo attraversamento, io suggerirei di usare un vettore e spingere gli elementi indipendentemente dal fatto che siano unici nel vettore. Questo è fatto in O(1).

Proprio quando è necessario passare attraverso il vettore, quindi ordinarlo e rimuovere gli elementi duplicati. Credo che questo possa essere fatto in O(n) in quanto sono numeri interi con limiti.

EDIT: Ordinamento in tempo lineare attraverso counting sort presentato in this video. Se non è fattibile, si ritorna a O(n lg(n)).

Si avrà un errore di cache molto piccolo a causa della contiguità del vettore in memoria e pochissime allocazioni (specialmente se si riserva sufficiente memoria nel vettore).

Answer 3

Ho fatto i tempi con alcuni metodi diversi che pensavo fossero probabilmente candidati. L'utilizzo di std::unordered_set è stato il vincitore.

Qui sono i miei risultati:

 
Using UnorderedSet: 0.078s 
Using UnsortedVector: 0.193s 
Using OrderedSet:  0.278s 
Using SortedVector: 0.282s 

Timing è basato sulla mediana di cinque piste per ogni singolo caso.

 
compiler: gcc version 4.9.1 
flags: -std=c++11 -O2 
OS:  ubuntu 4.9.1 
CPU:  Intel(R) Core(TM) i5-4690K CPU @ 3.50GHz 

Codice:.

#include <algorithm> 
#include <chrono> 
#include <cstdlib> 
#include <iostream> 
#include <random> 
#include <set> 
#include <unordered_set> 
#include <vector> 

using std::cerr; 
static const size_t n_distinct = 100; 

template <typename Engine> 
static std::vector<int> randomInts(Engine &engine,size_t n) 
{ 
    auto distribution = std::uniform_int_distribution<int>(0,n_distinct); 
    auto generator = [&]{return distribution(engine);}; 
    auto vec = std::vector<int>(); 
    std::generate_n(std::back_inserter(vec),n,generator); 
    return vec; 
} 


struct UnsortedVectorSmallSet { 
    std::vector<int> values; 
    static const char *name() { return "UnsortedVector"; } 
    UnsortedVectorSmallSet() { values.reserve(n_distinct); } 

    void insert(int new_value) 
    { 
    auto iter = std::find(values.begin(),values.end(),new_value); 
    if (iter!=values.end()) return; 
    values.push_back(new_value); 
    } 
}; 


struct SortedVectorSmallSet { 
    std::vector<int> values; 
    static const char *name() { return "SortedVector"; } 
    SortedVectorSmallSet() { values.reserve(n_distinct); } 

    void insert(int new_value) 
    { 
    auto iter = std::lower_bound(values.begin(),values.end(),new_value); 
    if (iter==values.end()) { 
     values.push_back(new_value); 
     return; 
    } 
    if (*iter==new_value) return; 
    values.insert(iter,new_value); 
    } 
}; 

struct OrderedSetSmallSet { 
    std::set<int> values; 
    static const char *name() { return "OrderedSet"; } 
    void insert(int new_value) { values.insert(new_value); } 
}; 

struct UnorderedSetSmallSet { 
    std::unordered_set<int> values; 
    static const char *name() { return "UnorderedSet"; } 
    void insert(int new_value) { values.insert(new_value); } 
}; 



int main() 
{ 
    //using SmallSet = UnsortedVectorSmallSet; 
    //using SmallSet = SortedVectorSmallSet; 
    //using SmallSet = OrderedSetSmallSet; 
    using SmallSet = UnorderedSetSmallSet; 

    auto engine = std::default_random_engine(); 

    std::vector<int> values_to_insert = randomInts(engine,10000000); 
    SmallSet small_set; 
    namespace chrono = std::chrono; 
    using chrono::system_clock; 
    auto start_time = system_clock::now(); 
    for (auto value : values_to_insert) { 
    small_set.insert(value); 
    } 
    auto end_time = system_clock::now(); 
    auto& result = small_set.values; 

    auto sum = std::accumulate(result.begin(),result.end(),0u); 
    auto elapsed_seconds = chrono::duration<float>(end_time-start_time).count(); 

    cerr << "Using " << SmallSet::name() << ":\n"; 
    cerr << " sum=" << sum << "\n"; 
    cerr << " elapsed: " << elapsed_seconds << "s\n"; 
}