Обставляя двоичный поиск

Быстро, какой самый быстрый способ поиска в упорядоченном массиве?

Двоичный поиск, правильно?

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

Вот простой пример: предположим, у вас есть массив размером 10, в котором содержится равномерно распределенная выборка чисел от 0 до 99. Интерполяционный поиск работает так же, как искал бы человек. Если бы вам требовалось найти 3, вы бы, наверное, попробовали бы первую ячейку, если бы требовалось найти 85, вы могли бы попробовать девятую ячейку слот и т.д.

Хорошо, этот подход делает лучшие предположения о позиции искомого ключа, но делает ли он асимптотически меньше итераций в среднем?

Ответ таков, что на самом деле он делает экспоненциально меньше итераций - он работает за время lg lg N, где N - размер массива. Анализ немного сложноват - он появился спустя 19 лет после официальной публикации алгоритма (согласно тому Кнута "Сортировка и поиск"). Мне нужно было отыскать его (и прежде чем я смог найти его, сначала я должен был убедиться, это не я изобрел его, и выяснить, как он назывался), и действительно каждый шаг уменьшает интервал до N^0,5 вместо 0,5 * N, что дает лучшее асимптотическое время работы. Это в среднем, поэтому стоит отметить, что дисперсия числа сравнений равна также lg lg N. Это означает, что предполагая, что ваш ключи хорошо распределены, вы почти наверняка получите среднее время работы или очень близко к нему (я попробовал его на случайных массивах и теория оказывается пугающе точной).

Так почему этот метод не используется на практике? Наверное, потому, что lg N уже достаточно мало. В конце концов, если у вас есть массив размером 2³², он дает сокращение с ~ 32 до ~ 5 сравнений, что с практической точки зрения, вероятно, не является большим ускорением поиска в массиве.

Однако мы получили огромную пользу от него в проекте "Вольдерморт" (Voldermort). Мы используем его при обработке очень больших файлов только для чтения, хранилищ "Вольдерморта". Что позволяет нам ежедневно вести огромный цикл обработки данных на Hadoop, как описано здесь. Структура данных, используемая для этого, использует огромный отсортированный индексных файл, по которому ведется поиск, и в котором хранятся MD5-хэши ключей. Поскольку сортировка идет по значениям MD5, это гарантирует, что файл равномерно распределен над пространством ключей, и зачастую может быть размером во много гигабайт. Эти файлы отображаются в память, чтобы снизить затраты на чтение, но улучшенный алгоритм поиска может помочь значительно сократить количество операций позиционирования головок, если индекс не полностью помещается в памяти.Одна операция позиционирования стоит около 10ms, поэтому экономия даже одной или двух - огромный выигрыш в производительности.

Иногда бывает полезно видеть, как оно выглядит на реальном примере. Для равномерно распределенных значений, заданном ключе для поиска, массиве для поиска, а также минимальном и максимальном значениях оно может выглядеть примерно так:

int interpolationSearch(int key, int[] array, int min, int max) {
    int low = 0;
    int high = array.length - 1;
    while(true) {
        if(low > high || key < min || key > max)
            return -1;

        // make a guess of the location
        int guess;
        if(high == low) {
            guess = high;
        } else {
            int size = high - low;
            int offset = (int) (((size - 1) * ((long) key - min)) / (max - min));
            guess = low + offset;
        }

        // maybe we found it?
        if(array[guess] == key)
            return guess;

        // if we didn't find it and we are out of space to look, give up
        if(guess == 0 || guess == array.length - 1)
            return -1;

        // if we guessed to high, guess lower or vice versa
        if(array[guess] > key) {
            high = guess - 1;
            max = array[guess-1];
        } else {
            low = guess + 1;
            min = array[guess + 1];
        }
    }
}

Вы можете увидеть реальную реализацию в "Волдеморте" здесь - оно немного сложнее, поскольку использует нецелые ключи и ищет в файле, но основная схема та же самая.

//jay @ SNA Projects Blog