用于多次搜索的 C++ 最快的数据结构

Question

用 C++ 编码。我需要一堆排序字符串的数据结构。我将一次性将所有字符串插入其中而不更新它，但我会经常搜索字符串。我只需要查看结构中是否存在给定字符串。我希望该列表大约有 100 个字符串。
什么是更快的结构？一开始我在考虑 hashmap 但我在某处看到对于如此少量的元素，对 vector 进行二分搜索会更好(因为它们已排序)。

Answer 1

假设您正在谈论“全尺寸”CPU1，至少相对于其他解决方案，即使只有 100 个元素，对字符串进行二进制搜索也可能会很慢。您可能会因每次搜索而遭受多次分支预测错误，并且最终可能会多次检查输入字符串中的每个字符(因为您需要在二分搜索中的每个节点重复 strcmp)。

正如有人已经指出的那样，唯一真正知道的方法是衡量 - 但要做到这一点，您仍然需要首先弄清楚候选人是什么!此外，并不总是可以在现实场景中进行测量，因为甚至可能不知道这样的场景(例如，想象一下，设计一个在许多不同情况下广泛使用的库函数)。

最后，了解什么可能是最快的可以让你排除你知道会表现不佳的候选人，并让你用你的直觉仔细检查你的测试结果:如果某些东西比你预期的慢得多，值得检查原因(编译器做一些愚蠢的事情)，如果某些事情要快得多，那么也许是时候更新您的直觉了。

所以我会尝试真正尝试一下什么是快速的——假设速度在这里真的很重要，你可以花一些时间来验证一个复杂的解决方案。作为基准，一个简单的实现可能需要 100 ns，而真正优化的可能需要 10 ns。因此，如果您为此花费 10 个小时的工程时间，则必须调用此函数 4000亿次只是为了赚回你的 10 小时 5。当您将错误风险、维护复杂性和其他开销考虑在内时，您将需要确保在尝试优化此函数之前调用了数万亿次。这种功能很少见，但肯定存在4。

也就是说，您遗漏了许多帮助设计非常快速的解决方案所需的信息，例如:

您对搜索功能的输入是 std::string或 const char *或者是其他东西？

平均和最大字符串长度是多少？

您的大部分搜索是成功还是失败？

你能接受一些误报吗？

这组字符串在编译时是否已知，或者您是否可以接受较长的初始化阶段？

上面的答案可以帮助您按如下所述划分设计空间。

布隆过滤器

如果按 (4) 您可以接受(可控)数量的误报 2，或根据 (3) 您的大部分搜索都不会成功，那么您应该考虑使用 Bloom Filter .例如，您可以使用 1024 位(128 字节)过滤器，并使用字符串的 60 位散列通过 6 个 10 位函数对其进行索引。这给出了 < 1% 的误报率。

这样做的好处是，在散列计算之外，它独​​立于字符串的长度，并且不依赖于匹配行为(例如，如果字符串趋于长，则依赖于重复字符串比较的搜索会变慢)常用前缀)。

如果您可以接受误报，那么您就完成了 - 但在您需要它始终正确但预计大多数搜索不成功的情况下，您可以将其用作过滤器:如果布隆过滤器返回 false(通常情况)，您就完成了，但如果它返回 true，您需要仔细检查下面讨论的始终正确的结构之一。所以常见的情况很快，但总是返回正确的答案。

完美哈希

如果在编译时已知这组 ~100 个字符串，或者您可以做一些一次性的繁重工作来预处理字符串，您可以考虑完美的散列。如果您有编译时已知的搜索集，您可以将字符串放入 gperf 它会吐出一个哈希函数和查找表。

例如，我只是将 100 个随机的英文单词 3 输入 gperf它生成了一个哈希函数，只需要查看两个字符即可唯一区分每个单词，如下所示:

static unsigned int hash (const char *str, unsigned int len)
{
  static unsigned char asso_values[] =
    {
      115, 115, 115, 115, 115,  81,  48,   1,  77,  72,
      115,  38,  81, 115, 115,   0,  73,  40,  44, 115,
       32, 115,  41,  14,   3, 115, 115,  30, 115, 115,
      115, 115, 115, 115, 115, 115, 115,  16,  18,   4,
       31,  55,  13,  74,  51,  44,  32,  20,   4,  28,
       45,   4,  19,  64,  34,   0,  21,   9,  40,  70,
       16,   0, 115, 115, 115, 115, 115, 115, 115, 115,
      /* most of the table omitted */
    };
  register int hval = len;

  switch (hval)
    {
      default:
        hval += asso_values[(unsigned char)str[3]+1];
      /*FALLTHROUGH*/
      case 3:
      case 2:
      case 1:
        hval += asso_values[(unsigned char)str[0]];
        break;
    }
  return hval;
}

