Не забывайте тривиальные алгоритмы

Почти все программисты по ходу учёбы изучают различные тривиальные алгоритмы. Действительно, многие алгоритмы (поиск, сортировка, всякие там операции с векторами\матрицами\графами) очень легко и понятно реализуются "в лоб". Что-то типа:

for (size_t i = 0; i < N; ++i)

{

	for (size_t j = 0; j < M; ++j)

	{

		// делаем что-нибудь

	}

}


Сразу после объяснения такого алгоритма в книге обычно большими буквами написано, что, алгоритм, мол, приведен только в учебных целях и никогда-никогда не применяйте его на практике. А причиной тому, как правило, назывались большие требования к памяти и вычислительная сложность (как правило у таких алгоритмов она О(N²), а иногда и того хуже). Дальше в книге обычно следует информация о том, что есть куда более умные алгоритмы решения данной задачи - ну например со сложностью в О(N*log(N)). В этом месте трудолюбивые садились разбираться в этих (часто сложных) алгоритмах, а лентяи просто находили в своём любимом языке\библиотеке\фреймворке функцию с уже реализованным таким алгоритмом и решали в будущем не парить себе мозги и использовать её. Оба решения имею право на жизнь - первое чуть правильнее в стратегическом плане, второе - в тактическом. Но вот людей, которые всерьёз решили бы использовать тот самый первый, тривиальный алгоритм, не остаётся вовсе. Ну и хорошо! Или нет?

Историческая ремарка
Давайте посмотрим на современное состояние развития разного компьютерного железа. Стоимость памяти всех видов изрядно упала, скорость доступа к ней изрядно возросла. Оба процесса продолжают развиваться. При этом рост тактовой частоты процессоров прекратился. Их развитие сфокусировано нынче на многоядерности и использовании более эффективных наборов инструкций (SSE, AVX). А теперь давайте вернемся к нашим тривиальным и нетривиальным алгоритмам.

Вычислительная сложность
Нынче и детей в садике, мне кажется, учат, что О(N*log(N)) это лучше, чем О(N*N), а О(log(N)) лучше, чем О(N). Но означают ли эти обозначения "лучше всегда" ? Нет. Символ О не означает "точное количество операций". Он говорит лишь о линейной зависимости количества операций от того, что написано в скобках. Т.е. алгоритм со сложностью О(N) может выполнятся ровно за N операций, а алгоритм со сложностью О(log(N)) - за 9999999 * log(N). Ну, положим, пример с "9999999" надуман, но вот в пределах нескольких десятков или сотен это число может быть вполне. Отсюда следует, что есть некоторое число K, до которого тривиальный алгоритм будет работать лучше, чем сложный. Да, пускай оно невелико. Просто запомните, что оно есть - это нам пригодиться дальше.

Предсказание ветвлений (переходов)
Возможно, вы знаете, о такой штуке как предсказание ветвлений (переходов). Грубо говоря, процессор в попытках работать эффективнее "забегает наперед" и пытается угадать, куда пойдет ваша программа в следующем условии и начать выполнять эту ветку кода до вычисления самого условия. Если условие выполняется - ура, мы имеем уже некоторую часть выполненной работы, если нет - результаты выбрасываются и начинается просчёт альтернативной ветки. К чему это я? Дело в том, что в тривиальных алгоритмах часто весьма мало условий (они просто обрабатывают весь массив данных). Соответственно, предсказание переходов для них работает прекрасно - "всегда идём вперед". Хитрые же алгоритмы для снижения вычислительной сложности применяют всякие эвристики, которые как раз включают много условий. Каждое условие - вероятность неверного предсказания ветвления, лишняя работа процессора. А значит, наше число К (см. предыдущий пункт) увеличивается.

Кэширование и Prefetch
В процессоре есть регистры. А еще есть кэши разного уровня. Доступ к ним в разы (и десятки раз) быстрее, чем к памяти. Тривиальные алгоритмы славятся своей линейностью. Т.е. данные читаются по порядку, а значит программист (или компилятор, или процессор) может загрузить в кэш сразу блок последовательных данных и хорошо сэкономить на доступе к памяти. Сложные алгоритмы в своей сути имеют задачу отбросить некоторое количество исходных данных или использовать их каким-то хитрым образом (построить временное дерево или хеш-таблицу). Понятное дело, это требует произвольного доступа к памяти - а значит кеширование и prefetch работают намного хуже. Опять таки - число К растет.

Память
Большие требования к объемам памяти, которыми пеняют тривиальные алгоритмы, понемногу становятся не так уж страшны. Рост объемов ОЗУ и HDD пока не упёрся в какие-то технологические рамки, при очередном апгрейде компа мы легко можем увеличить их в 2-4 (а то и больше) раз (чего не скажешь о тактовой частоте CPU). Кроме того, появляются такие занятные вещи, как SSD, многоканальная память и т.д. Даже при квадратичном требовании к памяти тривиальный алгоритм уже может оперировать сотнями тысяч записей - а очень часто больше и не надо. Кроме того, контроллеры памяти тоже быстрее отдают последовательные блоки, чем случайные. Число К растёт.

Векторные операции
Современные процессоры активно продвигают идею использования операций над блоками данных. Одна команда набора SSE или AVX заменяет от пары до десятка обычных инструкций, работая не сильно дольше времени выполнения одной из них. Тривиальные вычислительные алгоритмы идеально подходят для применения векторых инструкций (взяли вектор\матрицу - сложили\умножили с другой). Сложные - не всегда. В этом месте наше К увеличивается особенно круто - в пару раз.

Распараллеливание
Есть матрица NxN, квадратичный алгоритм и 4 ядра процессора. Распараллелить? Элементарно. Делим матрицу на четверти - и вперед. Можно с большой долей вероятности сказать, что распараллеливание будет эффективным, а простои минимальными. Теперь вспомним какой-нибудь сложный алгоритм с его рекурсией, графами и хеш-таблицами. Распараллелить? Хм. Можно попробовать. Но получится с большой вероятностью хуже. Ну потому что не угадаешь, как функция хеширования будет себя вести, и насколько быстро пройдется поиск по графу и т.д. И снова простой алгоритм в плюсе.

Выводы
Нет, я не фанатик-ретроград и понимаю, что на больших объёмах данных все высказанные в статье мысли яйца выеденного не стоят. Но на малых и средних - уже даже сейчас тривиальные алгоритмы весьма часто могут выиграть у теоретически более эффективных. Эта идея применена, например, в одном из лучших на сегодня алгоритмов сортировки Timsort, который при N < 64 перестаёт выпендриваться и вырождается в обычную сортировку вставками, поскольку честно признаёт её наиболее эффективной в данном случае. Скажете, 64 - это очень мало? Ну вот вам алгоритм Машека и Патерсона, который, имея сложность О(N*N/log(N)) начинает обгонять алгоритм Вагнера и Фишера со сложностью О(N²) только при N > 262418 (доказано самими авторами).

А знаете ли вы, начиная с каких величин применяемые вами сложные алгоритмы становятся эффективнее тривиальных? Или всегда просто смотрите на оценку сложности и всё?
For more complete information about compiler optimizations, see our Optimization Notice.
Categories: