কয়েকদিন আগের ঘটনা হাইড্রা সম্মেলন. JUG.ru গ্রুপের ছেলেরা ড্রিম স্পিকারদের আমন্ত্রণ জানিয়েছে (লেসলি ল্যামপোর্ট! ক্লিফ ক্লিক! মার্টিন ক্লেপম্যান!) এবং ডিস্ট্রিবিউটেড সিস্টেম এবং কম্পিউটিং এর জন্য দুই দিন সময় দিয়েছে। কনট্যুর সম্মেলনের তিন অংশীদারের একজন ছিলেন। আমরা বুথে কথা বলেছি, আমাদের বিতরণ করা স্টোরেজ সম্পর্কে কথা বলেছি, বিঙ্গো খেলেছি এবং ধাঁধা সমাধান করেছি।

এটি তাদের টেক্সট লেখক থেকে Kontur স্ট্যান্ড এ কর্মের একটি বিশ্লেষণ সহ একটি পোস্ট. হাইড্রায় কে ছিলেন - এটি আপনার মনোরম অভিজ্ঞতা মনে রাখার কারণ, কে ছিল না - আপনার মস্তিষ্ক প্রসারিত করার একটি সুযোগ বড় ও-স্বরলিপি।

এমনকি এমন অংশগ্রহণকারীও ছিলেন যারা তাদের সিদ্ধান্ত লিখতে স্লাইডে ফ্লিপচার্টটি ভেঙে দিয়েছিলেন। আমি রসিকতা করছি না - তারা যাচাইয়ের জন্য কাগজের এই স্ট্যাকটি হস্তান্তর করেছে:

মোট তিনটি কাজ ছিল:

• লোড ভারসাম্যের জন্য ওজন দ্বারা প্রতিলিপি নির্বাচন সম্পর্কে
• একটি ইন-মেমরি ডাটাবেসের বিরুদ্ধে অনুসন্ধান ফলাফল বাছাই সম্পর্কে
• একটি রিং টপোলজি সহ একটি বিতরণ ব্যবস্থায় রাষ্ট্রীয় স্থানান্তরের উপর

টাস্ক 1. ক্লাস্টার ক্লায়েন্ট

বিতরণ করা সিস্টেমের 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 থেকে সমস্ত ওজনের যোগফল পর্যন্ত একটি এলোমেলো সংখ্যা তৈরি করি, i-th রেপ্লিকাটি খুঁজে বের করি, এটিকে গাছ থেকে সরিয়ে ফেলি এবং অবশিষ্ট প্রতিলিপিগুলি খুঁজে বের করার পদ্ধতিটি পুনরাবৃত্তি করি। এই অ্যালগরিদমের সাহায্যে, একটি গাছ তৈরির জটিলতা হল O(N), i-th রেপ্লিকা খুঁজে বের করার এবং গাছ থেকে সরিয়ে ফেলার জটিলতা হল O(lg N), K রেপ্লিকা বেছে নেওয়ার জটিলতা হল O(N + K) lg N) ~ O(N lg N) .

রৈখিক-লগ জটিলতা দ্বিঘাত জটিলতার চেয়ে সুন্দর, বিশেষ করে বড় K-এর জন্য।

এটা এই অ্যালগরিদম কোডে বাস্তবায়িত প্রকল্প থেকে ClusterClient লাইব্রেরি "পূর্ব" (সেখানে, গাছটি 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)।

এটা স্পষ্ট যে সমস্ত M নথি বাছাই করা এবং তারপর তাদের শুধুমাত্র একটি ছোট অংশ গ্রহণ করা অদক্ষ। সমস্ত নথি বাছাই না করার জন্য, একটি অ্যালগরিদম উপযুক্ত দ্রুত নির্বাচন করুন, যা পছন্দসই নথিগুলির N + S নির্বাচন করবে (এগুলি যে কোনও অ্যালগরিদম দ্বারা বাছাই করা যেতে পারে)। এই ক্ষেত্রে, জটিলতা গড়ে O(M) এ কমে যাবে, যখন সবচেয়ে খারাপ অবস্থা একই থাকবে।

যাইহোক, আপনি এটি আরও দক্ষতার সাথে করতে পারেন - অ্যালগরিদম ব্যবহার করুন বাইনারি হিপ স্ট্রিমিং. এই ক্ষেত্রে, প্রথম N+S নথিগুলিকে ন্যূনতম- বা সর্বোচ্চ-স্তূপে যোগ করা হয় (বাছাই করার দিকনির্দেশের উপর নির্ভর করে), এবং তারপর প্রতিটি পরবর্তী নথিকে গাছের মূলের সাথে তুলনা করা হয়, যেখানে বর্তমান সর্বনিম্ন বা সর্বোচ্চ নথি রয়েছে, এবং প্রয়োজনে গাছে যোগ করা হয়। এই ক্ষেত্রে, সবচেয়ে খারাপ ক্ষেত্রে জটিলতা, যখন আপনাকে ক্রমাগত গাছটি পুনর্নির্মাণ করতে হয়, তা হল O(M lg M), গড় জটিলতা হল O(M), যেমন কুইকসিলেক্ট।

যাইহোক, হিপ স্ট্রিমিং আরও কার্যকরী হয়ে উঠেছে এই কারণে যে বাস্তবে বেশিরভাগ নথির মূল উপাদানের সাথে একক তুলনা করার পরে হিপটিকে পুনর্নির্মাণ না করেই বাতিল করা যেতে পারে। এই ধরনের বাছাই জেব্রা ইন-মেমরি ডকুমেন্ট ডাটাবেসে প্রয়োগ করা হয় যা কন্টুরে তৈরি এবং ব্যবহৃত হয়।

টাস্ক 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