0

我有兴趣了解 multi_index_container 在以下用例中的性能：

struct idx_1 {};
struct idx_2 {};

typedef multi_index_container<
    Object,
    indexed_by<
      // Keyed by: idx1
      hashed_unique<
        tag<idx_1>,
        unique_key >,
      // Keyed by: (attribute1, attribute2 and attribute3)
      ordered_non_unique<
        tag<idx_2>,
        composite_key<
          Object,
          attribute1,
          attribute2,
          attribute3 > >
    >
  > ObjectMap;

我需要一张地图来保存对象，对象的数量应该在 300,000 以上。而每个对象都有 1 个唯一键和 3 个属性。钥匙详情：

  1. 唯一键是“唯一”作为名称
  2. 每个属性只有几个可能的值，比如只有 16 种组合。因此，对于 300,000 个对象，每个组合将有一个包含 300,000/16 个对象的列表
  3. attribute1 偶尔需要从一个值修改为另一个值
  4. 对象查找总是通过 unique_key 完成，而 composite_key 用于迭代具有一个或多个属性的对象

对于这样的用例，multi_index_container 非常适合，因为我不需要独立维护多个地图。对于唯一键部分，我相信 hashed_unique 是一个很好的候选者，而不是 ordered_unique。

但我对“ordered_non_unique”部分非常不舒服。我不知道如何在 boost 中实现。我猜它提升了在单个列表中为类似于 unordered_map 的每个组合维护一个对象列表（如果它太天真，请原谅我！）。如果是这种情况，修改现有对象的属性将是一个很大的痛苦，因为它需要 1) 为特定组合检查一长串对象 2) 执行相等比较 3) 并移动目标组合。

我怀疑具有高延迟的步骤：

ObjectMap objects_;
auto& by_idx1 = objects_.get<idx1>();
auto it = by_idx1.find(some_unique_key);
Object new_value;
by_idx1.modify(it, [&](const Object& object) {
  object = new_value;
});

我担心的是，最后一个“修改”函数是否有一些线性行为，如所说的在一个组合下通过一些潜在的长对象列表......

4

2 回答 2

0

正如法比奥所说，您最好的选择是分析案例并查看结果。无论如何，ordered_non_unique索引是完全按照 a 来实现的std::multimap，即通过常规的 rb-tree 实现，前提是允许具有等效键的元素在容器中共存；没有等效元素或任何东西的列表。至于modify（对于您的特定用例replace更合适），执行以下过程：

  • 检查元素是否到位：O(1)。
  • 如果不是，请重新排列：O(log n)，对于 300,000 个元素，最多可进行 19 个元素比较（不是您建议的 300,000/16=18,750）：这些比较是按字典顺序在三元组 ( attribute1, attribute2, attribute3) 上完成的。这是否足够快？好吧，这取决于您的性能要求，因此只有分析才能真正说明问题。
于 2014-10-23T16:30:56.400 回答
0

由于这是一段非常具体的代码，我建议您使用大量真实数据对其进行基准测试和分析。

于 2014-10-23T14:46:15.343 回答