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

这里有一个优化它的技巧(我曾在一次求职面试中被问到过这个问题) :

• 如果数组中的最后一个条目包含您要查找的值，则返回 true
• 将要查找的值写入数组的最后一个条目中
• Iterate the array until you encounter the value that you're looking for
• 如果在数组的最后一个条目之前遇到它，则返回 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;
}

You can also get rid of the additional arithmetic embedded in theArray[i], using the following instead:

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

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

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

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

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

In this example implementation, the lookup time will typically be very low, but at the worst case can be up to the number of entries stored. For a realtime application, you can consider also an implementation using binary trees, which will have a more predictable lookup time.

如果事先知道表中的常量集，则可以使用 完美的散列确保只对表进行一次访问。完美散列确定散列函数 它将每个感兴趣的键映射到一个惟一的槽(该表并不总是稠密的，但是您可以决定您能够负担得起的稠密程度，而稠密程度较低的表通常会导致更简单的散列函数)。

通常情况下，特定键集的完美散列相对容易计算，你不会希望计算过程冗长复杂，因为这样会争取更多的时间来进行多个探测。

完美散列是一种“单探针 max”方案。我们可以概括这个想法，认为我们应该用制作 k 探测所需的时间来交换计算哈希代码的简单性。毕竟，目标是“最少的总查找时间”，而不是最少的探测或最简单的散列函数。然而，我从未见过有人构建一个 k 探针-max 哈希算法。我怀疑有人可以做到，但那很可能是研究。

另一个想法是: 如果您的处理器非常快，那么从一个完美散列到内存的一个探针可能会主导执行时间。如果处理器的速度不是很快，那么比 k > 1探针更实用。

In this case, it might be worthwhile investigating Bloom 过滤器. They're capable of quickly establishing that a value is not present, which is a good thing since most of the 2^32 possible values are not in that 1024 element array. However, there are some false positives that will need an extra check.

Since your table is apparently static, you can determine which false positives exist for your Bloom filter and put those in a perfect hash.

你正在寻求帮助优化你的算法，这可能会推动你汇编。但是您的算法(线性搜索)不是那么聪明，所以您应该考虑更改您的算法。例如:

• 完美散列
• 二进制搜索

完美散列

如果您的256个“有效”值是静态的并且在编译时已知，那么您可以使用 完美散列。您需要找到一个散列函数，它将您的输入值映射到范围0内的值。.n，其中不存在所有您关心的有效值的 碰撞。也就是说，没有两个“有效”值散列到相同的输出值。当搜索一个好的散列函数时，你的目标是:

• 保持哈希函数相当快。
• 尽量减少 N。你能得到的最小值是256(最小完美散列) ，但这可能很难实现，这取决于数据。

注意，对于有效的散列函数，n通常是2的幂，这相当于低位的按位掩码(AND 操作)。散列函数示例:

• 输入字节的 CRC，模 N。
• ((x << i) ^ (x >> j) ^ (x << k) ^ ...) % n(根据需要选择 i，j，k，... ，并进行左移或右移)

然后创建一个固定的 N条目表，其中散列将输入值映射到索引 我到该表中。对于有效值，表条目 我包含有效值。对于所有其他表条目，确保索引 我的每个条目包含一些其他无效值，这些无效值不会散列到 我。

然后在你的中断例程中，输入 X:

1. 散列 X索引 我(范围为0. . n)
2. 查找表中的条目 我，看看它是否包含值 x。

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

我使用 写了些 Python 代码来寻找合理的散列函数。

二进制搜索

如果对256个“有效”值的数组进行排序，那么可以执行 二进制搜索，而不是线性搜索。这意味着您只需要8个步骤(log2(256))就可以搜索256个条目表，或者10个步骤就可以搜索1024个条目表。同样，这将比线性搜索256或1024个值快得多。

如果你可以用 可用的内存量来适应你的应用程序的值域，那么，最快的解决方案就是把你的数组表示成一个比特数组:

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

剪辑

批评家的数量之多令我震惊。这个帖子的标题是 "How do I quickly find whether a value is present in a C array?"，我将坚持我的答案，因为它正好回答了这个问题。我可以说这个函数具有最快的散列函数(因为 address = = = value)。我看过评论，我知道一些明显的警告。毫无疑问，这些警告限制了它可以用来解决的问题的范围，但是，对于那些它确实解决的问题，它非常有效地解决了。

Rather than reject this answer outright, consider it as the optimal starting point for which you can evolve by using hash functions to achieve a better balance between speed and performance.

Keep the table in sorted order, and use Bentley's unrolled binary search:

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]);

重点是,

• if you know how big the table is, then you know how many iterations there will be, so you can fully unroll it.
• 然后，在每个迭代中都没有对 ==用例进行点测试，因为除了在最后一个迭代中，该用例的可能性太低，不值得花时间对其进行测试。**
• Finally, by expanding the table to a power of 2, you add at most one comparison, and at most a factor of two storage.

