Оптимизация для начинающих, или о пользе профилирования
Попалась мне задача написать на 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 раза быстрее первоначального варианта.
Сразу скажу, что я не претендую на то, что это лучшее решение, для меня самого оно довольно неожиданное, а весь процесс был таким себе приключением.
В комментариях буду раз увидеть любые комментарии по поводу того, почему именно такие результаты, и как еще можно это улучшить.
