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

Question

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

127

我有一个嵌入式应用程序，其中有一个时间关键的ISR需要遍历一个大小为256（最好是1024，但256是最小值）的数组，并检查是否匹配数组内容。如果匹配，则会将bool设置为true。

微控制器是NXP LPC4357，ARM Cortex M4内核，编译器是GCC。我已经使用了组合优化级别2（3更慢）并将函数放置在RAM而不是flash中。我还使用了指针算术和一个for循环，该循环进行递减计数而不是递增计数（检查i！=0比检查i<256要快）。总体而言，我得到了12.5 µs的持续时间，必须大幅缩短以实现可行性。这是我现在使用的（伪）代码：

uint32_t i;
uint32_t *array_ptr = &theArray[0];
uint32_t compareVal = 0x1234ABCD;
bool validFlag = false;

for (i=256; i!=0; i--)
{
    if (compareVal == *array_ptr++)
    {
         validFlag = true;
         break;
     }
}

有什么绝对最快的方法来做这件事？允许使用内联汇编。其他“不太优雅”的技巧也是可以的。

- wlamers

28

有没有办法用不同的方式存储数组中的值？如果可以将它们排序，二分查找肯定会更快。如果要存储和搜索的数据在一定范围内，它们可能可以用位图表示等等。 - Remo.D

20

@BitBank：你会惊讶于编译器在过去三十年里的巨大进步。特别是ARM，非常适合编译器。我确信至少从2009年开始，在GCC上的ARM可以发出多重加载指令。 - MSalters

8

太棒的问题，人们忘记了真实世界中性能很重要的情况。太多时候像这样的问题被回答为“只需使用STL”。 - Kik

14

标题“...遍历数组”是误导性的，因为实际上您只是在搜索给定的值。遍历数组意味着需要在每个条目上执行某些操作。如果成本可以分摊到多次搜索中，则排序确实是一种有效的方法，独立于语言实现问题。 - hardmath

8

你确定不能简单地使用二分查找或哈希表吗？256项的二分查找只需8次比较。哈希表平均只需要1次跳转（如果你有完美的哈希，则最多只需要1次跳转）。仅当你1）拥有体面的搜索算法（O（1）或O（logN），相对于O（N）），并且2）已经进行了性能分析，发现它是瓶颈时，才应该求助于汇编优化。 - vgru

显示剩余15条评论

15个回答

88

优化它的技巧（我曾在一次面试中被问到）：

如果数组中的最后一个条目包含您要查找的值，则返回true
将您要查找的值写入数组中的最后一个条目
迭代数组，直到遇到您要查找的值
如果在数组中的最后一个条目之前遇到它，则返回true
返回false

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;
}

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

- barak manos

2

@ratchetfreak：OP没有提供关于数组的分配和初始化的任何细节，因此我给出了一个不依赖于这些细节的答案。 - barak manos

3

数组在内存中，虽然不允许写入。 - wlamers

2

@EOF：问题中哪里提到了const？ - barak manos

4

如果我将一个数组和一个值传递给你，并问这个值是否在数组中，我通常不会假设你会修改这个数组。原始问题既没有提到“const”，也没有提到线程，但我认为提及这个警告是合理的。 - EOF

1

我来澄清一下我的意思：假设两个线程同时（或并发）在同一个数组中搜索两个不同的值。现在，它们都试图修改最后一个值（或者你想要写入超出数组末尾的哨兵值[顺便说一句，你甚至需要分配一个+1大小的数组才能这样做，否则行为未定义]），然后砰，就相当于其中一个线程中的非空结尾字符串。 - EOF

显示剩余18条评论

65

保持表格有序，并使用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 位。大约是一百分之一位。 这个测试不值得。

- Mike Dunlavey

5

我非常喜欢这个解决方案。如果值的位置是敏感信息，可以修改它以在固定数量的周期内运行，从而避免基于时间的取证。 - OregonTrail

1

@OregonTrail：基于时间的取证？有趣的问题，但悲伤的评论。 - Mike Dunlavey

17

在加密库中，我们会看到像这样展开循环的代码，以防止时序攻击（Timing Attacks）。这是一个很好的例子：https://github.com/jedisct1/libsodium/blob/e06ae6db9d843dd9614d34bc1a55977a6a403c3f/src/libsodium/crypto_verify/32/ref/verify_32.c 。在这种情况下，我们可以通过这种方式来防止攻击者猜测字符串的长度。通常，攻击者会取数百万次函数调用的样本来执行时序攻击。 - OregonTrail

1

@OregonTrail：我赞同你的基于时间的评论。我不止一次地编写了在固定数量的周期内执行的加密代码，以避免泄露信息给基于时间的攻击。 - TonyK

63

您正在寻求优化算法的帮助，这可能会推动您使用汇编语言。但是您的算法（线性搜索）并不是那么聪明，所以您应该考虑更改您的算法。例如：

完美哈希函数

