كيفية فرز المصفوفة التي تم فرزها تقريبًا في أسرع وقت ممكن؟(جافا)

Question

لدي مجموعة من القيم التي تم فرزها تقريبًا، ولكن لم يتم فرزها تمامًا، مع إزاحة عدد قليل من القيم (على سبيل المثال، 50 في 100000).كيفية فرزها بكفاءة أكبر؟(الأداء أمر بالغ الأهمية هنا ويجب أن يكون أسرع بكثير من O(N)).

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

Answer 1

في الواقع ، يحتوي ويكيبيديا على تطبيق Java لـ Smoothsort. يمكنك العثور عليها هنا:

http://en.wikipedia.org/wiki/smoothsort.

Answer 2

نوع الكوكتيل

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

Answer 3

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

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

1. ابحث عن جميع العناصر خارج الترتيب واستخراج القائمة الأصلية إلى قائمة منفصلة ، O (n)
2. والنتيجة هي قائمتان: قائمة مصنفة وقائمة قصيرة مستخرجة
3. لكل عنصر من العناصر المستخرجة ، أدخلها في القائمة المصنفة. سيكون ذلك O (log (n)) لكل منهما ، إجمالي هو o (xlog (n)) ، حيث x هو عدد العناصر المستخرجة. إذا كان X صغيرًا جدًا بالنسبة لـ N ، فسيكون ذلك بمجموع O (N).

Answer 4

هناك العديد من الخوارزميات الجيدة لهذا الغرض.

Smoothsort هو المفضل لدي ... لقد عملت بالفعل كل الرياضيات هنا إذا كنت فضوليًا لماذا يعمل بشكل جيد.

خوارزمية جيدة إلى حد ما للبيانات التي تم تصويرها بالفعل الاندماج الطبيعي, ، وهو إصدار من أسفل إلى أعلى من Mergesort يعمل عن طريق التعامل مع المدخلات كتسلسل من الفروع الفرعية ، ثم إجراء تمريرات متعددة على النطاق المدمج المجاورة. يتم تشغيله في وقت O (n) إذا تم فرز البيانات بالفعل (لأنه يمكن أن يكتشف أن هناك نطاقًا واحدًا فقط) ، و O (n lg n) في أسوأ الحالات. تعمل هذه الخوارزمية بشكل جيد إذا تم فرز البيانات "؛ أي أنه يتكون من الكثير من الكتل المصنفة الموضوعة بجوار بعضها البعض مباشرة.

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

Answer 5

Sun] JDK7 لديه (أو سيكون) تنفيذ من تيم فرز (من بيثون). إنه نوع دمج يستفيد من الترتيب الموجود بالفعل في الصفيف.

Answer 6

تعد Smoothsort أو Timsort خوارزميات رائعة ، وستكون أشياء معقولة للاستخدام.

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

Answer 7

فقط لوضعها على الطاولة ، سيكون من المؤكد أن خوارزمية الفقاعة التي تم تنفيذها جيدًا هي أبسط خوارزمية هنا. مع أسوأ حالة من O (n*m) ، M هو عدد النزوح. يعتمد الجزء M اعتمادًا كبيرًا على نمط النزوح ، وعادة ما يكون التعقيد الكلي O (N).

Answer 8

أنت محق في استحالة الوصول إلى O (n) ، ولكن بافتراض آلة متعددة النواة (التي لدي) ، يمكننا الغش قليلاً باستخدام خوارزمية فرز متوازية.

Answer 9

تنفيذ ما أسميناه في المدرسة أ نوع شل.هذا هو فرز المصفوفات الفرعية.المصفوفة الفرعية ذات الخطوة k هي مصفوفة من العناصر ذات المؤشرات 0، k، 2k، 3k...

إذا اخترت k = 3i+1، وقمت بإجراء عمليات فرز فقاعية متعددة، بدءًا من i-s الأعلى وصولاً إلى 0، فستكون الأوقات أصغر في المصفوفة التي تم فرزها تقريبًا.

Answer 10

هذا هو تطبيق Java الأصلي لـ SmoothSort الذي كان متاحًا عبر مقال ويكيبيديا.

// by keeping these constants, we can avoid the tiresome business
// of keeping track of Dijkstra's b and c. Instead of keeping
// b and c, I will keep an index into this array.