如果你不习惯用概率来思考问题，那么每个决策点都有一个 熵，这是你通过执行决策点得到的平均信息。 对于 >=测试，每个分支的概率大约是0.5,-log2(0.5)是1，这意味着如果你选择一个分支，你学习1位，如果你选择另一个分支，你学习1位，平均值就是你在每个分支上学习的总和乘以这个分支的概率。 所以 1*0.5 + 1*0.5 = 1，所以 >=测试的熵是1。因为你有10个比特要学，所以需要10个分支。 That's why it's fast!

另一方面，如果您的第一个测试是 if (key == a[i+512)呢？正确的概率是1/1024，而错误的概率是1023/1024。所以如果这是真的，你学会了所有的10位！ 但是如果它是错误的，那么您将学习 -log2(1023/1024) = .00141位，实际上什么也没有！ 所以你从这个测试中学到的平均值是 10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112比特 那个测试就是不承担它的重量！

这里可以使用向量化，因为在 memchr 的实现中经常使用这种方法:

1. Create a mask of your query repeating, equal in length to your OS'es bit count (64-bit, 32-bit, etc.). On a 64-bit system you would repeat the 32-bit query twice.

2. 一次将列表处理为多个数据块的列表，只需将列表转换为较大数据类型的列表并提取值即可。对于每个块，使用掩码进行 XOR，然后使用0b0111... 1进行 XOR，然后使用0b1000... 0重复的掩码添加1，然后 & 。如果结果为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

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

您声明“我还使用指针算法和 for 循环，它执行向下计数而不是向上(检查 i != 0是否比检查 i < 256快)。”

我的第一个建议是: 去掉指针算法和下降计数

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

对编译器来说倾向于是 成语。循环是惯用的，对循环变量上的数组进行索引是惯用的。与指针算法和指针的杂耍将倾向于 obfuscate的习惯用法编译器，使它生成代码相关的 你写什么，而不是编译器的编写者决定什么是最好的课程为一般的 task。

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

不要微优化。您只是将扳手投入到优化器的工作中。如果你想变得更聪明，那就研究一下数据结构和算法，但是不要对它们的表达式进行微优化。如果不是在当前的编译器/体系结构上，那么在下一个编译器/体系结构上，它只会反咬你一口。

特别是使用指针算法而不是数组和索引对于编译器来说是一种毒药，因为编译器需要完全意识到对齐、存储位置、别名注意事项和其他东西，并且需要以最适合机器架构的方式进行优化，比如强度降低。

I'm sorry if my answer was already answered - just I'm a lazy reader. Feel you free to downvote then ))

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.

all that won't give any significant improvement though, such optimization probably could be achieved by the compiler itself.

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 操作来从数组的基地址计算指针。这种优化可能没有明显的效果，因为 AFAIK ARM 架构具有加速阵列寻址的特殊功能。但是不管怎样，直接在 C 代码中做到最好总是更好的，对吗？

由于 ROM 的浪费，循环回滚可能看起来很笨拙(是的，如果你的电路板支持这个功能，你把它放在 RAM 的快速部分是正确的) ，但实际上这是一个公平的速度支付，基于 RISC 的概念。这只是计算优化的一个普遍要点——您为了速度而牺牲空间，反之亦然，这取决于您的需求。

如果您认为对于包含1024个元素的数组进行回滚对于您的情况来说牺牲太大，那么可以考虑“部分回滚”，例如将数组分成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];
}

因此，在进行二进制搜索之前，我检查了二进制过滤器:

// 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. 也许这能帮你节省更多的周期。

我是哈希的忠实粉丝。当然，问题是要找到一种既快又使用最少内存的高效算法(特别是在嵌入式处理器上)。

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.

我创建了这样一个程序，你可以在 这篇文章阅读，并取得了一些非常快的结果。16000个条目大致相当于2 ^ 14或平均14次比较，以便使用二进制搜索查找值。我的明确目标是非常快速的查找-平均在 < = 1.5查找中找到值-这导致更大的 RAM 需求。我相信使用更保守的平均值(比如 < = 3)可以节省大量内存。通过比较，对256个或1024个条目进行二进制搜索的平均情况将分别导致平均8个和10个比较。

我的平均查找需要大约60个周期(在笔记本电脑上使用 Intel i5)和一个通用算法(利用一个除以一个变量)和40-45个周期和一个专门的(可能利用乘法)。这应该转化为亚微秒查找时间在您的单片机，当然这取决于它执行的时钟频率。

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

确保指令(“伪代码”)和数据(“阵列”)在单独的(RAM)存储器中，以便 CM4哈佛架构得到充分利用。用户手册:

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

根据这个指导方针，我观察到了约30% 的速度增加(在我的例子中是 FFT 计算)。