خوارزمية لتصنيف رتابة صفيف (أي الحكم على "فرز" صفيف)

Question

---

تعديل: واو ، العديد من الردود العظيمة. نعم ، أنا أستخدم هذا كدالة للياقة البدنية للحكم على جودة النوع الذي تقوم به خوارزمية وراثية. لذا فإن تكلفة التقييم مهمة (أي ، يجب أن تكون سريعة ، ويفضل O(n).)

---

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

public double monotonicity(int[] array) {
    if (array.length == 0) return 1d;

    int longestRun = longestSortedRun(array);
    return (double) longestRun / (double) array.length;
}

public int longestSortedRun(int[] array) {

    if (array.length == 0) return 0;

    int longestRun = 1;
    int currentRun = 1;

    for (int i = 1; i < array.length; i++) {
        if (array[i] >= array[i - 1]) {
            currentRun++;
        } else {
            currentRun = 1;
        }

        if (currentRun > longestRun) longestRun = currentRun;
    }

    return longestRun;
}

هذه بداية جيدة ، لكنها تفشل في مراعاة احتمال وجود "كتل" من التسلسلات الفرعية المصنفة. على سبيل المثال:

{ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9}

يتم تقسيم هذه الصفيف إلى ثلاثة متسلسلات فرعية مرتبة. ستقوم الخوارزمية بتقييمها على أنها 40 ٪ فقط ، ولكن بشكل حدسي ، يجب أن تحصل على درجة أعلى من ذلك. هل هناك خوارزمية قياسية لهذا النوع من الأشياء؟

Answer 1

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

Answer 2

هذا يبدو وكأنه مرشح جيد ل ليفنشتين دامراو - ليفينشتين المسافة - عدد المقايضات اللازمة لفرز الصفيف. يجب أن يكون هذا يتناسب مع مدى بقاء كل عنصر من المكان الذي يجب أن يكون فيه في صفيف فرز.

إليك خوارزمية روبي بسيطة تلخص مربعات المسافات. يبدو أنه مقياس جيد للفرز-تصبح النتيجة أصغر في كل مرة يتم فيها تبديل عنصرين خارج الترتيب.

ap = a.sort
sum = 0
a.each_index{|i| j = ap.index(a[i])-i 
  sum += (j*j)
}
dist = sum/(a.size*a.size)

Answer 3

شيء مثل هؤلاء؟ http://en.wikipedia.org/wiki/rank_correlation

Answer 4

هذا واحد قمت للتو بتكوينه.

لكل زوج من القيم المجاورة ، احسب الفرق الرقمي بينهما. إذا كان الثاني أكبر من أو يساوي الأول ، أضف ذلك إلى sorted المجموع ، وإلا إضافة إلى unsorted المجموع. عند الانتهاء ، خذ نسبة الاثنين.

Answer 5

حساب lenghts من جميع التسلسلات الفرعية المصنفة ، ثم قم بربطها وإضافتها. إذا كنت ترغب في معايرة مقدار ما تضعه في أكبر قدرات ، فاستخدم قوة مختلفة عن 2.

لست متأكدًا ما هي أفضل طريقة لتطبيع هذا حسب الطول ، وربما أقسمه لكل طول مربع؟

Answer 6

ما الذي تبحث عنه هو كيندال تاو. إنها وظيفة فردية من مسافة فرز الفقاعة بين صفيفتين. لاختبار ما إذا كانت الصفيف "مصنفة تقريبًا" ، احسب كيندال تاو مقابل صفيف فرز.

Answer 7

أود أن أقترح النظر في مشكلة الفطيرة ومسافة الانعكاس من التباديل. غالبًا ما تستخدم هذه الخوارزميات للعثور على المسافة بين التباديل (الهوية والسلسلة المتكهبة). يجب أن يأخذ هذا المقياس المسافة في الاعتبار المزيد من الكتل من قيم الترتيب ، وكذلك الانعكاسات (تناقص رتابة بدلاً من زيادة التسلسل). هناك أيضا التقديرات التي هي وقت متعدد الحدود [PDF.

كل هذا يتوقف حقًا على معنى العدد وإذا كانت وظيفة المسافة هذه منطقية في سياقك.

Answer 8

لدي نفس المشكلة (تسجيل الرتابة) ، وأقترح عليك المحاولة أطول زيادة بعد. تعمل الخوارزمية الأكثر كفاءة في O(n log n), ، لا باس به.

أخذ مثال من السؤال ، أطول تسلسل متزايد من {4, 5, 6, 0, 1, 2, 3, 7, 8, 9} هو {0, 1, 2, 3, 7, 8, 9} (طول 7). ربما يكون معدل أفضل (70 ٪) من خوارزمية الأطول التي تديرها.

Answer 9

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

Answer 10

بعض التجارب مع تعديل راتكليف و Obershelp

>>> from difflib import SequenceMatcher as sm
>>> a = [ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9 ]
>>> c = [ 0, 1, 9, 2, 8, 3, 6, 4, 7, 5 ]
>>> b = [ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9 ]
>>> b.sort()
>>> s = sm(None, a, b)
>>> s.ratio()
0.69999999999999996
>>> s2 = sm(None, c, b)
>>> s2.ratio()
0.29999999999999999

لذلك نوع من يفعل ما تحتاج إليه. لست متأكدًا جدًا من كيفية إثبات ذلك.

Answer 11

ماذا عن حساب عدد الخطوات ذات القيمة المتزايدة مقابل عدد الخطوات الإجمالية. هذا O(n).