Хэд хоногийн өмнө болсон . JUG.ru группын залуус мөрөөдлийн илтгэгчдийг урьсан (Лесли Лампорт! Клифф Клик! Мартин Клепманн!) ба тархсан систем, тооцоололд хоёр өдрийг зориулав. Контур чуулга уулзалтын гурван түншийн нэг байв. Бид лангуун дээр ярилцаж, хуваарилагдсан хадгалах сангийнхаа талаар ярилцаж, бинго тоглож, оньсого тааварлав.
Энэ бол текстийн зохиогчоос Контурын индэр дээрх даалгаврын дүн шинжилгээ бүхий нийтлэл юм. Гидра дээр хэн байсан бол энэ нь танд тааламжтай туршлагыг санах шалтгаан болж, хэн нь тархиа тэлэх боломж байсангүй. том О-тэмдэглэгээ.
Шийдвэрээ бичихийн тулд флипчартыг слайд болгон задалсан оролцогчид хүртэл байсан. Би тоглоогүй - тэд баталгаажуулахын тулд энэ овоолгын цаасыг өгсөн.
Нийтдээ гурван даалгавар байсан:
- ачааллыг тэнцвэржүүлэхийн тулд жингээр хуулбарыг сонгох тухай
- асуулгын үр дүнг санах ойн мэдээллийн баазтай харьцуулах тухай
- цагираган топологи бүхий тархсан систем дэх төлөвийн шилжүүлгийн тухай
Даалгавар 1. ClusterClient
Тархсан системийн N жигнэсэн хуулбараас K-ийг үр ашигтай сонгох алгоритмыг санал болгох шаардлагатай байв.
Танай баг N зангилааны бөөнөөр тархсан кластерт зориулсан үйлчлүүлэгчийн номын сан боловсруулах үүрэгтэй. Номын сан нь зангилаатай холбоотой янз бүрийн мета өгөгдлүүдийг (жишээ нь, тэдгээрийн хоцролт, 4xx/5xx хариултын хувь гэх мэт) хянаж, тэдгээрт W1..WN хөвөгч цэгийн жин оноодог. Нэгэн зэрэг гүйцэтгэх стратегийг дэмжихийн тулд номын сан N зангилааны K-г санамсаргүй байдлаар сонгох боломжтой байх ёстой - сонгогдох боломж нь зангилааны жинтэй пропорциональ байх ёстой.
Зангилааг үр дүнтэй сонгох алгоритмыг санал болго. Том O тэмдэглэгээг ашиглан тооцооллын нарийн төвөгтэй байдлыг тооцоол.
Яагаад бүх зүйл англи хэл дээр байдаг вэ?
Чуулганд оролцогчид энэ хэлбэрээр тэдэнтэй тулалдаж, англи хэл нь Гидрагийн албан ёсны хэл байсан тул. Даалгаврууд дараах байдалтай байв.
Цаас, харандаа аваад бодоорой, спойлеруудыг шууд нээх гэж бүү яараарай 🙂
Шийдэлд дүн шинжилгээ хийх (видео)
5:53 минутаас эхлээд ердөө 4 минут:
Цаасан хуудастай залуус шийдлээ хэрхэн дэвшүүлснийг энд харуулав.
Шийдлийн дүн шинжилгээ (текст)
Дараах шийдэл нь гадаргуу дээр байна: бүх хуулбарын жинг нэгтгэж, 0-ээс бүх жингийн нийлбэр хүртэл санамсаргүй тоог гаргаж, дараа нь хуулбарын жингийн нийлбэр 0-ээс (i-1)-р байхаар i-хуулбарыг сонгоно уу. санамсаргүй тооноос бага бөгөөд 0-ээс 2-р хүртэлх хуулбарын жингийн нийлбэр нь түүнээс их. Тиймээс нэг хуулбарыг сонгох боломжтой бөгөөд дараагийнхыг сонгохын тулд сонгосон хуулбарыг харгалзахгүйгээр бүх процедурыг давтах хэрэгтэй. Ийм алгоритмтай бол нэг хуулбарыг сонгоход төвөгтэй байдал нь O(N), K хуулбарыг сонгоход төвөгтэй байдал нь O(N K) ~ O(NXNUMX) юм.
Квадрат нарийн төвөгтэй байдал муу, гэхдээ үүнийг сайжруулж болно. Үүнийг хийхийн тулд бид барих болно жингийн нийлбэрийн хувьд. 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 баримтуудыг min- эсвэл max-heap-д (эрэмлэх чиглэлээс хамаарч) нэмж, дараа нь дараагийн баримт бичиг бүрийг одоогийн хамгийн бага эсвэл дээд баримтыг агуулсан модны үндэстэй харьцуулна. шаардлагатай бол модонд нэмнэ. Энэ тохиолдолд хамгийн муу тохиолдолд, та модыг байнга сэргээн босгох шаардлагатай үед нарийн төвөгтэй байдал нь O(M lg M), дундаж нарийн төвөгтэй байдал нь O(M), хурдан сонголттой адил байна.
Гэсэн хэдий ч бодит байдал дээр ихэнх баримт бичгүүдийг үндсэн элементтэй нь нэг харьцуулсны дараа овоолгыг дахин бүтээхгүйгээр устгаж болдог тул нуруулдан дамжуулалт нь илүү үр дүнтэй болж хувирдаг. Ийм ангиллыг Kontur-д боловсруулж ашигласан Zebra санах ойн баримт бичгийн мэдээллийн санд хэрэгжүүлдэг.
Даалгавар 3. Төрийн своп
Нөхцөл байдлыг өөрчлөх хамгийн үр дүнтэй алгоритмыг санал болгох шаардлагатай байв.
Танай баг N зангилааны тархсан кластерт зориулсан төрийн солилцооны гоёмсог механизмыг боловсруулах үүрэгтэй. i-р зангилааны төлөвийг (i+1)-р зангилаа руу, N-р зангилааны төлөвийг эхний зангилаа руу шилжүүлэх ёстой. Дэмжигдсэн цорын ганц үйлдэл бол хоёр зангилаа төлөвөө атомаар солилцох үед төлвийн солилцоо юм. Төрийн своп нь M миллисекунд болдог нь мэдэгдэж байна. Зангилаа бүр ямар ч үед нэг төлөвийн солилцоонд оролцох боломжтой.
Кластер дахь бүх зангилааны төлөвийг шилжүүлэхэд хэр хугацаа шаардагдах вэ?
Шийдлийн дүн шинжилгээ (текст)
Гадаргуугийн шийдэл: эхний ба хоёр дахь элементийн төлөвийг солилцох, дараа нь эхний ба гуравдах, дараа нь эхний ба дөрөвдэх гэх мэт. Солилцоо бүрийн дараа нэг элементийн төлөв нь хүссэн байрлалд байх болно. Та O(N) сэлгэлт хийж, O(N M) цаг зарцуулах хэрэгтэй.
Шугаман хугацаа урт тул та элементүүдийн төлөвийг хосоор нь сольж болно: эхнийх нь хоёр дахь, гурав дахь нь дөрөв дэх гэх мэт. Төрийн солилцоо бүрийн дараа хоёр дахь элемент бүр зөв байрлалд байх болно. Та O(lg N) сэлгэлт хийж, O(M lg N) цаг зарцуулах хэрэгтэй.
Гэсэн хэдий ч, ээлжийг илүү үр дүнтэй болгох боломжтой - шугаман бус, харин тогтмол хугацаанд. Үүнийг хийхийн тулд эхний алхамд та эхний элементийн төлөвийг сүүлчийнхтэй, хоёр дахь элементийн төлөвийг сүүлчийнх гэх мэтээр солих хэрэгтэй. Сүүлийн элементийн төлөв зөв байрлалд байх болно. Одоо бид хоёр дахь элементийн төлөвийг сүүлчийнхтэй, гурав дахь элементийн төлөвийг сүүлчийнх гэх мэтээр солих хэрэгтэй. Энэ удаагийн солилцооны дараа бүх элементүүдийн төлөвүүд зөв байрлалд байх болно. Нийтдээ O(2M) ~ O(1) сэлгэлт байх болно.
Ийм шийдэл нь эргэлт нь хоёр тэнхлэгийн тэгш хэмийн найрлага гэдгийг санаж байгаа математикчийг огт гайхшруулахгүй. Дашрамд хэлэхэд, энэ нь нэгээр биш, харин K <N байрлалаар шилжихэд өчүүхэн ерөнхийлсөн байдаг. (Яг яаж гэдгийг коммент хэсэгт бичээрэй.)
Та эвлүүлдэг тоглоомд дуртай байсан уу? Та өөр шийдлүүдийг мэдэх үү? Сэтгэгдэл дээр хуваалцаарай.
Эцэст нь зарим хэрэгтэй холбоосууд энд байна:
- илүү ихийг суралц контурт
- дотоод бүртгэлийг үзнэ үү тархсан системийн тухай
- цуврал видео лекцүүдийг үзэх»
- манайд бүртгүүлнэ үү
Эх сурвалж: www.habr.com