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

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

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

Задача

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

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

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

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

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

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

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.0057 сек
insertBinary: 0.0068 сек
insertInterpolation: 0.0068 сек

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

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

Стало понятно, что обычный замер времени на эти вопросы не ответит. Что ж, 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;
}

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

insertBruteForce: 0.0047 сек
insertBinary: 0.0040 сек
insertInterpolation: 0.0040 сек

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

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

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.0015 сек., что в 4 раза быстрее первоначального варианта.

Сразу скажу, что я не претендую на то, что это лучшее решение, для меня самого оно довольно неожиданное, а весь процесс был таким себе приключением.

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

Автор: marenkov

Источник