快速查找某个值是否存在于 C 数组中？

在性能至关重要的情况下，与手动调整的汇编语言相比，C 编译器很可能不会生成最快的代码。我倾向于走阻力最小的道路——对于像这样的小例程，我只是编写 asm 代码，并且很好地知道执行需要多少个周期。您可能能够摆弄 C 代码并让编译器生成良好的输出，但您最终可能会浪费大量时间以这种方式调整输出。编译器（尤其是来自 Microsoft 的）在过去几年中取得了长足的进步，但它们仍然不如你耳边的编译器那么聪明，因为你正在处理你的具体情况，而不仅仅是一般情况。编译器可能不会使用可以加快此速度的某些指令（例如 LDM），并且它不太可能足够聪明地展开循环。这是一种方法，它结合了我在评论中提到的 3 个想法：循环展开、缓存预取和使用多重加载 (ldm) 指令。每个数组元素的指令周期数约为 3 个时钟，但这并未考虑内存延迟。

操作原理：ARM 的 CPU 设计在一个时钟周期内执行大多数指令，但指令是在流水线中执行的。 C 编译器将尝试通过在其间交错其他指令来消除流水线延迟。当出现像原始 C 代码这样的紧密循环时，编译器将很难隐藏延迟，因为必须立即比较从内存中读取的值。我下面的代码在 2 组 4 个寄存器之间交替，以显着减少内存本身的延迟和获取数据的管道。通常，当处理大型数据集并且您的代码没有使用大部分或所有可用寄存器时，您将无法获得最佳性能。

; r0 = count, r1 = source ptr, r2 = comparison value

   stmfd sp!,{r4-r11}   ; save non-volatile registers
   mov r3,r0,LSR #3     ; loop count = total count / 8
   pld [r1,#128]
   ldmia r1!,{r4-r7}    ; pre load first set
loop_top:
   pld [r1,#128]
   ldmia r1!,{r8-r11}   ; pre load second set
   cmp r4,r2            ; search for match
   cmpne r5,r2          ; use conditional execution to avoid extra branch instructions
   cmpne r6,r2
   cmpne r7,r2
   beq found_it
   ldmia r1!,{r4-r7}    ; use 2 sets of registers to hide load delays
   cmp r8,r2
   cmpne r9,r2
   cmpne r10,r2
   cmpne r11,r2
   beq found_it
   subs r3,r3,#1        ; decrement loop count
   bne loop_top
   mov r0,#0            ; return value = false (not found)
   ldmia sp!,{r4-r11}   ; restore non-volatile registers
   bx lr                ; return
found_it:
   mov r0,#1            ; return true
   ldmia sp!,{r4-r11}
   bx lr

更新：评论中有很多怀疑者认为我的经历是轶事/毫无价值，需要证明。我使用 GCC 4.8（来自 Android NDK 9C）使用优化 -O2 生成以下输出（所有优化都打开，包括循环展开）。我编译了上面问题中提供的原始 C 代码。这是 GCC 产生的：

.L9: cmp r3, r0
     beq .L8
.L3: ldr r2, [r3, #4]!
     cmp r2, r1
     bne .L9
     mov r0, #1
.L2: add sp, sp, #1024
     bx  lr
.L8: mov r0, #0
     b .L2

GCC 的输出不仅不会展开循环，还会在 LDR 之后的停顿上浪费一个时钟。每个阵列元素至少需要 8 个时钟。它很好地使用了地址来知道何时退出循环，但是编译器能够做的所有神奇的事情在这段代码中都找不到。我没有在目标平台上运行代码（我没有），但是任何有 ARM 代码性能经验的人都可以看到我的代码更快。

更新 2：我让 Microsoft 的 Visual Studio 2013 SP2 有机会在代码上做得更好。它能够使用 NEON 指令对我的数组初始化进行矢量化，但是 OP 编写的线性值搜索与 GCC 生成的结果相似（我重命名了标签以使其更具可读性）：

loop_top:
   ldr  r3,[r1],#4  
   cmp  r3,r2  
   beq  true_exit
   subs r0,r0,#1 
   bne  loop_top
false_exit: xxx
   bx   lr
true_exit: xxx
   bx   lr

正如我所说，我不拥有 OP 的确切硬件，但我将在 3 个不同版本的 nVidia Tegra 3 和 Tegra 4 上测试性能，并很快在此处发布结果。

更新 3：我在 Tegra 3 和 Tegra 4（Surface RT、Surface RT 2）上运行了我的代码和 Microsoft 编译的 ARM 代码。我运行了 1000000 次循环迭代，但未能找到匹配项，因此所有内容都在缓存中并且很容易测量。

             My Code       MS Code
Surface RT    297ns         562ns
Surface RT 2  172ns         296ns  

在这两种情况下，我的代码运行速度几乎是原来的两倍。大多数现代 ARM CPU 可能会给出类似的结果。

---

有一个优化它的技巧（我在一次工作面试中被问到这个）：

如果数组中的最后一个条目包含您要查找的值，则返回 true

将您要查找的值写入数组的最后一个条目

迭代数组，直到遇到要查找的值

如果在数组的最后一个条目之前遇到过，则返回 true

返回假

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    uint32_t x = theArray[SIZE-1];
    if (x == compareVal)
        return true;
    theArray[SIZE-1] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    theArray[SIZE-1] = x;
    return i != SIZE-1;
}

这样每次迭代产生一个分支，而不是每次迭代产生两个分支。

更新：

如果允许您将数组分配给 SIZE+1，那么您可以摆脱“最后一个条目交换”部分：

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    theArray[SIZE] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    return i != SIZE;
}

您还可以去掉 theArray[i] 中嵌入的额外算术，改用以下代码：

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t *arrayPtr;
    theArray[SIZE] = compareVal;
    for (arrayPtr = theArray; *arrayPtr != compareVal; arrayPtr++);
    return arrayPtr != theArray+SIZE;
}

