Come sorta quasi ordinato matrice nel più breve tempo possibile? (Giava)

Question

Ho una matrice di valori che è quasi, ma non del tutto risolto, con pochi valori sfollati (diciamo, 50 a 100000). Come ordinare nel modo più efficiente? (Prestazioni è assolutamente cruciale e deve essere il modo più veloce di O (N)).

So di smoothsort, ma non riesco a trovare implementazione Java. Qualcuno sa se è già in atto? O che cosa posso usare per questo compito, invece di smoothsort?

Answer 1

In realtà, la Wikipedia contiene un'implementazione Java di smoothsort. Lo si può trovare qui:

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

Answer 2

Cocktail Ordina

Se si desidera un semplice algoritmo che è facile da implementare, si potrebbe fare un rel="noreferrer"> cocktail . Funzionerebbe abbastanza bene su input quasi-ordinato.

Answer 3

Come osservato Botz3000, non è possibile eseguire tale operazione più veloce di O (N). L'elemento più fondamentale di qualsiasi algoritmo sarebbe quello di trovare quelle voci nella matrice che sono fuori uso. Ciò richiede O (N), prima ancora di capire cosa fare con loro.

Se, infatti, il numero di elementi "out-of-order" è ordini di grandezza al di sotto del numero totale di elementi, è possibile utilizzare il seguente algoritmo (supponendo lista collegata):

1. Trova tutte le out-of-order oggetti ed estrarre il dall'elenco originale per un elenco separato, O (N)
2. Il risultato è due liste: una lista ordinata e un elenco breve estratto
3. Per ciascuno degli elementi estratti, inserirli nella lista ordinata. Questo sarebbe O (log (N)) per ciascuna, totale è O (xlog (N)), dove X è il numero degli elementi estratti. Se X è molto piccolo rispetto a N, si finisce con un totale di O (N).

Answer 4

Ci sono molti buoni algoritmi per questo.

smoothsort è il mio preferito ... Io in realtà lavorato tutta la matematica qui se siete curiosi perché funziona così bene.

Un abbastanza buon algoritmo per i dati già filtrate è Mergesort naturale , che è una versione bottom-up di Mergesort che funziona trattando l'input come una sequenza di intervalli ordinati, quindi rendendo più passaggi sopra la gamma fusione gamme filtrate adiacenti. Viene eseguito in O (n) se i dati è già ordinato (perché si può rilevare che c'è solo una gamma ordinato), e O (n lg n) nel caso peggiore. Questo algoritmo funziona abbastanza bene se i dati sono "blocco ordinato"; cioè, si compone di un sacco di blocchi ordinati collocato proprio accanto gli uni agli altri.

inserimento dritto funziona sorta decisamente bene per la maggior parte dei dati-ordinati, ma può degenerare molto male su un sacco di input. Alcuni veramente buoni tipi (come introsort ) effettivamente utilizzare questa proprietà di insertion sort di fare un "passo di pulizia" sull'ingresso.

Answer 5

[Sun] JDK7 ha (o avrà) un'implementazione di Tim sorta (da Pitone). È una sorta di unione che sfrutta ordine già esistente nella matrice.

Answer 6

smoothsort o timsort sono grandi algoritmi, e sarebbe cose sensibili da utilizzare.

mi piacerebbe aggiungere che ciò che si potrebbe non rendersi conto è che le insertion sort è adattivo. Infatti, per le liste davvero quasi ordinati, come ti sembra di avere, la mia comprensione (che non posso eseguire il backup con un riferimento) è che è più veloce di algoritmi più sofisticati. Il problema è che se l'ingresso non viene quasi-ordinato, si degrada rapidamente a O (n ^ 2). Eppure, è molto semplice da implementare in modo corretto, quindi se si sa per certo che il vostro ingresso è sempre quasi-allineati, sarebbe una buona scelta.

Answer 7

Giusto per mettere sul tavolo, un ben implementato bolla-tipo sarebbe certamente l'algoritmo più semplice qui. Con un caso peggiore di O (n * m), dove M è il numero di spostamenti. La parte m dipende fortemente dalla configurazione degli spostamenti, di solito complessità totale sarebbe O (n).

Answer 8

Hai ragione per l'impossibilità di raggiungere O (N), ma assumendo una macchina multi-core (che ho), possiamo ingannare un po utilizzando un algoritmo di ordinamento parallelo.

Answer 9

implementare ciò che abbiamo chiamato a scuola una sorta di Shell . Questo è bubblesorting sub-array. Una sub-array con passo k è un array di elementi con indicies 0, k, 2k, 3k ...

Se si sceglie k = 3i + 1, e di eseguire molteplici tipi di bolle, a partire dal più alto i-s downto 0, i tempi saranno più piccoli sulla matrice quasi-ordinato.

Answer 10

Questa è l'implementazione Java originale del smoothsort che ha usato essere disponibile tramite il Wikipedia articolo .

// 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);
  }
}