Бир нече күн мурун болгон . JUG.ru тобунун балдары кыялданган спикерлерди (Лесли Лэмпорт! Клифф Клик! Мартин Клепманн!) чакырып, эки күндү бөлүштүрүлгөн системаларга жана эсептөөлөргө арнашты. Контур конференциянын үч өнөктөшүнүн бири болгон. Биз стендде сүйлөшүп, бөлүштүрүлгөн сактагычыбыз жөнүндө сүйлөштүк, бинго ойнодук жана табышмактарды чечтик.
Бул Контур стендиндеги тапшырмалардын текстинин авторунун талдоосу менен пост. Гидрада ким болгон - бул сиздин жагымдуу окуяны эстеп калуу үчүн негиз, ал эми ким болгон эмес - мээңизди сунуу мүмкүнчүлүгү чоң О-белги.
Атүгүл өз чечимин жазуу үчүн флипчартты слайддарга түшүргөн катышуучулар да болду. Мен тамашалап жаткан жокмун – алар текшерүү үчүн бул десте кагазды беришти:
Жалпысынан үч тапшырма бар эле:
- жүк баланстоо үчүн салмагы боюнча репликаларды тандоо жөнүндө
- эстутумдагы маалымат базасына каршы суроо натыйжаларын сорттоо жөнүндө
- шакекче топологиясы бар бөлүштүрүлгөн системада мамлекеттик өткөрүп берүү боюнча
Тапшырма 1. ClusterClient
Бөлүштүрүлгөн системанын N салмактуу репликасынан К эффективдүү тандоо алгоритмин сунуштоо зарыл болгон:
Сиздин командаңызга N түйүндөрдүн массалык бөлүштүрүлгөн кластери үчүн кардар китепканасын иштеп чыгуу милдети коюлган. Китепкана түйүндөр менен байланышкан ар кандай метаберилиштерге көз салып турат (мисалы, алардын кечигүүлөрү, 4xx/5xx жооп ылдамдыгы ж.б.) жана аларга W1..WN калкыма чекиттин салмагын дайындайт. Бир эле учурда аткаруу стратегиясын колдоо үчүн китепкана N түйүндөрдүн К-ын туш келди тандай алышы керек — тандалган болуу мүмкүнчүлүгү түйүндүн салмагына пропорционалдуу болушу керек.
Түйүндөрдү эффективдүү тандоо үчүн алгоритмди сунуштаңыз. Чоң O белгисин колдонуу менен анын эсептөө татаалдыгын баалаңыз.
Эмне үчүн баары англис тилинде?
Анткени бул формада конференциянын катышуучулары алар менен мушташкан жана англис тили Гидранын расмий тили болгондуктан. Милдеттер мындай көрүндү:
Кагаз менен карандашты алыңыз, ойлонуңуз, спойлерлерди дароо ачууга шашпаңыз 🙂
Чечимдин анализи (видео)
5:53төн баштап, болгону 4 мүнөт:
Бул жерде флипчарт менен жигиттер өз чечимдерин кантип айтышты:
Чечимдин анализи (текст)
Төмөнкү чечим бетинде жатат: бардык репликалардын салмагын кошуңуз, 0дөн бардык салмактардын суммасына чейин кокустук санды түзүңүз, андан кийин репликанын салмагынын суммасы 0дөн (i-1)чиге чейин болгон i-репликаны тандаңыз. кокустук сандан аз, ал эми 0дөн i-чиге чейинки реплика салмактарынын суммасы андан көп. Ошентип, бир репликаны тандап алууга болот, ал эми кийинкисин тандоо үчүн тандалган репликаны эске албай туруп, процедураны толугу менен кайталашыңыз керек. Мындай алгоритм менен бир репликаны тандоонун татаалдыгы O(N), К репликаларды тандоонун татаалдыгы O(N K) ~ O(N2).
Квадраттык татаалдык начар, бирок аны жакшыртууга болот. Бул үчүн биз курабыз салмактардын суммасы үчүн. Тереңдиги lg N дарак алынат, анын жалбырактарында реплика салмактары, ал эми калган түйүндөрүндө дарактын тамырындагы бардык салмактардын суммасына чейин жарым-жартылай суммалар болот. Андан кийин, биз 0дөн бардык салмактардын суммасына чейин кокус санды жаратып, i-репликаны табабыз, аны дарактан алып салабыз жана калган репликаларды табуу үчүн процедураны кайталайбыз. Бул алгоритм менен даракты куруунун татаалдыгы O(N), i-репликаны табуу жана аны дарактан алып салуу татаалдыгы O(lg N), K репликаларды тандоо татаалдыгы O(N + K) lg N) ~ O(N lg N) .
Сызыктуу-лог татаалдыгы, өзгөчө чоң К үчүн квадраттык татаалдыкка караганда жакшыраак.
Бул алгоритм Долбоордон ClusterClient китепканалары "". (Ал жерде дарак O(N lg N) ичинде курулган, бирок бул алгоритмдин акыркы татаалдыгына таасир этпейт.)
Тапшырма 2. Зебра
Эстутумдагы документтерди ыктыярдуу индекстелбеген талаа боюнча эффективдүү сорттоо үчүн алгоритмди сунуштоо зарыл болгон:
Сиздин командаңызга эс тутумдагы документ базасын түзүү милдети жүктөлгөн. Кадимки жумуш жүгү M өлчөмүндөгү (адатта N < 100 << M) коллекциядан ыктыярдуу (индекстелбеген) сандык талаа боюнча иреттелген N жогорку документти тандоо болот. Бир аз азыраак таралган жумуш жүгү жогорку S документтерин (S ~ N) өткөрүп жибергенден кийин жогорку N тандоо болот.
Мындай суроо-талаптарды натыйжалуу аткаруу үчүн алгоритмди сунуштаңыз. Орточо учурда жана эң начар сценарийлерде чоң O белгисин колдонуу менен анын эсептөө татаалдыгын баалаңыз.
Чечимдин анализи (видео)
Саат 34:50дөн баштап, болгону 6 мүнөт:
Чечимдин анализи (текст)
Беттик чечим: бардык документтерди иреттөө (мисалы ), анда N+S документтерди алыңыз. Бул учурда сорттоо татаалдыгы орто эсеп менен O(M lg M), эң начары O(M2) болот.
Баардык М документтерди иреттеп, анан алардын аз гана бөлүгүн алуу натыйжасыз экени айдан ачык. Бардык документтерди сорттобоо үчүн, алгоритм ылайыктуу , ал каалаган документтердин N + S тандайт (аларды каалаган алгоритм боюнча сорттоого болот). Бул учурда, татаалдыгы орточо O(M) чейин төмөндөйт, ал эми эң начары ошол эле бойдон калат.
Бирок, сиз аны андан да натыйжалуу кыла аласыз - алгоритмди колдонуңуз . Бул учурда, биринчи N+S документтери мин- же макс-үймөккө (сорттоо багытына жараша) кошулат, андан кийин ар бир кийинки документ учурдагы минималдуу же максималдуу документти камтыган дарактын тамыры менен салыштырылат, жана зарыл болсо, даракка кошулат. . Бул учурда, даракты тынымсыз кайра курууга туура келгенде, эң начар учурда татаалдык O(M lg M) болот, тез тандоодогудай татаалдык орточо O(M).
Бирок, үймөк агымы натыйжалуураак болуп чыкты, анткени иш жүзүндө документтердин көбүн анын түпкү элементи менен бир эле салыштыруудан кийин үймөктү кайра түзбөстөн эле жок кылууга болот. Мындай сорттоо Контурда иштелип чыккан жана колдонулган Zebra эстутумдагы документтер базасында ишке ашырылат.
Тапшырма 3. Мамлекеттик своптар
Бул абалдарды алмаштыруу үчүн эң натыйжалуу алгоритмди сунуштоо зарыл болгон:
Сиздин командаңызга N түйүндөрдүн бөлүштүрүлгөн кластери үчүн кооз мамлекеттик алмашуу механизмин иштеп чыгуу тапшырылган. i-чи түйүндүн абалы (i+1)-чи түйүнгө, N-чи түйүнүнүн абалы биринчи түйүнгө өтүшү керек. Колдоого алынган жалгыз операция - бул эки түйүн өз абалын атомдук түрдө алмаштырганда абалды алмаштыруу. Белгилүү болгондой, мамлекеттик своп M миллисекундду талап кылат. Ар бир түйүн каалаган учурда бирдиктүү мамлекеттик алмашууга катыша алат.
Кластердеги бардык түйүндөрдүн абалын өткөрүүгө канча убакыт кетет?
Чечимдин анализи (текст)
Беттик чечим: биринчи жана экинчи элементтин абалын алмаштыруу, андан кийин биринчи жана үчүнчү, андан кийин биринчи жана төртүнчү жана башкалар. Ар бир алмашуудан кийин бир элементтин абалы каалаган абалда болот. Сиз O(N) алмаштырууну жасап, O(NM) убактысын өткөрүшүңүз керек.
Сызыктуу убакыт узун, андыктан элементтердин абалын жупта алмаштырса болот: биринчиси экинчиси менен, үчүнчүсү төртүнчүсү менен ж.б.у.с. Ар бир мамлекеттик алмашуудан кийин ар бир экинчи элемент туура абалда болот. Сиз O(lg N) алмаштырууну жасап, O(M lg N) убактысын өткөрүшүңүз керек.
Бирок сменаны ого бетер эффективдуу — линиялык эмес, туруктуу убакытта жасоого болот. Бул үчүн, биринчи кадамда, биринчи элементтин абалын акыркысы менен, экинчисин акыркы менен жана башкалар менен алмаштыруу керек. Акыркы элементтин абалы туура абалда болот. Эми экинчи элементтин абалын акыркысы менен, үчүнчүсүн акыркыга чейинкиси менен алмаштырышыбыз керек жана башкалар. Бул алмашуу раундунан кийин бардык элементтердин абалы туура позицияда болот. Жалпысынан O(2M) ~ O(1) алмаштыруу болот.
Айлануу эки октук симметриянын курамы экенин эстеп жүргөн математикти мындай чечим таптакыр таң калтырбайт. Айтмакчы, ал сменага бир эмес, К < N позициялары боюнча терец жалпыланган. (Так кантип комментарийге жазыңыз.)
Сизге паззлдар жактыбы? Башка чечимдерди билесизби? Комментарийлерде бөлүшүңүз.
Жана бул жерде аягында кээ бир пайдалуу шилтемелер:
- жөнүндө көбүрөөк билүү контурда
- ички жазууларды карагыла бөлүштүрүлгөн системалар жөнүндө
- видеолекциялардын сериясын көрүңүз»
- биздин каналга жазылыңыз
Source: www.habr.com