如果编译器还没有应用它，那么这个函数肯定会这样做。另一方面，它可能会使优化器更难展开循环，因此您必须在生成的汇编代码中验证...

---

保持表格排序，并使用 Bentley 展开的二进制搜索：

i = 0;
if (key >= a[i+512]) i += 512;
if (key >= a[i+256]) i += 256;
if (key >= a[i+128]) i += 128;
if (key >= a[i+ 64]) i +=  64;
if (key >= a[i+ 32]) i +=  32;
if (key >= a[i+ 16]) i +=  16;
if (key >= a[i+  8]) i +=   8;
if (key >= a[i+  4]) i +=   4;
if (key >= a[i+  2]) i +=   2;
if (key >= a[i+  1]) i +=   1;
return (key == a[i]);

重点是，

如果您知道表有多大，那么您就知道会有多少次迭代，因此您可以完全展开它。

然后，在每次迭代中对 == 情况进行测试是没有意义的，因为除了最后一次迭代之外，这种情况的概率太低，无法证明花时间测试它是合理的。**

最后，通过将表格扩展为 2 的幂，您最多可以添加一个比较，最多可以添加两倍的存储空间。

** 如果您不习惯用概率来思考，那么每个决策点都有一个熵，它是您通过执行它学到的平均信息。对于 >= 测试，每个分支的概率约为 0.5，-log2(0.5) 为 1，这意味着如果您选择一个分支，您将学习 1 位，如果您选择另一个分支，您将学习 1 位，平均值就是你在每个分支上学到的知识乘以该分支的概率的总和。所以 1*0.5 + 1*0.5 = 1，所以 >= 测试的熵是 1。因为你有 10 位要学习，所以需要 10 个分支。这就是为什么它很快！

