Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще

Даже роботы-пылесосы служат хорошим примером. Не все они одинаковы. Уровень сложности зависит от того, как много пространства они способны охватить. Самые простые пылесосы бродят беспорядочными линиями или кругами, в то время как более продвинутые сначала составляют карту комнаты, определяя, где находятся стены, углы и повороты, а потом ездят взад-вперед по принципу решетки. Иными словами, когда робот знает, как лучше всего добраться с одного конца комнаты в другой, это приближает его цель, а результат – более чистая комната.[22]

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

5

Сортировка почты

Чарли Магна не успевает закончить свои почтовые дела. Сейчас уже середина дня, июль, Кейптаун. Температура 45 °C. К тому же рассеянный и неуклюжий Чарли выронил коробку с отсортированными письмами и перемешал пачки, которые нужно доставить 33 адресатам в его округе. Но и это не все: у почтальона повышенная чувствительность к солнечному свету, а он забыл кепку и солнцезащитные очки дома. Стоя на коленях на раскаленной гальке, он собирает конверты и пытается разложить их в нужном порядке, чтобы закончить работу, прежде чем на коже появятся волдыри.

Подсказка: подумайте, как можно разбить одну большую проблему на несколько маленьких.

Порядок поможет нам управиться с задачей быстрее. Представьте, что было бы, если бы местная газета не анонсировала предстоящие события по дням недели. Если бы серии телесериала, которые вы планируете посмотреть, не перечислялись в телепрограмме. Как было бы досадно тратить время на поиски следующего эпизода, вместо того чтобы посмотреть очередную историю о неудавшемся наркодилере, получившем еще один удар от жестокой вселенной.

Давайте посмотрим, как Чарли может справиться со своей неожиданной поблемой.

ЦЕЛЬ: СНОВА РАЗЛОЖИТЬ РАССЫПАННЫЕ ПАЧКИ КОНВЕРТОВ В НУЖНОМ ПОРЯДКЕ

МЕТОД 1: ПОЛОЖИТЬ ОДНУ ПАЧКУ НА ЗЕМЛЮ ПЕРЕД СОБОЙ. ВЗЯТЬ ВТОРУЮ ПАЧКУ, И, ЕСЛИ МЕСТО ЖИТЕЛЬСТВА АДРЕСАТА БЛИЗКО К ПЕРВОМУ, ПОМЕСТИТЬ ЕЕ СЛЕВА. И ТАК ДАЛЕЕ, ПОКА САМЫЕ БЛИЗКИЕ АДРЕСА НЕ ОКАЖУТСЯ СЛЕВА ОТ ЛИНИИ, А САМЫЕ ДАЛЕКИЕ – СПРАВА.

МЕТОД 2: 

РАЗЛОЖИТЕ ПАЧКИ КОНВЕРТОВ В РЯД ПЕРЕД СОБОЙ. РАЗДЕЛИТЕ ИХ ТАК, ЧТОБЫ СПРАВА И СЛЕВА ОКАЗАЛОСЬ ОДИНАКОВОЕ КОЛИЧЕСТВО КОНВЕРТОВ. ЗАТЕМ РАЗДЕЛИТЕ КАЖДУЮ ГРУППУ ПОПОЛАМ. КЛАДИТЕ БЛИЗКИЙ АДРЕС СЛЕВА, А ДАЛЕКИЙ – СПРАВА. ЗАТЕМ ДЕЛАЙТЕ ЭТО ДЛЯ КАЖДОЙ ПАРЫ ПАР И ТАК ДАЛЕЕ.

Вот как эти два метода выглядят на графике:

В реальной жизни при сортировке каких-либо вещей вручную, как это делает Чарли, допустимы некоторые вариации метода 1, которые он скорее всего использовал бы. Как мы видели из прежних сравнительных графиков, общее правило таково: для сортировки нескольких вещей годится любой метод. И только когда предметов много, один из методов может оказаться намного лучше другого. Хотя метод 2 не всегда имеет практическую корреляцию в реальной жизни, по крайней мере при сортировке, мы обсудим общий подход в концептуальных терминах.[23]

Для начала заметим, что метод 1 несет в себе определенный ритм. Чарли берет одну пачку конвертов, затем просматривает другие пачки, чтобы определить, куда ее положить. Затем он берет другую пачку конвертов, просматривает остальные пачки и так далее. Мы видели подобный подход раньше, когда разбирали носки, не так ли? Разница в том, что с каждым конвертом Чарли просматривает все другие только один раз, в то время как с носками Марджи могла потратить много времени, выискивая к каждому пару в куче белья.

Подход Чарли в методе 1 – характерная черта алгоритма с квадратичным временем.[24] Каждый раз, когда у вас есть набор предметов (независимо от того, одинаковые ли они или разные) и вы перебираете их все в поисках одного, у вас есть алгоритм с квадратичным временем. Другие примеры подобного алгоритма – примерка нескольких рубашек с целью выбрать подходящую к вашим брюкам или сравнение списка покупок с продуктами на полке в магазине.