Duela egun batzuk gertatu zen Hidra Jardunaldia. JUG.ru Taldeko mutilek ametsetako hizlariak gonbidatu zituzten (Leslie Lamport! Cliff Click! Martin Kleppmann!) eta bi egun eskaini zituzten sistema banatuei eta informatikari. Kontur jardunaldiko hiru bazkideetako bat izan zen. Kabinan hitz egin genuen, banatutako biltegiari buruz hitz egin genuen, bingoan jokatu genuen eta puzzleak konpondu genituen.

Kontur standeko zereginen analisia egiten duen post bat da, euren testuaren egilearen eskutik. Nor zegoen Hydra - hau da esperientzia atsegina gogoratzeko zure arrazoia, nor ez zegoen - zure garuna luzatzeko aukera O handia-notazioa.

Parte-hartzaileak ere izan ziren paper-diagrama diapositibatan desmuntatu zuten erabakia idazteko. Ez naiz txantxetan ari - paper-pila hau entregatu zuten egiaztatzeko:

Hiru zeregin izan ziren guztira:

• karga orekatzeko erreplikak pisuen arabera hautatzeari buruz
• Kontsulten emaitzak memoriako datu-base baten aurka ordenatzeari buruz
• eraztun-topologia duen sistema banatu batean egoera-transferentziari buruz

1. ataza. ClusterClient

Sistema banatu baten N haztatutako errepliketatik K-ren aukeraketa eraginkorra egiteko algoritmo bat proposatu behar zen:

Zure taldeak N nodo masiboki banatutako kluster baterako bezero liburutegi bat garatzea du zeregina. Liburutegiak nodoekin lotutako hainbat metadaturen jarraipena egingo luke (adibidez, haien latentzia, 4xx/5xx erantzun-tasak, etab.) eta koma mugikorreko W1..WN pisuak esleituko lituzke. Aldibereko exekuzio-estrategiari eusteko, liburutegiak N nodoren K ausaz hautatzeko gai izan behar du; hautatzeko aukerak nodo baten pisuarekiko proportzionala izan behar du.

Proposatu algoritmo bat nodoak eraginkortasunez hautatzeko. Estima ezazu bere konputazio-konplexutasuna O notazio handia erabiliz.

Zergatik dago dena ingelesez?

Modu honetan hitzaldiko parte-hartzaileak haiekin borrokatu zirelako eta ingelesa Hydraren hizkuntza ofiziala zelako. Zereginak honelakoak ziren:

Hartu papera eta arkatza, pentsatu, ez izan presarik spoiler-ak berehala irekitzeko 🙂

Irtenbidearen analisia (bideoa)

5:53an hasita, 4 minutu bakarrik:

Eta hona hemen flipchart-a zuten mutilek euren irtenbidea nola aurkeztu zuten:

Irtenbidearen analisia (testua)

Honako soluzio hau gainazalean dago: batu ezazu erreplika guztien pisuak, sortu ausazko zenbaki bat 0tik pisu guztien baturara, gero aukeratu i-erreplika bat, hala nola erreplikaren pisuen batura 0tik (i-1)garrenera arte. ausazko zenbaki bat baino txikiagoa da, eta 0tik i-garrenera arteko erreplikaren pisuen batura - hori baino gehiago. Beraz, erreplika bat hautatzea posible izango da, eta hurrengoa hautatzeko, prozedura osoa errepikatu behar duzu hautatutako erreplika kontuan hartu gabe. Algoritmo horrekin, erreplika bat aukeratzearen konplexutasuna O(N) da, K erreplikak aukeratzearen konplexutasuna O(N K) ~ O(N2).

Konplexutasun koadratikoa txarra da, baina hobetu daiteke. Horretarako, eraikiko dugu segmentu zuhaitza pisuen batuketetarako. Lg N sakonera duen zuhaitz bat lortuko da, hostoetan pisu erreplikak egongo dira, eta gainerako nodoetan - batuketa partzialak, zuhaitzaren erroan dauden pisu guztien batura arte. Ondoren, ausazko zenbaki bat sortzen dugu 0tik pisu guztien batura arte, i-garren erreplika aurkitu, zuhaitzetik kendu eta prozedura errepikatuko dugu gainerako erreplikak aurkitzeko. Algoritmo honekin, zuhaitz bat eraikitzeko konplexutasuna O(N) da, i-garren erreplika aurkitzeko eta zuhaitzetik kentzeko konplexutasuna O(lg N), K erreplikak aukeratzeko konplexutasuna O(N + K) lg N) ~ O(N lg N) .

Log linealaren konplexutasuna konplexutasun koadratikoa baino politagoa da, batez ere K handientzat.

Algoritmo hau da kodean ezarrita ClusterClient proiektuko liburutegiak "Ekialdeko". (Hor, zuhaitza O(N lg N)n eraikitzen da, baina horrek ez du algoritmoaren azken konplexutasunean eragiten.)

2. ataza. Zebra

Beharrezkoa zen memorian dokumentuak indexatu gabeko eremu arbitrario baten bidez ordenatzeko algoritmo bat proposatzea:

Zure taldeak memorian zatitutako dokumentuen datu-base bat garatzea du zeregina. Ohiko lan-karga bat izango litzateke M tamainako bilduma batetik (normalean N < 100 << M) (normalean N < XNUMX << M) zenbakizko eremu arbitrario baten (indexatu gabeko) arabera ordenatuta dauden N dokumentu nagusiak hautatzea. Apur bat gutxiago ohikoa den lan-karga bat goiko N hautatzea izango litzateke goiko S dokumentuak (S ~ N) saltatu ondoren.

