کچھ دن پہلے کی بات ہے۔ . JUG.ru گروپ کے لڑکوں نے ڈریم سپیکرز (لیسلی لیمپورٹ! کلف کلک! مارٹن کلیپ مین!) کو مدعو کیا اور دو دن تقسیم شدہ نظاموں اور کمپیوٹنگ کے لیے وقف کیے تھے۔ کونتور کانفرنس کے تین شراکت داروں میں سے ایک تھا۔ ہم نے بوتھ پر بات کی، اپنے تقسیم شدہ اسٹوریج کے بارے میں بات کی، بنگو کھیلا، اور پہیلیاں حل کیں۔
یہ ان کے متن کے مصنف سے کونتور اسٹینڈ پر کاموں کے تجزیہ کے ساتھ ایک پوسٹ ہے۔ ہائیڈرا پر کون تھا - یہ آپ کے خوشگوار تجربے کو یاد رکھنے کی وجہ ہے، کون نہیں تھا - اپنے دماغ کو کھینچنے کا موقع بڑا O-نوٹیشن
یہاں تک کہ ایسے شرکاء بھی تھے جنہوں نے اپنا فیصلہ لکھنے کے لیے فلپ چارٹ کو سلائیڈوں میں توڑ دیا۔ میں مذاق نہیں کر رہا ہوں - انہوں نے تصدیق کے لیے کاغذ کا یہ ڈھیر حوالے کیا:
کل تین کام تھے:
- بوجھ کے توازن کے لیے وزن کے حساب سے نقلیں منتخب کرنے کے بارے میں
- ان میموری ڈیٹا بیس کے خلاف استفسار کے نتائج کو ترتیب دینے کے بارے میں
- رنگ ٹوپولوجی کے ساتھ تقسیم شدہ نظام میں ریاستی منتقلی پر
ٹاسک 1۔ کلسٹر کلائنٹ
تقسیم شدہ نظام کی N وزنی نقلوں سے K کے موثر انتخاب کے لیے الگورتھم تجویز کرنا ضروری تھا:
آپ کی ٹیم کو N نوڈس کے بڑے پیمانے پر تقسیم شدہ کلسٹر کے لیے کلائنٹ لائبریری تیار کرنے کا کام سونپا گیا ہے۔ لائبریری نوڈس کے ساتھ منسلک مختلف میٹا ڈیٹا (مثلاً، ان کی تاخیر، 4xx/5xx رسپانس ریٹ، وغیرہ) پر نظر رکھے گی اور انہیں فلوٹنگ پوائنٹ وزن W1..WN تفویض کرے گی۔ ایک ساتھ عمل درآمد کی حکمت عملی کو سپورٹ کرنے کے لیے، لائبریری کو N نوڈس کے K کو تصادفی طور پر لینے کے قابل ہونا چاہیے- منتخب کیے جانے کا موقع نوڈ کے وزن کے متناسب ہونا چاہیے۔
نوڈس کو مؤثر طریقے سے منتخب کرنے کے لیے الگورتھم تجویز کریں۔ بڑے O اشارے کا استعمال کرتے ہوئے اس کی کمپیوٹیشنل پیچیدگی کا اندازہ لگائیں۔
سب کچھ انگریزی میں کیوں ہے؟
کیونکہ اس شکل میں کانفرنس کے شرکاء ان سے لڑتے تھے اور کیونکہ انگریزی ہائیڈرا کی سرکاری زبان تھی۔ کام اس طرح نظر آئے:
کاغذ اور پنسل لیں، سوچیں، فوراً سپائلرز کھولنے میں جلدی نہ کریں 🙂
حل کا تجزیہ (ویڈیو)
5:53 پر شروع، صرف 4 منٹ:
اور یہ ہے کہ فلپ چارٹ والے لڑکوں نے اپنا حل کیسے نکالا:
حل کا تجزیہ (متن)
مندرجہ ذیل حل سطح پر موجود ہے: تمام نقلوں کے وزن کا مجموعہ، 0 سے تمام وزنوں کے مجموعہ تک ایک بے ترتیب نمبر بنائیں، پھر ایک i-replica کا انتخاب کریں کہ نقل کے وزن کا مجموعہ 0 سے (i-1)th تک ہو۔ ایک بے ترتیب نمبر سے کم ہے، اور نقل کا وزن 0 سے i-th تک - اس سے زیادہ ہے۔ لہذا ایک نقل کو منتخب کرنا ممکن ہوگا، اور اگلی کو منتخب کرنے کے لیے، آپ کو منتخب شدہ نقل پر غور کیے بغیر پورے طریقہ کار کو دہرانا ہوگا۔ اس طرح کے الگورتھم کے ساتھ، ایک نقل کو منتخب کرنے کی پیچیدگی O(N) ہے، K نقل کو منتخب کرنے کی پیچیدگی O(N K) ~ O(N2) ہے۔
چوکور پیچیدگی خراب ہے، لیکن اسے بہتر کیا جا سکتا ہے۔ ایسا کرنے کے لئے، ہم تعمیر کریں گے وزن کی رقم کے لیے۔ lg N کی گہرائی کا ایک درخت حاصل کیا جائے گا، جس کے پتوں میں نقلی وزن ہوں گے، اور باقی نوڈس میں - جزوی رقم، درخت کی جڑ میں تمام وزنوں کے مجموعہ تک۔ اس کے بعد، ہم 0 سے تمام وزنوں کے مجموعہ تک ایک بے ترتیب نمبر تیار کرتے ہیں، i-th نقل تلاش کرتے ہیں، اسے درخت سے ہٹاتے ہیں، اور باقی نقلیں تلاش کرنے کے لیے طریقہ کار کو دہراتے ہیں۔ اس الگورتھم کے ساتھ، درخت بنانے کی پیچیدگی O(N) ہے، i-th نقل کو تلاش کرنے اور اسے درخت سے ہٹانے کی پیچیدگی O(lg N) ہے، K نقل کے انتخاب کی پیچیدگی O(N+K) ہے۔ lg N) ~ O(N lg N) .
لکیری لاگ پیچیدگی چوکور پیچیدگی سے بہتر ہے، خاص طور پر بڑے K کے لیے۔
یہ الگورتھم ہے۔ پروجیکٹ سے کلسٹر کلائنٹ لائبریریاں "" (وہاں، درخت 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 دستاویزات کو کم سے کم یا زیادہ سے زیادہ ہیپ میں شامل کیا جاتا ہے (چھانٹنے کی سمت پر منحصر ہے)، اور پھر ہر اگلی دستاویز کا درخت کی جڑ سے موازنہ کیا جاتا ہے، جس میں موجودہ کم از کم یا زیادہ سے زیادہ دستاویز ہوتی ہے، اور اگر ضروری ہو تو درخت میں شامل کیا جاتا ہے۔ اس صورت میں، بدترین صورت میں پیچیدگی، جب آپ کو درخت کو مسلسل دوبارہ بنانا پڑتا ہے، O(M lg M) ہے، اوسطاً پیچیدگی O(M) ہے، جیسا کہ Quickselect کے ساتھ۔
تاہم، ہیپ سٹریمنگ اس حقیقت کی وجہ سے زیادہ کارآمد ثابت ہوتی ہے کہ عملی طور پر زیادہ تر دستاویزات کو اس کے بنیادی عنصر کے ساتھ ایک ہی موازنہ کے بعد ہیپ کو دوبارہ تعمیر کیے بغیر ضائع کیا جا سکتا ہے۔ اس طرح کی ترتیب کو کونٹور میں تیار کردہ اور استعمال شدہ زیبرا ان میموری دستاویز کے ڈیٹا بیس میں لاگو کیا جاتا ہے۔
ٹاسک 3۔ اسٹیٹ سویپ
ریاستوں کو تبدیل کرنے کے لئے سب سے زیادہ موثر الگورتھم تجویز کرنا ضروری تھا:
آپ کی ٹیم کو N نوڈس کے تقسیم شدہ کلسٹر کے لیے فینسی اسٹیٹ ایکسچینج میکانزم تیار کرنے کا کام سونپا گیا ہے۔ i-th نوڈ کی حالت (i+1) -th نوڈ میں منتقل کی جانی چاہیے، N-th نوڈ کی حالت کو پہلے نوڈ میں منتقل کیا جانا چاہیے۔ جب دو نوڈس جوہری طور پر اپنی ریاستوں کا تبادلہ کرتے ہیں تو واحد تعاون یافتہ آپریشن اسٹیٹ سویپ ہے۔ یہ معلوم ہے کہ ریاست کی تبدیلی میں M ملی سیکنڈ لگتے ہیں۔ ہر نوڈ کسی بھی لمحے ایک ریاست کی تبدیلی میں حصہ لینے کے قابل ہے۔
ایک کلسٹر میں تمام نوڈس کی ریاستوں کو منتقل کرنے میں کتنا وقت لگتا ہے؟
حل کا تجزیہ (متن)
سطح کا حل: پہلے اور دوسرے عنصر کی حالتوں کا تبادلہ کریں، پھر پہلے اور تیسرے، پھر پہلے اور چوتھے، وغیرہ۔ ہر تبادلے کے بعد، ایک عنصر کی حالت مطلوبہ پوزیشن میں ہوگی۔ آپ کو O(N) کی تبدیلیاں کرنی ہوں گی اور O(N M) وقت گزارنا ہوگا۔
لکیری وقت طویل ہے، لہذا آپ عناصر کی حالتوں کو جوڑوں میں تبدیل کر سکتے ہیں: پہلی دوسری کے ساتھ، تیسری چوتھے کے ساتھ، وغیرہ۔ ہر ریاست کے تبادلے کے بعد، ہر دوسرا عنصر صحیح پوزیشن میں ہوگا۔ آپ کو O(lg N) کی تبدیلیاں کرنی ہوں گی اور O(M lg N) وقت گزارنا ہوگا۔
تاہم، شفٹ کو اور زیادہ موثر بنانا ممکن ہے - لکیری میں نہیں، بلکہ مستقل وقت میں۔ ایسا کرنے کے لیے، پہلے مرحلے پر، آپ کو پہلے عنصر کی حالت کو آخری کے ساتھ، دوسرے کو آخری عنصر کے ساتھ تبدیل کرنے کی ضرورت ہے، وغیرہ۔ آخری عنصر کی حالت درست پوزیشن میں ہوگی۔ اور اب ہمیں دوسرے عنصر کی حالت کو آخری کے ساتھ، تیسرے کو آخری عنصر کے ساتھ تبدیل کرنے کی ضرورت ہے، وغیرہ۔ تبادلے کے اس دور کے بعد، تمام عناصر کی ریاستیں صحیح پوزیشن میں ہوں گی۔ مجموعی طور پر O(2M) ~ O(1) کی تبدیلیاں ہوں گی۔
اس طرح کا حل کسی ایسے ریاضی دان کو بالکل بھی حیران نہیں کرے گا جو اب بھی یاد رکھتا ہے کہ گردش دو محوری توازنوں کی تشکیل ہے۔ ویسے، یہ معمولی طور پر ایک تبدیلی کے لیے نہیں، بلکہ K <N پوزیشنز کے لیے عام کیا جاتا ہے۔ (کمنٹس میں لکھیں کہ بالکل کیسے۔)
کیا آپ کو پہیلیاں پسند تھیں؟ کیا آپ دوسرے حل جانتے ہیں؟ کمنٹس میں شیئر کریں۔
اور آخر میں کچھ مفید لنکس یہ ہیں:
- متعلق مزید پڑھئے سموچ میں
- اندرونی ریکارڈ دیکھیں تقسیم شدہ نظام کے بارے میں
- ویڈیو لیکچرز کا سلسلہ دیکھیں»
- ہمارے سبسکرائب کریں
ماخذ: www.habr.com