Як я выкарыстаў (кампутарную) НАУКУ! мець справу з больш чым тысячай штук лега

Большасць дзяцей абсалютна ЛЮБІЦЬ Лега. Мой сын гуляў з "Дупло", але мы нядаўна "мадэрнізавалі" яго да звычайнага. Паколькі ў нас пакуль не было калекцыі звычайных легасаў, мы вырашылі проста ўспадкаваць чужыя. У рэшце рэшт мы зрабілі перапынак, калі знайшлі кагосьці, хто прадае калекцыю Lego для сваіх дзяцей, бо яны былі для іх занадта старымі.

Гэта толькі палова калекцыі. Палова была ўжо адсартавана па колерах, але іх не было.

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

Такім чынам, улічваючы непераадольную задачу, мы вырашылі ўвайсці ў яе. Мы пачалі сартаваць, збіраючы ўсе зялёныя цэглы і збіраючы іх у тазік для мыцця. Так, гэта была вельмі старая калекцыя, таму яна была вельмі запыленай.

Першапачатковы план нападу быў такі:

  • Я сартую цэглу і мая жонка прыбірае іх і паліцы ўключае. Так, здзелка ўключала 3 паліцы, 9 скрынь, 1 сумку Lego (на фота) і 1 галоўку Lego, акрамя, напэўна, пяць-дзесяць тысяч штук
  • Затым мы іх спакуем - проста, праўда?

Гэта гучала як добры план, пакуль я не зразумеў, што сартаванне па колеры так, як я рабіў, было занадта марудным. Я збіраў толькі адзін колер за адзін раз. Я б, напэўна, адсартаваў каля 30 цаглін, і гэта заняло ў мяне пяць хвілін. Уявіце, колькі часу спатрэбілася б мне, каб скончыць з іншымі кветкамі, такімі як чорны, шэры, чырвоны і сіні!

Таму мне давялося перагледзець свой план. Я жартую з парай сяброў, якія потым згадвалі, што я, напэўна, рабіў гатункі бурбалак, што было адным з самых павольных алгарытмаў сартавання, якія ёсць у нас (так, ёсць некаторыя іншыя больш павольныя алгарытмы!). Я засмяяўся з жарту, а потым зразумеў, што, магчыма, буду мець магчымасць выкарыстоўваць свае веды па інфарматыцы - прынамсі, што ад гэтага засталося! Універ быў стагоддзяў таму, таму я ведаў, што прыйдзецца імправізаваць.

Увядзіце гарызантальнае маштабаванне

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

Як вэб-распрацоўнік, я бачыў гэта як звычайнае рашэнне праблемы з загрузкай сервера.

Калі ваш сервер перагружаны вялікай колькасцю ўваходнага трафіку, у вас звычайна ёсць два варыянты: вертыкальнае або гарызантальнае маштабаванне.

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

Тыпы асобнікаў Amazon EC2

Гарызантальнае маштабаванне азначае, што вы проста дадасце больш рэсурсаў. Такім чынам, замест таго, каб абнавіць асобнік singlet2.micro, вы дадасце яшчэ 5 для размяшчэння нагрузкі.

У абодвух ёсць свае выпадкі выкарыстання, але для гэтага канкрэтнага выпадку рашэнне было гарызантальнае маштабаванне.

Я маю на ўвазе, што я не мог бы па вертыкалі маштабаваць сябе, дадаўшы больш мозгу, таму адзіным выбарам быў гарызантальны маштаб, дадаўшы больш людзей.

Пасля пяці хвілін сартавання я заўважыў, што мы нейкі прагрэс. Мне гэтага было недастаткова. Час ішоў, і я стамляўся. Нам трэба было хутчэй!

Падзяліце і перамагчы алгарытм

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

З тых часоў я змяніў сваю пачатковую тэхніку простага пошуку зялёных блокаў. Замест гэтага ў мяне быў хуткі погляд, які колер быў падобны на большасць, і я атрымала столькі, колькі змагла. Уклаўшы цэглу ў адпаведную каляровую кошык, я зноў паглядзеў на кучу і зноў узяў «большасць». Звычайна гэта мянялася, бо пасля атрымання кучы скажаў, чырвоных, было б менш чырвоных. Наступная большасць, напрыклад, будзе сіняй ці зялёнай.

Гэта выглядала добра. Але прааналізаваўшы гэта, я ў асноўным глядзеў на дзве тысячы штук, атрымліваючы максімальную колькасць колеру, атрымліваючы гэты колер і адымаючы яго з кучы. Мая апрацоўка была павольнай, бо як вы на самой справе атрымліваеце большасць, не лічачы і не ацэньваючы?

Паколькі я ўзяў на сябе занадта шмат кагнітыўных нагрузак, я запавольваў хуткасць. Такім чынам, я перастаў глядзець на колер з найбольш цэглы і проста выбраў выпадковы колер кожны раз, калі я скінуў жменьку цэглы, якую я толькі што сабраў. Гэта трохі паскорыла маю апрацоўку, але я падумаў, што мы яшчэ можам палепшыць.

Дык вось, дзяліцеся і перамагайце. З пункту гледжання CS, гэта азначае алгарытм, які разбіў велізарную праблему на больш дробныя біты, каб іх было дастаткова проста вырашыць за больш хуткі час.