如果您的256个“有效”值在编译时是静态和已知的，则可以使用完美哈希函数。您需要找到一个哈希函数，将输入值映射到范围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 个值进行线性搜索要快得多。

我已经编写了一些 Python 代码来找到合理的哈希函数。

二分查找

如果您对 256 个“有效”值的数组进行排序，那么您可以进行二分查找而不是线性搜索。这意味着您应该能够在只有 8 步（log2(256)）内搜索 256 个条目的表，或者在 10 步内搜索 1024 个条目的表。同样，这比对 256 或 1024 个值进行线性搜索要快得多。

- Craig McQueen

谢谢。我选择了二分查找选项。请参见第一篇帖子中的早期评论。这样做非常好，而且不需要使用汇编语言。 - wlamers

11

在尝试优化代码（例如使用汇编或其他技巧）之前，您应该先看看能否降低算法复杂度。通常降低算法复杂度要比试图省略几个周期但保持相同的算法复杂度更加有效。 - ysdx

一个流行的观点是，找到一个高效的哈希例程需要太多的努力，因此“最佳实践”是二分查找。然而有时，“最佳实践”并不足够好。假设你正在动态路由网络流量，此时数据包的头部已经到达（但不包括有效载荷）：使用二分查找会使你的产品变得无比缓慢。嵌入式产品通常具有这样的限制和要求，即在例如x86执行环境中的“最佳实践”在嵌入式中是“走捷径”。 - Olof Forshell

16

如果您的表中常量集是预先已知的，您可以使用完美哈希来确保只对该表进行一次访问。完美哈希确定一个哈希函数，将每个有趣的键映射到唯一的插槽（该表并不总是稠密的，但您可以决定您能承受多少不稠密的表格，较不稠密的表格通常会导致更简单的哈希函数）。

通常，特定键集的完美哈希函数相对容易计算；您不希望它过长和复杂，因为这会与执行多个探测所用的时间相竞争。

完美哈希是“最多1次探测”的方案。人们可以推广这个想法，并思考应该用计算哈希码的简单性来交换进行k次探测所需的时间。毕竟，目标是“查找的总时间最短”，而不是最少的探测或最简单的哈希函数。然而，我从未见过有人构建k次探测最大哈希算法。我怀疑可以做到，但那可能需要进行研究。

还有一个想法：如果您的处理器非常快，则从完美哈希到内存的一次探测可能会占用执行时间的主导地位。如果处理器不是很快，那么进行k>1次探测可能是实际可行的。

- Ira Baxter

1

Cortex-M远远不算是“极快”的处理器。 - MSalters

2

实际上，在这种情况下，他根本不需要任何哈希表。他只想知道某个键是否在集合中，他不想将其映射到一个值。因此，如果完美的哈希函数将每个32位值映射到0或1，其中“1”可以定义为“在集合中”，那就足够了。 - David Ongaro

1

很好的观点，如果他可以获得一个完美的哈希生成器来产生这样的映射。但是，那将是“一个非常密集的集合”；我怀疑他能找到一个能够做到这一点的完美哈希生成器。他最好尝试获得一个完美的哈希，如果在集合中则产生某个常量K，否则产生任何K以外的值。我怀疑即使为后者获得完美的哈希也很难。 - Ira Baxter

@DavidOngaro 如果值在集合中，则 table [PerfectHash（value）] == value 返回1，如果不在集合中则返回0，并且有众所周知的方法来生成PerfectHash函数（请参见http://burtleburtle.net/bob/hash/perfect.html）。试图找到直接将集合中所有值映射为1并将不在集合中的所有值映射为0的哈希函数是一项愚蠢的任务。 - Jim Balter

@DavidOngaro：一个完美的哈希函数会有很多“误判”，也就是说，不在集合中的值会与集合中的值具有相同的哈希值。因此，您必须拥有一个表格，由哈希值索引，包含“在集合中”的输入值。因此，要验证任何给定的输入值，您需要（a）对其进行哈希；（b）使用哈希值进行表格查找；（c）检查表格中的条目是否与输入值匹配。 - Craig McQueen

显示剩余2条评论

14

使用哈希集合。它将提供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);
}

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

- jpa

3

这取决于需要执行多少次此查找才能使其有效。 - maxywb

1

嗯，查找可能会超出数组的末尾。而这种线性哈希具有高碰撞率 - 不可能获得O(1)。好的哈希集不是这样实现的。 - Jim Balter

@JimBalter 确实，代码并不完美。更像是一般的想法；本可以只指向现有的哈希集合代码。但考虑到这是一个中断服务例程，展示查找并不是非常复杂的代码可能会很有用。 - jpa

你应该修复它，使其包装 i。 - Jim Balter

完美哈希函数的关键在于它只进行一次探测。就这样。 - Ira Baxter

为什么i被标记为int？可能是因为编译器可以证明它保持非负（因此％HASH_LEN可以实现为＆（HASH_LEN-1）），但您可能会导致编译器发出考虑有符号余数语义的代码。 - Peter Cordes

