javascript - ترجمه - sort() python




الفرز بلغة JavaScript: ألا يعد إرجاع كلمة منطقية كافياً لوظيفة مقارنة؟ (2)

TL، DR

لقد نجحت في فرز مصفوفاتي على هذا النحو

لا ، لم تفعل. ولم ألاحظ ذلك. معاكس سريع:

> [1,1,0,2].sort(function(a, b){ return a>b })
Array [0, 1, 2, 1]
// in Opera 12. Results may vary between sorting algorithm implementations

لماذا ا؟

لأن دالة المقارنة الخاصة بك تقوم بإرجاع false (أو 0 ، مكافئ) حتى عندما تكون b أكبر من a . ولكن يشير 0 إلى أن العنصرين يعتبران متساويين - وتعتقد خوارزمية الفرز ذلك.

في العمق التفسير

وظائف مقارنة في جافا سكريبت

كيف تعمل وظائف المقارنة؟

يمكن أن تأخذ طريقة Array::sort دالة مقارنة اختيارية مخصصة كوسيطة لها. تأخذ هذه الدالة وسيطتين (يشار إليهما بشكل عام بـ " a و " b ) والتي يجب مقارنتها ، ومن المفترض أن تقوم بإرجاع رقم

  • > 0 عندما يعتبر a أكبر من b ويجب أن يتم فرزه بعد ذلك
  • == 0 عندما يعتبر a يساوي b ولا يهم أيهما يأتي أولاً
  • < 0 عندما يعتبر أصغر من b ويجب أن يتم فرزه قبله

إذا لم يقم بإرجاع رقم ، فسيتم إرسال النتيجة إلى رقم (وهو مفيد للبلويات). لا يلزم أن يكون الرقم الذي تم إرجاعه هو بالضبط -1 أو 0 أو 1 (على الرغم من أنه عادة ما يكون).

ترتيب متسق

لتكون متسقة ، سوف تحتاج الدالة مقارنة لتحقيق المعادلة

comp(a, b) == -1 * comp(b, a)
// or, if values other than -1, 0 and 1 are considered:
comp(a, b) * comp(b, a) <= 0

إذا كان هذا الشرط معطلاً ، فسيتصرف هذا السلوك غير محدد.

نقلا عن مواصفات ES5.1 على sort (نفس الشيء في مواصفات ES6 ):

إذا كانت comparefn […] ليست دالة مقارنة متناسقة لعناصر هذه الصفيف ، فإن سلوك الفرز يكون محددًا بالتنفيذ.

دالة comparefn هي دالة مقارنة متسقة لمجموعة من القيم S إذا تم استيفاء جميع المتطلبات الواردة أدناه لجميع القيم a و b و c (من المحتمل أن تكون نفس القيمة) في المجموعة S : الترميز a <CF b means comparefn(a,b) < 0 ؛ a =CF b means comparefn(a,b) = 0 (of a sign)؛ و a >CF b تعني comparefn(a,b) > 0 .

يؤدي استدعاء comparefn(a,b) دائمًا إلى إرجاع القيمة نفسها v عند إعطاء زوج معين من القيم a و b comparefn(a,b) لها. علاوة على ذلك ، Type(v) هو Number ، و v ليس NaN . لاحظ أن هذا يعني أن واحدًا بالضبط من a <CF b و a =CF b و a >CF b سيكون صحيحًا لزوج معين من a و b .

  • لا يؤدي استدعاء comparefn(a,b) تعديل هذا الكائن.
  • a =CF a ( reflexivity )
  • إذا كانت a =CF b ، ثم b =CF a ( symmetry )
  • إذا كانت a =CF b و b =CF c ، فإن a =CF c ( transitivity =CF )
  • إذا كانت a <CF b و b <CF c ، فإن a <CF c (العبور لـ <CF )
  • إذا كانت a >CF b و b >CF c ، فإن a >CF c (العبور لـ >CF )

ملاحظة: الشروط المذكورة أعلاه ضرورية وكافية للتأكد من أن comparefn المجموعة S في فئتي التكافؤ وبأن فئات التكافؤ هذه مرتبة بالكامل.

ماذا يعني هذا؟ لماذا يجب أن أهتم؟

تحتاج خوارزمية الفرز لمقارنة عناصر المصفوفة مع بعضها البعض. للقيام بعمل جيد وفعال ، يجب ألا تحتاج إلى مقارنة كل عنصر مع بعضها البعض ، ولكن يجب أن تكون قادراً على التفكير في طلبها. لكي يعمل هذا بشكل جيد ، هناك بعض القواعد التي يجب أن تلتزم بها وظيفة المقارنة المخصصة. واحد تافه هو أن عنصر يساوي نفسه ( compare(a, a) == 0 ) - هذا هو العنصر الأول في القائمة أعلاه (انعكاسي). نعم ، هذا شيء رياضي ، لكنه جيد.

أهم واحد هو العبور. حيث يقول أنه عندما قارنت الخوارزمية بين قيمتين a و b ، وكذلك b مع c ، ووجدت من خلال تطبيق دالة المقارنة على سبيل المثال a = b و b < c ، عندئذ يمكن أن تتوقع أن a < c يحمل كذلك . يبدو هذا منطقيًا فقط ، وهو مطلوب للحصول على طلب محدد ومتناسق جيدًا.

