Алгоритмы в повседневной жизни

Алгоритмы – это просто пошаговые инструкции для решения задачи. И если вы когда-либо собирали шкаф из IKEA, вы уже применяли алгоритм. Только без багов (надеюсь).

В этой статье не будет заумных сортировок массивов или хэш-таблиц в терминах C++. Вместо этого – про эффективное использование пространства и экономию времени в привычных вещах: поиска одежды, уборки квартиры и планирования дня.

Содержание

• Сортировка: порядок в шкафу и в голове ^[1]

• Параллелизм ^[2]

• Кэширование ^[3]

• Управление задачами ^[4]

• Поиск кратчайшего пути ^[5]

• Жадные алгоритмы: быстрые решения ^[6]

• Заключение ^[7]

Сортировка: порядок в шкафу и в голове

Представьте, вы собираетесь на митап. Ваш шкаф выглядит так:

Футболки, штаны, носки, шляпа, башмаки — все вперемешку

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

• В лучшем случае она лежит наверху

• В худшем — в самой заднице, вы доберетесь до нее в последнюю очередь

Это называется линейный поиск, или O(N), — работает, но медленно.

Теперь представим, что ваш шкаф выглядит так:

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

1. Найти место, где обитают футболки
   Это называется отображение (map). Вам не требуются размышления. Вы просто знаете — они наверху на вешалках. Это имеет сложность O(1).

2. Найти серую футболку среди остальных. Здесь можно применить линейный поиск, но на самом деле можно использовать и бинарный поиск:

   1. Вы мысленно делите ваши футболки на две части, берете середину и смотрите: а нужная вам футболка светлее или темнее?

   2. Если светлее, то делаем то же самое с первой половиной, иначе со второй.

   3. И так до тех пор, пока не найдем ту самую.

   Это имеет сложность O(logN). Если у вас 1000 футболок, то худший случай в линейном поиске – перебор всех 1000 футболок, в бинарном же – всего 10.

Вы, наверное, спросите – а как так сортировать, чтобы можно было быстро искать? Есть множество алгоритмов, но проще всего использовать сортировку вставками:

1. Вы фиксируете первую футболку

2. Берете вторую – она светлее или темнее первой?

3. Берете третью – куда ее вставить, чтобы не нарушить сортировку? Тут мы применяем бинарный поиск, описанный выше

Такой подход будет работать примерно за O(NlogN) – для каждой из N футболок мы находим ее место бинарным поиском за O(logN) и вставляем.

Тут технари возразят, что вставки работают за O(N^2). И они будут правы, живя в дискретном мире ячеек памяти ^[8]. В реальном мире мы запросто можем запихнуть футболку между двух других, не прилагая усилий для сдвига остальных.

Давайте прикинем, сколько времени мы можем сэкономить, если навести порядок в шкафу. У нас есть N = 50 вещей. На перебор одной вещи уходит полсекунды.

Использование шкафа, в котором порядок, обходится быстрее в 4 раза. Живя в хаосе, вы тратите на шкаф 2.5 часа в год; в порядке – 36 минут. Эта разница будет только увеличиваться с количеством вещей. 

Параллелизм

Домохозяйки отлично преуспели в этом. Они могут параллельно стирать вещи, убираться и готовить ужин. А еще и по телефону болтать одновременно!

Есть два вида задач:

• CPU Bound — это когда вы активно работаете над задачей.
  Например, чистка картошки, ручная стирка, мытье полов.

• IO Bound — это когда задача крутится фоном.
  Например, варка картошки, стирка в машинке, прослушивание музыки.

Если у вас только один мозг ^[9] (одно ядро), то вы, скорее всего, можете делать только одну CPU Bound задачу. IO Bound задач можно делать сколько угодно, но есть нюанс – смена контекста.

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

В случае с телефонным звонком это выглядит как “Ой, Люд, погоди, у меня молоко убежало”. Теперь Люда висит на фоне, а вы разбираетесь с пенной вечеринкой на плите. Произошла смена контекста.

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

Но как грамотно все распараллелить? В этом поможет направленный ациклический граф. Сложно? Да на самом деле нет: это просто набор связей, что от чего зависит.

Например, чтобы сварить картошку, ее надо почистить. Варить картошку и жарить мясо можно параллельно. А вот салат лучше делать в конце, чтобы не завял. А еще можно помыть не сразу всю посуду, а только кастрюли — в них поставить еду, а потом домыть все остальное.

Теперь осталось его отсортировать. В программировании это делается с помощью топологической сортировки. В жизни можно попроще — задачи без зависимостей идут в начало, остальное на глазок.

Здесь мы упорядочили действия, но не учли один момент. Чистка картошки и мытье посуды — это CPU Bound задачи, их не получится делать параллельно. А вот варка картошки и жарка мяса — это IO Bound задачи, поэтому их можно совместить. Поэтому на самом деле будет так:

Построение такого графа — очень важное умение, особенно когда вы выстраиваете работу целой команды. При плохой параллелизации 10 человеко-часов – это 10 часов; при идеальной – это 1 час.

