Почему Arrays.binarySearch не улучшает производительность по сравнению с ходом массива?

Ответ 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).

Кроме того, бинарный поиск может работать лучше или хуже линейного поиска в зависимости от плотности домов между башнями. Рассмотрим, скажем, 1024 дома с башней, равномерно распределенной каждые 4 дома. Линейный поиск будет выполняться 4 раза на каждую башню, тогда как бинарный поиск будет принимать log2 (1024) = 10 шагов на каждую башню.

Еще одна вещь... ваш метод minNumOfTransmitters сортирует уже отсортированный массив, переданный в него из test_01 и test_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 в целом (чтение/запись из файловой системы, сетевая связь) на порядок медленнее, чем операции, которые включают только доступ к ЦП и ОЗУ.

Перепишите свой тест таким образом, чтобы он не читал файл на каждой итерации цикла:

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. Мы сортируем массив (один раз) в любом случае в начале теста.

Теперь мы видим, что все гораздо быстрее. После удаления строки houseLocations = uniqueHouseLocationsSorted(houseLocations) из minNumOfTransmitters я получаю: 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.
}

Метод копируется из класса Arrays в JDK - я просто добавил счетчик циклов и println.
Когда длина массива для поиска равна 73382, цикл вводится только 16 раз. Это именно то, что мы ожидаем: log(73382) =~ 16.

Ответ 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);
}

Обратите внимание, что я удаляю все вызовы System.out.println из findNextTowerIndex и nextHouseNotCoveredIndex и uniqueHouseLocationsSorted вызовов из minNumOfTransmitters, поскольку они также влияют на тестирование производительности.

Итак, я думаю, что здесь важно:

• Перемещение всех операций ввода-вывода и сортировка из цикла измерения
• Проведите некоторое прогревание вне измерения.
• Используйте ту же случайную последовательность для всех измерений
• Не удаляйте результат вычисления, поэтому JIT не может оптимизировать этот вызов вообще

С таким тестом я вижу разницу в 10 раз на моей машине: около 80 мс против 8 мс.

И если вы действительно хотите выполнить тесты производительности на Java, вам следует рассмотреть возможность использования JMH aka Java Microbenchmark Harness

Ответ 4

Согласитесь с другими ответами, время ввода-вывода больше всего проблем, а сортировка - вторая, поиск - в последний раз.

И согласитесь с примером phatfingers, бинарный поиск когда-то худший, чем линейный поиск в вашей проблеме, потому что полностью линейный поиск идет по одному циклу для каждого элемента (n times compare), но бинарный поиск выполняется для времени башни (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;
}

Ответ 5

uniqueHouseLocationsSorted не эффективен, и решение кажется лучше, но я думаю, что это может улучшить время (обратите внимание, что я не тестировал код):

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

Рассмотрим также использование списка массивов, поскольку копирование массива требует времени.