Оптимизация для начинающих, или о пользе профилирования

Попалась мне задача написать на PHP оптимальный алгоритм вставки нового значения в упорядоченный массив. Причем аргументировано доказать, что именно этот алгоритм лучший. Для этого предлагалось написать три варианта и выбрать из них лучший. Конечно же я знаю, что лучший метод поиска — бинарный, но раз сказали доказать, что он лучший, так и быть, напишу еще два. С таким настроем и уверенностью в будущем результате я и принялся кодить.

Что из этого получилось приглашаю начинающих программистов почитать, а опытных обсудить.

Задача

Есть достаточно большой (10 тыс. элементов) упорядоченный массив с числами. Надо оптимальным образом вставить в него новое значение сохранив упорядоченность.

Варианты решения

Самый простой способ — вставить в конец и пересортировать встроенной функцией. Но изначально стояло условие так не делать.

Что же надо сделать, чтобы вставить новое значение? Для начала найти нужную позицию. С учетом размера массива, вероятно, это будет самая ресурсоемкая часть. А затем вставить это значение в найденную позицию. Значит надо написать 3 варианта поиска этой самой позиции. В качестве подопытных кроликов берем: перебор, бинарный поиск, поиск с интерполяцией (похож на бинарный, только делим не пополам, а пытаемся более точно угадать позицию).

Кому не интересно, программный код функций поиска можно пропустить.

Поиск перебором

function insertBruteForce(&$array, $value)
{
function insertBruteForce(&$array, $value)
{
    foreach($array as $position => $test) {
        if ($test >= $value) {
                break;
        }
    }

    insertTo($array, $position, $value);
}

Бинарный поиск

function insertBinary(&$array, $value)
{
    $begin = 0;
    $end   = count($array) - 1;

    while ($end - $begin > 1) {
        $position = round(($begin + $end) / 2);
        if ($array[$position] > $value) {
            $end = $position;
        } elseif ($array[$position] < $value) {
            $begin = $position;
        } else {
            break;
        }
    }

    if ($array[$position] < $value) {
        ++$position;
    }

    insertTo($array, $position, $value);
}

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

Поиск с интерполяцией

function insertInterpolation(&$array, $value)
{
    $begin = 0;
    $end   = count($array) - 1;

    while ($end - $begin > 1) {
        $range           = $array[$end] - $array[$begin];
        $percentPosition = ($value - $array[$begin]) / $range;
        $position        = $begin + round(($end - $begin) * $percentPosition);
        $position        = min($position, $end);
        if($array[$position] <= $value && (!isset($array[$position+1]) || $array[$position+1] >= $value)) {
            break;
        } elseif ($array[$position] > $value) {
            $end = $end != $position ? $position : $position - 1;
        } elseif ($array[$position] < $value) {
            $begin = $begin != $position ? $position : $position + 1;
        }
    }

    if ($array[$position] < $value) {
        ++$position;
    }

    insertTo($array, $position, $value);
}

Вставка значения в найденную позицию

Ну это должно быть просто (как я тогда думал). Однако в PHP нет встроенной функции вставки нового значения в заданную позицию, есть только замещение значения. Не страшно, воспользуется тем, что есть — разрежем, вставим значение и склеим. Это же не перебор массива, сделать надо только раз, используем встроенные функции, они же быстро работают.

function insertTo(&$array, $position, $value)
{
    $array = array_merge(array_slice($array, 0, $position), array($value), array_slice($array, $position));
}

Как оказалось позже, так делать не следует.

Результаты тестирования

Быстренько пишу код для генерации случайного массива с данными, тест для многократного запуска и сбора статистики. И вот тут случилось нечто странное. Результат был примерно таким:

insertBruteForce: 0.0088
insertBinary: 0.0088
insertInterpolation: 0.0087

Отсутствие разницы между бинарным поиском и интерполяцией еще можно объяснить. Но почему простой перебор дает такой же результат? Увеличение массива соотношение сил не меняет.

Профайлинг спешит на помощь

Стало понятно, что обычный замер времени на эти вопросы не ответит. Что ж, Xdebug уже установлен и настроен, осталось только включить в нем профилирование и посмотреть, что же происходит.

И тут меня снова ждал сюрприз. Основную часть времени занимал не поиск позиции, а вставка нового элемента в найденную позицию. При этом время выполнения самого поиска уже мало влияло не результат.

Значит надо переписать функцию вставки. Вместо разрезать и склеить пробую раздвинуть и вставить.

function insertDown(&$array, $value)
{
    $i = count($array);
    for ($i = $i - 1; $i >= 0 && $array[$i] < $value; --$i) {
        $array[$i+1] = $array[$i];
    }

    $array[$i] = $value;
}

Уже лучше, но все еще не правильно.

Такой вариант работает на 40% быстрее да и памяти расходует меньше. И результат получился таким:

insertBruteForce: 0.0052
insertBinary: 0.0053
insertInterpolation: 0.0053

А теперь еще раз смотрим на последнюю функцию. Что она делает? Она отодвигает элементы пока не дойдет до нужной позиции. А действительно ли ей заранее надо знать позицию?

Поиск и вставка в одном флаконе

function insertDown(&$array, $value)
{
    $i = count($array);
    for ($i = $i - 1; $i >= 0 && $array[$i] >= $value; --$i) {
        $array[$i+1] = $array[$i];
    }

    $array[$i] = $value;
}

Результат: всего одна простая функция (да, с перебором) и время прохождения тестов за 0.0049 сек., пока что лучший результат.

О пользе коллективного разума

Добавлено на следующий день
В результате обсуждения здесь товарищами и мной самим в коде были выявлены ошибки, которые я допустил во время его правок (начальный вариант я протестировал, но затем начал эксперименты). Уже исправил и вставил в текст обновленные результаты.

PQR подсказал заменить функцию вставки значения такой:

function insertTo(&$array, $position, $value)
{
    array_splice($array, $position, 0, $value);
}

Оказывается функция вставки в PHP есть, но она является частью более универсальной. Результат теста:

insertBruteForce: 0.0035
insertBinary: 0.0036
insertInterpolation: 0.0037
insertDown: 0.0047

Еще лучше, но все еще странно.

SerafimArts предложил использовать класс SplFixedArray вместо обычного массива. Пробую. Функцию вставки пришлось правда снова сделать «ручной»:

function insertTo($array, $position, $value)
{
    $size = $array->count();
    $array->setSize($size + 1);
    for ($i = $size - 1; $i >= $position; --$i) {
        $array[$i+1] = $array[$i];
    }

    $array[$position] = $value;
}

Рузультат:

insertBruteForce: 0.0033
insertBinary: 0.0019
insertInterpolation: 0.0018
insertDown: 0.0026

У всех вариантов время выполнения уменьшилось. И что самое интересное, результат именно тот, что ожидался изначально и именно такой как нас учили в универе.

Эпилог

Знания и предположения — это хорошо, но надо проверять, что же происходит на практике. Правильный инструмент для этого не общепринятый:

        $start = microtime(true);
        <какой-то код>
        $time = microtime(true) - $start;

а профайлинг. Хотя и вышеприведенный метод может быть полезен, все же профилирование дает более подробную информацию и собирает статистику не только там где вы это явно указали (хотя так тоже можно).

Во время экспериментов с кодом надо быть очень внимательным писать автоматические тесты. В моем случае это бы исключило ряд допущенных во время его правок ошибок.

Всем комментаторам большое спасибо за подсказки и высказанные предположения.