خوارزميات الفرز القريبة - متى تستخدم؟

Question

من وقت لآخر، أتصفح الويب وأبحث عن خوارزميات وهياكل بيانات مثيرة للاهتمام لأضعها في حقيبتي من الحيل.منذ عام مضى صادفت كومة ناعمة بنية البيانات وتعلمت عن الفرز القريب.

الفكرة وراء ذلك هي أنه من الممكن كسر حاجز O(n log n) للفرز القائم على المقارنة إذا كنت تستطيع التعايش مع حقيقة أن خوارزمية الفرز تغش قليلاً.تحصل على قائمة مرتبة تقريبًا ولكن عليك أن تتعايش مع بعض الأخطاء أيضًا.

لقد تلاعبت بالخوارزميات في بيئة اختبار ولكنني لم أجد أي فائدة لها مطلقًا.

إذن السؤال:هل سبق لأي شخص استخدام الفرز القريب في الممارسة العملية؟إذا كان الأمر كذلك في أي نوع من التطبيقات؟هل يمكنك التفكير في حالة استخدام يكون فيها الفرز القريب هو الشيء الصحيح الذي ينبغي عمله؟

Answer 1

هناك الكثير من الاستدلالات "الجشعة" حيث تقوم بشكل دوري بتحديد الحد الأدنى للمجموعة.إن الاستدلال الجشع ليس مثاليًا، لذلك حتى إذا اخترت الحد الأدنى، فلن نضمن لك الوصول إلى أفضل إجابة نهائية.في الواقع، فإن يمسك الاستدلال الفوقي، أنت تقوم عن عمد بإدخال خطأ عشوائي حتى تحصل على حلول نهائية متعددة واختيار أفضلها.في هذه الحالة، فإن إدخال بعض الأخطاء في روتين الفرز الخاص بك مقابل السرعة سيكون بمثابة مقايضة جيدة.

Answer 2

يعد هذا تخمينًا سريعًا تمامًا، ولكن نظرًا للذاتية المتأصلة في مقاييس "الملاءمة" عند فرز نتائج البحث، فأنا أجرؤ على أنه لا يهم حقًا ما إذا تم فرزها بشكل مثالي أم لا.ويمكن قول الشيء نفسه عن التوصيات.إذا كان بإمكانك بطريقة ما ترتيب أن كل جزء آخر من الخوارزمية الخاصة بك لهذه الأشياء هو O(n)، فقد تتطلع إلى تجنب هذا النوع.

كن على علم أيضًا أنه في أسوأ الحالات، تكون بياناتك "مرتبة تقريبًا". لا تعرف على إحدى الأفكار البديهية المحتملة لـ "مصنف تقريبًا"، وهي أنه لا يحتوي إلا على عدد صغير من الانقلابات.والسبب في ذلك هو أنه إذا كانت بياناتك تحتوي فقط على انقلابات O(n)، فيمكنك إنهاء فرزها في وقت O(n) باستخدام فرز الإدراج أو فرز الكوكتيل (أي فرز الكوكتيل).نوع الفقاعة في الاتجاهين).ويترتب على ذلك أنه لا يمكن أن تكون قد وصلت إلى هذه النقطة من دون فرز كامل، في زمن O(n) (باستخدام المقارنات).لذا، فأنت تبحث عن تطبيقات حيث يتم فرز أغلبية مجموعة فرعية من البيانات ويتم توزيع الباقي، لا للتطبيقات التي تتطلب أن يكون كل عنصر قريبًا من موضعه الصحيح.

Answer 3

مجرد تخمين هنا، ولكن الشيء الوحيد الذي أتخيله هو تحسين استعلام قاعدة البيانات.

يجب ترجمة استعلام قاعدة البيانات بلغة تعريفية مثل SQL إلى برنامج خطوة بخطوة يسمى "خطة التنفيذ".يمكن عادةً ترجمة استعلام SQL واحد إلى عدد من خطط التنفيذ هذه، والتي تعطي جميعها نفس النتيجة ولكن يمكن أن يكون لها أداء مختلف جدًا.يجب على مُحسِّن الاستعلام العثور على أسرع واحد، أو على الأقل واحد سريع بشكل معقول.

