چند روز پیش اتفاق افتاد کنفرانس هیدرا. بچه‌های گروه JUG.ru از سخنرانان رویایی (لزلی لمپورت! کلیف کلیک! مارتین کلپمن!) دعوت کردند و دو روز را به سیستم‌های توزیع شده و محاسبات اختصاص دادند. کنتور یکی از سه شریک کنفرانس بود. ما در غرفه صحبت کردیم، در مورد فضای ذخیره شده خود صحبت کردیم، یکنوع بازی شبیه لوتو بازی کردیم، و پازل ها را حل کردیم.

این یک پست با تجزیه و تحلیل وظایف در غرفه Kontur از نویسنده متن آنها است. چه کسی در Hydra بود - این دلیل شما برای به یاد آوردن تجربه لذت بخش است، چه کسی نبود - فرصتی برای کشش مغز شما بزرگ O-نشانه گذاری.

حتی شرکت‌کنندگانی بودند که برای نوشتن تصمیم خود، فلیپ‌چارت را در اسلایدها جدا کردند. شوخی نمی کنم - آنها این پشته کاغذ را برای تأیید تحویل دادند:

در کل سه کار وجود داشت:

• در مورد انتخاب کپی بر اساس وزن برای متعادل کردن بار
• در مورد مرتب سازی نتایج پرس و جو در برابر یک پایگاه داده در حافظه
• در مورد انتقال حالت در یک سیستم توزیع شده با توپولوژی حلقه

وظیفه 1. ClusterClient

لازم بود یک الگوریتم برای انتخاب کارآمد K از N کپی وزنی یک سیستم توزیع شده پیشنهاد شود:

تیم شما وظیفه دارد یک کتابخانه مشتری برای یک خوشه انبوه توزیع شده از N گره ایجاد کند. کتابخانه ابرداده های مختلف مرتبط با گره ها را ردیابی می کند (به عنوان مثال، تأخیر آنها، نرخ پاسخ 4xx/5xx، و غیره) و وزن های ممیز شناور W1..WN را به آنها اختصاص می دهد. به منظور پشتیبانی از استراتژی اجرای همزمان، کتابخانه باید بتواند K از N گره را به طور تصادفی انتخاب کند - شانس انتخاب شدن باید متناسب با وزن یک گره باشد.

الگوریتمی برای انتخاب موثر گره ها پیشنهاد کنید. پیچیدگی محاسباتی آن را با استفاده از نماد O بزرگ تخمین بزنید.

چرا همه چیز به زبان انگلیسی است؟

زیرا در این شکل شرکت کنندگان کنفرانس با آنها جنگیدند و به دلیل اینکه انگلیسی زبان رسمی هیدرا بود. وظایف به این شکل بود:

کاغذ و مداد بردارید، فکر کنید، برای باز کردن اسپویلرها عجله نکنید 🙂

تجزیه و تحلیل راه حل (فیلم)

شروع ساعت 5:53، فقط 4 دقیقه:

و در اینجا این است که چگونه بچه های دارای فلیپچارت راه حل خود را مطرح کردند:

تجزیه و تحلیل راه حل (متن)

راه حل زیر روی سطح قرار دارد: وزن همه ماکت ها را جمع کنید، یک عدد تصادفی از 0 تا مجموع همه وزن ها ایجاد کنید، سپس یک ماکت i انتخاب کنید به طوری که مجموع اوزان ماکت از 0 تا (i-1)ام باشد. کمتر از یک عدد تصادفی است و مجموع اوزان ماکت از 0 تا i-ام - بیشتر از آن است. بنابراین امکان انتخاب یک ماکت وجود خواهد داشت و برای انتخاب نسخه بعدی باید کل روش را بدون در نظر گرفتن ماکت انتخابی تکرار کنید. با چنین الگوریتمی، پیچیدگی انتخاب یک ماکت O(N) است، پیچیدگی انتخاب کپی‌ها O(N K) ~ O(N2) است.

پیچیدگی درجه دوم بد است، اما می توان آن را بهبود بخشید. برای این کار می سازیم درخت قطعه برای مجموع اوزان درختی با عمق lg N به دست می آید که در برگ های آن وزن های مشابه و در گره های باقی مانده - مجموع جزئی تا مجموع همه وزن ها در ریشه درخت وجود دارد. در مرحله بعد، یک عدد تصادفی از 0 تا مجموع همه وزن ها ایجاد می کنیم، ماکت i-ام را پیدا می کنیم، آن را از درخت حذف می کنیم و این روش را برای یافتن ماکت های باقی مانده تکرار می کنیم. با این الگوریتم، پیچیدگی ساخت درخت O(N)، پیچیدگی یافتن ماکت i و حذف آن از درخت O(lg N)، پیچیدگی انتخاب کپی‌های K O(N + K است. lg N) ~ O(N lg N) .

پیچیدگی لاگ خطی بهتر از پیچیدگی درجه دوم است، به خصوص برای 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 به min- یا max-heap (بسته به جهت مرتب سازی) اضافه می شود و سپس هر سند بعدی با ریشه درخت مقایسه می شود که حاوی حداقل یا حداکثر سند فعلی است. و در صورت لزوم به درخت اضافه می شود. در این مورد، پیچیدگی در بدترین حالت، زمانی که باید دائماً درخت را بازسازی کنید، O(M lg M) است، پیچیدگی به طور متوسط ​​O(M) است، مانند انتخاب سریع.

با این حال، جریان پشته کارآمدتر به نظر می رسد زیرا در عمل اکثر اسناد را می توان بدون بازسازی پشته پس از یک مقایسه با عنصر ریشه آن دور انداخت. چنین مرتب‌سازی در پایگاه داده سند درون حافظه Zebra که در 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 به طور بی اهمیت تعمیم داده می شود. (در نظرات بنویسید که دقیقا چگونه است.)

پازل دوست داشتی؟ آیا راه حل های دیگری می دانید؟ در نظرات به اشتراک بگذارید.

و در پایان چند لینک مفید وجود دارد:

• بیشتر بدانید توسعه زیرساخت ها در کانتور
• مشاهده سوابق داخلی بروشور با گزارش در مورد سیستم های توزیع شده
• مجموعه سخنرانی های ویدیویی را تماشا کنیدالگوریتم های غیر معمول برای مردم عادی»
• مشترک ما شوید کانال در تلگرام

منبع: www.habr.com