რამდენიმე დღის წინ მოხდა ჰიდრას კონფერენცია. ბიჭებმა JUG.ru ჯგუფიდან მოიწვიეს ოცნების დინამიკები (ლესლი ლამპორტი! კლიფ დაკლიკ! მარტინ კლეპმანი!) და ორი დღე დაუთმეს განაწილებულ სისტემებსა და გამოთვლებს. კონტური კონფერენციის სამი პარტნიორიდან ერთ-ერთი იყო. ჩვენ ვისაუბრეთ ჯიხურზე, ვისაუბრეთ ჩვენს განაწილებულ საცავზე, ვითამაშეთ ბინგო და მოვაგვარეთ თავსატეხები.

ეს არის პოსტი კონტურის სტენდზე ამოცანების ანალიზით მათი ტექსტის ავტორისგან. ვინ იყო ჰიდრაზე - ეს არის თქვენი მიზეზი, გაიხსენოთ სასიამოვნო გამოცდილება, ვინ არა - თქვენი ტვინის გაჭიმვის შანსი დიდი O- ნოტაცია.

იყვნენ მონაწილეებიც კი, რომლებმაც დაშალეს ფლიპჩარტი სლაიდებად, რათა დაეწერათ თავიანთი გადაწყვეტილება. არ ვხუმრობ - გადასცეს ეს დასტა გადასამოწმებლად:

სულ სამი დავალება იყო:

• დატვირთვის დასაბალანსებლად წონის მიხედვით ასლების შერჩევის შესახებ
• შეკითხვის შედეგების დახარისხების შესახებ მეხსიერების მონაცემთა ბაზაში
• რგოლის ტოპოლოგიით განაწილებულ სისტემაში მდგომარეობის გადაცემის შესახებ

ამოცანა 1. ClusterClient

საჭირო იყო ალგორითმის შეთავაზება განაწილებული სისტემის N შეწონილი რეპლიკებიდან K-ის ეფექტური შერჩევისთვის:

თქვენს გუნდს ევალება განავითაროს კლიენტის ბიბლიოთეკა N კვანძების მასიურად განაწილებული კლასტერისთვის. ბიბლიოთეკა თვალყურს ადევნებს კვანძებთან დაკავშირებულ სხვადასხვა მეტამონაცემებს (მაგ., მათი შეყოვნება, 4xx/5xx პასუხების სიხშირე და ა.შ.) და ანიჭებს მათ მცურავი წერტილის წონებს W1..WN. თანმხლები შესრულების სტრატეგიის მხარდასაჭერად, ბიბლიოთეკას უნდა შეეძლოს N კვანძებიდან K-ის არჩევა შემთხვევით - არჩევის შანსი უნდა იყოს კვანძის წონის პროპორციული.

შესთავაზეთ ალგორითმი კვანძების ეფექტურად შესარჩევად. შეაფასეთ მისი გამოთვლითი სირთულე დიდი O ნოტაციის გამოყენებით.

რატომ არის ყველაფერი ინგლისურად?

რადგან ამ ფორმით კონფერენციის მონაწილეები იბრძოდნენ მათთან და იმიტომ, რომ ინგლისური იყო ჰიდრას ოფიციალური ენა. დავალებები ასე გამოიყურებოდა:

აიღეთ ქაღალდი და ფანქარი, დაფიქრდით, ნუ იჩქარებთ სპოილერების გახსნას მაშინვე 🙂

ხსნარის ანალიზი (ვიდეო)

დასაწყისი 5:53 საათზე, მხოლოდ 4 წუთი:

და აი, როგორ წამოაყენეს თავიანთი გამოსავალი ბიჭებმა ფლიპჩარტით:

ამოხსნის ანალიზი (ტექსტი)

შემდეგი ამონახსნი დევს ზედაპირზე: შეაჯამეთ ყველა რეპლიკების წონა, გენერირება შემთხვევითი რიცხვი 0-დან ყველა წონის ჯამამდე, შემდეგ აირჩიეთ i-რეპლიკა ისე, რომ ასლების წონების ჯამი 0-დან (i-1)-მდე. შემთხვევით რიცხვზე ნაკლებია, ხოლო რეპლიკა წონების ჯამი 0-დან i-th-მდე - მასზე მეტი. ასე რომ, შესაძლებელი იქნება ერთი ასლის არჩევა, ხოლო შემდეგის ასარჩევად, თქვენ უნდა გაიმეოროთ მთელი პროცედურა შერჩეული რეპლიკის განხილვის გარეშე. ასეთი ალგორითმით, ერთი ასლის არჩევის სირთულე არის O(N), K რეპლიკების არჩევის სირთულე არის O(N K) ~ O(N2).

კვადრატული სირთულე ცუდია, მაგრამ მისი გაუმჯობესება შესაძლებელია. ამისათვის ჩვენ ავაშენებთ სეგმენტის ხე წონების ჯამებისთვის. მიიღება lg N სიღრმის ხე, რომლის ფოთლებში იქნება რეპლიკა წონები, ხოლო დანარჩენ კვანძებში - ნაწილობრივი ჯამები, ხის ფესვის ყველა წონის ჯამამდე. შემდეგი, ჩვენ ვქმნით შემთხვევით რიცხვს 0-დან ყველა წონის ჯამამდე, ვპოულობთ მე-ე რეპლიკას, ვხსნით მას ხიდან და ვიმეორებთ პროცედურას დარჩენილი რეპლიკების მოსაძებნად. ამ ალგორითმით, ხის აგების სირთულე არის O(N), i-ე რეპლიკას პოვნის და ხიდან ამოღების სირთულე არის O(lg N), K რეპლიკების არჩევის სირთულე არის O(N + K. ლგ ნ) ~ ო(ნ ლგ ნ) .

