我需要从uint64-> [uint64列表]进行映射(每个哈希表的列表长度是恒定的)。

我尝试通过两种方式使用google::dense_hash_map:

1. google::dense_hash_map<uint64, std::array<uint64, 10>, Hash64> //10 for example
2. google::dense_hash_map<uint64, std::vector<uint64>, Hash64>
(1)比(2)快得多(3倍)。问题是,我不想在编译时定义数组的大小,但是在定义哈希映射时,还有其他选择吗?

我的大部分操作都在修改哈希表中的值,有时我会擦除所有元素,以便可以使用相同的已分配内存。

最佳答案

您可以尝试使用一些内存池来避免动态分配,并获得更紧凑的(对缓存友好的)内存使用率。这是一个非常简单的示例解决方案,与boost::dense_hash_map一起适用于我:

template <typename T>
class pooled_rt_array {
   public:
      static void init_pool(size_t capacity) {
         pool_.resize(capacity);
         top_ = pool_.data();
      }

      pooled_rt_array() : data_(top_), size_(0) { }

      pooled_rt_array(size_t size) : data_(top_), size_(size) {
         assert(top_ + size <= pool_.data() + pool_.size()); // not safe, in fact
         top_ += size;
      }

      T & operator[](size_t n) { return *(data_ + n); }
      const T & operator[](size_t n) const { return *(data_ + n); }
      size_t size() const { return size_; }

   private:
      T * data_;
      size_t size_;

      static std::vector<T> pool_;
      static T * top_;
};

template <typename T>
std::vector<T> pooled_rt_array<T>::pool_;

template <typename T>
T * pooled_rt_array<T>::top_;

一个简单的用法:
int main() {
    using value_t = pooled_rt_array<uint64_t>;
    google::hash_dense_map<uint64_t, value_t
       /* , std::hash<uint64_t>, std::equal_to<uint64_t> */
    > m;
    m.set_empty_key(0xFFFFFFFFFFFFFFFF);

    size_t n;
    std::cin >> n;
    value_t::init_pool(1000000 * n); // pool for 1000000 arrays
    value_t a(n);
    for (size_t i = 0; i < a.size(); i++) a[i] = i;
    m[0] = std::move(a);
}

我也做了一些基准测试,这比在 map 中存储std::vector快得多。

如果所有数组的大小都相同,您甚至可以从size_中删除pooled_rt_array成员变量,这将使其实例具有单个指针的大小。

请注意,有很多更复杂的方法来使用内存池,例如Boost提供的方法。例如,您可以使用一些特殊的池感知分配器,并将它们与std::vector一起使用。

10-05 20:26
查看更多