为什么 Arrays.binarySearch 与遍历数组相比没有提高性能？

Question

我尝试解决了 Hackerland Radio Transmitters programming challange。

总而言之，挑战如下：

Hackerland is a one-dimensional city with n houses, where each house i is located at some x_i on the x-axis. The Mayor wants to install radio transmitters on the roofs of the city's houses. Each transmitter has a range, k, meaning it can transmit a signal to all houses ≤ k units of distance away.

Given a map of Hackerland and the value of k, can you find the minimum number of transmitters needed to cover every house?

我的实现如下：

package biz.tugay;

import java.util.*;

public class HackerlandRadioTransmitters {

    public static int minNumOfTransmitters(int[] houseLocations, int transmitterRange) {
        // Sort and remove duplicates..
        houseLocations = uniqueHouseLocationsSorted(houseLocations);
        int towerCount = 0;
        for (int nextHouseNotCovered = 0; nextHouseNotCovered < houseLocations.length; ) {
            final int towerLocation = HackerlandRadioTransmitters.findNextTowerIndex(houseLocations, nextHouseNotCovered, transmitterRange);
            towerCount++;
            nextHouseNotCovered = HackerlandRadioTransmitters.nextHouseNotCoveredIndex(houseLocations, towerLocation, transmitterRange);
            if (nextHouseNotCovered == -1) {
                break;
            }
        }
        return towerCount;
    }

    public static int findNextTowerIndex(final int[] houseLocations, final int houseNotCoveredIndex, final int transmitterRange) {
        final int houseLocationWeWantToCover = houseLocations[houseNotCoveredIndex];
        final int farthestHouseLocationAllowed = houseLocationWeWantToCover + transmitterRange;
        int towerIndex = houseNotCoveredIndex;
        int loop = 0;
        while (true) {
            loop++;
            if (towerIndex == houseLocations.length - 1) {
                break;
            }
            if (farthestHouseLocationAllowed >= houseLocations[towerIndex + 1]) {
                towerIndex++;
                continue;
            }
            break;
        }
        System.out.println("findNextTowerIndex looped : " + loop);
        return towerIndex;
    }

    public static int nextHouseNotCoveredIndex(final int[] houseLocations, final int towerIndex, final int transmitterRange) {
        final int towerCoversUntil = houseLocations[towerIndex] + transmitterRange;
        int notCoveredHouseIndex = towerIndex + 1;
        int loop = 0;
        while (notCoveredHouseIndex < houseLocations.length) {
            loop++;
            final int locationOfHouseBeingChecked = houseLocations[notCoveredHouseIndex];
            if (locationOfHouseBeingChecked > towerCoversUntil) {
                break; // Tower does not cover the house anymore, break the loop..
            }
            notCoveredHouseIndex++;
        }
        if (notCoveredHouseIndex == houseLocations.length) {
            notCoveredHouseIndex = -1;
        }
        System.out.println("nextHouseNotCoveredIndex looped : " + loop);
        return notCoveredHouseIndex;
    }

    public static int[] uniqueHouseLocationsSorted(final int[] houseLocations) {
        Arrays.sort(houseLocations);
        final HashSet<Integer> integers = new HashSet<>();
        final int[] houseLocationsUnique = new int[houseLocations.length];

        int innerCounter = 0;
        for (int houseLocation : houseLocations) {
            if (integers.contains(houseLocation)) {
                continue;
            }
            houseLocationsUnique[innerCounter] = houseLocation;
            integers.add(houseLocationsUnique[innerCounter]);
            innerCounter++;
        }
        return Arrays.copyOf(houseLocationsUnique, innerCounter);
    }
}

我很确定这个实现是正确的。但请查看函数中的详细信息：findNextTowerIndex 和 nextHouseNotCoveredIndex：它们一个一个地遍历数组！

我的一个测试如下：

