Tharla cúpla lá ó shin Comhdháil Hydra. Thug na guys ó JUG.ru Group cuireadh do chainteoirí aisling (Leslie Lamport! Cliff Click! Martin Kleppmann!) agus chaith siad dhá lá ar chórais dáilte agus ríomhaireachta. Bhí Kontur ar cheann de thrí chomhpháirtí comhdhála. Labhraíomar ag an seastán, labhair muid faoinár stóráil dháilte, d'imir muid bingo, agus réitigh muid fadhbanna.

Post é seo ina bhfuil anailís ar na tascanna ag seastán Kontur ó údar a dtéacs. Dóibh siúd a bhí i Hydra, seo do sheans cuimhneamh ar eispéiris thaitneamhacha; dóibh siúd nach raibh, is deis é seo chun d’inchinn a shíneadh. mór O.-nótaíocht.

Bhí fiú rannpháirtithe ann a dhíchóimeáil an smeach-chairt ina sleamhnáin chun a réiteach a scríobh síos. Níl mé ag magadh - chuir siad an chairn páipéir seo isteach lena iniúchadh:

Bhí trí thasc san iomlán:

• faoi ​​macasamhla a roghnú de réir meáchain le haghaidh cothromaithe ualaigh
• faoi ​​thorthaí fiosrúcháin a shórtáil chuig bunachar sonraí i gcuimhne
• ar aistriú stáit i gcóras dáilte le topology fáinne

Tasc 1. ClusterClient

Bhí sé riachtanach algartam a mholadh chun macasamhlacha ualaithe K as N de chóras dáilte a roghnú go héifeachtach:

Tá sé de chúram ar d’fhoireann leabharlann cliant a fhorbairt do bhraisle N nóid a bhfuil dáileadh ollmhór orthu. Choimeádfadh an leabharlann súil ar mheiteashonraí éagsúla a bhaineann le nóid (m.sh., a gcuid laonna, rátaí freagartha 4xx/5xx, etc.) agus sannfadh sí meáchain snámhphointe W1..WN dóibh. Chun tacú leis an straitéis forghníomhaithe chomhthráthach, ba cheart go mbeadh an leabharlann in ann K de nóid N a phiocadh go randamach - ba cheart go mbeadh an seans go roghnófaí é i gcomhréir le meáchan nód.

Mol algartam chun nóid a roghnú go héifeachtach. Déan meastachán ar a chastacht ríomhaireachtúil trí nodaireacht mhór O a úsáid.

Cén fáth go bhfuil gach rud i mBéarla?

Toisc gur mar seo a throid rannpháirtithe na comhdhála leo agus toisc gurbh é an Béarla teanga oifigiúil Hydra. Bhí cuma mar seo ar na fadhbanna:

Tóg páipéar agus peann luaidhe, smaoinigh, ná deifir chun spoilers a oscailt láithreach :)

Anailís ar an réiteach (físeán)

Ag tosú ag 5:53, ach 4 nóiméad:

Agus seo mar a chuir na fir chéanna sin leis an smeach-chairt a réiteach in iúl:

Anailís ar an réiteach (téacs)

Tá an tuaslagán seo a leanas ar an dromchla: suimigh meáchain na macasamhla go léir, gin uimhir randamach ó 0 go suim gach meáchain, ansin roghnaigh i-macasamhail a fhágann suim meáchain na macasamhla ó 0 go dtí an ( i-1)ú níos lú ná an uimhir randamach, agus suim mheáchan na macasamhla ó 0 go i-ú - níos mó ná í. Ar an mbealach seo is féidir leat macasamhail amháin a roghnú, agus chun an chéad cheann eile a roghnú, ní mór duit an nós imeachta iomlán a dhéanamh arís gan smaoineamh ar an macasamhail roghnaithe. Le algartam den sórt sin, is é O(N an chastacht a bhaineann le macasamhail amháin a roghnú), agus is é O(N·K) ~ O(N2) an chastacht a bhaineann le macasamhla K a roghnú.

