快速find一个值是否存在于C数组中？
我有一个embedded式应用程序，其中包含一个对时间要求严格的ISR，需要遍历256个数组（最好是1024，但最less为256），并检查一个值是否与数组内容匹配。 一个bool将被设置为true是这样的。 MCU是恩智浦LPC4357，ARM Cortex M4内核，编译器是GCC。 我已经组合了优化级别2（3慢），并将其放入RAM而不是闪存。 我也使用指针算术和for循环，而不是向下计数（检查i!=0是否快于检查i<256 ）。 总而言之，我最终需要12.5us的时间，这个时间必须大大缩短才行。 这是我现在使用的（伪）代码：
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; } }
什么是绝对最快的方法来做到这一点？ 使用内联汇编是允许的。 其他“不太优雅的”技巧也是允许的。
在性能至关重要的情况下，与手动调整汇编语言相比，C编译器很可能不会产生最快的代码。 我倾向于采取阻力最小的path – 对于这样的小例程，我只是写asm代码，并有一个好主意，要执行多less个周期。 您可能可以摆弄C代码，并让编译器生成良好的输出，但最终可能会浪费大量时间调整输出。 编译器（特别是来自微软）在过去的几年中已经走过了很长的一段路，但是它们仍然不像编译器那么聪明，因为你正在研究你的具体情况而不仅仅是一般情况。 编译器可能不会使用某些可以加快速度的指令（如LDM），而且不太可能足够聪明来展开循环。 这里有一个方法来实现它，它包含了我在我的评论中提到的3个想法：循环展开，caching预取和使用多重加载（ldm）指令。 每个数组元素的指令周期数大约为3个时钟，但是这并没有考虑到内存延迟。
操作原理： ARM的CPUdevise在一个时钟周期内执行大部分指令，但指令是在一个stream水线中执行的。 C编译器将尝试通过在其间交错其他指令来消除stream水线延迟。 当像原来的C代码一样呈现紧密循环时，编译器将很难隐藏延迟，因为必须立即比较从内存读取的值。 我下面的代码在两组4个寄存器之间交替，以显着减less存储器本身的延迟以及获取数据的stream水线。 一般来说，当处理大型数据集并且代码没有使用大部分或全部可用寄存器时，那么您没有获得最高的性能。
; 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
更新：评论中有很多怀疑者认为我的经验是轶事/毫无价值的，需要certificate。 我使用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
海湾合作委员会的输出不仅没有展开循环，而且在LDR之后也浪费了一个时钟。 每个数组元素至less需要8个时钟。 它在使用地址知道何时退出循环方面做得很好，但是所有这些神奇的东西编译器都有能力做的事情在这个代码中找不到。 我没有在目标平台上运行代码（我没有自己的代码），但是在ARM代码性能方面有经验的人可以看到我的代码更快。
更新2：我给了微软的Visual Studio 2013 SP2一个更好的代码机会。 它能够使用NEON指令来向量化我的数组初始化，但OP所写的线性值search与GCC生成的线性值search类似（我将标签重命名为使其更易读）：
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上testing性能，并在不久之后发布结果。
更新3：我在Tegra 3和Tegra 4（Surface RT，Surface RT 2）上运行我的代码和微软编译的ARM代码。 我跑了1000000次循环，无法find匹配的循环，因此所有内容都在caching中，而且很容易测量。
My Code MS Code Surface RT 297ns 562ns Surface RT 2 172ns 296ns
在这两种情况下，我的代码几乎运行两倍。 大多数现代的ARM CPU可能会给出类似的结果。
有一个技巧来优化它（我曾经在一次工作面试中被问到过）：
- 如果数组中的最后一个条目包含您正在查找的值，则返回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; }
你也可以使用下面的代码去除embedded在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; }
如果编译器还没有应用它，那么这个函数肯定会这样做。 另一方面，它可能会使优化器难以展开循环，因此您将不得不validation在生成的汇编代码中…
你正在寻求帮助优化你的algorithm，这可能会推动你的汇编。 但是你的algorithm（线性search）不是那么聪明，所以你应该考虑改变你的algorithm。 例如：
- 完美的散列函数
- 二进制search
完美的散列函数
如果你的256个“有效”值在编译时是静态的，那么你可以使用一个完美的哈希函数 。 您需要find一个散列函数，将您的input值映射到范围为0 … n的值，其中不存在所有您关心的有效值的冲突 。 也就是说，没有两个“有效”的值散列到相同的输出值。 当search一个好的散列函数时，你的目标是：
- 保持哈希函数合理快速。
- 最小化 你可以得到的最小值是256（最小完美散列函数），但这可能很难实现，这取决于数据。
注意高效散列函数， n通常是2的幂，相当于低位的位掩码（AND操作）。 哈希函数示例：
- input字节的CRC，模n 。
-
((x << i) ^ (x >> j) ^ (x << k) ^ ...) % n（根据需要select多个i，j，k，…，左移或右移）
然后你制作一个固定的n个表格条目，其中散列将input值映射到索引i到表格中。 对于有效值，表项i包含有效值。 对于所有其他表项，请确保索引i的每个条目都包含一些其他无效值，这些值不会散列到i 。
然后在你的中断程序中，inputx ：
- 散列x到索引i （范围在0..n）
- 在表中查找条目i ，看它是否包含值x 。
这将比256或1024的线性search快得多。
我写了一些Python代码来find合理的散列函数。
二进制search
如果你sorting你的256个“有效”值的数组，那么你可以做一个二分search ，而不是一个线性search。 这意味着你应该能够以8个步骤（ log2(256) ）search256条目表，或者以10个步骤search1024条目表。 再次，这将比256或1024值的线性search快得多。
按sorting顺序保留表格，并使用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]);
重点是，
- 如果你知道表有多大，那么你知道有多less次迭代，所以你可以完全展开它。
- 那么，在每次迭代时都没有必要testing
==情况，因为除了最后一次迭代，这种情况的可能性太低，无法花时间testing它。 - 最后，通过将表扩展到2的幂，最多添加一个比较，最多添加两个存储的因子。
**如果你不习惯用概率来思考，那么每个决策点都有一个熵 ，这是你通过执行它所学到的平均信息。 对于>=testing，每个分支的概率大约是0.5，而-log2（0.5）是1，所以这意味着如果你拿一个分支你学习1位，如果你拿另一个分支学习一个位，平均值只是您在每个分支上学到的总和乘以该分支的概率。 所以1*0.5 + 1*0.5 = 1 ，所以>= test的熵是1.因为你有10位学习，它需要10个分支。 这就是为什么它快！
另一方面，如果你的第一个testing是if (key == a[i+512) ？ 真实的概率是1/1024，而假的概率是1023/1024。 所以如果这是真的，你会学习所有的10位！ 但如果这是错误的，你会学到-log2（1023/1024）= 0.00141位，几乎没有任何东西！ 所以你从这个testing中学到的平均数量是10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112位。 大约百分之一。 那个testing没有承受它的重量！
如果事先知道表中的常量集合，则可以使用完美的散列函数来确保对表格只进行一次访问。 完美散列决定了一个散列函数，它把每一个有趣的键映射到一个独特的槽（这个表并不总是密集的，但是你可以决定一个表的密度是多么的不密集，通常密度较小的表通常导致更简单的散列函数）。
通常，特定的一组密钥的完美散列函数相对容易计算; 你不希望这样做会很漫长和复杂，因为这可能会花费更多的时间进行多次探测。
完美的哈希是“最大1个探针”scheme。 人们可以概括这个想法，认为应该简单地计算哈希码和制作k个探针所花费的时间。 毕竟，目标是“最less的总时间来查找”，不是最less的探测器或最简单的散列函数。 但是，我从来没有见过任何人build立k-probes-max哈希algorithm。 我怀疑可以做到这一点，但这可能是研究。
另一个想法是：如果你的处理器速度非常快，那么从一个完美的散列到内存的一个探测可能主宰着执行时间。 如果处理器速度不是很快，那么k> 1的探头可能是实用的。
使用哈希集。 它会给O（1）查找时间。
以下代码假设您可以将值0保留为“空”值，即不会在实际数据中出现。 如果情况并非如此，解决scheme可以扩展。
#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); }
在这个示例实现中，查找时间通常非常低，但是在最坏的情况下可以达到存储的条目的数量。 对于实时应用程序，也可以考虑使用二叉树的实现，这将有更可预测的查找时间。
在这种情况下，调查布隆filter可能是值得的。 它们能够快速确定一个值不存在，这是一件好事，因为大多数2 ^ 32可能值不在该1024个元素数组中。 但是，有一些误报需要额外的检查。
由于你的表格显然是静态的，所以你可以确定你的布卢姆filter存在哪些误报，并把它们放在一个完美的散列表中。
假设你的处理器运行在204 MHz，这似乎是LPC4357的最大值，并且假设你的时序结果反映了平均情况（半个数组遍历），我们得到：
- CPU频率：204 MHz
- 周期：4.9 ns
- 周期持续时间：12.5μs/ 4.9 ns = 2551个周期
- 每次循环：2551/128 = 19.9
所以，你的search循环每次迭代花费大约20个周期。 这听起来不太可怕，但我想为了让它更快，你需要看看程序集。
我会build议删除索引，而不是使用指针比较，并使所有的指针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; }
这至less是值得的testing。
其他人build议重新组织你的表格，在最后添加一个标记值，或者对它进行sorting，以提供二分查找。
你声明：“我也使用指针算术和for循环，而不是向下计数（检查i != 0是否快于检查i < 256 ）。
我的第一个build议是：摆脱指针算术和减计数。 东西像
for (i=0; i<256; i++) { if (compareVal == the_array[i]) { [...] } }
往往是编译器的习惯用法 。 循环是惯用的，并且循环variables上的数组的索引是惯用的。 使用指针算术和指针进行杂乱的操作往往会混淆编译器的习惯用法，并使其生成与您所写的内容相关的代码，而不是编译器作者决定成为一般任务的最佳方法。
例如，上面的代码可能被编译成一个循环，从-256或-255运行到零，索引&the_array[256] 。 可能的东西，甚至不能用有效的C来表示，但是与您所生成的机器的体系结构相匹配。
所以不要微观优化。 你只是把扳手扔进你的优化器的作品。 如果你想变得聪明一点，那么就要研究数据结构和algorithm，但不要对expression式进行微观优化。 如果不是在当前的编译器/体系结构上，那么它会回来咬你，然后在下一个。
特别是使用指针算术而不是数组和索引对于编译器充分意识到alignment，存储位置，别名考虑和其他内容以及以最适合机器体系结构的方式进行强度降低等优化是毒害。
这里可以使用vector化，因为它通常是在memchr的实现中。 您使用以下algorithm：
-
创build一个重复的查询掩码，长度等于OS的位数（64位，32位等）。 在64位系统上，您可以重复32位查询两次。
-
将列表一次处理为多个数据列表，只需将列表强制转换为较大数据types的列表并将值拉出即可。 对于每个块，将其与掩码异或，然后与0b0111 … 1异或，然后加1，然后用掩码0b1000 … 0重复。 如果结果是0，肯定不匹配。 否则，可能（通常具有很高的可能性）匹配，因此通常search块。
示例实施： https : //sourceware.org/cgi-bin/cvsweb.cgi/src/newlib/libc/string/memchr.c?rev=1.3&content-type=text/x-cvsweb-markup&cvsroot=src
如果您可以使用您的应用程序可用内存量来容纳值的域，那么最快的解决scheme就是将您的数组表示为一个数组：
bool theArray[MAX_VALUE]; // of which 1024 values are true, the rest false uint32_t compareVal = 0x1234ABCD; bool validFlag = theArray[compareVal];
编辑
批评者的数量令我感到震惊。 这个线程的标题是“我如何快速find一个值是否存在于C数组？ 对此，我会坚持我的回答，因为它正是答案。 我可以争辩说，这是最有效的哈希函数（因为地址===值）。 我已经阅读了评论，我知道这些明显的警告。 毫无疑问，这些警告限制了可以用来解决的问题的范围，但是对于它解决的那些问题，它解决得非常有效。
不要直接拒绝这个答案，而应该把它看作是通过使用散列函数来达到更好的速度和性能平衡的最佳起点。
对不起，如果我的答案已经得到解答 – 只是我是一个懒惰的读者。 感觉自由了，然后downvote））
1）你可以删除计数器'我' – 只是比较指针，即
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的主要优化是pipe道优化（以及英特尔和其他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:
这样优化就是在最坏的情况下stream水线不会被破坏（如果compareVal在数组中是不存在的），所以它是尽可能快的（当然不包括哈希表，sorting数组等algorithm优化， mentioned in other answers, which may give better results depending on array size. Cycles Rollback approach can be applied there as well by the way. I'm writing here about that I think I didn't see in others)
The second part of this optimization is that that array item is taken by direct address (calculated at compiling stage, make sure you use a static array), and do not need additional ADD op to calculate pointer from array's base address. This optimization may not have significant effect, since AFAIK ARM architecture has special features to speed up arrays addressing. But anyway it's always better to know that you did all the best just in C code directly, right?
Cycle Rollback may look awkward due to waste of ROM (yep, you did right placing it to fast part of RAM, if your board supports this feature), but actually it's a fair pay for speed, being based on RISC concept. This is just a general point of calculation optimization – you sacrifice space for sake of speed, and vice versa, depending on your requirements.
If you think that rollback for array of 1024 elements is too large sacrifice for your case, you can consider 'partial rollback', for example dividing the array into 2 parts of 512 items each, or 4×256, and so on.
3) modern CPU often support SIMD ops, for example ARM NEON instruction set – it allows to execute the same ops in parallel. Frankly speaking I do not remember if it is suitable for comparison ops, but I feel it may be, you should check that. Googling shows that there may be some tricks as well, to get max speed, see https://stackoverflow.com/a/5734019/1028256
I hope it can give you some new ideas.
This is more like an addendum than an answer.
I've had a simillar case in the past, but my array was constant over a considerable number of searches.
In half of them, the searched value was NOT present in array. Then I realized I could apply a "filter" before doing any search.
This "filter" is just a simple integer number, calculated ONCE and used in each search.
It's in java, but it's pretty simple:
binaryfilter = 0; for (int i = 0; i < array.length; i++) { // just apply "Binary OR Operator" over values. binaryfilter = binaryfilter | array[i]; }
So, before do a binary search, I check 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 ... }
You can use a 'better' hash algorithm, but this can be very fast, specially for large numbers. May be this could save you even more cycles.
I'm a great fan of hashing. The problem of course is to find an efficient algorithm that is both fast and uses a minimum amount of memory (especially on an embedded processor).
If you know beforehand the values that may occur you can create a program that runs through a multitude of algorithms to find the best one – or, rather, the best parameters for your data.
I created such a program that you can read about in this post and achieved some very fast results. 16000 entries translates roughly to 2^14 or an average of 14 comparisons to find the value using a binary search. I explicitly aimed for very fast lookups – on average finding the value in <=1.5 lookups – which resulted in greater RAM requirements. I believe that with a more conservative average value (say <=3) a lot of memory could be saved. By comparison the average case for a binary search on your 256 or 1024 entries would result in an average number of comparisons of 8 and 10, respectively.
My average lookup required around 60 cycles (on a laptop with an intel i5) with a generic algorithm (utilizing one division by a variable) and 40-45 cycles with a specialized (probably utilizing a multiplication). This should translate into sub-microsecond lookup times on your MCU, depending of course on the clock frequency it executes at.
It can be real-life-tweaked further if the entry array keeps track of how many times an entry was accessed. If the entry array is sorted from most to least accessed before the indeces are computed then it'll find the most commonly occuring values with a single comparison.