另一方面，如果您的第一个测试是 if (key == a[i+512) 怎么办？为真的概率为 1/1024，而为假的概率为 1023/1024。因此，如果这是真的，您将学习所有 10 位！但如果它是假的，你会学到 -log2(1023/1024) = .00141 位，几乎什么都没有！因此，您从该测试中学到的平均数量是 10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112 位。 大约百分之一。该测试无法承受它的重量！

---

您正在寻求优化算法的帮助，这可能会将您推向汇编程序。但是你的算法（线性搜索）不是那么聪明，所以你应该考虑改变你的算法。例如：

完美的哈希函数

二分查找

完善的哈希函数

如果您的 256 个“有效”值是静态的并且在编译时已知，那么您可以使用 perfect hash function。您需要找到一个哈希函数，将您的输入值映射到 0..n 范围内的值，其中您关心的所有有效值都没有冲突 .也就是说，没有两个“有效”值散列到相同的输出值。在搜索一个好的散列函数时，您的目标是：

保持哈希函数相当快。

最小化 n。你能得到的最小值是 256（最小的完美哈希函数），但这可能很难实现，具体取决于数据。

请注意，对于高效的散列函数，n 通常是 2 的幂，相当于低位的按位掩码（AND 运算）。示例哈希函数：

输入字节的 CRC，以 n 为模。

((x << i) ^ (x >> j) ^ (x << k) ^ ...) % n （根据需要选择尽可能多的 i、j、k、...，左移或右移）

然后制作一个包含 n 个条目的固定表，其中哈希将输入值映射到表中的索引 i。对于有效值，表条目 i 包含有效值。对于所有其他表条目，请确保索引 i 的每个条目都包含其他一些不会散列到 i 的无效值。

然后在您的中断程序中，输入 x：

将 x 散列到索引 i（在 0..n 范围内） 在表中查找条目 i 并查看它是否包含值 x。

这将比线性搜索 256 或 1024 个值快得多。

我已经 written some Python code 找到了合理的散列函数。

二进制搜索

如果您对包含 256 个“有效”值的数组进行排序，则可以执行 binary search，而不是线性搜索。这意味着您应该能够只用 8 个步骤 (log2(256)) 搜索 256 个条目的表，或者用 10 个步骤搜索一个 1024 个条目的表。同样，这将比线性搜索 256 或 1024 个值快得多。

---

如果事先知道表中的一组常量，则可以使用 perfect hashing 确保只对表进行一次访问。完美的散列确定了一个散列函数，它将每个有趣的键映射到一个唯一的槽（该表并不总是密集的，但您可以决定您可以承受的表的不密集程度，密度较低的表通常会导致更简单的散列函数）。

通常，特定键集的完美散列函数相对容易计算；您不希望它冗长而复杂，因为这会争夺时间，也许最好花在进行多次探测上。

完美散列是一种“1-probe max”方案。人们可以概括这一想法，认为应该用计算哈希码的简单性与进行 k 次探测所需的时间进行权衡。毕竟，目标是“最少的总查找时间”，而不是最少的探测或最简单的哈希函数。但是，我从未见过有人构建 k-probes-max 散列算法。我怀疑有人可以做到，但这可能是研究。

另一种想法：如果您的处理器非常快，那么从完美哈希中对内存的一次探测可能会主导执行时间。如果处理器不是很快，那么 k>1 探针可能是实用的。

---

使用哈希集。它将给 O(1) 查找时间。

以下代码假定您可以将值 0 保留为“空”值，即不会出现在实际数据中。如果情况并非如此，则可以扩展该解决方案。

#define HASH(x) (((x >> 16) ^ x) & 1023)
#define HASH_LEN 1024
uint32_t my_hash[HASH_LEN];

int lookup(uint32_t value)
{
    int i = HASH(value);
    while (my_hash[i] != 0 && my_hash[i] != value) i = (i + 1) % HASH_LEN;
    return i;
}

void store(uint32_t value)
{
    int i = lookup(value);
    if (my_hash[i] == 0)
       my_hash[i] = value;
}

bool contains(uint32_t value)
{
    return (my_hash[lookup(value)] == value);
}

在这个示例实现中，查找时间通常会非常短，但在最坏的情况下可能会达到存储的条目数。对于实时应用程序，您还可以考虑使用二叉树的实现，这将具有更可预测的查找时间。

---

在这种情况下，可能值得研究 Bloom filters。他们能够快速确定某个值不存在，这是一件好事，因为 2^32 个可能的值中的大多数都不在该 1024 元素数组中。但是，有一些误报需要额外检查。

由于您的表显然是静态的，因此您可以确定您的 Bloom 过滤器存在哪些误报，并将它们放入完美的哈希中。

---

假设您的处理器以 204 MHz 运行，这似乎是 LPC4357 的最大值，并且还假设您的时序结果反映了平均情况（遍历的阵列的一半），我们得到：

CPU频率：204兆赫

周期：4.9 ns

周期持续时间：12.5 µs / 4.9 ns = 2551 个周期

每次迭代的周期：2551 / 128 = 19.9

因此，您的搜索循环每次迭代花费大约 20 个周期。这听起来并不可怕，但我想为了让它更快，你需要查看程序集。

我建议删除索引并改用指针比较，并将所有指针设为 const。

bool arrayContains(const uint32_t *array, size_t length)
{
  const uint32_t * const end = array + length;
  while(array != end)
  {
    if(*array++ == 0x1234ABCD)
      return true;
  }
  return false;
}

这至少值得测试。

---

其他人建议重新组织您的表，在末尾添加一个标记值，或对其进行排序以提供二进制搜索。

您说“我还使用指针算术和 for 循环，它进行向下计数而不是向上计数（检查 i != 0 是否比检查 i < 256 更快）。”

我的第一个建议是：摆脱指针算术和递减计数。像这样的东西

for (i=0; i<256; i++)
{
    if (compareVal == the_array[i])
    {
       [...]
    }
}

对编译器来说往往是惯用的。循环是惯用的，循环变量上的数组索引是惯用的。使用指针算术和指针将倾向于混淆编译器的习语，并使其生成与您编写的内容相关的代码，而不是编译器编写者决定作为一般任务的最佳课程的代码。

例如，上面的代码可能被编译成一个循环，从 -256 或 -255 运行到零，索引 &the_array[256]。可能是在有效的 C 语言中甚至无法表达但与您为其生成的机器的体系结构相匹配的东西。

所以不要微优化。您只是将扳手扔进优化器的工作中。如果您想变得聪明，请研究数据结构和算法，但不要对其表达进行微优化。它会回来咬你，如果不是在当前的编译器/架构上，那么在下一个。

特别是使用指针算法而不是数组和索引对于编译器完全了解对齐、存储位置、别名注意事项和其他内容以及以最适合机器架构的方式进行强度降低等优化是有害的。

---

向量化可以在这里使用，因为它经常在 memchr 的实现中使用。您使用以下算法：

创建重复查询的掩码，长度等于操作系统的位数（64 位、32 位等）。在 64 位系统上，您将重复 32 位查询两次。一次将列表处理为多条数据的列表，只需将列表转换为更大数据类型的列表并提取值即可。对于每个块，将其与掩码异或，然后与 0b0111...1 异或，然后加 1，然后 & 与 0b1000...0 的掩码重复。如果结果为 0，则肯定不匹配。否则，可能（通常以非常高的概率）匹配，因此正常搜索块。

实施示例：https://sourceware.org/cgi-bin/cvsweb.cgi/src/newlib/libc/string/memchr.c?rev=1.3&content-type=text/x-cvsweb-markup&cvsroot=src

---

如果您可以使用应用程序可用的内存量来容纳值的域，那么最快的解决方案是将您的数组表示为位数组：

bool theArray[MAX_VALUE]; // of which 1024 values are true, the rest false
uint32_t compareVal = 0x1234ABCD;
bool validFlag = theArray[compareVal];

编辑

我对批评者的数量感到震惊。这个帖子的标题是“我如何快速找到一个值是否存在于 C 数组中？”我会坚持我的回答，因为它正是回答了这个问题。我可以争辩说这具有最高效的哈希函数（因为地址 === 值）。我已经阅读了评论，并且知道明显的警告。毫无疑问，这些警告限制了它可以用来解决的问题的范围，但是，对于它确实解决的那些问题，它可以非常有效地解决。

与其直接拒绝这个答案，不如将其视为最佳起点，您可以通过使用散列函数在此基础上进行改进，以在速度和性能之间取得更好的平衡。

---

如果我的答案已经被回答，我很抱歉 - 只是我是一个懒惰的读者。那么请随意投反对票））

1）你可以完全删除计数器'i' - 只需比较指针，即

for (ptr = &the_array[0]; ptr < the_array+1024; ptr++)
{
    if (compareVal == *ptr)
    {
       break;
    }
}
... compare ptr and the_array+1024 here - you do not need validFlag at all.

尽管所有这些都不会带来任何重大改进，但这种优化可能可以由编译器本身来实现。

2）正如其他答案已经提到的那样，几乎所有现代CPU都是基于RISC的，例如ARM。据我所知，即使是现代的英特尔 X86 CPU 在内部也使用 RISC 内核（从 X86 即时编译）。 RISC 的主要优化是流水线优化（对于 Intel 和其他 CPU 也是如此），最大限度地减少代码跳转。一种此类优化（可能是主要优化）是“循环回滚”一种。这是非常愚蠢和高效的，即使是英特尔编译器也可以做到这一点 AFAIK。看起来像：

if (compareVal == the_array[0]) { validFlag = true; goto end_of_compare; }
if (compareVal == the_array[1]) { validFlag = true; goto end_of_compare; }
...and so on...
end_of_compare:

这种方式的优化是管道在最坏的情况下不会被破坏（如果数组中没有 compareVal），所以它尽可能快（当然不计算哈希表、排序数组等算法优化，在其他答案中提到，这可能会根据数组大小给出更好的结果。顺便说一下，循环回滚方法也可以在那里应用。我在这里写的是我认为我在其他人中没有看到的）

该优化的第二部分是该数组项由直接地址获取（在编译阶段计算，请确保使用静态数组），并且不需要额外的 ADD op 来从数组的基地址计算指针。这种优化可能没有显着效果，因为 AFAIK ARM 架构具有加速阵列寻址的特殊功能。但无论如何，最好知道你直接在 C 代码中做了所有最好的事情，对吧？

由于 ROM 的浪费，循环回滚可能看起来很尴尬（是的，如果您的主板支持此功能，您将它放置到 RAM 的快速部分是正确的），但实际上它是基于 RISC 概念的公平支付速度。这只是计算优化的一般要点 - 您为了速度而牺牲空间，反之亦然，具体取决于您的要求。

如果您认为 1024 个元素的数组的回滚对您的情况来说牺牲太大，您可以考虑“部分回滚”，例如将数组分成 2 部分，每部分 512 项，或 4x256，等等。

3) 现代 CPU 通常支持 SIMD 操作，例如 ARM NEON 指令集 - 它允许并行执行相同的操作。坦率地说，我不记得它是否适合比较操作，但我觉得可能是，你应该检查一下。谷歌搜索显示可能还有一些技巧，以获得最大速度，请参阅 https://stackoverflow.com/a/5734019/1028256

