二进制搜索在较小阵列上变慢

我编写了一个程序，用于测试线性搜索和二分搜索的速度，并发现在排序数组大小为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|

来源

2015-10-13 Clutchy

我想这是与JIT热身 - 毕竟，线性搜索'1000'也非常慢。如果你通过'n'反转for循环的顺序会发生什么？ –

可能的重复[如何在Java中编写正确的微基准测试？]（http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java ） – resueman

谢谢@AndyTurner甚至没有想到这一点，我明白为什么现在:) – Clutchy

你应该给一个机会，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)); 
    } 
}

来源

2015-10-13 22:30:43 ursa

这很好地加热它，你可以看到变化。谢谢。 – Clutchy

二进制搜索在较小阵列上变慢

回答

相关问题