Алгоритмы – это просто пошаговые инструкции для решения задачи. И если вы когда-либо собирали шкаф из IKEA, вы уже применяли алгоритм. Только без багов (надеюсь).
В этой статье не будет заумных сортировок массивов или хэш-таблиц в терминах C++. Вместо этого – про эффективное использование пространства и экономию времени в привычных вещах: поиска одежды, уборки квартиры и планирования дня.
Содержание
Сортировка: порядок в шкафу и в голове
Представьте, вы собираетесь на митап. Ваш шкаф выглядит так:
Футболки, штаны, носки, шляпа, башмаки — все вперемешку
И вот вы хотите найти вашу любимую серую оверсайз футболку. Что ж, в такой груде вам придется перебирать все вещи по одной до тех пор, пока вы не найдете нужную.
В лучшем случае она лежит наверху
В худшем — в самой заднице, вы доберетесь до нее в последнюю очередь
Это называется линейный поиск, или O(N), — работает, но медленно.
Теперь представим, что ваш шкаф выглядит так:
Вы знаете, что футболки висят на вешалках. А еще вы знаете, что ваши футболки отсортированы по цвету. В таком случае вы гарантировано найдете вашу футболку в несколько действий:
Найти место, где обитают футболки
Это называется отображение (map). Вам не требуются размышления. Вы просто знаете — они наверху на вешалках. Это имеет сложность O(1).-
Найти серую футболку среди остальных. Здесь можно применить линейный поиск, но на самом деле можно использовать и бинарный поиск:
Вы мысленно делите ваши футболки на две части, берете середину и смотрите: а нужная вам футболка светлее или темнее?
Если светлее, то делаем то же самое с первой половиной, иначе со второй.
И так до тех пор, пока не найдем ту самую.
Это имеет сложность O(logN). Если у вас 1000 футболок, то худший случай в линейном поиске – перебор всех 1000 футболок, в бинарном же – всего 10.
Вы, наверное, спросите – а как так сортировать, чтобы можно было быстро искать? Есть множество алгоритмов, но проще всего использовать сортировку вставками:
Вы фиксируете первую футболку
Берете вторую – она светлее или темнее первой?
Берете третью – куда ее вставить, чтобы не нарушить сортировку? Тут мы применяем бинарный поиск, описанный выше
Такой подход будет работать примерно за O(NlogN) – для каждой из N футболок мы находим ее место бинарным поиском за O(logN) и вставляем.
Тут технари возразят, что вставки работают за O(N^2). И они будут правы, живя в дискретном мире ячеек памяти. В реальном мире мы запросто можем запихнуть футболку между двух других, не прилагая усилий для сдвига остальных.
Давайте прикинем, сколько времени мы можем сэкономить, если навести порядок в шкафу. У нас есть N = 50 вещей. На перебор одной вещи уходит полсекунды.
Взять |
Положить |
Взять + положить |
|
Хаос |
O(N) — 25 с |
O(1) — 0.5 с |
25.5 с |
Порядок |
O(logN) — 3 с |
O(logN) — 3 с |
6 с |
Использование шкафа, в котором порядок, обходится быстрее в 4 раза. Живя в хаосе, вы тратите на шкаф 2.5 часа в год; в порядке – 36 минут. Эта разница будет только увеличиваться с количеством вещей.
Параллелизм
Домохозяйки отлично преуспели в этом. Они могут параллельно стирать вещи, убираться и готовить ужин. А еще и по телефону болтать одновременно!
Есть два вида задач:
CPU Bound — это когда вы активно работаете над задачей.
Например, чистка картошки, ручная стирка, мытье полов.IO Bound — это когда задача крутится фоном.
Например, варка картошки, стирка в машинке, прослушивание музыки.
Если у вас только один мозг (одно ядро), то вы, скорее всего, можете делать только одну CPU Bound задачу. IO Bound задач можно делать сколько угодно, но есть нюанс – смена контекста.
Вы должны следить, чтобы картошка не переварилась, а вещи не стухли в стиральной машине, которая пропищала уже 4 часа назад. Поэтому вы периодически отвлекаетесь от основного занятия и проверяете состояние дел.
В случае с телефонным звонком это выглядит как "Ой, Люд, погоди, у меня молоко убежало". Теперь Люда висит на фоне, а вы разбираетесь с пенной вечеринкой на плите. Произошла смена контекста.
В программировании мы говорим про потоки и асинхронность. В жизни — про умение делегировать задачи разным "ядрам" (себе, партнеру, стиральной машине).
Но как грамотно все распараллелить? В этом поможет направленный ациклический граф. Сложно? Да на самом деле нет: это просто набор связей, что от чего зависит.
Например, чтобы сварить картошку, ее надо почистить. Варить картошку и жарить мясо можно параллельно. А вот салат лучше делать в конце, чтобы не завял. А еще можно помыть не сразу всю посуду, а только кастрюли — в них поставить еду, а потом домыть все остальное.
Теперь осталось его отсортировать. В программировании это делается с помощью топологической сортировки. В жизни можно попроще — задачи без зависимостей идут в начало, остальное на глазок.
Здесь мы упорядочили действия, но не учли один момент. Чистка картошки и мытье посуды — это CPU Bound задачи, их не получится делать параллельно. А вот варка картошки и жарка мяса — это IO Bound задачи, поэтому их можно совместить. Поэтому на самом деле будет так:
Построение такого графа — очень важное умение, особенно когда вы выстраиваете работу целой команды. При плохой параллелизации 10 человеко-часов – это 10 часов; при идеальной – это 1 час.
Поговаривают, что гении оптимизации с востока выстраивают процессы так, что их 9 жен рожают 1 ребенка за 1 месяц. Ладно, это плохая шутка...
Кэширование
Помните, как мы ловко определили, где находятся футболки в шкафу? Это память и привычки, а на языке программистов – это кэш.
Почему вы помните, где лежат ключи? Потому что каждый раз кладете их в одного и то же место. Это – кэш LRU (Least Recently Used): самые частые действия хранятся "в голове", а не ищутся каждый раз. То же с вещами:
Зонт у входа — кэш для дождливой погоды
Чашка рядом с чайником — кэш для утра
Шарф на крючке — кэш для зимы
Например, я каждый день собираю спортивный рюкзак за минуту: я просто знаю, что одежда у меня висит на сушилке, кроссовки на второй полке, шиповки на первой полке, а бутылка стоит на стеллаже.
Если выделить четкое место под каждый предмет, то вы невероятным образом упростите себе жизнь. Не будете опаздывать, вас будут уважать, ну а там уже туда-сюда и миллионер.
Управление задачами
Немножко терминов. У вас есть стопка книг. Нет, давайте что-нибудь потяжелее. Есть тренажерные блины по 25 кг, а под ними лежит блин 10 кг, который вам нужен. Вы не сможете его просто так взять — перед этим надо снять блины по 25 кг.
Вот, это называется стек (стопка). Такая структура данных характеризуется правилом: что последним положил, то первым надо снять; и наоборот, что первым положил, то последним снимется.
А есть очередь — хорошо знакомое вам понятие. Первый пришел — первый ушел. Как в магазине на кассе.
Так вот, управлять делами можно с помощью двух этих структур:
Стек — это когда вы делаете рабочую задачу, но вы получили уведомление от коллеги, он накинул другую задачу, вот вы уже делаете ее. И все по кругу — вы "забиваете стек". Результат: 5 дел, ни одно не закончено. Это как Stack Overflow — переполнение стека вызовов
Очередь — вы делаете то, что пришло первым. Более справедливо, но не всегда эффективно.
Компромиссом этих двух вариантов является приоритетная очередь (как куча, heap). У каждого дела свой приоритет. Сначала делаете важные, а не просто первые.
На практике чаще всего это:
Уведомления. Как минимум, вы отвлекаетесь (переключаете контекст).
Отвлекающие факторы. Обратить внимание на шум за окном — тоже задача. Ответить коллеге — тоже задача. Переключение контекста не дешевая операция, она выбивает вас из колеи и заставляет фокусироваться заново.
На самом деле это один из видов прокрастинации. Это не только когда вы залипаете в ютуб, хотя у вас куча дел. Это даже когда вы делаете важную задачу, хотя у вас есть гораздо более важные. Например, за два дня до дедлайна убираетесь вместо того, чтобы писать диплом.
Самый короткий путь
Вы выбираете, как добраться до работы:
Метро + пешком
Автобус + пересадка
Велосипед
Такси
Вы не просто смотрите на расстояние, а на время, комфорт, погоду. Здесь вы применяете алгоритм поиска кратчайшего пути в графе. Ребра — это дорога. Веса — ваши критерии.
Когда я переехал в Питер, мой маршрут был таким:
Общага → Универ → Общага → Тренировка → Общага
Затем я оптимизировал его до такого:
Общага → Универ → Тренировка → Общага
Я убрал общагу между универом и тренировкой. Это позволило мне сэкономить примерно 40 минут на дороге. Однако мне пришлось сразу брать с собой тренировочную одежду. То есть поменял время на комфорт.
Это касается не только передвижений, но и любых действий, где можно что-то накопить и разом сделать.
Например, как выглядит работа с почтой у обычного человека:
Уведомление → Зайти в почту → Написать ответ
Уведомление → Зайти в почту → Написать ответ
Если же заходить в почту всего раз в день, то будет следующий формат:
Зайти в почту → Написать ответ → Написать ответ
10 писем = 10 заходов в почту = 10 секунд лишнего времени, а что еще хуже — 10 раз меняется контекст.
Жадные алгоритмы: быстрые решения
Определитесь, какой вариант вам нужен – хороший или лучший. Если это действительно влияет на вашу дальнейшую жизнь, то ищите лучший вариант, здесь вопросов нет.
Но если вы страдаете от тирании выбора перед стелажом с хлебом, определите для себя критерий "хорошести" — то, что вас устроит.
Если вы всеядный, как я, то любой хлеб хорош — хватайте первый попавшийся, и будет вам счастье. Если вы от хлеба требуете, чтобы он был без глютена и с семечками, то берите первый, который будет без глютена и семечек. Зачем рассматривать все подходящие варианты?
Заключение
Жизнь — это система. Мы все — как процессоры в распределенной системе. У нас есть память (мозг), кэш (привычки), планировщик (воля), и мы постоянно решаем задачи.
Алгоритмы — это не про код. Это про мышление. Про структуру. Про эффективность.
Когда вы начинаете видеть жизнь как набор задач, которые можно оптимизировать, вы становитесь не просто программистом. Вы становитесь архитектором своей повседневности.
Применяйте алгоритмы не ради эффективности, а ради свободы. Чем меньше времени вы тратите на рутину — тем больше остается на то, что по-настоящему важно.
Если вам понравилась эта статья, вам точно зайдёт мой Telegram-канал. Там я на своем примере показываю, что совмещать работу, спорт и учебу не только можно, но и нужно! А также разбираю сложные вещи простыми словами: от алгоритмов в быту до психологии продуктивности, от системного мышления до лайфхаков, которые реально экономят время. Подписывайтесь — будет полезно, легко и с юмором!