static void test_01() throws FileNotFoundException {
    final long start = System.currentTimeMillis();
    final File file = new File("input.txt");
    final Scanner scanner = new Scanner(file);
    int[] houseLocations = new int[73382];
    for (int counter = 0; counter < 73382; counter++) {
        houseLocations[counter] = scanner.nextInt();
    }
    final int[] uniqueHouseLocationsSorted = HackerlandRadioTransmitters.uniqueHouseLocationsSorted(houseLocations);
    final int minNumOfTransmitters = HackerlandRadioTransmitters.minNumOfTransmitters(uniqueHouseLocationsSorted, 73381);
    assert minNumOfTransmitters == 1;
    final long end = System.currentTimeMillis();
    System.out.println("Took: " + (end - start) + " milliseconds..");
}

其中 input.txt 可以从 here 下载。（这不是这个问题中最重要的细节，但仍然..）所以我们有一个 73382 房子的数组，我特意设置了发射器范围，所以我的方法循环了很多：

这是在我的机器上进行的该测试的示例输出：

findNextTowerIndex looped : 38213
nextHouseNotCoveredIndex looped : 13785
Took: 359 milliseconds..

我也有这个测试，它没有断言任何东西，只是保持时间：

static void test_02() throws FileNotFoundException {
    final long start = System.currentTimeMillis();
    for (int i = 0; i < 400; i ++) {
        final File file = new File("input.txt");
        final Scanner scanner = new Scanner(file);
        int[] houseLocations = new int[73382];
        for (int counter = 0; counter < 73382; counter++) {
            houseLocations[counter] = scanner.nextInt();
        }
        final int[] uniqueHouseLocationsSorted = HackerlandRadioTransmitters.uniqueHouseLocationsSorted(houseLocations);

        final int transmitterRange = ThreadLocalRandom.current().nextInt(1, 70000);
        final int minNumOfTransmitters = HackerlandRadioTransmitters.minNumOfTransmitters(uniqueHouseLocationsSorted, transmitterRange);
    }
    final long end = System.currentTimeMillis();
    System.out.println("Took: " + (end - start) + " milliseconds..");
}

我随机创建 400 个发射器范围，运行程序 400 次。我将在我的机器中得到运行次，如下所示。

Took: 20149 milliseconds..

所以现在，我说，为什么我不使用二进制搜索而不是遍历数组，并按如下方式更改了我的实现：

public static int findNextTowerIndex(final int[] houseLocations, final int houseNotCoveredIndex, final int transmitterRange) {
    final int houseLocationWeWantToCover = houseLocations[houseNotCoveredIndex];
    final int farthestHouseLocationAllowed = houseLocationWeWantToCover + transmitterRange;
    int nextTowerIndex = Arrays.binarySearch(houseLocations, 0, houseLocations.length, farthestHouseLocationAllowed);

    if (nextTowerIndex < 0) {
        nextTowerIndex = -nextTowerIndex;
        nextTowerIndex = nextTowerIndex -2;
    }

    return nextTowerIndex;
}

public static int nextHouseNotCoveredIndex(final int[] houseLocations, final int towerIndex, final int transmitterRange) {
    final int towerCoversUntil = houseLocations[towerIndex] + transmitterRange;
    int nextHouseNotCoveredIndex = Arrays.binarySearch(houseLocations, 0, houseLocations.length, towerCoversUntil);

    if (-nextHouseNotCoveredIndex > houseLocations.length) {
        return -1;
    }

    if (nextHouseNotCoveredIndex < 0) {
        nextHouseNotCoveredIndex = - (nextHouseNotCoveredIndex + 1);
        return nextHouseNotCoveredIndex;
    }

    return nextHouseNotCoveredIndex + 1;
}

并且我期待性能的大幅提升，因为现在我将最多循环 log(N) 次，而不是 O(N).. 所以 test_01 输出：

Took: 297 milliseconds..

记住，之前是 Took: 359 毫秒。对于 test_02:

Took: 18047 milliseconds..

所以我总是在 20 秒左右的数组遍历实现和 18-19 秒的二进制搜索实现中获得值。

