poner - setbounds java

¿Cómo se ordena la matriz casi ordenada en el menor tiempo posible?(Java)

Question

Tengo una matriz de valores que está casi, pero no del todo ordenada, con algunos valores desplazados (digamos, 50 en 100000). ¿Cómo ordenarlo de manera más eficiente? (El rendimiento es absolutamente crucial aquí y debería ser mucho más rápido que O (N)).

Sé de smoothsort, pero no puedo encontrar la implementación de Java. ¿Alguien sabe si ya está implementado? ¿O qué puedo usar para esta tarea en lugar de smoothsort?

Answer 1

Cocktail Sort

Si desea un algoritmo simple que sea fácil de implementar, puede hacer un cóctel de clasificación . Funcionaría razonablemente bien en entradas casi ordenadas.

Answer 2

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

Si de hecho el número de elementos "fuera de servicio" es órdenes de magnitud por debajo de la cantidad total de elementos, puede usar el siguiente algoritmo (suponiendo que la lista esté enlazada):

1. Encuentre todos los artículos fuera de servicio y extraiga los de la lista original a una lista separada, O (N)
2. El resultado son dos listas: una lista ordenada y una lista breve extraída
3. Para cada uno de los elementos extraídos, insértelos en la lista ordenada. Eso sería O (log (N)) para cada uno, el total es O (Xlog (N)), donde X es el número de los elementos extraídos. Si X es muy pequeño en relación con N, terminas con un total de O (N).

Answer 3

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

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

Answer 4

Esta es la implementación Java original 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);
  }
}

Answer 5

Hay muchos buenos algoritmos para esto.

Smoothsort es mi favorito personal ... De hecho trabajé todas las matemáticas aquí si tienes curiosidad por qué funciona tan bien.

Un algoritmo bastante bueno para los datos ya ordenados es el mergesort natural , que es una versión bottom-up de mergesort que funciona tratando la entrada como una secuencia de subintervalos ordenados, luego haciendo múltiples pasadas sobre el rango fusionando rangos ordenados adyacentes. Se ejecuta en O (n) tiempo si los datos ya están ordenados (porque puede detectar que solo hay un rango ordenado), y O (n lg n) en el peor de los casos. Este algoritmo funciona bastante bien si los datos están "ordenados en bloque"; es decir, consiste en una gran cantidad de bloques ordenados colocados uno al lado del otro.

El tipo de inserción directa definitivamente funciona bien para datos ordenados en su mayoría, pero puede degenerar muy mal en muchas entradas. Algunos géneros realmente buenos (como introsort ) realmente usan esta propiedad de inserción para hacer un "paso de limpieza" en la entrada.

Answer 6

Implementar lo que llamamos en la escuela un tipo de Shell . Eso es sub-arrays de burbujeo. Una sub-matriz con el paso k es una matriz de elementos con indicios 0, k, 2k, 3k ...

Si eliges k = 3i + 1, y realizas varios tipos de burbujas, comenzando desde arriba es menor que 0, los tiempos serán más pequeños en una matriz casi ordenada.

Answer 7

Smoothsort o Timsort son excelentes algoritmos, y serían cosas sensatas de usar.

Añadiría que lo que quizás no se den cuenta es que el tipo de inserción humilde es adaptativo. De hecho, para las listas realmente casi ordenadas, como parece tener, mi comprensión (que no puedo respaldar con una referencia) es que es más rápida que los algoritmos más sofisticados. El problema es que si la entrada no está casi clasificada, se degrada rápidamente a O (n ^ 2). Aún así, es muy fácil de implementar correctamente, por lo que si está seguro de que su entrada siempre está casi ordenada, sería una buena opción.

Answer 8

Solo para ponerlo sobre la mesa, una especie de burbuja bien implementada sería ciertamente el algoritmo más simple aquí. Con el peor caso de O (n * m), m es el número de desplazamientos. La parte m depende en gran medida del patrón de desplazamientos, generalmente la complejidad total sería O (n).

Answer 9

Tiene razón acerca de la imposibilidad de alcanzar O (N), pero asumiendo una máquina multi-core (que yo tengo), podemos hacer trampa un poco usando un algoritmo de clasificación paralelo.

Answer 10

[Sun] JDK7 tiene (o tendrá) una implementación de Tim sort (de Python). Es un tipo de fusión que aprovecha el orden ya existente en la matriz.