الفرز فقط باستخدام المشغل الأقل من
-
24-09-2019 - |
سؤال
في C ++/STL ، يتم فرز باستخدام المشغل الأقل من فقط. ليس لدي أي فكرة عن كيفية تنفيذ خوارزميات الفرز بالفعل ، أفترض أن العمليات الأخرى يتم إنشاؤها ضمنية:
a > b *equals* b < a == true
a == b *equals* !(a < b) && !(b < a)
مقارنة باستخدام وظيفة Trivalue* المقارنة ، مثل Java على سبيل المثال ، هل هذا جيد للأداء ، أو لماذا تم اتخاذ قرار التصميم هذا؟
افتراضي هو أن أي وظيفة المقارنة Trivalue لا تزال يجب أن تنفذ هذه المقارنة في حد ذاتها ، مما يؤدي إلى نفس الأداء.
** بواسطة Trivalue مقارنة الوظيفة ، أعني دالة المقارنة التي تُرجع -1 و 0 و 1 لأقل من ، متساوية وأعلى من*
تحديث:يبدو سفينة فضائية <=>
يأتي المشغل في C ++ 20 ، لذا من الواضح أن اللجنة اعتقدت أن هناك جوانب سلبية لاستخدامها فقط operator<
.
المحلول
إلى حد ما ، فإن الاثنين الأخريين ضمنين ، ولكن أكثر دقة هو القول إن نوع المقارنة ليس في الواقع بحاجة إلى يتم تنفيذ مقارنات Tri-valued ، ويتم تنفيذ أنواع C ++ بطريقة لا تستخدم واحدة من أجل تقليل السلوك المطلوب للمقارنة.
سيكون من الخطأ أن تحدد STD :: SORTS واستخدامها بشكل حصري لشيء مثل هذا:
template <typename T, typename Cmp>
int get_tri_value(const T &a, const T &b, Cmp lessthan) {
if (lessthan(a,b)) return -1;
if (lessthan(b,a)) return 1;
return 0;
}
... لأنك ستنتهي بخوارزمية غير فعالة من حيث عدد المكالمات lessthan
. إذا لم تفعل الخوارزمية أي شيء مفيد مع الفرق بين عودة 1 وعودة 0 ، فأنت تضيع مقارنة.
يشير C ++ إلى "أوامر ضعف صارمة". إذا <
هو ترتيب ضعيف صارم ، و !(a < b) && !(b < a)
, ، لا بالضرورة يتبع ذلك a == b
. إنهم فقط "في نفس المكان" في الطلب ، و !(a < b) && !(b < a)
هي علاقة معادلة. لذلك المقارنة المطلوبة بواسطة sort
الطلب #٪ s فئات التكافؤ من الكائنات ، لا يوفر ترتيبًا كليًا.
الفرق الوحيد الذي يحدثه هو ما تقوله عندما !(a < b)
. للحصول على ترتيب إجمالي صارم ، سوف تستنتج b <= a
, ، اقرأ "أقل من أو يساوي". للحصول على ترتيب ضعيف صارم ، لا يمكنك تحديد b <= a
ليعني b < a || b == a
وهل هذا صحيح. C ++ محسّن حول هذا ، ولأنه يتيح للمشغل الزائد ، يجب أن يكون ذلك إلى حد كبير ، نظرًا لأن المشغلين الزائدين الذين يحتاجون إلى المصطلحات من أجل إخبار المستخدمين برمزهم ما يمكن أن يتوقعوه من حيث ارتباط المشغلين. تتحدث Java عن المقارنة وتوافق الرمز المتسق مع متساوين ، وهو كل ما تحتاجه. يجب أن يتعامل C ++ مع <،> ، == ، <= ،> = ، ما بعد التعيين ، وما إلى ذلك.
C ++ يأخذ نهجًا رياضيًا نقيًا لهذا في API ، لذلك يتم تعريف كل شيء من حيث العلاقة الثنائية الوحيدة. جافا أكثر ودية في بعض النواحي ، ويفضل المقارنات ثلاثية الاتجاه حيث يكون تعريف الوحدة الأساسية (المقارنة) أكثر تعقيدًا قليلاً ، لكن المنطق الذي يؤدي منه أبسط. وهذا يعني أيضًا أن خوارزمية الفرز تحصل على مزيد من المعلومات في المقارنة ، وهو أمر مفيد أحيانًا. على سبيل المثال ، راجع تحسين "العلم الهولندي" Quicksort ، وهو فائدة عندما يكون هناك الكثير من "في نفس المكان" يكرر في البيانات.
في هذه الحالة ، فإن المقارنة بين ثلاث قيم هي زيادة السرعة. لكن C ++ يستخدم تعريفًا ثابتًا لمقارن للفرز وأيضًا ل set
و map
, lower_bound
وهلم جرا ، والذي بالكاد يستفيد من مقارن ثلاث قيمة (ربما حفظ مقارنة واحدة ، ربما لا). أعتقد أنهم قرروا عدم تعقيد الواجهة العامة اللطيفة والمصالح لصالح مكاسب محتملة أو محدودة الكفاءة.
نصائح أخرى
تخميني في C ++ تم القيام به فقط لتقليل تكرار التعليمات البرمجية: بمجرد تحديد مقارن OP على فئة/نوع ، لا يمكنك فقط مقارنة هذه الكائنات عن طريق كتابة <B ، ولكن أيضًا الحصول على القدرة على فرز مجموعات من مثل هذه الأشياء.
أما بالنسبة للفرز ، فنحن بحاجة فقط إلى مشغل أقل من ذلك ، لماذا تقديم أشياء إضافية؟ قون
إذا كنت تشير إلى STD :: SORT () ، فإن استخدامها أقل () لا يحتاج إلى الحفاظ على الطلب النسبي للعنصر المكافئ ، لذلك سيحتاج إلى مشغل أقل () ، ومشغل أكبر ضمنيًا.
في حين أن STD :: STABLE_SORT ستحافظ عليها ، لكنها أبطأ. إنها تحتاج إلى أقل () مشغل وتكرار ثنائي الاتجاه في مقابل مشغل متساوٍ () لبناء وظيفة "Trivalue" مقارنة