我希望它能给你一些新的想法。

---

这更像是一个附录而不是一个答案。

过去我也遇到过类似的情况，但我的数组在相当多的搜索中保持不变。

其中一半，搜索的值不存在于数组中。然后我意识到我可以在进行任何搜索之前应用“过滤器”。

这个“过滤器”只是一个简单的整数，计算一次并在每次搜索中使用。

它在 Java 中，但非常简单：

binaryfilter = 0;
for (int i = 0; i < array.length; i++)
{
    // just apply "Binary OR Operator" over values.
    binaryfilter = binaryfilter | array[i];
}

因此，在进行二进制搜索之前，我检查了 binaryfilter：

// Check binaryfilter vs value with a "Binary AND Operator"
if ((binaryfilter & valuetosearch) != valuetosearch)
{
    // valuetosearch is not in the array!
    return false;
}
else
{
    // valuetosearch MAYBE in the array, so let's check it out
    // ... do binary search stuff ...

}

您可以使用“更好”的哈希算法，但这可能非常快，特别是对于大数字。也许这可以为您节省更多的周期。

---

确保指令（“伪代码”）和数据（“theArray”）位于单独的 (RAM) 存储器中，以便充分利用 CM4 哈佛架构。从用户手册：

https://i.stack.imgur.com/uqKk4.png

