c++ - 从一个巨大的列表中删除大量字符串

Question

我有一个大字符串列表存储在一个巨大的内存块中(通常有 100k+ 甚至 1M+)​​。这些实际上是散列，因此字符串的字母表仅限于 A-F0-9，并且每个字符串的长度恰好是 32 个字节(因此它存储为“压缩”)。从现在开始，我将把这个列表称为主列表。

我希望能够从主列表中删除项目。这通常是批量完成的，所以我得到一个很大的哈希列表(通常大约 100 到 10k)，我需要在这个列表中找到并删除它们。在此操作结束时，大内存块中不能有任何空 block ，因此我需要考虑到这一点。不能保证所有项目都会出现在主列表中，但不会多次出现。无法进行重定位，主 block 将始终保持相同大小。

简单的方法遍历主列表并检查是否应删除给定的哈希当然可行，但有点慢。小内存块的移动也有点太多，因为每次当一个散列被标记为要删除时，我都会用主列表的最后一个元素重写它，从而满足没有空 block 的条件。这当然会创建数以千计的小 memcpy ，这反过来又会减慢速度，因为我遇到了大量的缓存未命中。

有没有更好的方法？

一些重要的注意事项:

• 主列表没有排序，我不能浪费时间来排序，这个 是整个项目强加的限制并重写它所以 列表总是排序不是一个选项(它甚至可能不是 可能)
• 内存不是问题，但越少越好
• 我会用STL，但不会boost

Answer 1

好吧，如果我绝对必须对此进行优化，这就是我要做的。 我假设顺序无关紧要，这似乎是您 (IIUC) 通过将项目与最后一项交换来删除项目的情况。

• 存储 128 位整数(无论您如何表示它们，要么您的编译器本身支持它们，要么您使用 32/64 位整数的小型数组)而不是 32 字符字符串。请参阅我对该问题的评论。
• 滚动我自己的 128 位整数哈希集。请注意，如果您愿意稍微思考一下、做出一些假设并认真对待，您可以在此处优化很多。一些注意事项:
  • 您只需要存储哈希值本身(用于解决冲突)，以及一两个元数据来识别已删除/未使用的槽位。如果您不确定如何保证正确性，请查看现有哈希表的作用。我认为如果您只在构建哈希集后删除(而不是添加)，那就更简单了。虽然我认为如果您的值不是表示空槽的有效散列值，您甚至可以不使用该元数据，但这种方式删除更容易(只需翻转一点，而不是覆盖 128 位)。
  • 您不需要哈希函数，因为您的输入已经是整数。您只需要做每个哈希表无论如何都会做的事情:将哈希取模 2^n 来导出一个并不大的索引。选择 n 使得负载因子(使用的表条目的百分比)是合理的(< 2/3 似乎是标准的)。选择 的幂使得模运算成本更低(通过二进制 AND 屏蔽位)，并允许您仅在较低的 32 位或 64 位上执行(忽略其余位)。
  • 选择冲突解决策略很困难。我可能会选择 open addressing作为第一次尝试，使用线性探测。它可能效果不佳，但如果您的输入散列有任何好处，这似乎不太可能。还有一个探测方案，它考虑了越来越多的您最初切断的位，由 CPython's dict 使用。 .

现在，这比使用现成的解决方案要多得多的工作和维护负担。我不会建议它，除非这真的像您描述的那样对性能至关重要。 如果 C++11 是一个选项，并且您的编译器的 unordered_set 很好，也许您应该直接使用它并为自己省去大部分麻烦(但请注意，这可能会增加内存需求)。您仍然需要专门化 std::hash 和 std::equal_to 或 operator==。或者为 unordered_set 提供您自己的 Hash 和 KeyEqual，但这可能没有任何好处。