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，但这可能没有任何好处。