Алгоритмы неформально. Инструкция для начинающих питонистов - [27]

Однако у сортировки методом вставки есть один критический недостаток: она слишком долго выполняется. На вашем компьютере код из листинга 4.2 почти наверняка выполнялся меньше секунды, поэтому «слишком долго» для сортировки методом вставки не сравнится с временем, которое понадобится для превращения маленького желудя в могучий дуб, или даже с временем, которое мы проводим в очереди в автоинспекции. Скорее это слишком долго по сравнению с временем, за которое комар взмахивает крыльями.

Может показаться, что беспокоиться о том, что алгоритм выполняется «слишком долго» по сравнению со взмахом комариных крыльев, — это перебор. Однако есть несколько веских причин для того, чтобы использовать алгоритмы, выполняющиеся как можно быстрее.

Почему так важна эффективность

Первая причина неустанно стремиться к эффективности алгоритмов заключается в том, что они наращивают нашу вычислительную мощность. Если ваш неэффективный алгоритм сортирует список из восьми элементов за минуту, то это вроде бы не создает особых проблем. Но подумайте, что на сортировку списка из тысячи элементов такому неэффективному алгоритму потребуется час, а списка из миллиона элементов — неделя. На сортировку списка из миллиарда элементов может уйти год или столетие (если это вообще получится сделать). Если улучшить алгоритм так, чтобы он быстрее сортировал список из восьми элементов (вроде бы тривиальная задача, которая экономит всего минуту), то это может привести к тому, что список из миллиарда элементов будет сортироваться за час, а не за столетие, что может открыть много новых возможностей. Современные методы машинного обучения — такие как кластеризация методом k-средних или метод k-ближайших соседей — зависят от упорядочения длинных списков. Улучшение производительности таких фундаментальных алгоритмов, как сортировка, позволит нам выполнять такие методы с большими наборами данных, которые иначе бы выходили за пределы наших возможностей.

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

Последняя причина для создания быстрых алгоритмов — та же, по которой люди стараются добиться наилучших результатов в любом деле. Хотя нет очевидной необходимости, люди стараются быстрее пробегать стометровку, лучше играть в шахматы и готовить пиццу вкуснее, чем кто-либо прежде. Они делают это по той же причине, которой Джордж Мэллори объяснил свое желание покорить Эверест: «Потому что он есть». Человеческая природа заставляет пытаться выходить за пределы возможного и стараться создать лучшие, более быстрые, мощные и умные алгоритмы, чем создавали другие. Исследователи алгоритмов стараются добиться лучших результатов, поскольку среди прочего пытаются сделать что-то выдающееся независимо от того, приносит оно практическую пользу или нет.

Точное измерение времени

Так как время, необходимое для выполнения алгоритма, очень важно, оценкам типа «слишком долго» или «меньше секунды» не хватает точности. Сколько именно оно занимает? Чтобы получить буквальный ответ, можно воспользоваться модулем timeit на Python. Он позволяет создать таймер, который запускается непосредственно в начале сортировки и останавливается сразу же после ее завершения. Вычисляя разность между начальным и конечным временем, можно определить, сколько времени понадобится для выполнения кода.

from timeit import default_timer as timer

start = timer()

cabinet = [8,4,6,1,2,5,3,7]

sortedcabinet = insertion_sort(cabinet)

end = timer()

print(end - start)

Когда я выполнил этот код на моем обычном ноутбуке, на это потребовалось около 0,0017 секунды. Это дает разумную оценку эффективности алгоритма сортировки методом вставки — он способен полностью отсортировать список из восьми элементов за 0,0017 секунды. Если вы хотите сравнить сортировку методом вставки с любым другим алгоритмом сортировки, то можно сравнить результаты хронометража timeit с другим хронометражем, определить, какой работает быстрее, и сказать, что быстрый алгоритм лучше.

Однако сравнение быстродействия алгоритмов по хронометражу создает некоторые проблемы. Например, когда я запустил код хронометража на своем ноутбуке во второй раз, он был выполнен за 0,0008 секунды. В третий раз оказалось, что на другом компьютере он был выполнен за 0,03 секунды. Точный хронометраж, который вы получаете, зависит от скорости и архитектуры оборудования, текущей загруженности операционной системы (ОС), используемой версии Python, внутреннего планировщика задач ОС, эффективности вашего кода и, вероятно, других случайностей, движения электронов и фаз луны. Так как мы можем получать сильно различающиеся результаты при разных попытках измерения эффективности, трудно полагаться на хронометраж для оценки сравнительной эффективности. Один программист хвастается, что может отсортировать список за Y секунд, другой смеется и говорит, что его алгоритм эффективнее и справляется с задачей за Z секунд. Может оказаться, что они выполняли абсолютно одинаковый код, но на разном оборудовании в разное время, поэтому сравнение дает оценку не эффективности алгоритма, а вычислительной мощности оборудования и везения.