你有多快能进行线性搜索？
我正在寻找优化这种线性搜索：
static int linear (const int *arr, int n, int key) { int i = 0; while (i = key) break; ++i; } return i; } 数组已排序，函数应返回大于或等于键的第一个元素的索引。 它们的数组不大（低于200个元素），并且会为大量搜索准备一次。 如果需要，可以在第n个之后将数组元素初始化为适当的数组，如果这样可以加快搜索速度。
不，不允许二进制搜索，只允许线性搜索。
编辑 ：我在博客文章中总结了有关此主题的所有知识。
- 告诉你的老板你可以把它提高50％，但需要6个月，还有一些钱。
- 等六个月。
- 购买新硬件。
好吧，它与通过排序数组进行线性搜索一样有意义！
（更严重的是，你能给我们一些关于为什么没有二分搜索的线索吗？）
到目前为止，您收到了多条建议，其中大多数建议说线性搜索对排序数据没有任何意义，因为二进制搜索将更有效地工作。 这通常恰好是那些不关心过度思考问题的人所做出的那些流行的“听起来正确”的断言之一。 实际上，如果考虑到更大的图景，在适当的情况下，线性搜索可以比二元搜索更有效。
请注意，如果我们考虑对排序数组进行单个搜索查询，则二进制搜索比线性搜索更有效。 对此没有任何争议。 此外，当您对同一数据执行多个完全随机的查询时，二进制搜索仍然胜过线性搜索。
但是，如果我们考虑顺序搜索查询并且这些查询不是完全随机的，那么图片就会开始改变。 想象一下，查询按排序顺序到达，即每个下一个查询的值都高于上一个查询。 即查询也被排序 。 顺便说一句，它们不必全局且严格排序，查询序列可能不时“重置”，即查询低值，但平均而言，后续查询应按递增顺序到达。 换句话说，查询按顺序到达，每个系列按升序排序。 在这种情况下，如果序列的平均长度与数组的长度相当，则线性搜索将大大优于二进制搜索。 但是，要利用这种情况，您必须以增量方式实现搜索。 很简单：如果下一个查询大于前一个查询，则无需从数组的开头开始搜索。 相反，您可以从上一次搜索停止的位置进行搜索。 最简单的实现（仅用于说明该想法）可能如下所示
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块 。 - 在接收到查询后，对可能包含查询值的S块执行增量线性搜索，即它是具有步幅
S的普通线性搜索（当然，记住从上一次搜索中断的块开始）。 - 找到S块后，在S块中执行二进制搜索以查询查询值。
以上是最优化的增量搜索算法，从某种意义上说，它实现了重复搜索的渐近效率的理论极限。 注意，如果M的值远小于N ，则算法“自动地”将其自身移向二分搜索，而当M接近N ，算法“自动地”有利于线性搜索。 后者是有道理的，因为在这样的环境中，线性搜索比二分搜索明显更有效。
这一切只是为了说明诸如“对排序数组进行线性搜索总是无用的”这样的一揽子陈述，除了表明这些陈述的人缺乏知识之外别无其他。
由于您可以在最后一个有效条目之后放置已知值，因此添加一个额外的元素n + 1 = max以确保循环不会超过数组的末尾，而不必测试i 您也可以尝试使用相同的sentinel值展开循环：
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; }
首先，任何快速解决方案都必须使用矢量化来同时比较多个元素。
但是，到目前为止发布的所有矢量化实现都存在一个常见问题：它们具有分支。 因此，他们必须引入arrays的块处理（以减少分支的开销），这导致小arrays的低性能。 对于大型arrays，线性搜索比优化良好的二进制搜索更糟糕，因此优化它没有意义。
但是，线性搜索可以在没有分支的情况下实现。 这个想法很简单：你想要的索引正是数组中元素的数量少于你搜索的键。 因此，您可以将数组的每个元素与键值进行比较，并将所有标志相加：
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实现，它不应该真正影响整体性能。
我在英特尔酷睿2双核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万个arrays（每秒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
最后，我想指出，只要间隔变小，就可以通过切换到所描述的矢量化线性搜索来更快地优化二进制搜索。
更新：有关此事的博客文章中可以找到更多信息。
如果特定于目标的解决方案是可以接受的，那么您可以非常轻松地使用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，其中密钥位于arrays的中点（即result = n / 2）。 当n变大并且arrays因此超过高速缓存大小（在这种情况下可能变为内存带宽限制）时，性能下降到大约3.5x 。 当n很小时，性能也会下降，这是由于SIMD实现效率低下（当然，它针对大n进行了优化）。
您已收到许多改进建议，但您需要测量每个优化，以确定哪个最适合您的硬件和编译器 。
作为一个例子，在这个响应的第一个版本中，我猜测，通过100-200个数组元素，二进制搜索的略高开销应该很容易通过少量探测数据来支付。 但是，在下面的评论中，Mark Probst报告说他看到线性搜索在他的硬件上提前约500个条目。 这增强了在搜索最佳性能时进行测量的必要性。
注意 ：在Mark的评论下面编辑了他对线性与二元搜索相比较小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的设备 ：
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; }
如果你有一台量子计算机，你可以使用Grover算法在O（N 1/2 ）时间内搜索你的数据并使用O（log N）存储空间。 否则，你的问题很愚蠢。 二进制搜索或其中一种变体（例如三元搜索）确实是您的最佳选择。 当你可以选择一个优秀的算法时，对线性搜索进行微优化是很愚蠢的。
展开固定数组索引。
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; }
您可以避免类似于循环展开的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 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; }
Sentinel搜索的巨大改进是它的迭代只使用一个条件分支（key）而不是两个（index和key）。
while (arr[i] != key) ++i;
向后循环，这可能会被翻译……
// loop backward for (int i = arraySize - 1; i >=0; --i)
……对此（“可能”更快）：
mov cx, arraySize - 1 detectionHere: ... loop detectionHere
除此之外，只有二进制搜索才能使搜索更快
这可能会强制向量指令（由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
您可以一次搜索比int更大的元素 – 具体来说，平台可以更快或更慢，具体取决于它如何处理更大的数据读取。 例如，在64位系统上，一次读取数组2个元素并单独检查高/低元素可以由于较少的I / O而更快地运行。 不过，无论如何，这都是O（n）种类。
这个答案比我的另一个更加模糊，所以我将它单独发布。 它依赖于C保证布尔结果false = 0和true = 1的事实。 X86可以生成没有分支的布尔值，所以它可能更快，但我还没有测试过。 像这样的微优化将始终高度依赖于您的处理器和编译器。
和以前一样，调用者负责在数组末尾放置一个sentinel值，以确保循环终止。
确定最佳循环展开量需要一些实验。 你想找到减少（或消极）回报的点。 我打算参加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指出的那样，此函数在前面一行的每一行中引入了一个依赖项，这限制了处理器管道并行运行操作的能力。 因此，让我们尝试对函数进行一些小修改以删除依赖项。 现在该function确实需要最后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; }
实际上，这个问题的答案完全依赖于您编写代码的平台。 例如：
CPU : Memory speed | Example CPU | Type of optimisation ======================================================================== Equal | 8086 | (1) Loop unrolling ------------------------------------------------------------------------ CPU > RAM | Pentium | (2) None
- 避免循环访问数据所需的条件分支将略微提高性能。
- 一旦CPU开始变得比RAM快，那么循环的效率并不重要（除非它是一个非常糟糕的循环），由于必须等待从RAM引入数据，它将停止运行。 SIMD并没有真正帮助，因为必须等待更多数据到达才能超越并行测试的优势。 当你的CPU受限时，SIMD真正发挥作用。
In one of the comments you said the array length is 64.
Well if you must do it linearly, you can do:
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);
However, I seriously doubt if that is faster than this binary search: *
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;
*Thanks to Jon Bentley for that one.
Added: since you said this table is prepared once for a large number of searches, and you want fast , you could allocate some space somewhere and generate machine code with the values hard-wired into it. It could either be linear or binary search. If binary, the machine code would look like what the compiler would generate from this:
if (key < value32){ if (key < value16){ ... } else { ... } } else { if (key < value48){ ... } else { ... } }
Then you just copy that into a place where you can call it.
OR you could print the code above, compile and link it on the fly into a dll, and load the dll.
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; }
Well, you could use pointers…
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; }