我正在寻找优化这个线性搜索：
static int
linear (const int *arr, int n, int key)
{
int i = 0;
while (i < n) {
if (arr [i] >= key)
break;
++i;
}
return i;
}
数组已排序，函数应该返回大于或等于键的第一个元素的索引。它们的数组不大（少于 200 个元素），并且会为大量搜索准备一次。如果需要，可以将第 n 个之后的数组元素初始化为适当的值，如果这样可以加快搜索速度。
不，不允许二分查找，只能线性查找。
编辑：我关于这个主题的所有知识现在都在这篇博文中进行了总结。
到目前为止，您收到了多条建议，其中大部分指出线性搜索对已排序的数据毫无意义，而二进制搜索将更有效地工作。这通常恰好是那些不愿过多考虑问题的人所做的流行的“听起来正确”的断言之一。实际上，如果您考虑更大的图景，在适当的情况下，线性搜索可能比二分搜索更有效。
请注意，如果我们考虑对排序数组进行单个搜索查询，则二进制搜索比线性搜索要有效得多。对此没有任何争论。此外，当您对同一数据执行多个完全随机的查询时，二分搜索仍然胜过线性搜索。
但是，如果我们考虑顺序搜索查询并且这些查询并不是完全随机的，那么情况就会开始改变。假设查询以排序顺序到达，即每个下一个查询的值都高于前一个查询。即查询也被排序。顺便说一句，它们不必是全局和严格排序的，有时查询序列可能会“重置”，即查询一个低值，但平均而言，后续查询应该以递增的顺序到达。换句话说，查询按系列到达，每个系列按升序排序。在这种情况下，如果序列的平均长度与数组的长度相当，线性搜索将优于二进制搜索的巨大优势。但是，要利用这种情况，您必须以增量方式实施搜索。很简单：如果下一个查询大于上一个，则不需要从数组的开头开始搜索。相反，您可以从先前搜索停止的点开始搜索。最简单的实现（只是为了说明这个想法）可能如下所示
static int linear(const int *arr, int n, int key)
{
static int previous_key = INT_MIN;
static int previous_i = 0;
i = key >= previous_key ? previous_i : 0;
while (i < n) {
if (arr[i] >= key)
break;
++i;
}
previous_key = key;
previous_i = i;
return i;
}
（免责声明：上述实现非常难看，原因很明显，数组作为参数从外部到达，而之前的搜索状态存储在内部。当然，在实践中这样做是错误的。但同样，以上旨在说明这个想法，仅此而已）。
O(N)请注意，无论序列的长度如何，使用上述方法处理每个有序查询序列的复杂度始终为 。使用二分查找，复杂度为O(M * log N). 因此，由于明显的原因，当M接近 时N，即查询以足够长的有序序列到达，上述线性搜索将显着优于二分搜索，而对于较小M的二分搜索将获胜。
此外，即使查询的有序序列不是很长，考虑到您必须使用线性搜索，上述修改仍可能会显着提高搜索性能。
PS作为关于问题结构的附加信息：
当您需要在长度的有序数组中执行搜索N并且您事先知道查询将以 [近似，平均] 长度的有序序列到达时M，最佳算法将如下所示
S = [N/M]。S将 的值“捕捉”到 2 的 [最近] 幂也可能有意义。将排序数组视为长度块的序列S- 所谓的 S-blocks。S（当然要记得从上一次搜索中断的block开始）。以上是可能的最优增量搜索算法，从某种意义上说，它达到了重复搜索的渐近效率的理论极限。请注意，如果 的值M比 小得多N，则算法“自动”转向二分搜索，而当M接近N算法时，“自动”倾向于线性搜索。后者是有道理的，因为在这种环境下，线性搜索比二分搜索效率高得多。
这一切只是为了说明这样一个事实，即“对排序数组进行线性搜索总是无用的”之类的笼统陈述仅表明做出此类陈述的人缺乏知识。
首先，任何快速解决方案都必须使用矢量化来一次比较多个元素。
但是，到目前为止发布的所有矢量化实现都存在一个共同问题：它们都有分支。结果，他们必须引入数组的块式处理（以减少分支的开销），这导致小型数组的性能低下。对于大型数组，线性搜索比优化好的二分搜索更糟糕，所以优化它没有意义。
然而，线性搜索完全可以在没有分支的情况下实现。这个想法很简单：您想要的索引正是数组中小于您搜索的键的元素数。因此，您可以将数组的每个元素与键值进行比较并对所有标志求和：
static int linear_stgatilov_scalar (const int *arr, int n, int key) {
int cnt = 0;
for (int i = 0; i < n; i++)
cnt += (arr[i] < key);
return cnt;
}
这个解决方案的一个有趣之处在于，即使你对数组进行洗牌，它也会返回相同的答案 =) 虽然这个解决方案似乎相当慢，但它可以优雅地矢量化。下面提供的实现要求数组是 16 字节对齐的。此外，数组必须用 INT_MAX 元素填充，因为它一次消耗 16 个元素。
static int linear_stgatilov_vec (const int *arr, int n, int key) {
assert(size_t(arr) % 16 == 0);
__m128i vkey = _mm_set1_epi32(key);
__m128i cnt = _mm_setzero_si128();
for (int i = 0; i < n; i += 16) {
__m128i mask0 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+0]), vkey);
__m128i mask1 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+4]), vkey);
__m128i mask2 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+8]), vkey);
__m128i mask3 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+12]), vkey);
__m128i sum = _mm_add_epi32(_mm_add_epi32(mask0, mask1), _mm_add_epi32(mask2, mask3));
cnt = _mm_sub_epi32(cnt, sum);
}
cnt = _mm_hadd_epi32(cnt, cnt);
cnt = _mm_hadd_epi32(cnt, cnt);
// int ans = _mm_extract_epi32(cnt, 0); //SSE4.1
int ans = _mm_extract_epi16(cnt, 0); //correct only for n < 32K
return ans;
}
只有在必要时才可以使用 SSE2 实现单个 SSE2 寄存器的最终缩减，它应该不会真正影响整体性能。
我已经在 Intel Core2 Duo E4700 上使用 Visual C++ 2013 x64 编译器对其进行了测试（很旧，是的）。使用 rand() 提供的元素生成大小为 197 的数组。包含所有测试的完整代码在这里。这是执行 32M 搜索的时间：
[OP]
Time = 3.155 (-896368640) //the original OP's code
[Paul R]
Time = 2.933 (-896368640)
[stgatilov]
Time = 1.139 (-896368640) //the code suggested
OP 的原始代码每秒处理 1060 万个数组（每秒 21 亿个元素）。建议的代码每秒处理 2950 万个数组（每秒 58 亿个元素）。此外，建议的代码适用于较小的数组：即使对于 15 个元素的数组，它仍然比 OP 的原始代码快近三倍。
这是生成的程序集：
$LL56@main:
movdqa xmm2, xmm4
movdqa xmm0, xmm4
movdqa xmm1, xmm4
lea rcx, QWORD PTR [rcx+64]
pcmpgtd xmm0, XMMWORD PTR [rcx-80]
pcmpgtd xmm2, XMMWORD PTR [rcx-96]
pcmpgtd xmm1, XMMWORD PTR [rcx-48]
paddd xmm2, xmm0
movdqa xmm0, xmm4
pcmpgtd xmm0, XMMWORD PTR [rcx-64]
paddd xmm1, xmm0
paddd xmm2, xmm1
psubd xmm3, xmm2
dec r8
jne SHORT $LL56@main
$LN54@main:
phaddd xmm3, xmm3
inc rdx
phaddd xmm3, xmm3
pextrw eax, xmm3, 0
最后，我想指出，只要间隔变小，就可以通过切换到所描述的向量化线性搜索来更快地进行优化的二分搜索。
更新：更多信息可以在我的博客文章中找到。
由于您可以在最后一个有效条目之后放置已知值，因此添加一个额外的元素 n+1 = max 以确保循环不会越过数组末尾而无需测试 i < n。
static int
linear (const int *arr, int n, int key)
{
assert(arr[n] >= key);
int i = 0;
while (arr[i] < key) {
++i;
}
return i;
}
您也可以尝试使用相同的标记值展开循环：
static int
linear (const int *arr, int n, int key)
{
assert(arr[n] >= key);
int i = 0;
while (true) {
if (arr [i++] >= key)
break;
if (arr [i++] >= key)
break;
if (arr [i++] >= key)
break;
if (arr [i++] >= key)
break;
}
return --i;
}
如果可以接受特定于目标的解决方案，那么您可以很容易地使用 SIMD（SSE、AltiVec 或任何可用的）通过一次测试 4 个元素而不是仅测试 1 个元素来获得约 4 倍的加速。
出于兴趣，我整理了一个简单的 SIMD 实现，如下所示：
int linear_search_ref(const int32_t *A, int32_t key, int n)
{
int result = -1;
int i;
for (i = 0; i < n; ++i)
{
if (A[i] >= key)
{
result = i;
break;
}
}
return result;
}
int linear_search(const int32_t *A, int32_t key, int n)
{
#define VEC_INT_ELEMS 4
#define BLOCK_SIZE (VEC_INT_ELEMS * 32)
const __m128i vkey = _mm_set1_epi32(key);
int vresult = -1;
int result = -1;
int i, j;
for (i = 0; i <= n - BLOCK_SIZE; i += BLOCK_SIZE)
{
__m128i vmask0 = _mm_set1_epi32(-1);
__m128i vmask1 = _mm_set1_epi32(-1);
int mask0, mask1;
for (j = 0; j < BLOCK_SIZE; j += VEC_INT_ELEMS * 2)
{
__m128i vA0 = _mm_load_si128(&A[i + j]);
__m128i vA1 = _mm_load_si128(&A[i + j + VEC_INT_ELEMS]);
__m128i vcmp0 = _mm_cmpgt_epi32(vkey, vA0);
__m128i vcmp1 = _mm_cmpgt_epi32(vkey, vA1);
vmask0 = _mm_and_si128(vmask0, vcmp0);
vmask1 = _mm_and_si128(vmask1, vcmp1);
}
mask0 = _mm_movemask_epi8(vmask0);
mask1 = _mm_movemask_epi8(vmask1);
if ((mask0 & mask1) != 0xffff)
{
vresult = i;
break;
}
}
if (vresult > -1)
{
result = vresult + linear_search_ref(&A[vresult], key, BLOCK_SIZE);
}
else if (i < n)
{
result = i + linear_search_ref(&A[i], key, n - i);
}
return result;
#undef BLOCK_SIZE
#undef VEC_INT_ELEMS
}
在 2.67 GHz Core i7 上，使用 OpenSUSE x86-64 和 gcc 4.3.2，我7x - 8x在一个相当广泛的“甜蜜点”周围得到了改进，其中 n = 100000，密钥位于阵列的中点（即结果 = n / 2)。3.5x当 n 变大并且数组因此超过缓存大小（在这种情况下可能成为内存带宽限制）时，性能下降到大约。由于 SIMD 实现的效率低下，当 n 较小时，性能也会下降（当然，它针对较大的 n 进行了优化）。
如果你有一台量子计算机，你可以使用Grover 算法在 O(N 1/2 ) 时间内搜索你的数据并使用 O(log N) 存储空间。否则，你的问题很愚蠢。二分搜索或其变体之一（例如三分搜索）确实是您的最佳选择。当您可以选择更好的算法时，对线性搜索进行微优化是愚蠢的。
如果您使用的是英特尔平台：
int linear (const int *array, int n, int key)
{
__asm
{
mov edi,array
mov ecx,n
mov eax,key
repne scasd
mov eax,-1
jne end
mov eax,n
sub eax,ecx
dec eax
end:
}
}
但这只会找到完全匹配，而不是大于或等于匹配。
在 C 中，您还可以使用Duff 的 Device：
int linear (const int *array, int n, int key)
{
const int
*end = &array [n];
int
result = 0;
switch (n % 8)
{
do {
case 0:
if (*(array++) >= key) break;
++result;
case 7:
if (*(array++) >= key) break;
++result;
case 6:
if (*(array++) >= key) break;
++result;
case 5:
if (*(array++) >= key) break;
++result;
case 4:
if (*(array++) >= key) break;
++result;
case 3:
if (*(array++) >= key) break;
++result;
case 2:
if (*(array++) >= key) break;
++result;
case 1:
if (*(array++) >= key) break;
++result;
} while(array < end);
}
return result;
}
您可以并行执行。
如果列表很小，那么拆分搜索可能不值得，但如果必须处理大量搜索，那么您可以明确地并行运行它们。这不会减少操作的延迟，但会提高吞吐量。
您收到了许多改进建议，但您需要衡量每项优化，以查看哪种优化最适合您的硬件和编译器。
作为一个例子，在这个响应的第一个版本中，我猜测通过 100-200 个数组元素，二进制搜索的稍高的开销应该很容易用更少的数组探测来支付。然而，在下面的评论中，Mark Probst 报告说他看到线性搜索在他的硬件上多达 500 个条目。这加强了在寻找最佳性能时进行测量的必要性。
注意：根据 Mark 在下面关于他对合理小 N 的线性与二进制搜索的测量的评论进行编辑。
我知道这个话题很老了，但我无法阻止自己发帖。我对前哨线性搜索的优化是：
int sentinel_linear_search(int key, int *arr, int n)
{
int last_value, i;
/* considering that n is the real size of the array */
if (--n < 1)
return -1;
last_value = arr[n];
/* set array last member as the key */
arr[n] = key;
i = 0;
while (arr[i] != key)
++i;
/* recover the real array last member */
arr[n] = last_value;
return (arr[i] == key) ? i : -1;
}
哨兵搜索的巨大改进在于它的迭代只使用了一个条件分支（键）而不是两个（索引和键）。
while (arr[i] != key)
++i;
您可以避免 n 检查类似于循环展开的方式
static int linear(const int *array, int arraySize, int key)
{
//assuming the actual size of the array is always 1 less than arraySize
array[arraySize] = key;
int i = 0;
for (; ; ++i)
{
if (array[i] == key) return i;
}
}
使用固定的数组索引展开。
int linear( const int *array, int n, int key ) {
int i = 0;
if ( array[n-1] >= key ) {
do {
if ( array[0] >= key ) return i+0;
if ( array[1] >= key ) return i+1;
if ( array[2] >= key ) return i+2;
if ( array[3] >= key ) return i+3;
array += 4;
i += 4;
} while ( true );
}
return -1;
}
这个答案比我的另一个更晦涩，所以我单独发布。它依赖于 C 保证布尔结果 false=0 和 true=1 的事实。X86 可以在没有分支的情况下生成布尔值，所以它可能会更快，但我还没有测试过。像这样的微优化将始终高度依赖于您的处理器和编译器。
和以前一样，调用者负责在数组末尾放置一个标记值，以确保循环终止。
确定循环展开的最佳量需要一些实验。您想找到收益递减（或负）的点。这次我要拿一个 SWAG 试试 8。
static int
linear (const int *arr, int n, int key)
{
assert(arr[n] >= key);
int i = 0;
while (arr[i] < key) {
i += (arr[i] < key);
i += (arr[i] < key);
i += (arr[i] < key);
i += (arr[i] < key);
i += (arr[i] < key);
i += (arr[i] < key);
i += (arr[i] < key);
i += (arr[i] < key);
}
return i;
}
编辑：正如 Mark 指出的那样，这个函数在每一行中引入了对前一行的依赖，这限制了处理器管道并行运行操作的能力。因此，让我们尝试对函数进行小修改以消除依赖关系。现在该功能确实需要 8 个标记元素。
static int
linear (const int *arr, int n, int key)
{
assert(arr[n] >= key);
assert(arr[n+7] >= key);
int i = 0;
while (arr[i] < key) {
int j = i;
i += (arr[j] < key);
i += (arr[j+1] < key);
i += (arr[j+2] < key);
i += (arr[j+3] < key);
i += (arr[j+4] < key);
i += (arr[j+5] < key);
i += (arr[j+6] < key);
i += (arr[j+7] < key);
}
return i;
}
您可以一次搜索比 int 更大的元素 - 特别是平台，这可能更快或更慢，具体取决于它如何处理更大的数据读取。例如，在 64 位系统上，一次读取数组 2 个元素并分别检查高/低元素可能会由于 I/O 较少而运行得更快。尽管如此，无论如何，这都是一个 O(n) 种类。
这可能会强制执行向量指令（由 Gman 建议）：
for (int i = 0; i < N; i += 4) {
bool found = false;
found |= (array[i+0] >= key);
...
found |= ( array[i+3] >= key);
// slight variation would be to use max intrinsic
if (found) return i;
}
...
// quick search among four elements
这也减少了分支指令。您可以通过确保输入数组与 16 字节边界对齐来提供帮助
另一件事可能有助于矢量化（进行垂直最大值比较）：
for (int i = 0; i < N; i += 8) {
bool found = false;
found |= max(array[i+0], array[i+4]) >= key;
...
found |= max(array[i+3], array[i+7] >= key;
if (found) return i;
}
// have to search eight elements
向后循环，这可能会被翻译...
// loop backward
for (int i = arraySize - 1; i >=0; --i)
...对此（“可能”更快）：
mov cx, arraySize - 1
detectionHere:
...
loop detectionHere
除此之外，只有二分查找才能使查找更快
uint32 LinearFindSse4( uint8* data, size_t data_len, uint8* finddata, size_t finddatalen )
{
/**
* the following is based on...
* #define haszero(v) (((v) - 0x01010101UL) & ~(v) & 0x80808080UL)
* we split it into 2 sections
* first section is:
* (v) - 0x01010101UL)
*
* second section is:
* ~(v) & 0x80808080UL)
*/
__m128i ones = _mm_set1_epi8( 0x01 );
__m128i eights = _mm_set1_epi8( 0x80 );
__m128i find_field = _mm_set1_epi8( finddata[0] );
uint32 found_at = 0;
for (int i = 0; i < data_len; i+=16)
{
#define CHECKTHIS( n ) if (!memcmp(&data[i+n], &finddata[0], sizeof(finddata))) { found_at = i + n; break; }
__m128i chunk = _mm_stream_load_si128( (__m128i *)&data[i] );
__m128i xor_result = _mm_xor_si128( chunk, find_field );
__m128i first_sec = _mm_sub_epi64( xor_result, ones );
__m128i second_sec = _mm_andnot_si128( xor_result, eights );
if(!_mm_testz_si128(first_sec, second_sec))
{
CHECKTHIS(0);
CHECKTHIS(1);
CHECKTHIS(2);
CHECKTHIS(3);
CHECKTHIS(4);
CHECKTHIS(5);
CHECKTHIS(6);
CHECKTHIS(7);
CHECKTHIS(8);
CHECKTHIS(9);
CHECKTHIS(10);
CHECKTHIS(11);
CHECKTHIS(12);
CHECKTHIS(13);
CHECKTHIS(14);
CHECKTHIS(15);
}
}
return found_at;
}
在您所说的其中一条评论中，数组长度为 64。
好吧，如果你必须线性地做，你可以这样做：
int i = -1;
do {
if (arr[0] >= key){i = 0; break;}
if (arr[1] >= key){i = 1; break;}
...
if (arr[62] >= key){i = 62; break;}
if (arr[63] >= key){i = 63; break;}
} while(0);
但是，我严重怀疑这是否比这种二进制搜索更快：*
int i = 0;
if (key >= arr[i+32]) i += 32;
if (key >= arr[i+16]) i += 16;
if (key >= arr[i+ 8]) i += 8;
if (key >= arr[i+ 4]) i += 4;
if (key >= arr[i+ 2]) i += 2;
if (key >= arr[i+ 1]) i += 1;
*感谢 Jon Bentley 的那个。
补充：既然你说这个表是为大量搜索准备的，并且你想要快速，你可以在某处分配一些空间并生成机器代码，其中包含硬连接到其中的值。它可以是线性搜索，也可以是二分搜索。如果是二进制的，机器代码看起来就像编译器从这个生成的：
if (key < value32){
if (key < value16){
...
}
else {
...
}
}
else {
if (key < value48){
...
}
else {
...
}
}
然后，您只需将其复制到您可以调用它的地方。
或者您可以打印上面的代码，即时编译并将其链接到 dll 中，然后加载 dll。
实际上，这个问题的答案 100% 取决于您为其编写代码的平台。例如：
CPU : Memory speed | Example CPU | Type of optimisation
========================================================================
Equal | 8086 | (1) Loop unrolling
------------------------------------------------------------------------
CPU > RAM | Pentium | (2) None
好吧，你可以使用指针...
static int linear(const int *array, int arraySize, int key) {
int i;
for(i = 0; i < arraySize; ++i) {
if(*array >= key) {
return i;
}
++array;
}
return arraySize;
}