我原以为使用 Arrays.binarySearch 会有更好的性能提升，但显然事实并非如此，这是为什么？我错过了什么？我是否需要一个大于 73382 的数组才能看到好处，还是它无关紧要？

编辑 #01

在@huck_cussler 的评论之后，我尝试将我拥有的数据集加倍和加倍（使用随机数）并尝试运行ning test02（当然在测试中将数组大小加倍本身..）。对于线性实现，时间是这样的：

Took: 18789 milliseconds..
Took: 34396 milliseconds..
Took: 53504 milliseconds..

对于二进制搜索实现，我得到的值如下：

Took: 18644 milliseconds..
Took: 33831 milliseconds..
Took: 52886 milliseconds..

Answer 1

您的时间包括从您的硬盘中检索数据。这可能会占用您的大部分运行时间。从您的计时中省略数据加载，以更准确地比较您的两种方法。想象一下，如果它占用 18 秒，而你比较的是 18.644 和 18.789（改进 0.77%）而不是 0.644 和 0.789（改进 18.38%）。

如果你有一个 O(n) 的线性操作，例如加载一个二进制结构，并且你将它与一个 O(log n) 的二分搜索结合起来，你最终得到 O(n)。如果您相信大 O 表示法，那么您应该期望 O(n + log n) 与 O(2 * n) 没有显着差异，因为它们都减少到 O(n)。

此外，二分搜索的性能可能优于或低于线性搜索，具体取决于塔楼之间的房屋密度。考虑一下，假设有 1024 个家庭，每 4 个家庭平均分布一座塔楼。线性搜索将每塔步进 4 次，而二分搜索将每塔走 log2(1024)=10 步。

还有一件事...您的 minNumOfTransmitters 方法正在对从 test_01 和 test_02 传入的已经排序的数组进行排序。该求助步骤比您的搜索本身花费的时间更长，这进一步掩盖了您的两种搜索算法之间的时间差异。

======

我创建了一个小时间 class 以更好地了解正在发生的事情。我已经从 minNumOfTransmitters 中删除了代码行以防止它重新运行排序，并向 select 添加了一个布尔参数是否使用您的二进制版本。它总计 400 次迭代的时间总和，将每个步骤分开。我系统上的结果表明加载时间使排序时间相形见绌，而排序时间又使求解时间相形见绌。

  Load:  22.565s
  Sort:   4.518s
Linear:   0.012s
Binary:   0.003s

很容易看出优化最后一步对整体运行时间没有太大影响。

private static class Timing {
    public long load=0;
    public long sort=0;
    public long solve1=0;
    public long solve2=0;
    private String secs(long millis) {
        return String.format("%3d.%03ds", millis/1000, millis%1000);
    }
    public String toString() {
        return "  Load: " + secs(load) + "\n  Sort: " + secs(sort) + "\nLinear: " + secs(solve1) + "\nBinary: " + secs(solve2);
    }
    public void add(Timing timing) {
        load+=timing.load;
        sort+=timing.sort;
        solve1+=timing.solve1;
        solve2+=timing.solve2;
    }
}

static Timing test_01() throws FileNotFoundException {
    Timing timing=new Timing();
    long start = System.currentTimeMillis();
    final File file = new File("c:\path\to\xnpwdiG3.txt");
    final Scanner scanner = new Scanner(file);
    int[] houseLocations = new int[73382];
    for (int counter = 0; counter < 73382; counter++) {
        houseLocations[counter] = scanner.nextInt();
    }
    timing.load+=System.currentTimeMillis()-start;
    start=System.currentTimeMillis();
    final int[] uniqueHouseLocationsSorted = HackerlandRadioTransmitters.uniqueHouseLocationsSorted(houseLocations);
    timing.sort=System.currentTimeMillis()-start;
    start=System.currentTimeMillis();
    final int minNumOfTransmitters = HackerlandRadioTransmitters.minNumOfTransmitters(uniqueHouseLocationsSorted, 73381, false);
    timing.solve1=System.currentTimeMillis()-start;
    start=System.currentTimeMillis();
    final int minNumOfTransmittersBin = HackerlandRadioTransmitters.minNumOfTransmitters(uniqueHouseLocationsSorted, 73381, true);
    timing.solve2=System.currentTimeMillis()-start;
    final long end = System.currentTimeMillis();
    return timing;
}