Поговаривают, что гении ^[10] оптимизации с востока выстраивают процессы так, что их 9 жен рожают 1 ребенка за 1 месяц. Ладно, это плохая шутка…

Кэширование

Помните, как мы ловко определили, где находятся футболки в шкафу? Это память и привычки, а на языке программистов – это кэш.

Почему вы помните, где лежат ключи? Потому что каждый раз кладете их в одного и то же место. Это – кэш LRU (Least Recently Used): самые частые действия хранятся “в голове”, а не ищутся каждый раз. То же с вещами:

• Зонт у входа — кэш для дождливой погоды

• Чашка рядом с чайником — кэш для утра

• Шарф на крючке — кэш для зимы

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

Если выделить четкое место под каждый предмет, то вы невероятным образом упростите себе жизнь. Не будете опаздывать, вас будут уважать, ну а там уже туда-сюда и миллионер.

Управление задачами

Немножко терминов. У вас есть стопка книг. Нет, давайте что-нибудь потяжелее. Есть тренажерные блины по 25 кг, а под ними лежит блин 10 кг, который вам нужен. Вы не сможете его просто так взять — перед этим надо снять блины по 25 кг.

Вот, это называется стек (стопка). Такая структура данных характеризуется правилом: что последним положил, то первым надо снять; и наоборот, что первым положил, то последним снимется.

А есть очередь — хорошо знакомое вам понятие. Первый пришел — первый ушел. Как в магазине на кассе.

Так вот, управлять делами можно с помощью двух этих структур:

• Стек — это когда вы делаете рабочую задачу, но вы получили уведомление от коллеги, он накинул другую задачу, вот вы уже делаете ее. И все по кругу — вы “забиваете стек”. Результат: 5 дел, ни одно не закончено. Это как Stack Overflow — переполнение стека вызовов

• Очередь — вы делаете то, что пришло первым. Более справедливо, но не всегда эффективно.

Компромиссом этих двух вариантов является приоритетная очередь (как куча, heap). У каждого дела свой приоритет. Сначала делаете важные, а не просто первые.

На практике чаще всего это:

• Уведомления. Как минимум, вы отвлекаетесь (переключаете контекст).

• Отвлекающие факторы. Обратить внимание ^[11] на шум за окном — тоже задача. Ответить коллеге — тоже задача. Переключение контекста не дешевая операция, она выбивает вас из колеи и заставляет фокусироваться заново.

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

Самый короткий путь

Вы выбираете, как добраться до работы:

• Метро + пешком

• Автобус + пересадка

• Велосипед

• Такси

Вы не просто смотрите на расстояние, а на время, комфорт, погоду. Здесь вы применяете алгоритм поиска кратчайшего пути в графе. Ребра — это дорога. Веса — ваши критерии.

Когда я переехал в Питер, мой маршрут был таким:

• Общага → Универ → Общага → Тренировка → Общага

Затем я оптимизировал его до такого:

• Общага → Универ → Тренировка → Общага

Я убрал общагу между универом и тренировкой. Это позволило мне сэкономить примерно 40 минут на дороге. Однако мне пришлось сразу брать с собой тренировочную одежду. То есть поменял время на комфорт.

Это касается не только передвижений, но и любых действий, где можно что-то накопить и разом сделать.

Например, как выглядит работа с почтой у обычного человека:

• Уведомление → Зайти в почту → Написать ответ

• Уведомление → Зайти в почту → Написать ответ

Если же заходить в почту всего раз в день, то будет следующий формат:

• Зайти в почту → Написать ответ → Написать ответ

10 писем = 10 заходов в почту = 10 секунд лишнего времени, а что еще хуже — 10 раз меняется контекст.

Жадные алгоритмы: быстрые решения

Определитесь, какой вариант вам нужен – хороший или лучший. Если это действительно влияет на вашу дальнейшую жизнь, то ищите лучший вариант, здесь вопросов нет.

Но если вы страдаете от тирании выбора перед стелажом с хлебом, определите для себя критерий “хорошести” — то, что вас устроит.

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

Заключение

Жизнь — это система. Мы все — как процессоры в распределенной системе. У нас есть память (мозг), кэш (привычки), планировщик (воля), и мы постоянно решаем задачи.

Алгоритмы — это не про код. Это про мышление ^[12]. Про структуру. Про эффективность.

Когда вы начинаете видеть жизнь как набор задач, которые можно оптимизировать, вы становитесь не просто программистом. Вы становитесь архитектором своей повседневности.

Применяйте алгоритмы не ради эффективности, а ради свободы. Чем меньше времени вы тратите на рутину — тем больше остается на то, что по-настоящему важно.

---

Если вам понравилась эта статья, вам точно зайдёт мой Telegram-канал ^[13]. Там я на своем примере показываю, что совмещать работу, спорт и учебу не только можно, но и нужно! А также разбираю сложные вещи простыми словами: от алгоритмов в быту до психологии продуктивности, от системного мышления до лайфхаков, которые реально экономят время. Подписывайтесь — будет полезно, легко и с юмором ^[14]!