static final int LP[] = { 1, 1, 3, 5, 9, 15, 25, 41, 67, 109,
    177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891,
    35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457,
    1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703,
    48315633, 78176337, 126491971, 204668309, 331160281, 535828591,
    866988873 // the next number is > 31 bits.
};

public static <C extends Comparable<? super C>> void sort(C[] m,
    int lo, int hi) {
  int head = lo; // the offset of the first element of the prefix into m

  // These variables need a little explaining. If our string of heaps
  // is of length 38, then the heaps will be of size 25+9+3+1, which are
  // Leonardo numbers 6, 4, 2, 1. 
  // Turning this into a binary number, we get b01010110 = 0x56. We represent
  // this number as a pair of numbers by right-shifting all the zeros and 
  // storing the mantissa and exponent as "p" and "pshift".
  // This is handy, because the exponent is the index into L[] giving the
  // size of the rightmost heap, and because we can instantly find out if
  // the rightmost two heaps are consecutive Leonardo numbers by checking
  // (p&3)==3

  int p = 1; // the bitmap of the current standard concatenation >> pshift
  int pshift = 1;

  while (head < hi) {
    if ((p & 3) == 3) {
      // Add 1 by merging the first two blocks into a larger one.
      // The next Leonardo number is one bigger.
      sift(m, pshift, head);
      p >>>= 2;
      pshift += 2;
    } else {
      // adding a new block of length 1
      if (LP[pshift - 1] >= hi - head) {
        // this block is its final size.
        trinkle(m, p, pshift, head, false);
      } else {
        // this block will get merged. Just make it trusty.
        sift(m, pshift, head);
      }

      if (pshift == 1) {
        // LP[1] is being used, so we add use LP[0]
        p <<= 1;
        pshift--;
      } else {
        // shift out to position 1, add LP[1]
        p <<= (pshift - 1);
        pshift = 1;
      }
    }
    p |= 1;
    head++;
  }

  trinkle(m, p, pshift, head, false);

  while (pshift != 1 || p != 1) {
    if (pshift <= 1) {
      // block of length 1. No fiddling needed
      int trail = Integer.numberOfTrailingZeros(p & ~1);
      p >>>= trail;
      pshift += trail;
    } else {
      p <<= 2;
      p ^= 7;
      pshift -= 2;

      // This block gets broken into three bits. The rightmost
      // bit is a block of length 1. The left hand part is split into
      // two, a block of length LP[pshift+1] and one of LP[pshift].
      // Both these two are appropriately heapified, but the root
      // nodes are not necessarily in order. We therefore semitrinkle
      // both of them

      trinkle(m, p >>> 1, pshift + 1, head - LP[pshift] - 1, true);
      trinkle(m, p, pshift, head - 1, true);
    }

    head--;
  }
}

private static <C extends Comparable<? super C>> void sift(C[] m, int pshift,
    int head) {
  // we do not use Floyd's improvements to the heapsort sift, because we
  // are not doing what heapsort does - always moving nodes from near
  // the bottom of the tree to the root.

  C val = m[head];

  while (pshift > 1) {
    int rt = head - 1;
    int lf = head - 1 - LP[pshift - 2];

    if (val.compareTo(m[lf]) >= 0 && val.compareTo(m[rt]) >= 0)
      break;
    if (m[lf].compareTo(m[rt]) >= 0) {
      m[head] = m[lf];
      head = lf;
      pshift -= 1;
    } else {
      m[head] = m[rt];
      head = rt;
      pshift -= 2;
    }
  }

  m[head] = val;
}

private static <C extends Comparable<? super C>> void trinkle(C[] m, int p,
    int pshift, int head, boolean isTrusty) {

  C val = m[head];

  while (p != 1) {
    int stepson = head - LP[pshift];

    if (m[stepson].compareTo(val) <= 0)
      break; // current node is greater than head. Sift.

    // no need to check this if we know the current node is trusty,
    // because we just checked the head (which is val, in the first
    // iteration)
    if (!isTrusty && pshift > 1) {
      int rt = head - 1;
      int lf = head - 1 - LP[pshift - 2];
      if (m[rt].compareTo(m[stepson]) >= 0
          || m[lf].compareTo(m[stepson]) >= 0)
        break;
    }

    m[head] = m[stepson];

    head = stepson;
    int trail = Integer.numberOfTrailingZeros(p & ~1);
    p >>>= trail;
    pshift += trail;
    isTrusty = false;
  }

  if (!isTrusty) {
    m[head] = val;
    sift(m, pshift, head);
  }
}