Answer 2

在您的时间测量中，您包括了比数组搜索慢得多的操作。即文件系统 I/O 和数组排序。 I/O 通常（reading/writing 来自文件系统、网络通信）比仅涉及 CPU 和 RAM 访问的操作慢几个数量级。

让我们以一种不在每次循环迭代时都读取文件的方式重写您的测试：

static void test_02() throws FileNotFoundException {
        final File file = new File("input.txt");
        final Scanner scanner = new Scanner(file);
        int[] houseLocations = new int[73382];
        for (int counter = 0; counter < 73382; counter++) {
            houseLocations[counter] = scanner.nextInt();
        }
        scanner.close();
        final int rounds = 400;
        final int[] uniqueHouseLocationsSorted = uniqueHouseLocationsSorted(houseLocations);
        final int transmitterRange = 73381;
        final long start = System.currentTimeMillis();
        for (int i = 0; i < rounds; i++) {
            final int minNumOfTransmitters = minNumOfTransmitters(uniqueHouseLocationsSorted, transmitterRange);
        }
        final long end = System.currentTimeMillis();
        System.out.println("Took: " + (end - start) + " milliseconds..");
}

注意在这个版本的测试中，文件只被读取一次，之后开始计时。通过以上，我得到 Took: 1700 milliseconds.. （或多或少几毫秒）的迭代版本和二进制搜索。所以我们还是看不出二分查找更快。那是因为几乎所有时间都用于对数组进行 400 次排序。

现在让我们从 minNumOfTransmitters 方法中删除对输入数组进行排序的行。无论如何，我们在测试开始时对数组进行排序（一次）。

现在我们可以看到事情要快得多。从 minNumOfTransmitters 中删除行 houseLocations = uniqueHouseLocationsSorted(houseLocations) 后，我得到：迭代版本的 Took: 68 milliseconds..。显然，由于这个持续时间已经很小，我们不会看到与二进制搜索版本有显着差异。

所以让我们将循环次数增加到：100000。
现在我得到 Took: 2121 milliseconds.. 的迭代版本和 Took: 36 milliseconds.. 的二进制搜索版本。

因为我们现在隔离了我们测量的内容并专注于数组搜索，而不是包括慢得多的操作，所以我们可以注意到二分搜索在性能上的巨大差异（更好）。

如果想看二分查找进入了多少次它的while循环，可以自己实现，加上一个计数器：

private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;
        int loop = 0;
        while (low <= high) {
            loop++;
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key) {
                low = mid + 1;
            } else if (midVal > key) {
                high = mid - 1;
            } else {
                return mid; // key found
            }
        }
        System.out.println("binary search looped " + loop + " times");
        return -(low + 1);  // key not found.
}

该方法是从 JDK 中的数组 class 复制而来的 - 我刚刚添加了循环计数器和 println。
当要查找的数组长度为73382时，循环只进入16次。这正是我们所期望的：log(73382) =~ 16.

Answer 3

我同意其他答案，即您的测试的主要问题是它们测量了错误的东西：IO 和排序。但我不认为建议的测试是好的。我的建议如下：

