Как я использовал (компьютерную) НАУКУ! иметь дело с более чем тысячей деталей Lego

1656626774 kak ya ispolzoval kompyuternuyu nauku imet delo s bolee chem

Большинство детей абсолютно ЛЮБЯТ Лего. Мой сын играет с Duplo, но недавно мы обновили его до обычных. Поскольку у нас еще не было коллекции обычных конструкторов Лего, мы решили просто унаследовать чьи-то. Наконец-то мы получили отдых, когда нашли, что кто-то распродает коллекцию Lego своих детей, поскольку они были слишком старыми для них.

LqBNo6G6BJtK7N1F6MwlWi-nSgAhrLj70NWH
Это только половина коллекции. Половина уже была отсортирована по цвету, а эти нет.

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

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

Первоначальный план атаки был такой:

  • Я сортирую кирпич, а моя жена чистит их и полки в комплекте. Так, сделка включала 3 полки, 9 коробок, 1 сумку Lego (на фото) и 1 голову Lego в дополнение к, вероятно, от пяти до десяти тысяч штук.
  • Потом мы их упаковываем – легко, правда?

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

Потому мне пришлось переосмыслить свой план. Я шутил с несколькими друзьями, которые потом вспомнили, что я, вероятно, делаю пузырчатую сортировку, который был одним из самых медленных алгоритмов сортировки (да, есть некоторые другие более медленные алгоритмы!). Я посмеялся над шуткой, а потом понял, что, возможно, смогу использовать здесь свои знания по информатике – по крайней мере, то, что от них осталось! Uni был много лет назад, потому я знал, что мне придется импровизировать.

Введите горизонтальное зумирование

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

Как веб-разработчик, я считаю это обычным решением проблемы загрузки сервера.

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

Вертикальный зум означает, что вы в основном добавляете больше мощности своему серверу. Например, если вы используете AWS, вместо того, чтобы иметь a t2.micro который имеет только 1 ЦБ и 1 Гб оперативной памяти, вы обновляете его до a t2.xlarge который имеет 4 процессора и 16 ГБ оперативной памяти.

9DhR1m-V-piFE7y0m1-L-8notdcAfY6VLeCP
Типы экземпляров Amazon EC2

Горизонтальное масштабирование означает, что вы просто добавляете больше ресурсов. Итак, вместо того, чтобы обновлять свой синглt2.micro например, вы добавляете еще 5, чтобы вместить нагрузку.

Оба имеют свои варианты использования, но для этого конкретного случая решением являлось горизонтальное масштабирование.

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

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

Алгоритм разделяй и властвуй

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

С тех пор я сменил свою начальную технику простого поиска зеленых блоков. Я быстро посмотрел, какой цвет выглядит как большинство, и получил как можно больше рукой. Положив кирпич в корзину подходящего цвета, я снова посмотрел на кучу и снова выбрал «большинство». Обычно он менялся, поскольку после получения кучи, скажем, красных, в нем будет меньше красных. Следующее большинство будет синим или зеленым, например.

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

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

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

Скажем, ваш сайт принимает загруженные пользователями zip-файлы с фотографиями и обрабатывает их. Если бы ваш сервер принял ZIP-файл, разархивировал его и обработал в ту минуту, когда вы его загрузили, все остальные ждали бы его завершения. Конечно, вы можете горизонтально или вертикально масштабировать свой сервер, но время ожидания не требуется. Кроме того, что происходит, когда пользователь скачивает zip-файл со 100 фотографиями?

Вы можете решить эту проблему, используя технику «разделяй и властвуй». Во-первых, вы делегируете обработку инфраструктуры отложенных задач, таких как ActiveJob Rails. Или если вы не используете Rails, Sidekiq. Однако эта работа заняла бы много времени, будь это 100 фотографий, и была бы вероятность того, что ваш работник умрет от нагрузки.

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

Имея это в виду, я заключил с сыном заводское соглашение: он должен был достать из мешка горсть (или два) кирпичей и сбросить их в мой угол. Это означало, что у меня было около 50 кирпичей для сортировки, что было проще и быстрее — главным образом потому, что к этому моменту я знал цвет с наибольшим количеством кирпичей: серый.

nfwkLNviXS9NJzYYvlZLwoK2Ultncxb7cyoV
Самым распространенным цветом блока был серый.

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

Через час…

Готово! Теперь нам осталось их почистить. Первоначальный план был:

  • Высыпьте коробку с цветом в таз.
  • Вымойте водой с мылом
  • Сухой

В чем здесь была проблема? Я дам вам предположение.

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

Измененный план был:

  • Высыпьте коробку с цветами в таз
  • Тщательно промыть водой
  • Сухой

Переходим к следующей проблеме: сушка Legos.

Центробежная сила в помощь!

Сначала мы попытались высушить кусочки полотенцем. Это было не очень эффективно. Дальше было воспользоваться феном и дуть горячим воздухом в куски. Все было хорошо, но это все равно не высушило кусочки – мы были безнадежными и почти решили просто уложить их на пол и дать всей воде испариться.

Только была осень, так что не было бы достаточно жарко. Поэтому, размышляя о том, как высушить тысячи деталей Lego, я вдруг вспомнил, как я сушил листья салата с помощью блендера. «Я бы хотел использовать блендер для салата», — подумал я. Затем я озарила: блесна для салатов работает, используя центробежную силу, чтобы отделить воду от листьев. Я мог бы сделать то же самое!

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

Что вы знаете – это действительно сработало! Я видел, как полотенце вдруг намокнуло, когда вода из кусочков вылетела из них на полотенце. НАУКА!

HEp6MVkDlD9fjO7zFMgzQ0Wj1Xwpl4vcfFi1
НАУКА!

Конечно, конструкторы Legos не полностью высохли, поэтому мне все равно пришлось воспользоваться феном, чтобы помочь оставшимся капелькам испариться. Но это было хорошо – тяжелая часть закончилась.

Я никогда не думал, что буду использовать свои базовые знания CS для чего-то вроде сортировки Legos. В любом случае, это был хороший и веселый опыт горизонтального масштабирования, использование стратегии «разделяй и властвуй» и даже использование центробежной силы, чтобы организовать недавно унаследованную коллекцию Lego моего сына. Я не с нетерпением жду того дня, когда он перемешает их все, и нам придется их сортировать снова!

Добавить комментарий

Ваш адрес email не будет опубликован.