ხაზოვანი ჟურნალის სირთულე უფრო ლამაზია, ვიდრე კვადრატული, განსაკუთრებით დიდი K-სთვის.

ეს არის ეს ალგორითმი დანერგილი კოდით ClusterClient ბიბლიოთეკები პროექტიდან "აღმოსავლეთი". (იქ, ხე აგებულია O(N lg N-ში), მაგრამ ეს არ იმოქმედებს ალგორითმის საბოლოო სირთულეზე.)

ამოცანა 2. ზებრა

საჭირო იყო მეხსიერების დოკუმენტების ეფექტური დახარისხების ალგორითმის შეთავაზება თვითნებური არაინდექსირებული ველით:

თქვენს გუნდს ევალება შემუშავებული მეხსიერების დოკუმენტების მონაცემთა ბაზა. საერთო დატვირთვა იქნება ზედა N დოკუმენტების შერჩევა, რომლებიც დალაგებულია თვითნებური (არაინდექსირებული) რიცხვითი ველის მიხედვით M ზომის კოლექციიდან (ჩვეულებრივ N < 100 << M). ოდნავ ნაკლებად გავრცელებული დატვირთვა იქნება ზედა N-ის არჩევა ზედა S დოკუმენტების გამოტოვების შემდეგ (S ~ N).

შესთავაზეთ ალგორითმი ასეთი მოთხოვნების ეფექტურად შესასრულებლად. შეაფასეთ მისი გამოთვლითი სირთულის გამოყენებით დიდი O აღნიშვნა საშუალო შემთხვევაში და უარეს შემთხვევაში.

ხსნარის ანალიზი (ვიდეო)

დასაწყისი 34:50 საათზე, მხოლოდ 6 წუთი:

ამოხსნის ანალიზი (ტექსტი)

ზედაპირული გადაწყვეტა: დაალაგეთ ყველა დოკუმენტი (მაგ სიჩქარე), შემდეგ აიღეთ N+S დოკუმენტები. ამ შემთხვევაში დახარისხების სირთულე საშუალოდ არის O(M lg M), უარეს შემთხვევაში O(M2).

აშკარაა, რომ ყველა M დოკუმენტის დახარისხება და შემდეგ მათი მხოლოდ მცირე ნაწილის აღება არაეფექტურია. იმისათვის, რომ არ მოხდეს ყველა დოკუმენტის დალაგება, ალგორითმი შესაფერისია სწრაფი შერჩევა, რომელიც შეარჩევს სასურველ დოკუმენტებს N + S (მათი დახარისხება შესაძლებელია ნებისმიერი ალგორითმით). ამ შემთხვევაში, სირთულე შემცირდება საშუალოდ O(M)-მდე, ხოლო უარესი შემთხვევა იგივე დარჩება.

თუმცა, თქვენ შეგიძლიათ ამის გაკეთება კიდევ უფრო ეფექტურად - გამოიყენეთ ალგორითმი ორობითი გროვის ნაკადი. ამ შემთხვევაში, პირველი N+S დოკუმენტები ემატება მინ- ან მაქსიმალურ გროვას (დამოკიდებულია დალაგების მიმართულებაზე), შემდეგ კი ყოველი შემდეგი დოკუმენტი შედარებულია ხის ფესვთან, რომელიც შეიცავს მიმდინარე მინიმალურ ან მაქსიმალურ დოკუმენტს. და საჭიროების შემთხვევაში ემატება ხეს. ამ შემთხვევაში, სირთულე უარეს შემთხვევაში, როდესაც თქვენ მუდმივად გიწევთ ხის ხელახალი აშენება, არის O(M lg M), სირთულე საშუალოდ არის O(M), როგორც სწრაფი არჩევისას.

თუმცა, გროვის ნაკადი უფრო ეფექტურია იმის გამო, რომ პრაქტიკაში დოკუმენტების უმეტესი ნაწილი შეიძლება განადგურდეს გროვის აღდგენის გარეშე მის ძირეულ ელემენტთან ერთი შედარების შემდეგ. ასეთი დახარისხება ხორციელდება ზებრას მეხსიერების დოკუმენტების მონაცემთა ბაზაში, რომელიც შემუშავებულია და გამოიყენება Kontur-ში.

ამოცანა 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 პოზიციებით. (დაწერეთ კომენტარებში ზუსტად როგორ.)

მოგეწონა თავსატეხები? სხვა გადაწყვეტილებები იცით? გააზიარეთ კომენტარებში.

და ბოლოს აქ არის რამდენიმე სასარგებლო ბმული:

• შეიტყვეთ მეტი ინფრასტრუქტურის განვითარება კონტურში
• იხილეთ შიდა ჩანაწერები ფლაერი მოხსენებებით განაწილებული სისტემების შესახებ
• ნახეთ ვიდეო ლექციების სერიაარაჩვეულებრივი ალგორითმები ჩვეულებრივი ადამიანებისთვის»
• გამოიწერეთ ჩვენი არხი Telegram-ში

წყარო: www.habr.com