بعض أسئلة الفرز

Question

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

1. أحد الأنواع التي كنت أقارنها بـ Quicksort هي STD :: SORT من مكتبة C ++ القياسية. ومع ذلك ، يبدو أنه بطيء للغاية. أنا فقط أقوم بفرز المصفوفات من ints و longs ، لكن يبدو أن حوالي 8-10 مرات أبطأ من كل من Quicksort و Quicksort القياسي من قبل Bentley و McIlroy (وربما Sedgewick). هل لدى أي شخص أي أفكار حول سبب كونها بطيئة جدًا؟ الرمز الذي أستخدمه لهذا النوع هو مجرد std :: sort (a ، a+numelem) ؛ حيث A هي مجموعة من longs أو ints و numelem هي عدد العناصر في الصفيف. الأرقام عشوائية للغاية ، وقد جربت أحجام مختلفة بالإضافة إلى كميات مختلفة من العناصر المتكررة. لقد جربت QSort أيضًا ، لكن الأمر أسوأ كما كنت أتوقع. تحرير: تجاهل هذا السؤال الأول - تم حله.

2. أرغب في العثور على المزيد من تطبيقات Quicksort الجيدة للمقارنة مع Quicksort. حتى الآن لديّ Bentley-Mcilroy ، وقمت أيضًا بمقارنة مع أول نسخة منشورة من Vladimir Yaroslavskiy Quicksort المزدوجة. بالإضافة إلى ذلك ، أخطط لتنظيف Timsort (وهو نوع دمج أعتقد) و Quicksort المزدوج المحسّن من مصدر JDK 7. ما هي تطبيقات Quicksorts الجيدة الأخرى التي تعرفها؟ إذا لم تكن موجودة في C أو C ++ ، فقد يكون ذلك على ما يرام لأنني جيد في النقل ، لكنني أفضل منها C أو C ++ إذا كنت تعرفها.

3. كيف تنصح بالخروج من كلمة الإضافات إلى Quicksort؟ حتى الآن ، يبدو أن الرشق السريع الخاص بي أسرع بكثير من جميع الأدوات السريعة الأخرى التي اختبرتها ضدها. المصدر الرئيسي لسرعته هو أنه يتعامل مع العناصر المتكررة بشكل أكثر كفاءة من الطرق الأخرى التي وجدتها. إنه يزيل أسوأ سلوك الحالة بشكل كامل دون إضافة الكثير من الوقت في التحقق من العناصر المتكررة. لقد نشرت حول هذا الموضوع في منتديات Java ، لكن لم تحصل على أي رد. حاولت أيضًا الكتابة إلى جون بنتلي لأنه كان يعمل مع فلاديمير على سكونه السريع المزدوج ولم يحصل على أي رد (على الرغم من أنني لم أكن مندهشًا من هذا). هل يجب أن أكتب ورقة عنها ووضعها على arxiv.org؟ هل يجب أن أنشر في بعض المنتديات؟ هل هناك بعض القوائم البريدية التي يجب أن أنشرها؟ لقد كنت أعمل على هذا لبعض الوقت الآن وطريقتي شرعية. لدي بعض الخبرة في نشر الأبحاث لأنني مرشح الدكتوراه في الفيزياء الحسابية. هل يجب أن أحاول التعامل مع شخص ما في قسم علوم الكمبيوتر في جامعتي؟ بالمناسبة ، قمت أيضًا بتطوير Quicksort Dual-Pivot Dual ، لكنه ليس أفضل من Quicksort أحادي المركز (على الرغم من أنه أفضل من Quicksort المزدوج المزدوج في فلاديمير مع بعض مجموعات البيانات).

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

Answer 1

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

Answer 2

إذا كنت قد حققت حقًا اختراقًا ولديك الرياضيات لإثبات ذلك ، فيجب أن تحاول نشرها في مجلة ACM. إنها بالتأكيد واحدة من المجلات الأكثر شهرة لعلوم الكمبيوتر.

ثاني الأفضل سيكون أحد مجلات IEEE مثل المعاملات على هندسة البرمجيات.