Proposatu algoritmo bat horrelako kontsultak eraginkortasunez exekutatzeko. Estima ezazu bere konputazio-konplexutasuna O notazio handia erabiliz batez besteko kasuetan eta kasurik txarrenetan.

Irtenbidearen analisia (bideoa)

34:50ean hasita, 6 minutu bakarrik:

Irtenbidearen analisia (testua)

Azaleko irtenbidea: ordenatu dokumentu guztiak (adibidez bizkorra), ondoren hartu N+S dokumentuak. Kasu honetan, ordenatzearen konplexutasuna batez beste O(M lg M) da, okerrenean O(M2).

Bistan da M dokumentu guztiak ordenatzea eta gero horien zati txiki bat hartzea eraginkorra ez dela. Dokumentu guztiak ez ordenatzeko, algoritmo bat egokia da azkar hautatzeko, nahi diren dokumentuen N + S hautatuko duena (edozein algoritmoren arabera ordena daitezke). Kasu honetan, konplexutasuna O(M)ra jaitsiko da batez beste, eta kasurik txarrena berdin jarraituko du.

Hala ere, are eraginkorrago egin dezakezu: erabili algoritmoa pila bitarra streaming. Kasu honetan, lehenengo N+S dokumentuak min- edo max-heap-era gehitzen dira (ordenatzeko norabidearen arabera), eta, ondoren, hurrengo dokumentu bakoitza zuhaitzaren erroarekin konparatzen da, zeinak uneko gutxieneko edo gehienezko dokumentua daukan, eta behar izanez gero zuhaitzari gehitzen zaio. Kasu honetan, konplexutasuna kasurik txarrenean, zuhaitza etengabe berreraiki behar duzunean, O(M lg M) da, batez besteko konplexutasuna O(M) da, hautaketa azkarrarekin bezala.

Hala ere, heap streaming eraginkorragoa da, izan ere, praktikan dokumentu gehienak baztertu daitezkeelako pila berreraiki gabe bere erro-elementuarekin alderatu ondoren. Ordenaketa hori Kontur-en garatu eta erabiltzen den Zebra memoriako dokumentuen datu-basean ezartzen da.

3. ataza. Estatu-trukeak

Egoerak aldatzeko algoritmo eraginkorrena proposatu behar zen:

Zure taldeak N nodo banatutako multzo baterako egoera trukatzeko mekanismo dotore bat garatzea du zeregina. I-garren nodoaren egoera (i+1)-garren nodora transferitu behar da, N-garren nodoaren egoera lehenengo nodora transferitu behar da. Onartzen den eragiketa bakarra egoera trukatzea da bi nodok beren egoera atomikoki trukatzen dutenean. Jakina da egoera-trukeak M milisegundo behar dituela. Nodo bakoitzak une bakoitzean egoera-truke bakarrean parte hartzeko gai da.

Zenbat denbora behar da kluster bateko nodo guztien egoerak transferitzeko?

Irtenbidearen analisia (testua)

Azaleko soluzioa: lehenengo eta bigarren elementuaren egoerak trukatu, gero lehenengoa eta hirugarrena, gero lehenengoa eta laugarrena, eta abar. Truke bakoitzaren ondoren, elementu baten egoera nahi duzun posizioan egongo da. O(N) permutazioak egin eta O(N M) denbora pasa behar duzu.

Denbora lineala luzea da, beraz, binaka elementuen egoerak truka ditzakezu: lehenengoa bigarrenarekin, hirugarrena laugarrenarekin eta abar. Estatu-truke bakoitzaren ondoren, bigarren elementu bakoitza posizio egokian egongo da. O(lg N) permutazioak egin eta O(M lg N) denbora pasa behar duzu.

Hala ere, aldaketa are eraginkorragoa izan daiteke - ez linealean, baizik eta denbora konstantean. Horretarako, lehen urratsean, lehenengo elementuaren egoera azkenekoarekin trukatu behar da, bigarrena azkenaurrekoarekin eta abar. Azken elementuaren egoera posizio egokian egongo da. Eta orain bigarren elementuaren egoera azkenarekin trukatu behar dugu, hirugarrena azkenaurrekoarekin eta abar. Truke txanda honen ondoren, elementu guztien egoerak posizio egokian egongo dira. Guztira O(2M) ~ O(1) permutazioak egongo dira.

Horrelako irtenbide batek ez du batere harrituko biraketa bi simetria axialen osaera dela oraindik gogoan duen matematikari bat. Bide batez, hutsalki orokortuta dago desplazamendu baterako ez batengatik, K < N posizioekin baizik. (Idatzi iruzkinetan nola zehazki.)

Gustuko al zenuen puzzleak? Ezagutzen al dituzu beste irtenbiderik? Partekatu iruzkinetan.

Eta hona hemen esteka erabilgarriak azkenean:

• buruz gehiago ikasi azpiegituren garapena sestran
• ikusi barneko erregistroak txostenekin eskuorriarekin sistema banatuei buruz
• ikusi bideo hitzaldi sortaJende arruntarentzat ezohiko algoritmoak»
• harpidetu gure kanala Telegramen

Iturria: www.habr.com