Cómo especie casi ordenados matriz en el menor tiempo posible? (Java)

Question

Tengo una matriz de valores que es casi, pero no del todo ordenadas, con unos valores de desplazados (digamos, 50 en 100000). Cómo solucionar el problema de manera más eficiente? (Rendimiento es absolutamente crucial aquí y debería ser mucho más rápido que O (N)).

Me sabe de smoothsort, pero no puedo encontrar la aplicación Java. ¿Alguien sabe si ya se implementa? O lo que puedo utilizar para esta tarea en lugar de smoothsort?

Answer 1

En realidad, la Wikipedia contiene una implementación en Java de smoothsort. Lo puedes encontrar aquí:

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

Answer 2

Cocktail Ordenar

Si desea un algoritmo simple que es fácil de implementar, se podría hacer un cóctel de tipo . Sería funcionar razonablemente bien en la entrada de casi-ordenada.

Answer 3

Como Botz3000 señaló, no se puede realizar una operación tal rápido que O (N). El elemento más básico de cualquier algoritmo sería encontrar esas entradas de la matriz que están fuera de orden. Esto requiere O (N), incluso antes de averiguar qué hacer con ellos.

Si, efectivamente, el número de elementos "fuera de orden" es varios órdenes de magnitud por debajo del número total de elementos, se puede utilizar el siguiente algoritmo (suponiendo lista enlazada):

1. Encontrar todos los artículos fuera de orden y extraer el de la lista original a una lista separada, O (N)
2. El resultado son dos listas: una lista ordenada y una corta lista extraída
3. Para cada uno de los elementos extraídos, insertarlos en la lista ordenada. Eso sería O (log (N)) para cada uno, total es O (xlog (N)), donde X es el número de los elementos extraídos. Si X es muy pequeña en relación a N, se termina con un total de O (N).

Answer 4

Hay muchos algoritmos buenos para esto.

Smoothsort es mi favorita ... en realidad trabajé todas las matemáticas a cabo aquí Si tienes curiosidad por qué funciona tan también.

A bastante buena algoritmo para datos ya-ordenada es mergesort naturales , que es una versión de abajo hacia arriba de mergesort que obras de tratamiento de la entrada como una secuencia de subintervalos ordenados, luego hacer múltiples pasadas a través de el rango de fusión de rangos ordenados adyacentes. Se ejecuta en tiempo O (n) si los datos ya está ordenada (ya que puede detectar que sólo hay una gama ordenada), y O (n lg n) en el peor de los casos. Este algoritmo funciona bastante bien si los datos son "bloque ordenadas"; es decir, que consiste en una gran cantidad de bloques ordenados colocado justo al lado de la otra.

inserción ordenación directa definitivamente funciona bien para la mayoría de los datos ordenados, pero puede degenerar muy mal en una gran cantidad de entradas. Algunos muy buenos tipos (como introsort ) en realidad utilizar esta propiedad de ordenación por inserción a hacer un "paso de limpieza" en la entrada.

Answer 5

[Sol] JDK7 tiene (o tendrá) una implementación de Tim tipo (de Pitón). Es una especie de mezcla que se aprovecha de orden ya existente en la matriz.

Answer 6

Smoothsort o Timsort son grandes algoritmos, y serían las cosas sensibles al uso.

Yo añadiría que lo que es posible que no se dan cuenta es que el humilde ordenación por inserción adaptado. De hecho, para las listas realmente casi ordenados, ya que parecen tener, mi entendimiento (que no puedo realizar copias de seguridad con una referencia) es que es más rápido que los algoritmos más sofisticados. El problema es que si la entrada no está-ordenadas casi, rápidamente se degrada a O (n ^ 2). Aún así, es muy sencillo de implementar correctamente, por lo que si se sabe con certeza que su entrada es siempre ordenadas casi, sería una buena opción.

Answer 7

Sólo para poner sobre la mesa, una burbuja-tipo bien implementado sin duda sería el algoritmo más simple aquí. Con un peor caso de O (n * m), siendo m el número de desplazamientos. El m parte depende en gran medida el patrón de desplazamientos, por lo general la complejidad total sería de O (n).

Answer 8

Estás razón sobre la imposibilidad de llegar a O (N), pero suponiendo una máquina multi-núcleo (que tengo), podemos un poco de trampa mediante el uso de un algoritmo de ordenación paralela.

Answer 9

poner en práctica lo que llamamos en la escuela un tipo de Shell . Eso bubblesorting sub-arrays. Un sub-matriz con el paso k es una matriz de elementos con índices del 0, k, 2k, 3k ...

Si elige k = 3i + 1, y realizar múltiples tipos de burbujas, a partir de una mayor i-S downto 0, los tiempos serán más pequeños en la matriz de casi-ordenada.

Answer 10

Esta es la implementación original de Java de Smoothsort que solía estar disponible a través del artículo de Wikipedia .

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