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

arrays binary-search java

2022-09-02 03:59:01

总而言之，挑战如下：

Hackerland是一个拥有n栋房屋的一维城市，其中每个房屋i位于x轴上的某个x _i处。市长想在城市房屋的屋顶上安装无线电发射器。每个发射器都有一个范围k，这意味着它可以将信号传输到≤k单位距离之外的所有房屋。

给定一张哈克兰的地图和k的值，你能找到覆盖每个房子所需的最小发射器数量吗？

我的实现如下：

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..");
}

输入.txt可以从此处下载。（这不是这个问题中最重要的细节，但仍然..）所以我们有一个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..

请记住，它是“已用：359毫秒”。以前。对于test_02：

Took: 18047 milliseconds..

因此，使用数组遍历实现，我总是在 20 秒左右获得值，在二进制搜索实现中始终获得 18 - 19 秒的值。

我期望使用Arrays.binarySearch获得更好的性能提升，但显然情况并非如此，为什么会这样？我错过了什么？我是否需要一个超过 73382 的数组才能看到好处，还是无关紧要？

编辑 #01

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

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

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

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

答案 1

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

如果你有一个线性运算O（n），例如加载一个二元结构，并且你把它与二进制搜索O（log n）组合在一起，你最终会得到O（n）。如果你信任 Big O 表示法，那么你应该期望 O（n + log n）与 O（2 * n）没有显著差异，因为它们都都简化为 O（n）。

此外，二进制搜索可能比线性搜索执行得更好或更差，具体取决于塔之间房屋的密度。假设每4个家庭中有1024个家庭，塔楼均匀分布。线性搜索将每个塔执行 4 次，而二进制搜索将采用 log2（1024）=每个塔 10 步。

还有一件事...您的方法正在对从和中传递到其中的已排序数组进行排序。该求助步骤比搜索本身花费的时间更长，这进一步模糊了两种搜索算法之间的时间差异。minNumOfTransmitterstest_01test_02

======

我创建了一个小型的计时课，以便更好地了解正在发生的事情。我已经从minNumOfTransmitters中删除了代码行，以防止它重新运行排序，并添加了一个布尔参数来选择是否使用二进制版本。它总计 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;
}

答案 2

在时间测量中，您包括比数组搜索慢得多的操作。即文件系统 I/O 和数组排序。一般来说，I/O（从文件系统读取/写入，网络通信）比仅涉及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..");
}

请注意，在此版本的测试中，文件仅读取一次，之后开始时间测量。通过上述内容，我得到了（或多或少的几毫）迭代版本和二进制搜索。因此，我们仍然看不到二进制搜索更快。这是因为几乎所有的时间都用于对数组进行排序 400 次。Took: 1700 milliseconds..

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

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

因此，让我们将循环轮次数增加到：。
现在我得到了迭代版本和二进制搜索版本。100000Took: 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中的Arrays类复制的 - 我刚刚添加了循环计数器和println。
当要搜索的数组的长度为 73382 时，循环仅输入 16 次。这正是我们所期望的：.log(73382) =~ 16