ڪجهه ڏينهن اڳ ٿيو هائيڊرا ڪانفرنس. JUG.ru گروپ جي ماڻهن خوابن جي ڳالهائيندڙن کي دعوت ڏني (ليسلي لامپورٽ! ڪلف ڪلڪ! مارٽن ڪلپمن!) ۽ ٻه ڏينهن ورهايل سسٽم ۽ ڪمپيوٽنگ لاءِ وقف ڪيا. Kontur ڪانفرنس جي ٽن ڀائيوارن مان هڪ هو. اسان بوٿ تي ڳالهايو، اسان جي ورهايل اسٽوريج بابت ڳالهايو، بينگو کيڏيو، ۽ پزل حل ڪيو.

هي هڪ تحرير آهي جنهن ۾ ڪمن جي تجزيي سان Kontur اسٽينڊ تي انهن جي متن جي ليکڪ کان. هائڊرا تي ڪير هو - اهو توهان جو خوشگوار تجربو ياد ڪرڻ جو سبب آهي، جيڪو نه هو - توهان جي دماغ کي وڌائڻ جو هڪ موقعو وڏو اي- نوٽيفڪيشن.

اتي به شرڪت ڪندڙ ھئا جن پنھنجي فيصلي کي لکڻ لاءِ فلپ چارٽ کي سلائڊن ۾ ٽوڙي ڇڏيو. مان مذاق نه ڪري رهيو آهيان - انهن تصديق لاءِ ڪاغذ جو هي اسٽيڪ ڏنو:

مجموعي طور تي ٽي ڪم هئا:

• لوڊ بيلنسنگ لاءِ وزن ذريعي نقل چونڊڻ بابت
• ميموري ڊيٽابيس جي خلاف سوالن جي نتيجن کي ترتيب ڏيڻ بابت
• ورهايل نظام ۾ رياست جي منتقلي تي هڪ انگوزي ٽوپولوجي سان

ٽاسڪ 1. ڪلسٽر ڪلائنٽ

اهو ضروري هو ته هڪ ورهايل نظام جي N وزن ٿيل نقلن مان K جي موثر چونڊ لاءِ هڪ الگورٿم تجويز ڪيو وڃي:

توهان جي ٽيم کي N nodes جي وڏي پيماني تي ورهايل ڪلستر لاءِ ڪلائنٽ لائبريري کي ترقي ڪرڻ جو ڪم سونپي وئي آهي. لائبريري نوڊس سان جڙيل مختلف ميٽا ڊيٽا جي نگراني ڪندي (مثال طور، انهن جي دير، 4xx/5xx جوابي شرح، وغيره) ۽ انهن کي فلوٽنگ پوائنٽ وزن W1..WN تفويض ڪندي. سمورو عمل جي حڪمت عملي کي سپورٽ ڪرڻ لاءِ، لائبريري کي N نوڊس جي K کي بي ترتيب طور چونڊڻ جي قابل ٿيڻ گهرجي- چونڊڻ جو هڪ موقعو نوڊ جي وزن جي متناسب هجڻ گهرجي.

نوڊس کي موثر طريقي سان چونڊڻ لاءِ هڪ الگورٿم پيش ڪريو. وڏي O نوٽشن استعمال ڪندي ان جي ڪمپيوٽري پيچيدگي جو اندازو لڳايو.

سڀ ڪجهه انگريزيءَ ۾ ڇو آهي؟

ڇاڪاڻ ته انهيءَ شڪل ۾ ڪانفرنس جي شرڪت ڪندڙن سان وڙهندي هئي ۽ ڇاڪاڻ ته انگريزي هائيڊرا جي سرڪاري ٻولي هئي. ڪم هن طرح نظر اچن ٿا:

ڪاغذ ۽ پينسل وٺو، سوچيو، فوري طور تي اسپائيلر کولڻ لاءِ جلدي نه ڪريو 🙂

حل جو تجزيو (وڊيو)

5:53 تي شروع ٿي، صرف 4 منٽ:

۽ هتي اهو آهي ته فلپ چارٽ وارا ماڻهو ڪيئن پنهنجو حل پيش ڪن ٿا:

حل جو تجزيو (متن)

