存储唯一值的容器是什么？

Question

我有以下问题.我的游戏平均每秒运行60帧.我需要在容器中存储值的每个帧,并且必须没有重复.

它可能每帧存储少于100个项目,但插入调用的数量将更多(许多被拒绝,因为它必须是唯一的).只有在框架的末尾,我才需要遍历容器.因此每帧约60次迭代容器,但插入的次数更多.

请记住,要存储的项目是简单的整数.

我可以使用一堆容器,但我无法决定选择什么.性能是关键问题.

我收集的一些优点/缺点:

---

向量

• (专业):有条件的记忆,一个巨大的因素.
• (PRO):可以先保留内存,然后再进行很少的分配/解除分配
• (CON):除了遍历容器(std :: find)每个insert()以找到唯一键之外别无选择？虽然比较很简单(整数),但整个容器可能适合缓存

组

• (专业):简单,显然意味着这一点
• (CON):不是恒定的插入时间
• (CON):每帧有很多分配/解除分配
• (CON):没有重点记忆.遍历一组数百个对象意味着在内存中跳转很多.

unordered_set

• (专业):简单,显然意味着这一点
• (PRO):平均情况常数时间插入
• (CON):看作我存储整数,哈希操作可能比其他任何东西都要贵
• (CON):每帧有很多分配/解除分配
• (CON):没有重点记忆.遍历一组数百个对象意味着在内存中跳转很多.

---

由于内存访问模式,我倾向于使用向量路由,即使set明显是针对此问题的.我不清楚的一个大问题是,遍历每个插入的向量是否比分配/解除分配(特别是考虑必须这样做的频率)和set的内存查找更昂贵.

我知道最终这一切都归结为每个案例的分析,但如果不是作为一个头脑或理论上,在这种情况下可能最好的是什么？我可能会错过任何优点/缺点吗？

编辑:正如我没有提到的,容器在每帧结束时被清除()

Answer 1

我要把我的脖子放在这里的块上,并建议当大小为100并且存储的对象是整数值时,向量路径可能是最有效的.原因很简单,set和unordered_set为每个插入分配内存,而向量不需要多于一次.

您可以通过保持向量排序来显着提高搜索性能,因为所有搜索都可以是二进制搜索,因此在log2N时间内完成.

缺点是由于内存移动,插入将花费更长的时间,但听起来好像会有比插入更多的搜索,并且移动(平均)50个连续的内存字几乎是瞬时操作.

最后一句话:现在写出正确的逻辑.当用户抱怨时担心性能.

编辑:因为我无法自助,这是一个相当完整的实现:

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

我用一些我认为可能候选的不同方法做了计时.使用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";
}