Tá castacht chearnach dona, ach is féidir é a fheabhsú. Chun seo beidh muid a thógáil crann deighleog le haghaidh suimeanna meáchain. Is é an toradh ná crann doimhneacht lg N, a mbeidh meáchain na macasamhla ar na duilleoga, agus beidh suimeanna páirteacha sna nóid atá fágtha, suas go dtí suim na meáchain uile ag bun an chrainn. Ansin, ginimid uimhir randamach ó 0 go suim na meáchain uile, faigh an i-ú macasamhail, bain den chrann é agus déan an nós imeachta arís chun na macasamhla atá fágtha a fháil. Le algartam den sórt sin, is é O(N an chastacht a bhaineann le crann a thógáil), is é O(L N + an chastacht chun an i-ú macasamhail a aimsiú agus é a bhaint den chrann), agus is í an chastacht a bhaineann le macasamhla K a roghnú ná O(N + K lg N) ~ Ó(N lg N).

Tá castacht líneach-logartamach níos deise ná an chastacht chearnach, go háirithe i gcás K mór.

Is é an algartam seo curtha i bhfeidhm sa chód Leabharlanna Cnuasaigh ón tionscadal "Oirthear" (Tá an crann tógtha in O(N lg N), ach ní chuireann sé seo isteach ar chastacht deiridh an algartam.)

Fadhb 2. Séabra

Bhí sé riachtanach algartam a mholadh chun doiciméid chuimhne a shórtáil go héifeachtach de réir réimse treallach neamh-innéacsaithe:

Tá sé de chúram ar d’fhoireann bunachar sonraí de dhoiciméid chomhroinnte cuimhneacháin a fhorbairt. Ualach oibre coitianta a bheadh ​​ann ná barrdhoiciméid N a roghnú arna sórtáil de réir réimse uimhriúil treallach (neamhinnéacsaithe) ó bhailiúchán de mhéid M (N < 100 << M de ghnáth). ualach oibre beagán níos lú coitianta a bheadh ​​ann ná barr N a roghnú tar éis scipeáil a dhéanamh ar dhoiciméid barr S (S ~ N).

Mol algartam chun fiosrúcháin den sórt sin a fhorghníomhú go héifeachtach. Déan meastachán ar a gcastacht ríomhaireachtúil trí úsáid a bhaint as nodaireacht O mór sa mheánchás agus sna cásanna is measa.

Anailís ar an réiteach (físeán)

Ag tosú ag 34:50, ach 6 nóiméad:

Anailís ar an réiteach (téacs)

Réiteach ar an dromchla: na doiciméid go léir a shórtáil (mar shampla, ag baint úsáide as sciobtha), ansin tóg doiciméid N+S. Sa chás seo, is é O(M lg M an chastacht a bhaineann le sórtáil ar an meán), agus O(M2 is measa) é.

Ar ndóigh, tá sé mí-éifeachtach gach doiciméad M a shórtáil agus gan ach cuid bheag díobh a ghlacadh. D'fhonn gan na doiciméid go léir a shórtáil, déanfaidh algartam mearroghnú, a roghnóidh N+S na doiciméid riachtanacha (is féidir iad a shórtáil de réir algartam ar bith). Sa chás seo, laghdófar an chastacht go dtí O(M) ar an meán, agus fanfaidh an cás is measa mar a chéile.

Mar sin féin, is féidir leat é a dhéanamh níos éifeachtaí - bain úsáid as an algartam sruthú carn dénártha. Sa chás seo, cuirtear na chéad doiciméid N+S le híosmhéid nó le huascharn (ag brath ar an treo sórtála), agus ansin cuirtear gach doiciméad ina dhiaidh sin i gcomparáid le fréamh an chrainn, ina bhfuil an doiciméad íosta nó uasta reatha. , agus, más gá, cuirtear leis an gcrann é. Sa chás seo, is í an chastacht sa chás is measa, nuair a bhíonn ort an crann a atógáil i gcónaí ná O(M lg M), is é O(M an chastacht ar an meán), mar nuair a bhíonn quickselect in úsáid.

