Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще - [14]
Представьте, что вы едете по незнакомой дороге и видите знак, который показывает, сколько километров до трех окрестных городов. Вы можете поддаться искушению и поехать в ближайший из них.
Нежадный алгоритм сложнее и часто приносит лучшие результаты. Можно увидеть его аналог в военных действиях, где быстрый успех, например защита столицы, приносится в жертву ради более важной победы. Вспомните, как русская армия обошлась с армией Наполеона в 1812 году.
Нежадный алгоритм может быть охарактеризован как длинная, или затянувшаяся, игра. Wall Street Journal недавно опубликовал статью о чемпионах по скрабблу из Нигерии. Их победа была обусловлена не обширным словарным запасом, а интуитивной практикой выбора более коротких слов. Вместо того чтобы подбирать семи- и восьмибуквенные слова, которые приносят больше очков, нигерийские игроки обнаружили, что игра четырех- и пятибуквенными словами приводит к улучшению стратегии в долгосрочной перспективе. Они сохраняли самые сочетаемые буквы для будущих раундов, когда им выпадали не лучшие варианты из мешка. Вот отрывок из статьи, рисующий преимущества такого подхода:
«Британцы лидируют со словом «утверждение», которое дало им 86 очков, но в следующие пять раундов им удавалось выбирать слова, которые приносили меньше 30 очков. После слова «анкета» (93) мистер Джигере вырвался вперед. В финале счет был 449 против 432. Члены команды-победительницы подняли своего чемпиона на руки и понесли по комнате под популярную нигерийскую песню «Мы победили».
Метод 3 устраняет один из недостатков метода 2, фокусируясь на задачах, которые действительно важны. Мы составляем список задач, событий или чего-либо еще и располагаем их по приоритету. Заметьте, что «приоритетность» бывает и функцией «времени завершения», поэтому можно сказать, что метод 2 также располагает задачи в соответствии с их приоритетом. Возьмем, к примеру, принтер. Если в очереди на печать стоит 10 документов по 50 страниц каждый, а за ними идет один одностраничный документ, то, возможно, для принтера имеет смысл поставить последнюю задачу в приоритет, а не заставлять ее ждать до самого конца печати. Разделение двух методов показывает, что приоритетность иногда базируется на других свойствах, а не только на времени выполнения.
Получая новое задание, мы можем поместить его не в конец списка, а куда-нибудь в середину – в зависимости от приоритетности. Включение нового пункта в середину списка приоритетных задач порой приводит к увеличению времени, пока вы стираете старые задачи, освобождая место под новые. В главе 12 мы поговорим о том, как компьютер выбирает способ хранения такого списка (который часто называют очередью с приоритетом), чтобы такие вставки совершались достаточно быстро. Часто в повседневной жизни этот алгоритм наиболее эффективен.
Вот как все три метода выглядят на графике:
При условии, что задачи не зависят друг от друга (то есть очередность выполнения более ранних заданий не связана с временем выполнения последующих задач), все три метода Кви займут одинаковое время.[35] Как было упомянуто в главе 1, мы сравниваем основные операции во всех трех методах, то есть оцениваем, сколько времени Кви тратит на работу над задачами. Если бы мы вместо этого рассматривали, скажем, время, которое уходит у Кви на составление и ведение ее списка задач, то мы бы сказали, что метод 1 занимает постоянное время, то есть 0, а метод 2 и метод 3 занимают в худшем случае логарифмический объем времени. Для чего концентрироваться на одном наборе опций и приносить в жертву другой? Возможно, потому первый набор больше способствует достижению итоговой цели по сравнению со вторым, поскольку составление и ведение списка заданий – не такое уж сложное дело.[36] Больше об этом будет рассказано в главах 10 и 12.
Недостаточно смотреть на относительные величины; когда речь идет о результате задания, все становится существенным. Это относится и к алгоритмам, исполняемым за постоянное время. Представьте работника парковки, который хочет впихнуть как можно больше машин в ряд, чтобы эффективнее использовать пространство. Все ваши алгоритмы по выезду с парковки могут быть таковыми, но уровень сервиса разительно отличается. Например, если не оставлять свободного проезда, то парковщику придется в худшем случае убрать восемь других машин, чтобы добраться до нужного авто. Если оставлять проезд свободным все время, то придется убирать максимум три машины. Введение временных ограничений на то, когда можно оставлять или забирать машины, с правилом «без привилегий на въезд и выезд» позволит вообще не убирать другие машины при возвращении авто клиенту.
Если Кви не удастся выполнить задание в полном объеме, то какой результат будет для нее вторым по значимости? Если она решит уделять больше внимания высокоприоритетным задачам, то вдруг первое же задание, за которое она возьмется, займет целую неделю? Можно ли это совместить?[37] Такие вопросы порой порождают творческие и оригинальные решения.
Отступление: в романе Кейго Хигашино «Страсть подозреваемого Х» (2005) учитель математики говорит о решении геометрической задачи путем превращения ее в алгебраическую, чтобы понять, как оценивают его студенты свои пробелы в знаниях. Это удивительное напоминание о том, насколько легко принимать прочитанное как данность, не оспаривая его. Мы интерпретируем новую информацию тем способом, который соответствует имеющимся у нас знаниям. Это явление ученый-компьютерщик Алан Кай назвал