هيٺ ڏنل حل مٿاڇري تي آهي: سڀني نقلن جي وزن جو مجموعو، 0 کان سڀني وزنن جي مجموعن تائين بي ترتيب نمبر ٺاهيو، پوء هڪ i-replica چونڊيو جيئن نقل وزن جو مجموعو 0 کان (i-1)th تائين. هڪ بي ترتيب نمبر کان گهٽ آهي، ۽ نقل جو مجموعو 0 کان i-th تائين - ان کان وڌيڪ. تنهن ڪري اهو ممڪن ٿيندو ته هڪ نقل چونڊيو، ۽ ٻئي کي چونڊڻ لاء، توهان کي چونڊيل نقل تي غور ڪرڻ کان سواء سڄي عمل کي ورجائڻ جي ضرورت آهي. اهڙي الورورٿم سان، هڪ نقل چونڊڻ جي پيچيدگي O(N) آهي، K replicas چونڊڻ جي پيچيدگي O(N K) ~ O(N2) آهي.

Quadratic پيچيدگي خراب آهي، پر ان کي بهتر ڪري سگهجي ٿو. هن کي ڪرڻ لاء، اسان تعمير ڪنداسين ڀاڱو وڻ وزن جي رقم لاء. lg N جي کوٽائي جو ھڪڙو وڻ حاصل ڪيو ويندو، جنھن جي پنن ۾ ريپليڪا وزن ھوندا، ۽ باقي نوڊس ۾ - جزوي رقم، وڻ جي پاڙ تي سڀني وزن جي مجموعن تائين. اڳيون، اسان 0 کان سڀني وزنن جي مجموعن تائين بي ترتيب نمبر ٺاھيون ٿا، i-th ريپليڪا ڳولھيو، ان کي وڻ تان هٽايو، ۽ باقي ريپليڪس کي ڳولڻ لاء طريقيڪار کي ورجايو. هن الگورتھم سان، وڻ جي تعمير جي پيچيدگي O(N) آهي، i-th جي نقل کي ڳولڻ ۽ ان کي وڻ مان هٽائڻ جي پيچيدگي O(lg N) آهي، K replicas چونڊڻ جي پيچيدگي O(N + K) آهي. lg N) ~ O(N lg N) .

لڪير-لاگ پيچيدگي quadratic پيچيدگي کان وڌيڪ سٺي آهي، خاص طور تي وڏي K لاء.

اهو ئي الورورٿم آهي ڪوڊ ۾ لاڳو پروجيڪٽ مان ClusterClient لائبريريون "اوڀر". (اتي، وڻ O (N lg N) ۾ ٺهيل آهي، پر اهو الورورٿم جي آخري پيچيدگي کي متاثر نٿو ڪري.)

ٽاسڪ 2. زيبرا

اهو ضروري هو ته ميموري ۾ دستاويزن جي موثر ترتيب ڏيڻ لاءِ هڪ الگورٿم پيش ڪرڻ لاءِ هڪ غير ترتيب ڏنل فيلڊ ذريعي:

توهان جي ٽيم کي شارڊڊ ان ميموري ڊاڪيومينٽ ڊيٽابيس ٺاهڻ جو ڪم سونپيو ويو آهي. ھڪڙو عام ڪم لوڊ ھوندو مٿاھين N دستاويزن کي چونڊڻ لاءِ جيڪو ترتيب ڏنل (غير ترتيب ڏنل) عددي فيلڊ جي ماپ M (عام طور تي N <100 << M) جي مجموعن مان. ھڪڙو ٿورڙو گھٽ عام ڪم لوڊ آھي مٿين 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) آهي، جيئن جلدي چونڊ سان.

بهرحال، هيپ اسٽريمنگ ان حقيقت جي ڪري وڌيڪ ڪارائتو ثابت ٿئي ٿو ته عملي طور تي اڪثر دستاويزن کي رد ڪري سگھجن ٿا، ان جي روٽ عنصر سان هڪ مقابلي کان پوءِ هيپ کي ٻيهر تعمير ڪرڻ کان سواءِ. اهڙي ترتيب کي زبرا ان-ميموري ڊاڪيومينٽ ڊيٽابيس ۾ لاڳو ڪيو ويو آهي جيڪو Kontur ۾ ترقي يافته ۽ استعمال ڪيو ويو آهي.

ٽاسڪ 3. رياستي ادل