لدى مُحسِّني الاستعلامات المستندة إلى التكلفة "وظيفة التكلفة"، التي يستخدمونها لتقدير وقت تنفيذ خطة معينة.يقوم المحسنون الشاملون بمراجعة جميع الخطط الممكنة (للحصول على قيمة معينة من "كل ما هو ممكن") واختيار أسرعها.بالنسبة للاستعلامات المعقدة، قد يكون عدد الخطط المحتملة كبيرًا للغاية، مما يؤدي إلى أوقات تحسين طويلة للغاية (حتى قبل أن تبدأ البحث في قاعدة البيانات!) لذلك هناك أيضًا أدوات تحسين غير شاملة.إنهم ينظرون فقط إلى بعض الخطط، وربما مع عنصر عشوائي في اختيار أي منها.ينجح هذا الأمر، نظرًا لوجود عدد كبير من الخطط "الجيدة" عادةً، وقد لا يكون من المهم العثور على أفضلها على الإطلاق -- ربما يكون من الأفضل اختيار خطة مدتها 5 ثوانٍ بدلاً من الخطة المثالية التي مدتها ثانيتان ، إذا كان الأمر يتطلب عدة دقائق من التحسين للعثور على خطة الثواني.

تستخدم بعض خوارزميات التحسين قائمة انتظار مرتبة من الخطط "الواعدة" (الجزئية).إذا لم يكن من المهم حقًا العثور على أفضل خطة على الإطلاق، فربما يمكنك استخدام قائمة انتظار مرتبة تقريبًا؟

هناك فكرة أخرى (وما زلت أتكهن فقط) وهي جدولة العمليات أو سلاسل الرسائل في نظام مشاركة الوقت، حيث قد لا يكون من المهم أن تحصل عملية أو خيط معين على مهلة زمنية متأخرة ببضعة مللي ثانية عما إذا تم فرزها بشكل صارم حسب الأولوية .

Answer 4

أحد التطبيقات الشائعة للفرز القريب هو عندما يقوم أحد الأشخاص بإجراء المقارنة الزوجية ولا ترغب في طرح العديد من الأسئلة عليه.

لنفترض أن لديك الكثير من العناصر التي ترغب في أن يقوم الإنسان بفرزها من خلال المقارنة الزوجية.يمكنك تقليل عدد المقارنات التي تحتاج إلى إجرائها بشكل كبير إذا كنت على استعداد لقبول أن الترتيب لن يكون دقيقًا.ربما، على سبيل المثال، لا تهتم إذا تم تبديل العناصر المجاورة طالما أن العناصر المفضلة موجودة في الأعلى.

Answer 5

في أى مكان

1. من المفترض أن تتفاعل بسرعة،
2. أنت لا تعد العميل بالسلوك الدقيق،
3. ولكن داخليا لديك بعض القواعد

يمكنك استخدامها.ماذا عن قائمة انتظار الأولوية "غير الصارمة" القائمة على القواعد؟أين سيكون ذلك مفيدا؟ربما موضوع/عملية/جدولة الموارد.في جدولة سلسلة المحادثات/العمليات، لا تعد حقًا بأن أي سلسلة رسائل واحدة ستنتقل أولاً أو ثانيًا أو أخيرًا، ولكن بشكل عام تريد منح الجميع بعض الفرص.قد ترغب في فرض قاعدة فضفاضة بحيث تكون وقائية، وذات أولوية، بلابلا..

مثال جدول الموارد هو الاستجابة لتوصيل البيتزا أو شحن صناديق الكتب للأشخاص وما إلى ذلك.لا يمكنك استخدامه عندما تكون النتيجة حتمية متوقعة، ولكن هناك الكثير من الأمثلة في الحياة الواقعية حيث لا تكون الأمور حتمية/قابلة للتنبؤ بها.

Answer 6

O(n log n) سريع جدًا بالفعل.لا أعتقد أن أي شخص سيفعل ذلك على الإطلاق ابدأ باستخدام خوارزمية الفرز القريب.ستبدأ باستخدام تعليمات برمجية تقوم بفرز كامل (نظرًا لأن لغة البرمجة التي تختارها من المحتمل أن توفر ملف sort وظيفة وليس أ nearsort وظيفة)، وعندما وجدت تجريبيا أن هذا النوع يستغرق وقتا طويلا، سوف تبدأ في التساؤل عما إذا كانت بياناتك حقًا يجب أن يتم فرزها بالكامل، وفكر في استخدام الفرز القريب.

في الأساس، لن تفكر مطلقًا في استخدام الفرز القريب إلا إذا اكتشفت أولًا أن الفرز يمثل عنق الزجاجة الشديد في برنامجك.