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

Вурзма Моне до недавнего времени работал менеджером в фонде управления инвестиционными бумагами. Непостижимое решение стать рэпером возникло у него после того, как он прочитал в одной из школ лекцию о страховке кредиторов от дефолта. Беседа прошла под лозунгом «Кем работает мой отец», и к полудню Вурзма решил вести более осмысленную жизнь. Он ходит в местный супермаркет каждые две недели и часто ловит себя на том, что бродит по проходам из одного конца в другой в поисках нужных ему вещей из списка покупок. Туда-сюда, туда-сюда – у него уходит целая вечность на покупки. Визит в магазин еще больше затягивается из-за странной походки Вурзмы, которая мало походит на «крутую пацанскую» и больше напоминает ребят, которые своим видом будто говорят: «Я пропустил очередную консультацию у психотерапевта». Другие рэперы сразу замечают это несоответствие, и хрупкое доверие к Вурзме со стороны уличной продвинутой молодежи еще больше слабеет. Ему надо перестать выглядеть идиотом и избавиться от мыслей, обрекающих его на смехотворное существование.

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

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

МЕТОД 1: ПРОСМОТРЕТЬ ВЕСЬ СПИСОК ПОКУПОК ПО ПУНКТАМ.

МЕТОД 2: 

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

Я положу свой массив в твой массив, чтоб ты не стартовал, не спросив

До сих пор мы говорили о массивах как о фундаментальной структуре, предназначенной для хранения набора элементов. В главе 6 мы ввели еще одну полезную структуру под названием матрица, которая также нужна для хранения групп элементов. Но здесь они сохраняются в двух измерениях, а не в одном. Что общего у этих двух структур? А то, что массив может быть преобразован в матрицу. Все, что нужно для этого сделать, – вместо сохранения 

литер (как, например, цифра, буква или слово) в каждом расположении сохранить массив. Массив массивов называется двумерным, или в более общем виде многомерным массивом.

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

Итак, список покупок из простого перечня пунктов становится списком категорий, причем каждая из них, в свою очередь, представляет собой список пунктов.[43] Поскольку продукты в магазине обычно группируются по категориям, Вурзма может просто отправиться в ту часть магазина, где находятся, например, предметы личной гигиены, пробежаться по массиву под названием «личная гигиена» и взять нужные ему вещи со стеллажа. То же самое – для всех остальных покупок. Вот как занимаются шопингом по методу 2. Если бы Вурзма использовал обычный список – массив, как в методе 1, то он бы бродил примерно 13 минут от одного ряда к другому, в худшем случае – просто изучая полки.

Вурзма проходит мимо всех стеллажей для покупки одного предмета из списка. Если n – число проходов, а m – количество пунктов в списке, тогда n/2 × m=(nxm/2). Иными словами, для покупки 20 вещей Вурзма проходит через 20 рядов 20 раз. Принимая во внимание, что для прохождения каждого ряда требуется 2 секунды, то потерянное время составит до 13 минут. С методом 2 его общее время на ходьбу между рядами составляет примерно минуту, так как он не появляется в одном и том же ряду больше одного раза. Вурзма в лучшем случае проходит все ряды один раз, то есть n/2. Так что для приобретения 20 наименований покупок Вурзма, идя от одного ряда к другому, теряет меньше минуты.

Заметьте, что метод 1 не выглядит в точности как сортировка по квадратичному времени, которую мы видели в главах 5 и 11. Он следует шаблону, заставляя Вурзму в худшем случае пройти по всем рядам в магазине для каждой покупки в его списке. Вот как сравниваются два метода:

Бум-бум-бум, делай это часто и пожалеешь, как герой книги Мураками