اهو ضروري هو ته رياستن کي تبديل ڪرڻ لاء سڀ کان وڌيڪ موثر الگورتھم پيش ڪرڻ لاء:

توهان جي ٽيم کي N نوڊس جي ورهايل ڪلستر لاءِ فينسي اسٽيٽ ايڪسچينج ميڪانيزم ٺاهڻ جو ڪم سونپي وئي آهي. i-th node جي رياست کي (i+1) -th node ڏانھن منتقل ڪيو وڃي، N-th node جي رياست کي پھرئين نوڊ ڏانھن منتقل ڪيو وڃي. صرف سپورٽ ٿيل آپريشن رياستي ادل آھي جڏھن ٻه نوڊس پنھنجي رياستن کي ايٽمي طور تبديل ڪن ٿا. اهو معلوم ٿئي ٿو ته هڪ رياست ادل M milliseconds وٺندو آهي. هر نوڊ ڪنهن به وقت هڪ واحد رياست جي ادل ۾ حصو وٺڻ جي قابل آهي.

ڪلستر ۾ سڀني نوڊس جي رياستن کي منتقل ڪرڻ لاء ڪيترو وقت وٺندو آهي؟

حل جو تجزيو (متن)

مٿاڇري جو حل: پهرين ۽ ٻئي عنصر جي رياستن کي مٽايو، پوء پهريون ۽ ٽيون، پوء پهريون ۽ چوٿون، وغيره. هر تبادلي کان پوء، هڪ عنصر جي حالت گهربل پوزيشن ۾ هوندي. توهان کي O (N) اجازت ڏيڻي پوندي ۽ O (N M) وقت گذارڻو پوندو.

لڪير وارو وقت ڊگهو آهي، تنهنڪري توهان عناصر جي رياستن کي جوڑوں ۾ تبديل ڪري سگهو ٿا: پهريون ٻئي سان، ٽيون چوٿين سان، وغيره. هر رياست جي بدلي کان پوء، هر سيڪنڊ عنصر صحيح پوزيشن ۾ هوندو. توهان کي O(lg N) اجازت ڏيڻي پوندي ۽ O(M lg N) وقت خرچ ڪرڻو پوندو.

بهرحال، اهو ممڪن آهي ته شفٽ کي اڃا به وڌيڪ موثر بڻائڻ - نه لڪير ۾، پر مسلسل وقت ۾. هن کي ڪرڻ لاء، پهرين قدم تي، توهان کي تبديل ڪرڻ جي ضرورت آهي پهرين عنصر جي حالت کي آخري هڪ سان، ٻئي کي ختم ڪرڻ واري هڪ سان، وغيره. آخري عنصر جي حالت صحيح پوزيشن ۾ هوندي. ۽ ھاڻي اسان کي ٻئي عنصر جي حالت کي آخري ھڪڙي سان تبديل ڪرڻ جي ضرورت آھي، ٽيون ھڪڙي ختم ٿيڻ واري ھڪڙي سان، وغيره. تبادلي جي هن دور کان پوء، سڀني عنصرن جون رياستون صحيح پوزيشن ۾ هونديون. مجموعي طور تي O(2M) ~ O(1) اجازتون هونديون.

اهڙو حل ڪنهن به رياضي دان کي حيران نه ڪندو، جيڪو اڃا تائين ياد رکي ٿو ته گردش ٻن محوري هموارن جو ٺهيل آهي. رستي جي ذريعي، اهو معمولي طور تي عام طور تي هڪ شفٽ لاء نه، پر K < N پوزيشن طرفان. (تبصرن ۾ لکو ته ڪيئن بلڪل.)

ڇا توهان پزل پسند ڪيو؟ ڇا توهان ٻين حلن کي ڄاڻو ٿا؟ تبصرن ۾ حصيداري ڪريو.

۽ آخر ۾ هتي ڪجهه مفيد لنڪس آهن:

• بابت وڌيڪ سکو بنيادي ڍانچي جي ترقي شڪل ۾
• اندروني رڪارڊ ڏسو رپورٽن سان گڏ مسافر ورهايل نظام جي باري ۾
• وڊيو ليڪچر جو سلسلو ڏسوعام ماڻهن لاء غير معمولي الگورتھم»
• اسان جي رڪنيت حاصل ڪريو ٽيليگرام ۾ چينل

جو ذريعو: www.habr.com