static void test_02() throws FileNotFoundException {

    final File file = new File("43620487.txt");
    final Scanner scanner = new Scanner(file);
    int[] houseLocations = new int[73382];
    for (int counter = 0; counter < 73382; counter++) {
        houseLocations[counter] = scanner.nextInt();
    }
    final int[] uniqueHouseLocationsSorted = uniqueHouseLocationsSorted(houseLocations);


    final Random random = new Random(0); // fixed seed to have the same sequences in all tests
    long sum = 0;
    // warm up
    for (int i = 0; i < 100; i++) {
        final int transmitterRange = random.nextInt(70000) + 1;
        final int minNumOfTransmitters = minNumOfTransmitters(uniqueHouseLocationsSorted, transmitterRange);
        sum += minNumOfTransmitters;
    }

    // actual measure
    final long start = System.currentTimeMillis();
    for (int i = 0; i < 4000; i++) {
        final int transmitterRange = random.nextInt(70000) + 1;
        final int minNumOfTransmitters = minNumOfTransmitters(uniqueHouseLocationsSorted, transmitterRange);
        sum += minNumOfTransmitters;
    }
    final long end = System.currentTimeMillis();
    System.out.println("Took: " + (end - start) + " milliseconds. Sum = " + sum);
}

另请注意，我删除了来自 findNextTowerIndex 的所有 System.out.println 调用以及来自 minNumOfTransmitters 的 nextHouseNotCoveredIndex 和 uniqueHouseLocationsSorted 调用，因为它们也会影响性能测试。

所以我认为这里重要的是：

将所有I/O和排序移出测量循环
在测量之外进行一些热身
对所有测量使用相同的随机序列
不要处理计算结果，因此 JIT 无法完全优化调用

通过这样的测试，我在我的机器上看到了大约 10 倍的差异：大约 80 毫秒与大约 8 毫秒。

如果你真的想在 Java 中进行性能测试，你应该考虑使用 JMH aka Java Microbenchmark Harness

Answer 4

同意其他答案，IO时间问题最大，排序次之，搜索是最后一次消费者。

同意 phatfingers 的例子，在你的问题中二分搜索有时比线性搜索更糟糕，因为完全线性搜索对每个元素进行一个循环（n 次比较）但是二分搜索运行塔次（O(logn)*#tower)），一个建议是二分查找不是从0开始，而是从当前位置开始

 int nextTowerIndex = Arrays.binarySearch(houseLocations, houseNotCoveredIndex+1, houseLocations.length, arthestHouseLocationAllowed)

那么应该O(logn)*#tower/2) 甚至，也许你可以计算每座塔覆盖多少房子 avg 然后先比较 avg 房子然后使用二进制搜索从 houseNotCoveredIndex + avg + 1 开始，但不确定性能会好得多。

ps：可以使用 TreeSet 作为排序和唯一性

public static int[] uniqueHouseLocationsSorted(final int[] houseLocations) {
    final Set<Integer> integers = new TreeSet<>();

    for (int houseLocation : houseLocations) {
        integers.add(houseLocation);
    }
    int[] unique = new int[integers.size()];
    int i = 0;
    for(Integer loc : integers){
        unique[i] = loc;
        i++;
    }
    return unique;
}

Answer 5

uniqueHouseLocationsSorted 效率不高，andy 解决方案似乎更好，但我认为这可以改善花费的时间（注意我没有测试代码）：

public static int[] uniqueHouseLocationsSorted(final int[] houseLocations) {
    int size = houseLocations.length;

    if (size == 0)  return null; // you have to check for null later or maybe throw an exception here

    Arrays.sort(houseLocations);

    final int[] houseLocationsUnique = new int[size];

    int previous = houseLocationsUnique[0] = houseLocations[0];
    int innerCounter = 1;

    for (int i = 1; i < size; i++) {
        int houseLocation = houseLocations[i];

        if (houseLocation == previous) continue; // since elements are sorted this is faster

        previous = houseLocationsUnique[innerCounter++] = houseLocation;
    }

    return Arrays.copyOf(houseLocationsUnique, innerCounter);
}

也考虑使用数组列表，因为复制数组需要时间。

为什么 Arrays.binarySearch 与遍历数组相比没有提高性能？

Why is Arrays.binarySearch not improving the performance compared to walking the array?

java

arrays

binary-search