3

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

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

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

有更好的方法吗？

一些重要的注意事项：

  • 主列表未排序，我不能浪费时间对其进行排序，这是整个项目施加的限制并重写它，因此列表始终排序不是一个选项（甚至可能不可能）
  • 内存不是问题，但越少越好
  • 我可以使用 STL，但不能提升
4

2 回答 2

2

好的，如果我绝对必须优化这个地狱，这就是我会做的。我假设顺序无关紧要，这似乎是您（IIUC）通过将它们与最后一个项目交换来删除项目的情况。

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

现在，这比使用现成的解决方案要多得多的工作和维护负担。除非这确实像您的描述中听起来那样对性能至关重要，否则我不会建议这样做。如果 C++11 是一个选项，并且您的编译器unordered_set很好，也许您应该使用它并省去大部分麻烦（但请注意，这可能会增加内存需求）。你仍然需要专门化std::hashand std::equal_toor operator==。替代提供您自己的Hash和KeyEqualfor unordered_set，但这可能不会提供任何好处。

于 2013-02-11T15:44:30.813 回答
1

有两件事可能会有所帮助。首先，至少对要移除的项目列表进行排序；这样，您可以std::lower_bounds对其使用二进制搜索 ( )。其次，保留两个指针：源和目标。如果源指向的内容不在要删除的列表中，请将其复制到目标，然后将两者都推进。如果源指向要删除的东西，只需推进源指针，不复制。永远不应该有理由多次复制条目。

于 2013-02-11T15:31:22.773 回答