为了优化 CPU 性能，ARM Cortex-M4 具有用于指令（代码）（I）访问、数据（D）访问和系统（S）访问的三个总线。当指令和数据保存在单独的存储器中时，代码和数据访问可以在一个周期内并行完成。当代码和数据保存在同一内存中时，加载或存储数据的指令可能需要两个周期。

按照这个指南，我观察到了大约 30% 的速度增加（在我的例子中是 FFT 计算）。

---

我是哈希的忠实粉丝。问题当然是找到一种既快速又使用最少内存（尤其是在嵌入式处理器上）的有效算法。

如果您事先知道可能出现的值，您可以创建一个程序，通过多种算法运行以找到最佳算法 - 或者更确切地说，为您的数据找到最佳参数。

我创建了一个您可以在 this post 中阅读的程序，并取得了一些非常快的结果。 16000 个条目大致转换为 2^14 或 14 次比较的平均值，以使用二进制搜索查找值。我明确的目标是非常快速的查找 - 平均找到 <=1.5 查找中的值 - 这导致更大的 RAM 需求。我相信使用更保守的平均值（比如 <=3）可以节省大量内存。相比之下，对 256 或 1024 个条目进行二进制搜索的平均情况将分别导致平均比较次数为 8 次和 10 次。

我的平均查找需要大约 60 个周期（在带有英特尔 i5 的笔记本电脑上）使用通用算法（使用一个除以变量）和 40-45 个周期使用专用算法（可能使用乘法）。这应该转化为 MCU 上的亚微秒查找时间，当然取决于它执行的时钟频率。

如果条目数组跟踪条目被访问的次数，它可以在现实生活中进一步调整。如果在计算索引之前对条目数组从访问次数最多到最少进行排序，那么它将通过一次比较找到最常出现的值。

---