现在，您的哈希函数很快，并且可能已得到很好的预测(如果您没有太多长度为 3 或更少的字符串)。要查找字符串，您只需索引哈希表(也由 gperf 生成)，并将得到的内容与输入字符串进行比较。

在一些合理的假设下，这将尽可能快 - clang生成这样的代码:

in_word_set:                            # @in_word_set
        push    rbx
        lea     eax, [rsi - 3]
        xor     ebx, ebx
        cmp     eax, 19
        ja      .LBB0_7
        lea     ecx, [rsi - 1]
        mov     eax, 3
        cmp     ecx, 3
        jb      .LBB0_3
        movzx   eax, byte ptr [rdi + 3]
        movzx   eax, byte ptr [rax + hash.asso_values+1]
        add     eax, esi
.LBB0_3:
        movzx   ecx, byte ptr [rdi]
        movzx   edx, byte ptr [rcx + hash.asso_values]
        cdqe
        add     rax, rdx
        cmp     eax, 114
        ja      .LBB0_6
        mov     rbx, qword ptr [8*rax + in_word_set.wordlist]
        cmp     cl, byte ptr [rbx]
        jne     .LBB0_6
        add     rdi, 1
        lea     rsi, [rbx + 1]
        call    strcmp
        test    eax, eax
        je      .LBB0_7
.LBB0_6:
        xor     ebx, ebx
.LBB0_7:
        mov     rax, rbx
        pop     rbx
        ret

这是大量代码，但具有合理数量的 ILP。关键路径是通过 3 个依赖的内存访问(在 char 中查找 str 值-> 在哈希函数表中查找 char 的哈希值-> 在实际哈希表中查找字符串)，你预计这通常需要 20 个周期(当然还有 strcmp 时间)。

特里

这个问题的“经典”compsci 解决方案是 trie .对于您的问题，trie 可能是一种合理的方法，尤其是在前几个字符内可以快速拒绝许多不成功的匹配(这在很大程度上取决于匹配集的内容和您正在检查的字符串)。

您需要一个快速的尝试实现来完成这项工作。总的来说，我觉得这种方法会受到串行相关内存访问的限制——每个节点都可能以一种指针追逐方法被访问，所以你会受到 L1 访问延迟的影响。

优化 strcmp
以上几乎所有的解决方案都依赖于 strcmp在某些时候 - 异常(exception)是布隆过滤器，它允许误报。所以你要确保这部分代码是快速的。

特别是编译器有时可能会内联 strcmp 的“内置”版本而不是调用库函数:在快速测试中 icc做了内联，但是 clang和 gcc选择调用库函数。对于哪个更快，没有简单的规则，但通常库例程通常经过 SIMD 优化，对于长字符串可能更快，而内联版本避免了函数调用开销，对于短字符串可能更快。您可以测试这两种方法，并且主要是强制编译器在您的情况下执行更快的操作。

更好的是，您可以利用对输入的控制来做得更好 - 例如，如果您可以确保输入字符串将被空填充，使其长度是 8 的倍数，那么您可以对哈希表(或任何其他结构)中的引用字符串执行相同操作，您可以一次比较字符串 8 个字节。这不仅大大加快了匹配速度，而且大大减少了分支错误预测，因为它本质上量化了循环行为(所有 1-8 个字符的字符串循环一次等)。

1 这里我指的是台式机、服务器、笔记本电脑 CPU，甚至现代智能手机 CPU，而不是嵌入式设备 MCU 或类似的东西。

2 允许误报意味着即使输入字符串不在集合中，如果您的“在集合中”有时也会返回 true，这也没关系。请注意，反过来它永远不会出错:当字符串在集合中时，它总是返回 true - 没有漏报。

3 具体来说， awk 'NR%990==0' /usr/share/dict/american-english > words .

4 例如，你做多少次 strcmp在计算史上被称为？如果它快 1 ns 会节省多少时间？

5 这在某种程度上将 CPU 时间与工程时间等同起来，这可能相差 1000 多倍:亚马逊 AWS 对 CPU 时间的收费大约为每小时 0.02 美元，而一名优秀的工程师可能预计每小时 50 美元(在第一个世界)。因此(非常粗略!)度量工程时间比 CPU 时间宝贵 2500 倍。因此，也许您需要 10 小时的工作所需的数万亿次电话才能获得返回...