Birkaç gün önce oldu . JUG.ru Grubundan adamlar rüya konuşmacıları (Leslie Lamport! Cliff Click! Martin Kleppmann!) davet etti ve iki gününü dağıtık sistemlere ve hesaplamaya ayırdı. Kontur, konferansın üç ortağından biriydi. Standda konuştuk, dağıtılmış depolamamız hakkında konuştuk, bingo oynadık ve bulmacaları çözdük.
Bu, metninin yazarından Kontur standındaki görevlerin analizini içeren bir yazıdır. Hydra'da kim vardı - bu, keyifli deneyimi hatırlama nedeniniz, kim değildi - beyninizi esnetme şansı büyük O- notasyon.
Kararlarını yazmak için kağıtlı sunum tahtasını slaytlara ayıran katılımcılar bile vardı. Şaka yapmıyorum - doğrulama için bu kağıt destesini teslim ettiler:
Toplamda üç görev vardı:
- yük dengeleme için ağırlıklara göre replikaların seçilmesi hakkında
- sorgu sonuçlarını bellek içi bir veritabanına göre sıralama hakkında
- halka topolojisine sahip dağıtılmış bir sistemde durum aktarımında
Görev 1. ClusterClient
Dağıtılmış bir sistemin N ağırlıklı kopyalarından K'nın verimli seçimi için bir algoritma önermek gerekliydi:
Ekibiniz, büyük ölçüde dağıtılmış N düğüm kümesi için bir istemci kitaplığı geliştirmekle görevlendirildi. Kitaplık, düğümlerle ilişkili çeşitli meta verileri (ör. gecikme süreleri, 4xx/5xx yanıt oranları, vb.) takip edecek ve bunlara W1..WN kayan nokta ağırlıkları atayacaktır. Eşzamanlı yürütme stratejisini desteklemek için kitaplık, K of N düğümü rastgele seçebilmelidir; seçilme şansı bir düğümün ağırlığıyla orantılı olmalıdır.
Düğümleri verimli bir şekilde seçmek için bir algoritma önerin. Büyük O gösterimini kullanarak hesaplama karmaşıklığını tahmin edin.
Neden her şey İngilizce?
Çünkü bu formda konferans katılımcıları onlarla savaştı ve çünkü Hydra'nın resmi dili İngilizce idi. Görevler şuna benziyordu:
Kağıt kalem alın, düşünün, hemen spoiler açmak için acele etmeyin 🙂
Çözümün analizi (video)
5:53'ten başlayarak, sadece 4 dakika:
Ve kağıtlı sunum tahtası olan adamlar çözümlerini şu şekilde sundular:
Çözümün analizi (metin)
Aşağıdaki çözüm yüzeyde yatıyor: tüm replikaların ağırlıklarını topla, 0'dan tüm ağırlıkların toplamına kadar rasgele bir sayı oluştur, sonra replika ağırlıklarının toplamı 0'dan (i-1)'e olacak şekilde bir i-replika seç rasgele bir sayıdan daha küçüktür ve 0'dan i'inciye kadar kopya ağırlıklarının toplamı ondan fazladır. Böylece bir kopyayı seçmek mümkün olacak ve bir sonrakini seçmek için, seçilen kopyayı dikkate almadan tüm prosedürü tekrarlamanız gerekecek. Böyle bir algoritma ile, bir kopyayı seçmenin karmaşıklığı O(N), K kopyayı seçmenin karmaşıklığı O(N K) ~ O(N2).
İkinci dereceden karmaşıklık kötüdür, ancak geliştirilebilir. Bunu yapmak için inşa edeceğiz ağırlıkların toplamları için. Yapraklarında kopya ağırlıkların olacağı lg N derinliğinde bir ağaç elde edilecek ve kalan düğümlerde - ağacın kökündeki tüm ağırlıkların toplamına kadar kısmi toplamlar. Ardından, 0'dan tüm ağırlıkların toplamına kadar rasgele bir sayı üretiyoruz, i'inci kopyayı buluyoruz, onu ağaçtan kaldırıyoruz ve kalan kopyaları bulmak için prosedürü tekrarlıyoruz. Bu algoritma ile, bir ağaç inşa etmenin karmaşıklığı O(N), i-inci kopyayı bulmanın ve onu ağaçtan kaldırmanın karmaşıklığı O(lg N), K kopyalarını seçmenin karmaşıklığı O(N + K) lg N) ~ O(N lg N) .
Doğrusal günlük karmaşıklığı, özellikle büyük K için ikinci dereceden karmaşıklıktan daha iyidir.
bu algoritma " projesindeki ClusterClient kitaplıkları". (Orada, ağaç O(N lg N) şeklinde oluşturulmuştur, ancak bu, algoritmanın nihai karmaşıklığını etkilemez.)
Görev 2. Zebra
Bellekteki belgelerin keyfi bir dizine eklenmemiş alan tarafından verimli bir şekilde sıralanması için bir algoritma önermek gerekliydi:
Ekibiniz, parçalanmış bir bellek içi belge veritabanı geliştirmekle görevlendirilmiştir. Yaygın bir iş yükü, M boyutundaki bir koleksiyondan (genellikle N < 100 << M) rastgele (dizine eklenmemiş) bir sayısal alana göre sıralanmış en iyi N belgeyi seçmek olacaktır. Biraz daha az yaygın olan bir iş yükü, en üstteki S belgelerini (S ~ N) atladıktan sonra en üstteki N'yi seçmek olacaktır.
Bu tür sorguları verimli bir şekilde yürütmek için bir algoritma önerin. Ortalama durumda ve en kötü durum senaryolarında büyük O gösterimini kullanarak hesaplama karmaşıklığını tahmin edin.
Çözümün analizi (video)
34:50'den itibaren sadece 6 dakika:
Çözümün analizi (metin)
Yüzey çözümü: tüm belgeleri sıralayın (örneğin, ), ardından N+S belgeleri alın. Bu durumda sıralamanın karmaşıklığı ortalama olarak O(M lg M), en kötü ihtimalle O(M2)'dir.
Tüm M belgelerini sıralamanın ve ardından bunların yalnızca küçük bir bölümünü almanın verimsiz olduğu açıktır. Tüm belgeleri sıralamamak için bir algoritma uygundur , istenen belgelerin N + S'sini seçecek (herhangi bir algoritmaya göre sıralanabilirler). Bu durumda, karmaşıklık ortalama olarak O(M)'ye düşecek, en kötü durum ise aynı kalacaktır.
Ancak, bunu daha verimli bir şekilde yapabilirsiniz - algoritmayı kullanın . Bu durumda, ilk N+S belgeleri min- veya max-heap'e eklenir (sıralama yönüne bağlı olarak) ve ardından sonraki her belge, geçerli minimum veya maksimum belgeyi içeren ağacın köküyle karşılaştırılır. ve gerekirse ağaca eklenir. . Bu durumda, en kötü durumdaki karmaşıklık, sürekli olarak ağacı yeniden oluşturmanız gerektiğinde O(M lg M), hızlı seçimde olduğu gibi ortalama karmaşıklık O(M)'dir.
Bununla birlikte, yığın akışının, pratikte belgelerin çoğunun kök öğesiyle tek bir karşılaştırmadan sonra yığını yeniden oluşturmadan atılabilmesi nedeniyle daha verimli olduğu ortaya çıkıyor. Bu sıralama, Kontur'da geliştirilen ve kullanılan Zebra bellek içi belge veritabanında uygulanır.
Görev 3. Durum takasları
Durumları değiştirmek için en verimli algoritmayı önermek gerekliydi:
Ekibiniz, dağıtılmış bir N düğüm kümesi için süslü bir durum değişim mekanizması geliştirmekle görevlendirildi. i'inci düğümün durumu (i+1)'inci düğüme, N'inci düğümün durumu birinci düğüme aktarılmalıdır. Desteklenen tek işlem, iki düğüm durumlarını atomik olarak değiştirdiğinde durum takasıdır. Bir durum takasının M milisaniye sürdüğü bilinmektedir. Her düğüm, herhangi bir anda tek bir durum takasına katılabilir.
Bir kümedeki tüm düğümlerin durumlarını aktarmak ne kadar sürer?
Çözümün analizi (metin)
Yüzey çözümü: birinci ve ikinci elementin, ardından birinci ve üçüncünün, ardından birinci ve dördüncünün vb. durumlarını değiş tokuş edin. Her değişimden sonra, bir elemanın durumu istenen konumda olacaktır. O(N) permütasyonları yapmanız ve O(N M) zaman harcamanız gerekiyor.
Doğrusal zaman uzundur, bu nedenle öğelerin durumlarını çiftler halinde değiştirebilirsiniz: birinci ile ikinci, üçüncü ile dördüncü vb. Her durum değişiminden sonra, her ikinci öğe doğru konumda olacaktır. O(lg N) permütasyonları yapmalı ve O(M lg N) zaman harcamalısınız.
Bununla birlikte, vardiyayı daha da verimli hale getirmek mümkündür - doğrusal değil, sabit zamanda. Bunu yapmak için, ilk adımda, ilk öğenin durumunu sonuncuyla, ikinciyi sondan bir öncekiyle vb. değiştirmeniz gerekir. Son öğenin durumu doğru konumda olacaktır. Ve şimdi ikinci öğenin durumunu sonuncuyla, üçüncü öğeyi sondan bir önceki öğeyle vs. değiştirmemiz gerekiyor. Bu değiş tokuş turundan sonra, tüm elementlerin durumları doğru konumda olacaktır. Toplamda O(2M) ~ O(1) permütasyonları olacaktır.
Böyle bir çözüm, dönmenin iki eksenel simetrinin bileşimi olduğunu hala hatırlayan bir matematikçiyi hiç şaşırtmayacaktır. Bu arada, bir kayma için bir değil, K < N konumlarına göre önemsiz bir şekilde genelleştirilmiştir. (Tam olarak nasıl olduğunu yorumlara yazın.)
Bulmacaları sevdin mi? Başka çözümler biliyor musunuz? Yorumlarda paylaşın.
Ve işte sonunda bazı yararlı bağlantılar:
- hakkında daha fazla öğren konturda
- dahili kayıtlara bakın dağıtık sistemler hakkında
- video ders dizisini izle»
- abone ol
Kaynak: habr.com