Какой контейнер хранит уникальные значения?

Question

У меня есть следующая проблема. У меня есть игра, которая работает в среднем 60 кадров в секунду. Каждому кадру мне нужно хранить значения в контейнере и не должно быть дубликатов.

Возможно, он хранит менее 100 элементов на фрейм, но количество вставных вызовов будет намного больше (и многие из них отклоняются из-за того, что он должен быть уникальным). Только в конце рамки мне нужно пройти контейнер. Таким образом, около 60 итераций контейнера за кадр, но еще больше вставок.

Имейте в виду, что предметы для хранения - простые целые числа.

Есть куча контейнеров, которые я могу использовать для этого, но я не могу решить, что выбрать. Для этого ключевой проблемой является производительность.

Некоторые плюсы/минусы, которые я собрал:

---

вектор

• (PRO): Contigous памяти, огромный фактор.
• (PRO): память может быть зарезервирована вначале, очень мало выделений/освобождений после этого
• (CON): Нет альтернативы, чтобы пересечь контейнер (std :: find), каждая вставка(), чтобы найти уникальные ключи? Сравнение прост, хотя (целые) и весь контейнер, вероятно, может поместиться кэшированные

набор

• (PRO): Простой, очевидно, имел в виду для этого
• (CON): Не постоянное время вставки
• (CON): Атрибуты распределения/освобождения на фрейм
• (CON): Небезразличная память. Перемещение множества сотен объектов означает прыжок вокруг много в памяти.

unordered_set

• (PRO): Простой, очевидно, имел в виду для этого
• (PRO): Средний случай постоянная времени вставки
• (CON): Видя, как хранить целые числа, хеш-операция, вероятно, намного дороже, чем что-либо еще
• (CON): Атрибуты распределения/освобождения на фрейм
• (CON): Не сопутствующая память. Перемещение множества сотен объектов означает прыжок вокруг много в памяти.

---

Я склоняюсь идти вектор-маршрут из моделей доступа памяти, даже если набор явно имел в виду эту проблему. Большая проблема, которая для меня непонятна, заключается в том, является ли перемещение вектора для каждой вставки более дорогостоящим, чем распределение/освобождение (особенно учитывая, как часто это нужно делать) и поиск в памяти набора.

Я знаю, что в конечном итоге все сводится к профилированию каждого случая, но если не что иное, как головной план или только теоретически, что, вероятно, было бы лучше всего в этом сценарии? Есть ли какие-либо плюсы и минусы, которые я, возможно, пропустил?

EDIT: Как я не упоминаю, контейнер очищается() в конце каждого кадра

Answer 1

Я собираюсь поставить свою шею на блоке здесь и предположить, что вектор маршрут, вероятно, наиболее эффективными, когда размер 100, а сохраняемые объекты являются целыми значениями. Простая причина этого заключается в том, что set и unordered_set выделяют память для каждой вставки, тогда как вектор нужен не более одного раза.

Вы можете значительно увеличить эффективность поиска, сохранив векторный заказ, так как все поисковые запросы могут быть бинарными поисками и поэтому заполняться в log2N времени.

Недостатком является то, что вставки будут занимать меньшую часть дольше из-за перемещения памяти, но это звучит так, как если бы было еще много поисков, чем вставки, а перемещение (среднее) 50 смежных слов памяти - это почти мгновенная операция ,

Заключительное слово: Напишите правильную логику. Беспокоитесь о производительности, когда пользователи жалуются.

EDIT: Потому что я не мог помочь себе, вот достаточно полная реализация:

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

Как вы сказали, у вас есть много вставок и только один обход, я предложил бы использовать вектор и толчок элементы независимо от того, являются ли они уникальными в векторе. Это делается в O(1).

Просто, когда вам нужно пройти через вектор, затем отсортируйте его и удалите повторяющиеся элементы. Я считаю, что это можно сделать в O(n), поскольку они являются ограниченными целыми числами.

EDIT: Сортировка в линейном времени через подсчета рода представлены в this video. Если это невозможно, вернитесь к O(n lg(n)).

У вас будет очень мало промахов в кеше из-за смежности вектора в памяти и очень мало распределений (особенно если вы зарезервируете достаточное количество памяти в векторе).

Answer 3

Я сделал выбор времени с несколькими различными методами, которые, как я думал, были кандидатами. Победителем стал std::unordered_set.

Вот мои результаты:

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

Хронометраж основан на среднем пять трасс для каждого случая.

 
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 

Код:.

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