Вернёмся теперь к вопросу о том, какой же список следует считать «достаточно» длинным, и какой критерий сортировки – «достаточно» сложным.

Тестируйте, тестируйте и ещё раз тестируйте

Переходим от теории к практике: к тестам на реальных задачах.

Я производил свои тесты на Perl версии 5.6.1 (revision 5.0 version 6 subversion 1)[9]. Для оценки производительности кода использовался метод timethese стандартного пакета Benchmark. Все тесты производились на изначально несортированных, «случайных», массивах. Тесты производились многократно, результаты усреднялись.

Давайте для начала сравним производительность кода листинга 4 (без оптимизации) и листинга 6 (с оптимизацией).

При сортировке списка из 1000 однокилобайтных строк оптимизированный код показывает производительность, в пять раз превосходящую производительность неоптимизированного кода. При сортировке аналогичного списка из 100 элементов выигрыш от оптимизации снижается, становясь четырёхкратным. При работе со списком из 10 элементов выигрыш становится меньше трёхкратного. Для пяти элементов – менее двукратного. Наконец, с двухэлементным списком оптимизированная сортировка работает примерно вдвое медленнее, чем неоптимизированная[10].

Для иллюстрации ещё одного приёма оптимизации и тестов предлагаю средней сложности сортировку.

Пусть у нас имеется некий список версий вида:

Листинг 8

# Список версий

@unsorted=('Ver 1.0',

           'version 1.1',

           'v. 1.10',

           'ver 2.20',

           'Ver 2.0',

           'Version 2.3',

           'V 2.12');

Нам необходимо отсортировать его по возрастанию номера версии. Сортировка по алфавиту (как в листинге 1) не даст ничего удовлетворительного. Сортировка версий, как десятичных дробей тоже потерпит крах, так как в этом случае окажется, что 1.1 равно 1.10, а 2.3 больше, чем 2.12. Здесь нужен более деликатный подход[11].