Дапусцім, ваш сайт прымае загружаныя карыстальнікам паштовыя файлы з фатаграфіямі і апрацоўвае іх. Калі ваш сервер прыняў ZIP файл, распакаваў яго і апрацаваў яго ў хвіліну, калі вы загрузілі яго, усе астатнія чакалі б яго завяршэння. Вядома, вы можаце гарызантальна ці вертыкальна маштабаваць свой сервер, але час чакання непатрэбны. Акрамя таго, што адбываецца, калі карыстальнік загружае паштовы файл са 100 фотаздымкамі?

Вы можаце вырашыць гэта, выкарыстоўваючы тэхніку "падзяліць" і "перамагчы". Па-першае, вы дэлегуеце апрацоўку інфраструктуры з затрымкай працы, як, напрыклад, ActiveJob Rails. Ці калі вы не выкарыстоўваеце Rails, Sidekiq. Але ўсё ж такі праца заняла б шмат часу, калі б было 100 фотаздымкаў, і была б верагоднасць памерці вашага работніка ад нагрузкі.

Адзін з рашэнняў - стварыць працу, якая распакуе яе, а потым прымусіць кожную фатаграфію апрацаваць як асобную працу. Цяпер замест таго, каб вашаму працаўніку трэба было самастойна апрацаваць 100 фотаздымкаў, ён ставіць у чаргу 100 малюсенькіх задач па апрацоўцы адзіночных фатаграфій, якія потым могуць забраць іншыя работнікі.

Маючы гэта на ўвазе, я заключыў з сынам заводскую здзелку: яму давялося дастаць з мяшка жменю (ці дзве) цэглы і скінуць іх у мой куток. Гэта азначала, што ў мяне было каля 50 цаглін, каб разабрацца было прасцей і хутчэй - галоўным чынам таму, што да гэтага моманту я ведаў, што колер з самай цэглы: шэры.

Самым распаўсюджаным колерам блока быў шэры.

Дык што, калі б я ведаў, што гэта шэры колер? Ну, гэта азначала, што мне трэба было толькі падабраць усю чырвоную, зялёную, жоўтую, сінюю, чорную і белую цэглу. Калі мне засталося шэрае, я кінуў астатнія цагліны ў шэрую скрыню - гэта дазволіла мне захаваць адзін колер менш, каб адсартаваць, што я не мог бы зрабіць у большым маштабе.

Праз гадзіну ...

Усё гатова! Цяпер нам заставалася толькі іх чысціць. Першапачатковы план быў:

  • Скіньце скрынку з кветкамі ў тазік.
  • Памыйце вадой з мылам
  • Сухі

У чым тут была праблема? Я дам вам здагадку.

Ўсё яшчэ там? Добра. Калі мы мыліся вадой і мылам, гэта азначала, што мы павінны змыць мыла - гэта азначае, што мы павінны былі мыць яго двойчы! Ніякім чынам! Таму я вырашыў не дадаваць мыла, а проста старанна памыць цёплай вадой.

Зменены план быў:

  • Скіньце скрынку з кветкамі ў тазік
  • Старанна вымыйце вадой
  • Сухі

Да наступнай праблемы: сушка Легаса.

Цэнтрабежная сіла на дапамогу!

Першапачаткова мы спрабавалі высушыць кавалачкі ручніком. Гэта было не вельмі эфектыўна. Далей было скарыстацца фенам і надзьмуць гарачае паветра на кавалачкі. Гэта было нармальна, але кавалкі ўсё яшчэ не высыхалі - мы станавіліся безнадзейнымі і амаль вырашылі проста пакласці іх на падлогу, каб вада выпарылася.

Толькі была восень, таму яна не была б дастаткова гарачай. Такім чынам, разважаючы пра тое, як высушыць тысячы кавалачкаў лега, я раптам успомніў, як я сушы лісце салаты пры дапамозе прадзільнай салаты. "Хацелася б, каб я магла выкарыстоўваць коўзанку для салаты", - падумала я. Потым на мяне азарыла: прадзілка салата працуе, выкарыстоўваючы цэнтрабежную сілу, каб аддзяліць ваду ад лісця. Я мог бы зрабіць тое ж самае!

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

Што вы ведаеце - гэта на самай справе спрацавала! Я бачыў, як ручнік раптам змочвае, калі вада з кавалкаў вылятала з іх і ў рушнік. НАУКА!

НАУКА!

Вядома, Legos быў не зусім сухі, і таму мне прыйшлося карыстацца фенам, каб астатнія кроплі выпарыліся. Але ўсё было ў парадку - цяжкая частка скончылася.

Я ніколі не думаў, што буду выкарыстоўваць свае веды па CS для чагосьці накшталт сартавання Legos. У любым выпадку, гэта маштабны і цікавы досвед маштабавання па гарызанталі, выкарыстоўваючы стратэгію раздзялення і ўлады, і нават выяўляючы цэнтрабежную сілу, каб арганізаваць нядаўна ўспадкаваны збор лега майго сына. Я не з нецярпеннем чакаю таго дня, калі ён усё пераблытае, і нам давядзецца сартаваць іх зноў!