Archive for October 2009

Bubblesort, кеши и быстродействие

Несколько интересных соображений, навеянных публикациями по dual-pivot quicksort.

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

Эффектов масса. Это может быть и изменение ассемблерного кода, и избавление от лишних аллокаций, и оптимизация доступа к данным, и многое многое другое. Вот на закуску – несколько замеров скорости вычисления старой доброй пузырьковой сортировки.

Continue reading ‘Bubblesort, кеши и быстродействие’ »