java - 较小数组上的二分查找速度较慢

Question

我编写了一个程序来测试线性和二分搜索的速度，发现一开始当排序数组的大小为 1000 时，二分搜索所用的时间比后来数组大小增加时要多得多。有没有解释为什么会出现这种情况。

程序检查算法 1000 次，并计算为包含 1 到 n 的元素的每个大小为 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|

Answer 1

你应该给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));
    }
}