أسرع طريقة فرز الإدخالات من "سلس" 2D array

Question

ما هي أسرع طريقة فرز القيم في سلسة 2D المصفوفة ؟

مدخل صغير تصفية الصورة:

• حوالي 60 80 بكسل
• قناة واحدة
• مفردة أو مزدوجة الدقة تطفو
• الصف التخزين الرئيسية ، متتابعة في الذاكرة
• قيم مختلطة التوقيع
• piecewise "السلس" ، مع المناطق على أمر من 10 بكسل

الإخراج هو شقة (حوالي 4800 قيمة) مجموعة من فرز القيم جنبا إلى جنب مع مؤشرات فرز مجموعة الأصلي.

Answer 1

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

On random images...
quicksort took 0.000153 seconds per image.
mergesort took 0.000170 seconds per image.
heapsort took 0.000241 seconds per image.
On real images...
quicksort took 0.000136 seconds per image.
mergesort took 0.000143 seconds per image.
heapsort took 0.000230 seconds per image.

جميع خوارزميات يبدو أن تستفيد من القائمة جزئية يأمر خاصة فرز سريع.Numpy لا يبدو أن لديها قائمة تم فرزها دمج وظيفة, لذلك لا أستطيع أن حاول قبل فرز الصفوف ، للأسف.

Answer 2

أتوقع أن يفوز Timsort بهذا لأنه يستفيد من "التشغيل" في البيانات.

عادةً ما تكون Quicksort سريعة ولكن هناك خطر من أن تصل إلى سيناريو أسوأ الحالات. على سبيل المثال ، بعض إصدارات QuickShort هي O (n^2) عند إعطائها إدخال تم فرزها بالفعل. التي لن تكون ودية للغاية إذا أعطاك شخص ما النوع الخاطئ من الصورة المليئة بالتدرج ......

إليك فكرة مجنونة قليلاً - قد تجرب أيضًا تمريرة Z (رابط ويكيبيديا) والتي يمكن أن تمكنك من الاستفادة من الألوان المماثلة المجاورة في كلا البعدين.

Answer 3

سأبدأ مع Quicksort في مكان. تكون مقارنات النقاط العائمة سريعة على معظم المعالجات (بالتأكيد أسرع بكثير من التخصيص اللازم لدمج ايمارات).

Answer 4

هناك Timsort ، لكنني رأيت في العديد من الأماكن أنه مخصص للتطبيقات مع المقارنات البطيئة ؛ يبدو أن Devs Numpy قرروا عدم أن يزعجوا تنفيذها:

http://mail.scipy.org/pipermail/scipy-dev/2009-may/011929.html

Answer 5

يمكن للمرء دمج الصفوف بشكل فردي ، ثم دمج الصفوف المرتبة.

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