Mar sin féin, bíonn sruthú carn níos éifeachtaí toisc gur féidir an chuid is mó de na doiciméid a chaitheamh amach go praiticiúil gan an carn a atógáil, tar éis comparáid amháin a dhéanamh lena fhréamhghné. Cuirtear an sórtáil seo i bhfeidhm i mbunachar sonraí doiciméad i gcuimhne Séabra, a forbraíodh agus a úsáidtear in Kontur.

Fadhb 3. Babhtálacha stáit

Bhí sé riachtanach an t-algartam is éifeachtaí a mholadh do stáit aistrithe:

Tá sé de chúram ar d’fhoireann meicníocht malartaithe stáit bhréige a fhorbairt do bhraisle dáilte N nóid. Ba chóir staid an nód i-ú a aistriú go dtí an (i+1)-ú nód, ba chóir staid an N-ú nód a aistriú go dtí an chéad nód. Is é an t-aon oibríocht a dtacaítear léi ná an babhtáil stáit nuair a mhalartaíonn dhá nód a stáit go adamhach. Tá sé ar eolas go dtógann babhtáil stáit M milleasoicindí. Tá gach nód in ann páirt a ghlacadh i mbabhtáil stáit aonair ag aon tráth ar leith.

Cé chomh fada a thógann sé staid na nóid go léir a aistriú i mbraisle?

Anailís ar an réiteach (téacs)

An réiteach ar an dromchla: staid an chéad agus an dara eilimint a mhalartú, ansin an chéad agus an tríú, ansin an chéad agus an ceathrú, agus mar sin de. Tar éis gach malartú, beidh staid eilimint amháin sa suíomh atá ag teastáil. Beidh ort iomalartaithe O(N) a dhéanamh agus am O(N·M) a chaitheamh.

Tá am líneach fada, ionas gur féidir leat staid na n-eilimintí a mhalartú i mbeirteanna: an chéad cheann leis an dara, an tríú leis an gceathrú, agus mar sin de. Tar éis gach malartú stáit, beidh gach dara eilimint sa suíomh inmhianaithe. Beidh ort iomalartaithe O(lg N) a dhéanamh agus am O(M lg N) a chaitheamh.

Mar sin féin, is féidir leat an t-aistriú a dhéanamh níos éifeachtaí - ní i líneach, ach in am leanúnach. Chun seo a dhéanamh, sa chéad chéim is gá duit staid an chéad eilimint a mhalartú leis an gceann deireanach, an dara ceann leis an leathdhéanach, agus mar sin de. Beidh staid na heiliminte deiridh sa suíomh atá ag teastáil. Agus anois ní mór dúinn staid an dara eilimint a mhalartú leis an gceann deireanach, an tríú ceann leis an leathdhéanach, agus mar sin de. Tar éis an bhabhta malartuithe seo, beidh stáit na n-eilimintí go léir sa suíomh atá ag teastáil. San iomlán, déanfar iomalartaithe O(2M) ~ O(1).

Ní chuirfidh réiteach den sórt sin iontas ar matamaiticeoir ar chor ar bith, a chuimhníonn fós gur comhdhéanamh de dhá shiméadracht aiseach é an rothlú. Dála an scéil, tá sé fánach ginearálaithe a aistriú ní amháin, ach de réir K < N suímh. (Scríobh sna tuairimí go cruinn conas.)

Ar thaitin na puzail leat? An bhfuil réitigh eile ar eolas agat? Comhroinn sna tuairimí.

Seo roinnt naisc úsáideacha deiridh:

• tuilleadh eolais a fháil faoi forbairt bonneagair i gContúirt
• breathnú ar thaifid inmheánacha bileog le tuarascálacha faoi ​​chórais dáilte
• féachaint ar an tsraith léachtaí físe"Algartaim neamhghnácha do ghnáthdhaoine»
• liostáil lenár Cainéal teileagraim

Foinse: will.com