二分查找位运算
Binary search bit operation
我想知道这两个实现中哪一个更快，为什么？
int N, A[N];
int binary_search(int val)
{
int i, step;
for (step = 1; step < N; step <<= 1)
;
for (i = 0; step; step >>= 1)
if (i + step < N && A[i + step] <= val)
i += step;
}
和一个正常的实现，你找到 mid=(st+dr)/2 然后根据 A[mid] 的值和你的值应用到数组的左侧或右侧？
伪代码到C代码的转换
该问题询问的代码片段不是二进制搜索函数的有效实现，因为它不处理数组中不存在所寻求的值的情况。
代码可以像这样转换为有效的 C 代码函数：
int binary_search(int N, const int A[N], int val)
{
int i, step;
for (step = 1; step < N; step <<= 1)
;
for (i = 0; step; step >>= 1)
if (i + step < N && A[i + step] <= val)
i += step;
if (A[i] != val)
i = -1;
return i;
}
这已经在严格的测试工具中进行了测试，它产生了与在同一工具中测试的其他二进制搜索变体相同的答案。
与替代二进制搜索算法的比较
我的 material 文件夹中恰好有 4 个其他二进制搜索实现与 SO 问题相关。给定一个可以在给定范围内生成随机数的程序，以及一些支持脚本，加上可以将经过时间报告为微秒的计时代码（它在 Mac OS X 上使用 gettimeofday()，很多令某些人感到厌恶，但在这种情况下这已经足够了），我生成了这个计时程序。它包括算法：
BinSearch_A — 在数组 X[0..N-1] 中找到与 T.BinSearch_B — 在数组 X[0..N-1] 中找到与 T.BinSearch_C — 在数组 X[0..N-1] 中找到与 T.BinSearch_D — 在数组 X[0..N-1] 中找到与 T.BinSearch_E — 在数组 X[0..N-1] 中找到与 T 匹配的任意索引 P（使用上面修改的问题中的算法）。
请注意，算法 B、C 和 D 正在解决比 A 和 E 解决的更难的问题，因此预计 B、C 和 D 将比 A 和 E 慢。
大纲代码(binsearch-speed-1.c)
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct Pair
{
int lo;
int hi;
} Pair;
extern Pair BinSearch_D(int N, const int X[N], int T);
extern int BinSearch_A(int N, const int X[N], int T);
extern int BinSearch_B(int N, const int X[N], int T);
extern int BinSearch_C(int N, const int X[N], int T);
extern int BinSearch_E(int N, const int X[N], int T);
#ifndef lint
extern const char jlss_id_modbinsearch_c[];
const char jlss_id_modbinsearch_c[] = "@(#)$Id$";
#endif
int BinSearch_A(int N, const int X[N], int T)
{
int L = 0;
int U = N-1;
while (1)
{
if (L > U)
return -1;
int M = (L + U) / 2;
if (X[M] < T)
L = M + 1;
else if (X[M] > T)
U = M - 1;
else
return M;
}
assert(0);
}
int BinSearch_B(int N, const int X[N], int T)
{
int L = -1;
int U = N;
while (L + 1 != U)
{
int M = (L + U) / 2;
if (X[M] < T)
L = M;
else
U = M;
}
assert(L+1 == U && (L == -1 || X[L] < T) && (U >= N || X[U] >= T));
int P = U;
if (P >= N || X[P] != T)
P = -1;
return P;
}
int BinSearch_C(int N, const int X[N], int T)
{
int L = -1;
int U = N;
while (L + 1 != U)
{
int M = (L + U) / 2;
if (X[M] <= T)
L = M;
else
U = M;
}
assert(L+1 == U && (L == -1 || X[L] <= T) && (U >= N || X[U] > T));
int P = L;
if (P < 0 || X[P] != T)
P = -1;
return P;
}
Pair BinSearch_D(int N, const int X[N], int T)
{
int L_lo = -1;
int L_hi = N;
int U_lo = -1;
int U_hi = N;
while (L_lo + 1 != L_hi || U_lo + 1 != U_hi)
{
if (L_lo + 1 != L_hi)
{
int L_md = (L_lo + L_hi) / 2;
if (X[L_md] < T)
L_lo = L_md;
else
L_hi = L_md;
}
if (U_lo + 1 != U_hi)
{
int U_md = (U_lo + U_hi) / 2;
if (X[U_md] <= T)
U_lo = U_md;
else
U_hi = U_md;
}
}
assert(L_lo+1 == L_hi && (L_lo == -1 || X[L_lo] < T) && (L_hi >= N || X[L_hi] >= T));
int L = L_hi;
if (L >= N || X[L] != T)
L = -1;
assert(U_lo+1 == U_hi && (U_lo == -1 || X[U_lo] <= T) && (U_hi >= N || X[U_hi] > T));
int U = U_lo;
if (U < 0 || X[U] != T)
U = -1;
return (Pair) { .lo = L, .hi = U };
}
int BinSearch_E(int N, const int X[N], int T)
{
int i, step;
for (step = 1; step < N; step <<= 1)
;
for (i = 0; step; step >>= 1)
if (i + step < N && X[i + step] <= T)
i += step;
if (X[i] != T)
i = -1;
return i;
}
#include "timer.h"
static const int numbers[] =
{
10000, 10002, 10003, 10003, 10003, 10004, 10006, 10010, 10011, 10015,
10016, 10020, 10023, 10024, 10029, 10029, 10030, 10031, 10032, 10035,
10036, 10036, 10037, 10037, 10038, 10041, 10043, 10044, 10046, 10049,
10066, 10066, 10069, 10070, 10071, 10074, 10079, 10080, 10085, 10086,
10087, 10089, 10090, 10090, 10090, 10091, 10092, 10094, 10095, 10095,
…省略990行相似…
29869, 29870, 29872, 29872, 29874, 29877, 29877, 29882, 29884, 29888,
29895, 29898, 29899, 29908, 29912, 29922, 29923, 29924, 29925, 29929,
29934, 29936, 29938, 29939, 29941, 29942, 29943, 29943, 29944, 29945,
29947, 29949, 29951, 29953, 29956, 29958, 29959, 29959, 29964, 29965,
29965, 29966, 29968, 29969, 29981, 29983, 29983, 29984, 29984, 29988,
};
enum { NUM_NUMBERS = sizeof(numbers) / sizeof(numbers[0]) };
static void check_sorted(const char *a_name, int size, const int array[size])
{
int ok = 1;
for (int i = 1; i < size; i++)
{
if (array[i-1] > array[i])
{
fprintf(stderr, "Out of order: %s[%d] = %d, %s[%d] = %d\n",
a_name, i-1, array[i-1], a_name, i, array[i]);
ok = 0;
}
}
if (!ok)
exit(1);
}
static int BinSearch_D1(int size, const int array[size], int value)
{
Pair p = BinSearch_D(size, array, value);
return p.lo;
}
typedef int (*BinSearch)(int size, const int data[size], int value);
static void time_search(const char *a_name, int size, const int array[size],
BinSearch function)
{
Clock clk;
clk_init(&clk);
int x0 = array[0] - 1;
int x1 = array[size-1] + 2;
long long vsum = 0;
clk_start(&clk);
for (int i = x0; i < x1; i++)
{
int index = (*function)(size, array, i);
vsum += (index == -1) ? index : array[index];
}
clk_stop(&clk);
char buffer[32];
printf("%s: (%d) %lld %s\n", a_name, size, vsum,
clk_elapsed_us(&clk, buffer, sizeof(buffer)));
}
int main(void)
{
check_sorted("numbers", NUM_NUMBERS, numbers);
for (int i = 0; i < 10; i++)
{
time_search("BinSearch_A", NUM_NUMBERS, numbers, BinSearch_A);
time_search("BinSearch_B", NUM_NUMBERS, numbers, BinSearch_B);
time_search("BinSearch_C", NUM_NUMBERS, numbers, BinSearch_C);
time_search("BinSearch_D", NUM_NUMBERS, numbers, BinSearch_D1);
time_search("BinSearch_E", NUM_NUMBERS, numbers, BinSearch_E);
}
return 0;
}
此代码适用于 10,000 个随机数的数组，重复范围为 10,000 到 29,999。这意味着数组中存在范围内大约一半的可能值。对于每个函数，它计算从数组中的最小数字 - 1 到数组中的最大数字 + 1 范围内的每个值的索引。因为当可能存在多个匹配时，算法合法地 return 不同的索引，测试代码对找到的值求和（并为每次搜索失败减去 1）。输出标识所用时间（以微秒为单位），并打印数组大小和计算值。计算的原因之一是确保优化器不会优化太多。
我还使用相同的代码生成了第二个程序 (binsearch-speed-2.c)，但包含 1,000,000 到 3,000,000 范围内的 1,000,000 个数字。由于 binsearch-speed-1.c 的时间在 0.7 - 1.4 毫秒范围内，数据量比我认为合适的要少一些，所以我将问题大小增加了 100 以生成相应更大的时间。然而，更大规模的问题改变了算法的相对时间（这就是你看到这个的原因）。
测试是 运行 旧的 MacBook Pro（2011 年初），配备 2.3 GHz Intel Core i7 CPU 和 16 GiB 的 1333 MHz DDR3 内存，运行ning Mac OS X 10.11.4，并使用 GCC 5.3.0。您的里程会有所不同！
示例编译命令行：
$ gcc -O3 -g -I$HOME/inc -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
> -Wold-style-definition -Werror binsearch-speed-2.c -o binsearch-speed-2 \
> -L$HOME/lib/64 -ljl
$
计时函数在引用的库中。
原始结果binsearch-speed-1（大小 10,000）
BinSearch_A: (10000) 158341368 0.000817
BinSearch_B: (10000) 158341368 0.001076
BinSearch_C: (10000) 158341368 0.001006
BinSearch_D: (10000) 158341368 0.001337
BinSearch_E: (10000) 158341368 0.000787
BinSearch_A: (10000) 158341368 0.000771
BinSearch_B: (10000) 158341368 0.001540
BinSearch_C: (10000) 158341368 0.001003
BinSearch_D: (10000) 158341368 0.001344
BinSearch_E: (10000) 158341368 0.000791
BinSearch_A: (10000) 158341368 0.000799
BinSearch_B: (10000) 158341368 0.001078
BinSearch_C: (10000) 158341368 0.001008
BinSearch_D: (10000) 158341368 0.001386
BinSearch_E: (10000) 158341368 0.000802
BinSearch_A: (10000) 158341368 0.000774
BinSearch_B: (10000) 158341368 0.001083
BinSearch_C: (10000) 158341368 0.001176
BinSearch_D: (10000) 158341368 0.001495
BinSearch_E: (10000) 158341368 0.000907
BinSearch_A: (10000) 158341368 0.000817
BinSearch_B: (10000) 158341368 0.001080
BinSearch_C: (10000) 158341368 0.001007
BinSearch_D: (10000) 158341368 0.001357
BinSearch_E: (10000) 158341368 0.000786
BinSearch_A: (10000) 158341368 0.000756
BinSearch_B: (10000) 158341368 0.001080
BinSearch_C: (10000) 158341368 0.001899
BinSearch_D: (10000) 158341368 0.001644
BinSearch_E: (10000) 158341368 0.000791
BinSearch_A: (10000) 158341368 0.000770
BinSearch_B: (10000) 158341368 0.001087
BinSearch_C: (10000) 158341368 0.001014
BinSearch_D: (10000) 158341368 0.001378
BinSearch_E: (10000) 158341368 0.000793
BinSearch_A: (10000) 158341368 0.001415
BinSearch_B: (10000) 158341368 0.001160
BinSearch_C: (10000) 158341368 0.001006
BinSearch_D: (10000) 158341368 0.001336
BinSearch_E: (10000) 158341368 0.000786
BinSearch_A: (10000) 158341368 0.000763
BinSearch_B: (10000) 158341368 0.001079
BinSearch_C: (10000) 158341368 0.001012
BinSearch_D: (10000) 158341368 0.001309
BinSearch_E: (10000) 158341368 0.000796
BinSearch_A: (10000) 158341368 0.000769
BinSearch_B: (10000) 158341368 0.001094
BinSearch_C: (10000) 158341368 0.001029
BinSearch_D: (10000) 158341368 0.001397
BinSearch_E: (10000) 158341368 0.000800
原始结果binsearch-speed-2（大小 1,000,000）
BinSearch_A: (1000000) 1573140220897 0.081161
BinSearch_B: (1000000) 1573140220897 0.137057
BinSearch_C: (1000000) 1573140220897 0.132743
BinSearch_D: (1000000) 1573140220897 0.166290
BinSearch_E: (1000000) 1573140220897 0.189696
BinSearch_A: (1000000) 1573140220897 0.083374
BinSearch_B: (1000000) 1573140220897 0.136225
BinSearch_C: (1000000) 1573140220897 0.128654
BinSearch_D: (1000000) 1573140220897 0.168078
BinSearch_E: (1000000) 1573140220897 0.190977
BinSearch_A: (1000000) 1573140220897 0.083391
BinSearch_B: (1000000) 1573140220897 0.135630
BinSearch_C: (1000000) 1573140220897 0.131179
BinSearch_D: (1000000) 1573140220897 0.168578
BinSearch_E: (1000000) 1573140220897 0.188785
BinSearch_A: (1000000) 1573140220897 0.083069
BinSearch_B: (1000000) 1573140220897 0.135803
BinSearch_C: (1000000) 1573140220897 0.136248
BinSearch_D: (1000000) 1573140220897 0.170167
BinSearch_E: (1000000) 1573140220897 0.188973
BinSearch_A: (1000000) 1573140220897 0.084509
BinSearch_B: (1000000) 1573140220897 0.145219
BinSearch_C: (1000000) 1573140220897 0.129374
BinSearch_D: (1000000) 1573140220897 0.168213
BinSearch_E: (1000000) 1573140220897 0.186770
BinSearch_A: (1000000) 1573140220897 0.086911
BinSearch_B: (1000000) 1573140220897 0.141995
BinSearch_C: (1000000) 1573140220897 0.134353
BinSearch_D: (1000000) 1573140220897 0.169639
BinSearch_E: (1000000) 1573140220897 0.194442
BinSearch_A: (1000000) 1573140220897 0.082882
BinSearch_B: (1000000) 1573140220897 0.135095
BinSearch_C: (1000000) 1573140220897 0.129635
BinSearch_D: (1000000) 1573140220897 0.166059
BinSearch_E: (1000000) 1573140220897 0.186700
BinSearch_A: (1000000) 1573140220897 0.083190
BinSearch_B: (1000000) 1573140220897 0.134491
BinSearch_C: (1000000) 1573140220897 0.130103
BinSearch_D: (1000000) 1573140220897 0.169454
BinSearch_E: (1000000) 1573140220897 0.188583
BinSearch_A: (1000000) 1573140220897 0.083038
BinSearch_B: (1000000) 1573140220897 0.135738
BinSearch_C: (1000000) 1573140220897 0.129727
BinSearch_D: (1000000) 1573140220897 0.169101
BinSearch_E: (1000000) 1573140220897 0.188749
BinSearch_A: (1000000) 1573140220897 0.082099
BinSearch_B: (1000000) 1573140220897 0.135025
BinSearch_C: (1000000) 1573140220897 0.130743
BinSearch_D: (1000000) 1573140220897 0.168684
BinSearch_E: (1000000) 1573140220897 0.188640
原始数据统计
Program Algorithm Tests Avg Time Std Dev
binsearch-speed-1 BinSearch_A 10 0.0008451 0.0002014
BinSearch_B 10 0.0011357 0.0001442
BinSearch_C 10 0.0011160 0.0002801
BinSearch_D 10 0.0013983 0.0001003
BinSearch_E 10 0.0008039 0.0000366
binsearch-speed-2 BinSearch_A 10 0.0833624 0.0015203
BinSearch_B 10 0.1372278 0.0035168
BinSearch_C 10 0.1312759 0.0024403
BinSearch_D 10 0.1684263 0.0013514
BinSearch_E 10 0.1892315 0.0022148
临时结论
当问题规模为一万时，'shift'算法（BinSearch_E）似乎比简单的'midpoint'算法（BinSearch_A）表现得更好一点，但差异并不明显 — 我没有对数据进行 运行 T 检验或类似检验。
当问题规模为一百万时，'midpoint'算法明显优于'shift'算法，实际上它的性能比三个更复杂的算法差。
这是出乎意料的（尤其是比更复杂的算法更糟糕）；我希望这两种算法基本相同。我没有很好的解释为什么。这种结果说明了为什么基准测试很难。如果我不得不猜测，我怀疑尽管更大的数组只需要大约 4 MiB 的内存，但 'shift' 算法的元素访问模式意味着缓存效率较低。证明（或反驳）这很困难——需要比我更好的性能测试工程师。
鉴于算法 A（简单中点）的一致性能，它基本上线性缩放执行的测试，我会使用它而不是算法 E — 除非我能证明算法 E（移位）在代码使用的数据集的大小。
这说明了如果性能最大化很重要，那么基准测试也很重要。
我想知道这两个实现中哪一个更快，为什么？
int N, A[N];
int binary_search(int val)
{
int i, step;
for (step = 1; step < N; step <<= 1)
;
for (i = 0; step; step >>= 1)
if (i + step < N && A[i + step] <= val)
i += step;
}
和一个正常的实现，你找到 mid=(st+dr)/2 然后根据 A[mid] 的值和你的值应用到数组的左侧或右侧？
伪代码到C代码的转换
该问题询问的代码片段不是二进制搜索函数的有效实现，因为它不处理数组中不存在所寻求的值的情况。
代码可以像这样转换为有效的 C 代码函数：
int binary_search(int N, const int A[N], int val)
{
int i, step;
for (step = 1; step < N; step <<= 1)
;
for (i = 0; step; step >>= 1)
if (i + step < N && A[i + step] <= val)
i += step;
if (A[i] != val)
i = -1;
return i;
}
这已经在严格的测试工具中进行了测试，它产生了与在同一工具中测试的其他二进制搜索变体相同的答案。
与替代二进制搜索算法的比较
我的 material 文件夹中恰好有 4 个其他二进制搜索实现与 SO 问题相关。给定一个可以在给定范围内生成随机数的程序，以及一些支持脚本，加上可以将经过时间报告为微秒的计时代码（它在 Mac OS X 上使用 gettimeofday()，很多令某些人感到厌恶，但在这种情况下这已经足够了），我生成了这个计时程序。它包括算法：
BinSearch_A— 在数组 X[0..N-1] 中找到与 T. 匹配的任意索引 P
BinSearch_B— 在数组 X[0..N-1] 中找到与 T. 匹配的最小索引 P
BinSearch_C— 在数组 X[0..N-1] 中找到与 T. 匹配的最大索引 P
BinSearch_D— 在数组 X[0..N-1] 中找到与 T. 匹配的最小 (L) 和最大 (U) 索引
BinSearch_E— 在数组 X[0..N-1] 中找到与 T 匹配的任意索引 P（使用上面修改的问题中的算法）。
请注意，算法 B、C 和 D 正在解决比 A 和 E 解决的更难的问题，因此预计 B、C 和 D 将比 A 和 E 慢。
大纲代码(binsearch-speed-1.c)
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct Pair
{
int lo;
int hi;
} Pair;
extern Pair BinSearch_D(int N, const int X[N], int T);
extern int BinSearch_A(int N, const int X[N], int T);
extern int BinSearch_B(int N, const int X[N], int T);
extern int BinSearch_C(int N, const int X[N], int T);
extern int BinSearch_E(int N, const int X[N], int T);
#ifndef lint
extern const char jlss_id_modbinsearch_c[];
const char jlss_id_modbinsearch_c[] = "@(#)$Id$";
#endif
int BinSearch_A(int N, const int X[N], int T)
{
int L = 0;
int U = N-1;
while (1)
{
if (L > U)
return -1;
int M = (L + U) / 2;
if (X[M] < T)
L = M + 1;
else if (X[M] > T)
U = M - 1;
else
return M;
}
assert(0);
}
int BinSearch_B(int N, const int X[N], int T)
{
int L = -1;
int U = N;
while (L + 1 != U)
{
int M = (L + U) / 2;
if (X[M] < T)
L = M;
else
U = M;
}
assert(L+1 == U && (L == -1 || X[L] < T) && (U >= N || X[U] >= T));
int P = U;
if (P >= N || X[P] != T)
P = -1;
return P;
}
int BinSearch_C(int N, const int X[N], int T)
{
int L = -1;
int U = N;
while (L + 1 != U)
{
int M = (L + U) / 2;
if (X[M] <= T)
L = M;
else
U = M;
}
assert(L+1 == U && (L == -1 || X[L] <= T) && (U >= N || X[U] > T));
int P = L;
if (P < 0 || X[P] != T)
P = -1;
return P;
}
Pair BinSearch_D(int N, const int X[N], int T)
{
int L_lo = -1;
int L_hi = N;
int U_lo = -1;
int U_hi = N;
while (L_lo + 1 != L_hi || U_lo + 1 != U_hi)
{
if (L_lo + 1 != L_hi)
{
int L_md = (L_lo + L_hi) / 2;
if (X[L_md] < T)
L_lo = L_md;
else
L_hi = L_md;
}
if (U_lo + 1 != U_hi)
{
int U_md = (U_lo + U_hi) / 2;
if (X[U_md] <= T)
U_lo = U_md;
else
U_hi = U_md;
}
}
assert(L_lo+1 == L_hi && (L_lo == -1 || X[L_lo] < T) && (L_hi >= N || X[L_hi] >= T));
int L = L_hi;
if (L >= N || X[L] != T)
L = -1;
assert(U_lo+1 == U_hi && (U_lo == -1 || X[U_lo] <= T) && (U_hi >= N || X[U_hi] > T));
int U = U_lo;
if (U < 0 || X[U] != T)
U = -1;
return (Pair) { .lo = L, .hi = U };
}
int BinSearch_E(int N, const int X[N], int T)
{
int i, step;
for (step = 1; step < N; step <<= 1)
;
for (i = 0; step; step >>= 1)
if (i + step < N && X[i + step] <= T)
i += step;
if (X[i] != T)
i = -1;
return i;
}
#include "timer.h"
static const int numbers[] =
{
10000, 10002, 10003, 10003, 10003, 10004, 10006, 10010, 10011, 10015,
10016, 10020, 10023, 10024, 10029, 10029, 10030, 10031, 10032, 10035,
10036, 10036, 10037, 10037, 10038, 10041, 10043, 10044, 10046, 10049,
10066, 10066, 10069, 10070, 10071, 10074, 10079, 10080, 10085, 10086,
10087, 10089, 10090, 10090, 10090, 10091, 10092, 10094, 10095, 10095,
…省略990行相似…
29869, 29870, 29872, 29872, 29874, 29877, 29877, 29882, 29884, 29888,
29895, 29898, 29899, 29908, 29912, 29922, 29923, 29924, 29925, 29929,
29934, 29936, 29938, 29939, 29941, 29942, 29943, 29943, 29944, 29945,
29947, 29949, 29951, 29953, 29956, 29958, 29959, 29959, 29964, 29965,
29965, 29966, 29968, 29969, 29981, 29983, 29983, 29984, 29984, 29988,
};
enum { NUM_NUMBERS = sizeof(numbers) / sizeof(numbers[0]) };
static void check_sorted(const char *a_name, int size, const int array[size])
{
int ok = 1;
for (int i = 1; i < size; i++)
{
if (array[i-1] > array[i])
{
fprintf(stderr, "Out of order: %s[%d] = %d, %s[%d] = %d\n",
a_name, i-1, array[i-1], a_name, i, array[i]);
ok = 0;
}
}
if (!ok)
exit(1);
}
static int BinSearch_D1(int size, const int array[size], int value)
{
Pair p = BinSearch_D(size, array, value);
return p.lo;
}
typedef int (*BinSearch)(int size, const int data[size], int value);
static void time_search(const char *a_name, int size, const int array[size],
BinSearch function)
{
Clock clk;
clk_init(&clk);
int x0 = array[0] - 1;
int x1 = array[size-1] + 2;
long long vsum = 0;
clk_start(&clk);
for (int i = x0; i < x1; i++)
{
int index = (*function)(size, array, i);
vsum += (index == -1) ? index : array[index];
}
clk_stop(&clk);
char buffer[32];
printf("%s: (%d) %lld %s\n", a_name, size, vsum,
clk_elapsed_us(&clk, buffer, sizeof(buffer)));
}
int main(void)
{
check_sorted("numbers", NUM_NUMBERS, numbers);
for (int i = 0; i < 10; i++)
{
time_search("BinSearch_A", NUM_NUMBERS, numbers, BinSearch_A);
time_search("BinSearch_B", NUM_NUMBERS, numbers, BinSearch_B);
time_search("BinSearch_C", NUM_NUMBERS, numbers, BinSearch_C);
time_search("BinSearch_D", NUM_NUMBERS, numbers, BinSearch_D1);
time_search("BinSearch_E", NUM_NUMBERS, numbers, BinSearch_E);
}
return 0;
}
此代码适用于 10,000 个随机数的数组，重复范围为 10,000 到 29,999。这意味着数组中存在范围内大约一半的可能值。对于每个函数，它计算从数组中的最小数字 - 1 到数组中的最大数字 + 1 范围内的每个值的索引。因为当可能存在多个匹配时，算法合法地 return 不同的索引，测试代码对找到的值求和（并为每次搜索失败减去 1）。输出标识所用时间（以微秒为单位），并打印数组大小和计算值。计算的原因之一是确保优化器不会优化太多。
我还使用相同的代码生成了第二个程序 (binsearch-speed-2.c)，但包含 1,000,000 到 3,000,000 范围内的 1,000,000 个数字。由于 binsearch-speed-1.c 的时间在 0.7 - 1.4 毫秒范围内，数据量比我认为合适的要少一些，所以我将问题大小增加了 100 以生成相应更大的时间。然而，更大规模的问题改变了算法的相对时间（这就是你看到这个的原因）。
测试是 运行 旧的 MacBook Pro（2011 年初），配备 2.3 GHz Intel Core i7 CPU 和 16 GiB 的 1333 MHz DDR3 内存，运行ning Mac OS X 10.11.4，并使用 GCC 5.3.0。您的里程会有所不同！
示例编译命令行：
$ gcc -O3 -g -I$HOME/inc -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
> -Wold-style-definition -Werror binsearch-speed-2.c -o binsearch-speed-2 \
> -L$HOME/lib/64 -ljl
$
计时函数在引用的库中。
原始结果binsearch-speed-1（大小 10,000）
BinSearch_A: (10000) 158341368 0.000817
BinSearch_B: (10000) 158341368 0.001076
BinSearch_C: (10000) 158341368 0.001006
BinSearch_D: (10000) 158341368 0.001337
BinSearch_E: (10000) 158341368 0.000787
BinSearch_A: (10000) 158341368 0.000771
BinSearch_B: (10000) 158341368 0.001540
BinSearch_C: (10000) 158341368 0.001003
BinSearch_D: (10000) 158341368 0.001344
BinSearch_E: (10000) 158341368 0.000791
BinSearch_A: (10000) 158341368 0.000799
BinSearch_B: (10000) 158341368 0.001078
BinSearch_C: (10000) 158341368 0.001008
BinSearch_D: (10000) 158341368 0.001386
BinSearch_E: (10000) 158341368 0.000802
BinSearch_A: (10000) 158341368 0.000774
BinSearch_B: (10000) 158341368 0.001083
BinSearch_C: (10000) 158341368 0.001176
BinSearch_D: (10000) 158341368 0.001495
BinSearch_E: (10000) 158341368 0.000907
BinSearch_A: (10000) 158341368 0.000817
BinSearch_B: (10000) 158341368 0.001080
BinSearch_C: (10000) 158341368 0.001007
BinSearch_D: (10000) 158341368 0.001357
BinSearch_E: (10000) 158341368 0.000786
BinSearch_A: (10000) 158341368 0.000756
BinSearch_B: (10000) 158341368 0.001080
BinSearch_C: (10000) 158341368 0.001899
BinSearch_D: (10000) 158341368 0.001644
BinSearch_E: (10000) 158341368 0.000791
BinSearch_A: (10000) 158341368 0.000770
BinSearch_B: (10000) 158341368 0.001087
BinSearch_C: (10000) 158341368 0.001014
BinSearch_D: (10000) 158341368 0.001378
BinSearch_E: (10000) 158341368 0.000793
BinSearch_A: (10000) 158341368 0.001415
BinSearch_B: (10000) 158341368 0.001160
BinSearch_C: (10000) 158341368 0.001006
BinSearch_D: (10000) 158341368 0.001336
BinSearch_E: (10000) 158341368 0.000786
BinSearch_A: (10000) 158341368 0.000763
BinSearch_B: (10000) 158341368 0.001079
BinSearch_C: (10000) 158341368 0.001012
BinSearch_D: (10000) 158341368 0.001309
BinSearch_E: (10000) 158341368 0.000796
BinSearch_A: (10000) 158341368 0.000769
BinSearch_B: (10000) 158341368 0.001094
BinSearch_C: (10000) 158341368 0.001029
BinSearch_D: (10000) 158341368 0.001397
BinSearch_E: (10000) 158341368 0.000800
原始结果binsearch-speed-2（大小 1,000,000）
BinSearch_A: (1000000) 1573140220897 0.081161
BinSearch_B: (1000000) 1573140220897 0.137057
BinSearch_C: (1000000) 1573140220897 0.132743
BinSearch_D: (1000000) 1573140220897 0.166290
BinSearch_E: (1000000) 1573140220897 0.189696
BinSearch_A: (1000000) 1573140220897 0.083374
BinSearch_B: (1000000) 1573140220897 0.136225
BinSearch_C: (1000000) 1573140220897 0.128654
BinSearch_D: (1000000) 1573140220897 0.168078
BinSearch_E: (1000000) 1573140220897 0.190977
BinSearch_A: (1000000) 1573140220897 0.083391
BinSearch_B: (1000000) 1573140220897 0.135630
BinSearch_C: (1000000) 1573140220897 0.131179
BinSearch_D: (1000000) 1573140220897 0.168578
BinSearch_E: (1000000) 1573140220897 0.188785
BinSearch_A: (1000000) 1573140220897 0.083069
BinSearch_B: (1000000) 1573140220897 0.135803
BinSearch_C: (1000000) 1573140220897 0.136248
BinSearch_D: (1000000) 1573140220897 0.170167
BinSearch_E: (1000000) 1573140220897 0.188973
BinSearch_A: (1000000) 1573140220897 0.084509
BinSearch_B: (1000000) 1573140220897 0.145219
BinSearch_C: (1000000) 1573140220897 0.129374
BinSearch_D: (1000000) 1573140220897 0.168213
BinSearch_E: (1000000) 1573140220897 0.186770
BinSearch_A: (1000000) 1573140220897 0.086911
BinSearch_B: (1000000) 1573140220897 0.141995
BinSearch_C: (1000000) 1573140220897 0.134353
BinSearch_D: (1000000) 1573140220897 0.169639
BinSearch_E: (1000000) 1573140220897 0.194442
BinSearch_A: (1000000) 1573140220897 0.082882
BinSearch_B: (1000000) 1573140220897 0.135095
BinSearch_C: (1000000) 1573140220897 0.129635
BinSearch_D: (1000000) 1573140220897 0.166059
BinSearch_E: (1000000) 1573140220897 0.186700
BinSearch_A: (1000000) 1573140220897 0.083190
BinSearch_B: (1000000) 1573140220897 0.134491
BinSearch_C: (1000000) 1573140220897 0.130103
BinSearch_D: (1000000) 1573140220897 0.169454
BinSearch_E: (1000000) 1573140220897 0.188583
BinSearch_A: (1000000) 1573140220897 0.083038
BinSearch_B: (1000000) 1573140220897 0.135738
BinSearch_C: (1000000) 1573140220897 0.129727
BinSearch_D: (1000000) 1573140220897 0.169101
BinSearch_E: (1000000) 1573140220897 0.188749
BinSearch_A: (1000000) 1573140220897 0.082099
BinSearch_B: (1000000) 1573140220897 0.135025
BinSearch_C: (1000000) 1573140220897 0.130743
BinSearch_D: (1000000) 1573140220897 0.168684
BinSearch_E: (1000000) 1573140220897 0.188640
原始数据统计
Program Algorithm Tests Avg Time Std Dev
binsearch-speed-1 BinSearch_A 10 0.0008451 0.0002014
BinSearch_B 10 0.0011357 0.0001442
BinSearch_C 10 0.0011160 0.0002801
BinSearch_D 10 0.0013983 0.0001003
BinSearch_E 10 0.0008039 0.0000366
binsearch-speed-2 BinSearch_A 10 0.0833624 0.0015203
BinSearch_B 10 0.1372278 0.0035168
BinSearch_C 10 0.1312759 0.0024403
BinSearch_D 10 0.1684263 0.0013514
BinSearch_E 10 0.1892315 0.0022148
临时结论
当问题规模为一万时，'shift'算法（BinSearch_E）似乎比简单的'midpoint'算法（BinSearch_A）表现得更好一点，但差异并不明显 — 我没有对数据进行 运行 T 检验或类似检验。
当问题规模为一百万时，'midpoint'算法明显优于'shift'算法，实际上它的性能比三个更复杂的算法差。
这是出乎意料的（尤其是比更复杂的算法更糟糕）；我希望这两种算法基本相同。我没有很好的解释为什么。这种结果说明了为什么基准测试很难。如果我不得不猜测，我怀疑尽管更大的数组只需要大约 4 MiB 的内存，但 'shift' 算法的元素访问模式意味着缓存效率较低。证明（或反驳）这很困难——需要比我更好的性能测试工程师。
鉴于算法 A（简单中点）的一致性能，它基本上线性缩放执行的测试，我会使用它而不是算法 E — 除非我能证明算法 E（移位）在代码使用的数据集的大小。
这说明了如果性能最大化很重要，那么基准测试也很重要。