Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще - [13]
Все эти методы наверняка знакомы. Применяя метод 1, мы используем единицы времени, чтобы определять, когда переключиться с одного задания на другое. Например, у нас три набора заданий по трем различным предметам в школе, и все нужно сдать до конца недели. Можно посвятить утро одному предмету, день – второму, а вечером заняться третьим. На следующий день повторяем эту схему и так далее, пока не будут готовы все задания. Этот метод распределения времени – хороший пример того, как современные операционные системы справляются с многочисленными приложениями, и его иногда называют контекстным переключением. Диспетчер следит за текущими процессами,[33] отводит им определенное время, а потом контролирует, чтобы каждый процесс умещался в предписанный ему хронометраж.
Переключение между процессами происходит так плавно, что при наблюдении за операционной системой создается впечатление, будто они протекают параллельно. Сегодня при наличии многоядерных процессоров так оно и есть. Четырехъядерный процессор может одновременно вести четыре процесса, и контекстуальное переключение ему требуется только тогда, когда процессов запускается больше, чем у него ядер.
Это напоминает приложение параллельной обработки, которое имеет аналог в реальной жизни и называется конвейерной обработкой. Набор взаимосвязанных заданий распределяется и выполняется так, чтобы оптимизировать имеющиеся в наличии ресурсы. Например, вы с двумя вашими друзьями вдруг вспомнили, что забыли приготовить мешки с подарками для гостей, а вечеринка вот-вот закончится. Чтобы сделать как можно больше мешков в единицу времени, эффективно применить что-то вроде конвейерного метода: вы пишете поздравления на мешке, один друг складывает в него подарки, а второй – завязывает мешки лентой. Это лучше других подходов, когда один или оба ваших друга будут ждать, пока вы подпишете все мешки. Распределение заданий важно, но до определенной степени: как однажды написал Фред Брукс, девять женщин не родят ребенка за один месяц.
При современных характеристиках «железа» мы не замечаем границ возможностей контекстуального переключения. Между тем каждый раз, когда система его выполняет, ей нужно придержать состояние последнего процесса, очистить регистры и удалить передаваемые данные, а затем загрузить новое состояние процесса.[34]
Для человека когнитивная нагрузка, которая сопровождает этот тип переключения, может быть довольно серьезной. Одно из препятствий на пути обеспечения продуктивности – необходимость прервать текущее занятие, переключиться на что-то срочное, а затем вернуться к предыдущему делу. Операционная система работает подобным образом, запуская так называемый обработчик прерываний, который может временно остановить текущий процесс, чтобы либо передать ему некоторые данные, которых ждет система, либо изменить приоритетность задач.
Если время прерывания достаточно велико, мы можем побороться, приводя разум в состояние, необходимое для выполнения оригинального задания. Контекстное переключение имеет определенные преимущества – оно гарантирует, что мы поработаем по крайней мере над какой-то частью каждого задания. В то же время, когда задача имеет временные рамки, стратегия «Не пропускать ни одного задания» грозит разочарованием и переутомлением.
Метод 2 – это подход, знакомый многим любителям откладывать на потом. В соответствии с ним нужно оставлять сложные задачи под самый конец, а вначале делать только самое простое. Его преимущество в том, что он приносит множество небольших, но быстрых побед. Его часто называют жадным алгоритмом, но этот термин необязательно подразумевает пренебрежение какими-либо делами. Он просто подчеркивает, что алгоритм пытается достичь максимального результата за счет минимума усилий.
Удачное применение жадного алгоритма – найти самую быструю дорогу из одной точки в другую, например, между двумя городами. Мы спрашиваем себя в каждом пункте: «До какого города здесь ближе всего?» Это хороший способ принимать решения, хотя он может помешать вам увидеть оптимальные пути на ранних этапах путешествия. Мы уже встречали разновидность такого подхода в главе 4, хотя Иоаннис просто хотел выбраться из лабиринта и не задумывался, сколько времени у него это займет.
Об алгоритмах поиска кратчайшего пути написано много, и здесь есть несколько соперничающих друг с другом подходов. Один из самых известных называется алгоритмом Дейкстры. Он был создан в 1959 году голландским ученым-компьютерщиком Эдсгером В. Дейкстрой. В более общем виде этот класс алгоритмов известен как алгоритмы поиска по графу.
Другое применение жадных алгоритмов, которое стоит отметить, – это поиск потенциальных совпадений в массиве текста, часто с целью заменить совпавшие символы другими. Например, в тексте есть словосочетание «Джесса Джессика», и мы хотим унифицировать разные варианты написания этого имени. Команда «Искать сочетание «Джесс»», после которой стоит набор других букв, оканчивающийся на «а», даст нам все встречающиеся формы написания этого имени (Джесса Джессика), а не отдельные имена («Джесса», «Джессика»). Поисковик совпадений остановится на последней «а», а не на первой. Иногда это полезно, хоть в данном случае у нас другая цель поиска.