لكن وظيفة المقارنة الخاصة بك لا تفشل . دعونا ننظر في هذا المثال:

 function compare(a, b) { return Number(a > b); }
 compare(0, 2) == 0 // ah, 2 and 0 are equal
 compare(1, 0) == 1 // ah, 1 is larger than 0
 // let's conclude: 1 is also larger than 2

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

لماذا الحل الخاطئ شائع؟

لأنه في العديد من اللغات الأخرى ، هناك خوارزميات الفرز التي لا تتوقع مقارنة ثلاثية ولكن مجرد عامل منطقي أصغر من المشغل. C ++ std::sort مثال جيد على ذلك. سيتم تطبيقه مرتين فقط مع الحجج المبادلة إذا كان لا بد من تحديد المساواة. من المسلم به أن هذا يمكن أن يكون أكثر كفاءة وأقل عرضة للخطأ ، ولكنه يحتاج إلى المزيد من المكالمات إلى وظيفة المقارنة إذا كان المشغل غير قابل للتحديد.

المعاكسة

لقد اختبرت وظيفة المقارنة الخاصة بي ، وهي تعمل!

فقط بالحظ المطلق ، إذا حاولت بعض الأمثلة العشوائية. أو لأن مجموعة الاختبار لديك معيبة - غير صحيحة و / أو غير كاملة.

في ما يلي النص البرمجي الصغير الذي اعتدت على العثور عليه في المثال المقابل الأدنى:

function perms(n, i, arr, cb) {
// calls callback with all possible arrays of length n
    if (i >= n) return cb(arr);
    for (var j=0; j<n; j++) {
        arr[i] = j;
        perms(n, i+1, arr, cb);
    }
}
for (var i=2; ; i++) // infinite loop
    perms(i, 0, [], function(a) {
        if (    a.slice().sort(function(a,b){ return a>b }).toString()
             != a.slice().sort(function(a,b){ return a-b }).toString() )
            // you can also console.log() all of them, but remove the loop!
            throw a.toString();
    });

ما وظيفة المقارنة صحيحة؟

لا تستخدم وظيفة المقارنة على الإطلاق ، عندما تريد نوع معجم. سيتم توحيد العناصر في المصفوفة إذا لزم الأمر.

يمكن تنفيذ وظيفة المقارنة العامة التي تعمل مثل مشغلي العلاقات

function(a, b) {
    if (a > b) return 1;
    if (a < b) return -1;
    /* else */ return 0;
}

باستخدام بعض الحيل ، يمكن تقليل هذا إلى function(a,b){return +(a>b)||-(a<b)} المكافئة function(a,b){return +(a>b)||-(a<b)} .

بالنسبة إلى الأرقام ، يمكنك ببساطة إرجاع الفرق الذي يلتزم بجميع القوانين أعلاه:

function(a, b) {
    return a - b; // but make sure only numbers are passed (to avoid NaN)
}

إذا كنت تريد الترتيب في الاتجاه المعاكس ، فخذي الخيار المناسب وقم بتبديل النقطة b .

إذا كنت ترغب في فرز أنواع مركبة (كائنات إلخ) ، فاستبدل كل منها b a و ( b مع الوصول إلى الخصائص المعنية ، أو استدعاء طريقة أو ما تريد الفرز حسبه.

لقد نجحت في فرز مصفوفاتي مثل هذا (عندما لم أكن أرغب في ترتيب المعاجم المعياري):

var arr = […] // some numbers or so
arr.sort(function(a, b) {
    return a > b;
});

الآن ، قال لي أحدهم إن هذا خطأ ، وأنني سأحتاج إلى return ab بدلاً من ذلك. هل هذا صحيح ، وإذا نعم ، لماذا؟ لقد اختبرت وظيفة المقارنة الخاصة بي ، وهي تعمل! أيضا ، لماذا يكون حل بلدي شائع جدا عندما يكون خطأ؟


تتوقع دالة sort دالة تتوقع وسيطين ( a و ( b ، ثم ترجع:

  • رقم سالب إذا أتى قبل b
  • رقم موجب إذا جاء بعد b
  • صفر إذا كان الأمر النسبي من أ و ب لا يهم

من أجل فرز الأرقام بترتيب تصاعدي return a - b ستقوم بإنتاج قيم الإرجاع الصحيحة؛ فمثلا:

a    b    ret
1    2    -1
3    2     1
2    2     0

من ناحية أخرى ، يُرجع return a > b قيم الإرجاع التالية:

a    b    ret      implied
1    2    false    0
3    2    true     1
2    2    false    0

في المثال أعلاه ، يتم إخبار دالة الفرز أن 1 و 2 هما نفس الشيء (ولا يهم وضع 1 قبل 2 أو 2 قبل 1). سيؤدي هذا إلى نتائج غير صحيحة ، على سبيل المثال (في Chrome 49):

[5, 8, 7, 1, 2, 3, 4, 6, 9, 10, 11, 12, 13].sort(function(a, b) {
    return a > b;
});
// [4, 5, 3, 1, 2, 6, 7, 8, 9, 10, 11, 12, 13]




comparison