Jaki kontener przechowywać wartości unikatowe?

Question

Mam następujący problem. Mam grę, która działa średnio 60 klatek na sekundę. Każda klatka potrzebna do przechowywania wartości w kontenerze i nie może być żadnych duplikatów.

Prawdopodobnie musi przechowywać mniej niż 100 elementów na ramkę, ale liczba wstawionych wywołań będzie o wiele większa (a wiele odrzuconych z powodu tego musi być unikatowych). Tylko na końcu ramy muszę przejść przez pojemnik. A więc około 60 iteracji kontenera na ramkę, ale o wiele więcej wstawek.

Należy pamiętać, że pozycje do zapisania to prosta liczba całkowita.

Istnieje kilka pojemników, które mogę wykorzystać do tego, ale nie mogę zdecydować, co wybrać. Najważniejszą kwestią jest wydajność.

Niektóre plusy/minusy, że zebraliśmy:

---

wektorowe

• (PRO): pamięć Contigous, ogromny czynnik.
• (PRO): Pamięć może być zarezerwowana jako pierwsza, bardzo niewiele alokacji/deallocations następnie
• (CON): Nie ma alternatywy, aby przejść kontener (std :: find) do każdej wkładki(), aby znaleźć unikalne klucze? Porównanie jest proste, choć (liczby całkowite), a cały pojemnik może prawdopodobnie pasuje cache

ustawiony zostanie

• (PRO): Prosty, wyraźnie przeznaczone do tego
• (CON): Nie stały czas wstawiania
• (CON): Wiele alokacji/deallokacji na ramkę
• (CON): Nie jest to pamięć ciągła. Przemierzanie zestawu setek obiektów oznacza skakanie dookoła w pamięci.

unordered_set

• (PRO): Prosty, wyraźnie przeznaczone do tego
• (PRO): Średnie sprawa stała czasowa wstawić
• (Con): Widząc, jak przechowywać liczby całkowite, operacja mieszania jest prawdopodobnie o wiele droższa niż cokolwiek innego:
• (CON): wiele alokacji/deallocations na ramkę
• (CON): Not contigous memory. Przemierzanie zestawu setek obiektów oznacza skakanie dookoła w pamięci.

---

ja opierając się dzieje z Vector-trasę z powodu wzorców dostępu do pamięci, mimo że zestaw jest wyraźnie przeznaczona na ten temat. Największym problemem, który jest dla mnie niejasny, jest to, czy przemieszczenie wektora dla każdej wstawki jest droższe niż alokacje/deallokacje (szczególnie biorąc pod uwagę, jak często musi to być zrobione) i sprawdzanie pamięci zestawu.

Wiem, że ostatecznie wszystko sprowadza się do profilowania każdego przypadku, ale jeśli nic innego, jak tylko headstart lub teoretycznie, co prawdopodobnie byłoby najlepsze w tym scenariuszu? Czy są jakieś plusy/minusy, które również mogłem ominąć?

EDIT: Ponieważ nie zrobił wspomnieć, pojemnik jest usuwany() na końcu każdej ramki

Answer 1

Zamierzam umieścić szyję na bloku tu i sugerują, że trasa wektor jest prawdopodobnie najbardziej skuteczny, gdy rozmiar wynosi 100, a przechowywane obiekty są wartościami integralnymi. Powodem tego jest to, że set i unordered_set przydzielają pamięć dla każdej wstawki, podczas gdy wektor nie musi więcej niż jeden raz.

Możesz znacznie zwiększyć wydajność wyszukiwania, utrzymując zamówiony wektor, ponieważ wtedy wszystkie wyszukiwania mogą być wyszukiwane binarnie, a zatem zakończyć w czasie log2N.

Wadą jest to, że wkładki będą trwać odrobinę dłużej ze względu na ruchy pamięci, ale brzmi to tak, jakby było o wiele więcej wyszukiwań niż wstawek, a przenoszenie (średnio) 50 sąsiednich słów pamięci jest niemal natychmiastową operacją .

Ostatnie słowo: Napisz teraz poprawną logikę. Martw się o wydajność, gdy użytkownicy narzekają.

EDIT: Ponieważ nie mogłem się powstrzymać, tu jest dość pełna realizacja:

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

Jak mówiłeś, że mają wiele wstawki i tylko jeden przechodzenie, sugeruję użycie wektor i pchania elementy bez względu na to, czy są one unikalne w wektorze. Odbywa się to w O(1).

Wystarczy, aby przejść przez wektor, a następnie posortuj go i usuń zduplikowane elementy. Wierzę, że można to zrobić w O(n), ponieważ są one ograniczonymi liczbami całkowitymi.

EDIT: Sortowanie w czasie liniowym poprzez sortowanie przez zliczanie przedstawiony w this video. Jeśli nie jest to wykonalne, wracasz do O(n lg(n)).

Będziesz miał bardzo mało brakującej pamięci podręcznej ze względu na ciągłość wektora w pamięci i bardzo niewiele przydziałów (szczególnie jeśli zarezerwujesz wystarczającą ilość pamięci w wektorze).

Answer 3

Zrobiłem wyczucie czasu za pomocą kilku różnych metod, które według mnie były prawdopodobnymi kandydatami. Wygrał zwycięzca przy użyciu std::unordered_set.

Oto moje wyniki:

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

czas jest w oparciu o medianę pięciu seriach dla każdego przypadku.

 
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 

Kod:.

#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"; 
}