Come sorta quasi ordinato matrice nel più breve tempo possibile? (Giava)
-
21-09-2019 - |
Domanda
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?
Soluzione
In realtà, la Wikipedia contiene un'implementazione Java di smoothsort. Lo si può trovare qui:
Altri suggerimenti
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.
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):
- Trova tutte le out-of-order oggetti ed estrarre il dall'elenco originale per un elenco separato, O (N)
- Il risultato è due liste: una lista ordinata e un elenco breve estratto
- 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).
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.
[Sun] JDK7 ha (o avrà) un'implementazione di Tim sorta (da Pitone). È una sorta di unione che sfrutta ordine già esistente nella matrice.
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.
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).
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.
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.
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);
}
}