11

在这种情况下，值得研究Bloom过滤器。它们能够快速判断一个值是否不存在，这是件好事，因为在那个1024元素数组中，有可能出现2^32个可能的值中的大多数都不在其中。然而，还有一些误报需要进行额外检查。

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

- MSalters

8

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

CPU频率：204 MHz
周期时间：4.9 ns
持续时间（周期数）：12.5微秒/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;
}

这至少值得测试一下。

- unwind

1

-1，ARM具有索引地址模式，因此这是无意义的。至于使指针“const”，GCC已经发现它不会改变。const也没有添加任何内容。 - MSalters

11

@MSalters，好的，我没有用生成的代码进行验证，重点是表达一些在C语言级别上使其更简单的东西，而且我认为仅管理指针而不是一个指针和一个索引确实更简单。我完全不同意"const没有添加任何元素"这一观点：它非常清楚地告诉读者该值不会改变。这是非常有用的信息。 - unwind

9

这是深度嵌入的代码；到目前为止，已经进行了一些优化，包括将代码从闪存移动到RAM。然而，它仍然需要更快的速度。此时，可读性不是目标。 - MSalters

1

@MSalters：“ARM具有索引地址模式，因此这是无意义的”——好吧，如果你完全错过了重点……OP写道：“我还使用指针算术和for循环”。unwind没有用指针替换索引，他只是消除了索引变量，从而消除了每次循环迭代中的额外减法。但OP很明智（不像许多回答和评论的人），最终采用了二分查找。 - Jim Balter

7

其他人建议重新组织您的表格，在末尾添加哨兵值，或将其按顺序排序以提供二分查找。

您说：“我还使用指针算术和for循环，它采用向下计数而不是向上（检查i！= 0比检查i & lt;256 更快）。”

我的第一个建议是：放弃指针算术和向下计数。像这样的东西

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

循环语句和使用循环变量索引数组的方法通常是编译器的惯用法。而通过指针算术和指针操作，则会使编译器较难理解代码惯用法，从而生成与任务最佳处理方式无关的代码。有时，这些代码甚至无法在有效 C 语言中表达，但却适合正在生成代码的计算机架构。

因此，请勿过于微观地优化代码。过度优化只会让优化器出现问题。如果您想要提高代码效率，应该考虑数据结构和算法的优化而不是单纯的表达式优化。否则，这样做可能会对目前或未来的编译器/架构产生负面影响。

尤其是，使用指针算术来代替数组和索引会影响编译器全面认识到对齐、存储位置、别名考虑以及其他一些内容，并且不能最佳地利用机器架构实施强制规约等优化。

- user4015204

在C语言中，使用指针循环是惯用的方式，好的编译器可以像索引一样处理它们。但这整个问题都没有意义，因为OP最终进行了二分查找。 - Jim Balter

4

如果您可以将您的值域与应用程序可用的内存量相匹配，那么最快的解决方案是将数组表示为一组位：

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

编辑

我对批评者的数量感到惊讶。这个主题的标题是"如何快速查找C数组中是否存在一个值？"，我的回答恰好回答了这个问题。我可以争论这是最高效的哈希函数（因为地址 === 值）。我已经阅读了评论，并且我知道明显的注意事项。毫无疑问，这些注意事项限制了它可以用来解决的问题范围，但是对于它解决的那些问题，它解决得非常高效。

与其直接拒绝这个答案，不如将其视为最佳起点，通过使用哈希函数实现更好的速度和性能平衡来发展。

- Stephen Quan

8

这怎么会得到4个赞？问题说这是Cortex M4芯片，但实际上该芯片只有136KB的RAM，而不是262,144 KB。 - MSalters

1

令人震惊的是，因为回答者忽略了大局而明显错误的答案竟然获得了如此之多的点赞。对于问题中最大的情况来说，O(log n) 远小于 O(n)。 - msw

3

如果有更好的解决方案可供选择，但程序员们仍浪费大量内存，我会感到非常不爽。每隔5年，我的电脑似乎就会用尽内存，而在5年前，那个数量还绰绰有余。 - Craig McQueen

1

@CraigMcQueen 这些孩子们，浪费内存，太过分了！在我年轻的时候，我们只有1 MiB的内存和16位的字长。/s - Cole Tobin

2

严厉的批评家是怎么回事？OP明确表示速度对于代码的这一部分至关重要，而StephenQuan已经提到了“荒谬的内存量”。 - Bogdan Alexandru

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- BitBank · Accepted Answer

在对性能要求极高的情况下，与手写汇编相比，C编译器可能无法生成最快的代码。我倾向于采用最简易的方法 - 对于像这样的小程序，我只编写汇编代码，并且对执行所需的周期数有很好的了解。您可以尝试调整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：我给微软的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精确的硬件设备，但我将在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处理器可能会给出类似的结果。