هل timsort للأغراض العامة أم خاص ببايثون؟
https://stackoverflow.com/questions/154504
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
Timsort هو نظام متكيف ومستقر دمج طبيعي.لديها خارق للطبيعة الأداء على أنواع كثيرة من جزئيًا المصفوفات المطلوبة (أقل من lg (N!) المقارنات اللازمة ، وعدد قليل من N-1) ، ولكن بنفس سرعة بايثون السابقة عينات مختلطة منفردة عالية المصفوفات العشوائية.
هل شاهدت timsort مستخدمة خارج CPython؟هل يعقل؟
المحلول
نعم ، من المنطقي استخدام timsort خارج CPython ، بشكل خاص ، أو Python بشكل عام.
تُبذل حاليًا جهد جارٍ لاستبدال "الدمج المعدل لجافا"Sort "مع timsort ، والنتائج الأولية إيجابية تمامًا.
نصائح أخرى
تعتبر الخوارزمية عامة جدًا ، لكن الفوائد خاصة ببايثون.على عكس معظم إجراءات الفرز ، فإن ما تهتم به قائمة Python (وهو ما يستخدم timsort) هو تجنب المقارنات غير الضرورية ، لأن المقارنات عمومًا تكون كثيرًا أكثر تكلفة من تبديل العناصر (والتي تكون دائمًا مجرد مجموعة مننسخ المؤشر) أو حتى تخصيص بعض الذاكرة الإضافية (لأنها دائمًا مجرد مصفوفة من المؤشرات ، والحمل صغير مقارنة بمتوسط الحمل في أي عملية بايثون.)
إذا كنت تخضع لقيود مماثلة ، فقد يكون ذلك مناسبًا.لم أر حتى الآن أي حالة أخرى تكون فيها المقارنات باهظة الثمن حقًا ، على الرغم من :-)
لا يبدو الأمر مألوفًا بشكل خاص ، ولكن عمليات الدمج "الذكية" شائعة جدًا في عالم البرامج الواسع.
فيما يتعلق بما إذا كان الأمر منطقيًا ، فهذا يعتمد على ما تقوم بفرزه والتكلفة النسبية للمقارنات مقابل تخصيص الذاكرة.لن يكون النوع الذي يتطلب 2 * N بايت من الذاكرة الإضافية خيارًا جيدًا في بيئة مقيدة بالذاكرة.
تمت الإجابة عليه الآن على Wikipedia : سيتم استخدام timsort في Java 7 الذين قاموا بنسخه من Android.
يتوفر Timsort أيضًا في Android الآن: http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort
يبدو الوصف الذي ربطته عامًا تمامًا.
