二进制搜索在较小的数组上很慢
Binary search slow on smaller arrays
我写了一个程序来测试线性和二进制搜索的速度，发现在排序数组的大小为 1000 的开始时，二进制搜索比后来数组大小增加时使用更多的时间。有没有解释为什么会这样。
程序检查算法 1000 次并计算为每个数组找到所需项目所花费的平均时间，大小为 n，包含从 1 到 n 的元素。
import java.util.*;
public class Test {
public static void main(String[] args) {
System.out.println(" n | linear | binary |\n---------+--------------+---------------");
for (int i = 1000; i <= 100000; i += 1000) {
System.out.printf("%9d|%14d|%14d|\n", i, timeLinear(i), timeBinary(i));
}
}
static int[] generateTable(int n) {
int[] a = new int[n];
int ind = 0;
for (int i = 1; i <= n; i++) {
a[ind++] = i;
}
return a;
}
static int findLinear(int[] a, int n) {
for (int i = 0; i < a.length; i++) {
if (a[i] == n) return i;
}
return -1;
}
static int findBinary(int[] a, int l, int r, int n) {
if (l > r) return -1;
int mid = l + (r - l) / 2;
if (n < a[mid]) {
findBinary(a, l, mid - 1, n);
}
else if (n > a[mid]) {
findBinary(a, mid + 1, r, n);
}
return mid;
}
static long timeLinear(int n) {
Random rn = new Random();
int[] arr = generateTable(n);
long start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
findLinear(arr, rn.nextInt(n) + 1);
}
long stop = System.nanoTime() - start;
return stop / 1000;
}
static long timeBinary(int n) {
Random rn = new Random();
int[] arr = generateTable(n);
long start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
findBinary(arr, 0, arr.length - 1, rn.nextInt(n) + 1);
}
long stop = System.nanoTime() - start;
return stop / 1000;
}
}
输出：
n | linear | binary |
---------+--------------+---------------
1000| 5736| 1518|
2000| 787| 2012|
3000| 1313| 626|
4000| 1230| 711|
5000| 1281| 723|
6000| 1888| 463|
7000| 1846| 213|
8000| 1089| 187|
9000| 1213| 188|
10000| 1583| 216|
11000| 1607| 302|
12000| 3294| 311|
13000| 3656| 274|
14000| 3497| 274|
15000| 2315| 141|
16000| 1945| 135|
17000| 2223| 154|
18000| 2964| 136|
19000| 2464| 138|
20000| 2472| 138|
21000| 2829| 140|
22000| 3209| 157|
23000| 2901| 141|
24000| 3095| 140|
25000| 3157| 142|
26000| 3235| 162|
27000| 4118| 143|
28000| 3483| 145|
29000| 3906| 144|
30000| 3801| 145|
31000| 4322| 166|
32000| 4057| 146|
33000| 4516| 167|
34000| 4566| 147|
35000| 4453| 148|
36000| 4708| 148|
37000| 4772| 149|
38000| 5391| 168|
39000| 5500| 150|
40000| 5048| 150|
41000| 4979| 150|
42000| 5402| 151|
43000| 6160| 171|
44000| 6402| 153|
45000| 5855| 152|
46000| 5702| 152|
47000| 6184| 153|
48000| 5963| 154|
49000| 6927| 155|
50000| 6611| 154|
51000| 6326| 155|
52000| 6488| 155|
53000| 7690| 156|
54000| 7245| 156|
55000| 7074| 156|
56000| 6998| 154|
57000| 8299| 157|
58000| 7456| 156|
59000| 7776| 156|
60000| 8015| 189|
61000| 7762| 160|
62000| 8145| 158|
63000| 7946| 158|
64000| 9157| 156|
65000| 8299| 157|
66000| 8399| 159|
67000| 9119| 159|
68000| 8758| 159|
69000| 8921| 161|
70000| 9366| 162|
71000| 9326| 170|
72000| 9035| 161|
73000| 9873| 189|
74000| 9642| 189|
75000| 10272| 185|
76000| 10299| 163|
77000| 10602| 162|
78000| 9878| 165|
79000| 10790| 168|
80000| 10535| 165|
81000| 10627| 164|
82000| 11579| 166|
83000| 11003| 167|
84000| 11778| 164|
85000| 10686| 167|
86000| 11280| 168|
87000| 12562| 171|
88000| 11190| 197|
89000| 12949| 167|
90000| 11954| 169|
91000| 13170| 168|
92000| 12013| 169|
93000| 12245| 170|
94000| 12949| 194|
95000| 12264| 172|
96000| 13754| 170|
97000| 12919| 171|
98000| 14172| 170|
99000| 13436| 172|
100000| 14466| 171|
你应该给JIT编译器一个加热的机会。试试这个：
for (int j = 0; j < 20; j++) {
System.out.printf("%n%nCycle # %d%n%n%n%n", j);
for (int i = 1000; i <= 100000; i += 1000) {
System.out.printf("%9d|%14d|%14d|\n", i, timeLinear(i), timeBinary(i));
}
}
较小的列表仅由 1 或 2 个 cpu 内核执行，但较大的列表 bing 使用了所有内核，因此速度更快。
我写了一个程序来测试线性和二进制搜索的速度，发现在排序数组的大小为 1000 的开始时，二进制搜索比后来数组大小增加时使用更多的时间。有没有解释为什么会这样。
程序检查算法 1000 次并计算为每个数组找到所需项目所花费的平均时间，大小为 n，包含从 1 到 n 的元素。
import java.util.*;
public class Test {
public static void main(String[] args) {
System.out.println(" n | linear | binary |\n---------+--------------+---------------");
for (int i = 1000; i <= 100000; i += 1000) {
System.out.printf("%9d|%14d|%14d|\n", i, timeLinear(i), timeBinary(i));
}
}
static int[] generateTable(int n) {
int[] a = new int[n];
int ind = 0;
for (int i = 1; i <= n; i++) {
a[ind++] = i;
}
return a;
}
static int findLinear(int[] a, int n) {
for (int i = 0; i < a.length; i++) {
if (a[i] == n) return i;
}
return -1;
}
static int findBinary(int[] a, int l, int r, int n) {
if (l > r) return -1;
int mid = l + (r - l) / 2;
if (n < a[mid]) {
findBinary(a, l, mid - 1, n);
}
else if (n > a[mid]) {
findBinary(a, mid + 1, r, n);
}
return mid;
}
static long timeLinear(int n) {
Random rn = new Random();
int[] arr = generateTable(n);
long start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
findLinear(arr, rn.nextInt(n) + 1);
}
long stop = System.nanoTime() - start;
return stop / 1000;
}
static long timeBinary(int n) {
Random rn = new Random();
int[] arr = generateTable(n);
long start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
findBinary(arr, 0, arr.length - 1, rn.nextInt(n) + 1);
}
long stop = System.nanoTime() - start;
return stop / 1000;
}
}
输出：
n | linear | binary |
---------+--------------+---------------
1000| 5736| 1518|
2000| 787| 2012|
3000| 1313| 626|
4000| 1230| 711|
5000| 1281| 723|
6000| 1888| 463|
7000| 1846| 213|
8000| 1089| 187|
9000| 1213| 188|
10000| 1583| 216|
11000| 1607| 302|
12000| 3294| 311|
13000| 3656| 274|
14000| 3497| 274|
15000| 2315| 141|
16000| 1945| 135|
17000| 2223| 154|
18000| 2964| 136|
19000| 2464| 138|
20000| 2472| 138|
21000| 2829| 140|
22000| 3209| 157|
23000| 2901| 141|
24000| 3095| 140|
25000| 3157| 142|
26000| 3235| 162|
27000| 4118| 143|
28000| 3483| 145|
29000| 3906| 144|
30000| 3801| 145|
31000| 4322| 166|
32000| 4057| 146|
33000| 4516| 167|
34000| 4566| 147|
35000| 4453| 148|
36000| 4708| 148|
37000| 4772| 149|
38000| 5391| 168|
39000| 5500| 150|
40000| 5048| 150|
41000| 4979| 150|
42000| 5402| 151|
43000| 6160| 171|
44000| 6402| 153|
45000| 5855| 152|
46000| 5702| 152|
47000| 6184| 153|
48000| 5963| 154|
49000| 6927| 155|
50000| 6611| 154|
51000| 6326| 155|
52000| 6488| 155|
53000| 7690| 156|
54000| 7245| 156|
55000| 7074| 156|
56000| 6998| 154|
57000| 8299| 157|
58000| 7456| 156|
59000| 7776| 156|
60000| 8015| 189|
61000| 7762| 160|
62000| 8145| 158|
63000| 7946| 158|
64000| 9157| 156|
65000| 8299| 157|
66000| 8399| 159|
67000| 9119| 159|
68000| 8758| 159|
69000| 8921| 161|
70000| 9366| 162|
71000| 9326| 170|
72000| 9035| 161|
73000| 9873| 189|
74000| 9642| 189|
75000| 10272| 185|
76000| 10299| 163|
77000| 10602| 162|
78000| 9878| 165|
79000| 10790| 168|
80000| 10535| 165|
81000| 10627| 164|
82000| 11579| 166|
83000| 11003| 167|
84000| 11778| 164|
85000| 10686| 167|
86000| 11280| 168|
87000| 12562| 171|
88000| 11190| 197|
89000| 12949| 167|
90000| 11954| 169|
91000| 13170| 168|
92000| 12013| 169|
93000| 12245| 170|
94000| 12949| 194|
95000| 12264| 172|
96000| 13754| 170|
97000| 12919| 171|
98000| 14172| 170|
99000| 13436| 172|
100000| 14466| 171|
你应该给JIT编译器一个加热的机会。试试这个：
for (int j = 0; j < 20; j++) {
System.out.printf("%n%nCycle # %d%n%n%n%n", j);
for (int i = 1000; i <= 100000; i += 1000) {
System.out.printf("%9d|%14d|%14d|\n", i, timeLinear(i), timeBinary(i));
}
}
较小的列表仅由 1 或 2 个 cpu 内核执行，但较大的列表 bing 使用了所有内核，因此速度更快。