algorithm - examples - o n !)

¿Algoritmos de clasificación para datos de distribución estadística conocida?

Question

Me acabo de ocurrir, si sabe algo sobre la distribución (en el sentido estadístico) de los datos que se van a ordenar, el rendimiento de un algoritmo de clasificación podría ser beneficioso si toma esa información en cuenta.

Entonces mi pregunta es, ¿hay algún algoritmo de clasificación que tenga en cuenta ese tipo de información? ¿Qué tan buenos son?

Editar: un ejemplo para aclarar: si sabe que la distribución de sus datos es gaussiana, puede estimar la media y la media sobre la marcha a medida que procesa los datos. Esto le daría una estimación de la posición final de cada número, que podría utilizar para colocarlos cerca de su posición final.

Editar # 2: Estoy bastante sorprendido de que la respuesta no sea un enlace de la wiki a una página completa sobre este tema. ¿No es este un caso muy común (el caso de Gauss, por ejemplo)?

Editar # 3: Estoy agregando una recompensa a esta pregunta, porque estoy buscando respuestas definitivas con las fuentes, no la especulación. Algo así como "en el caso de los datos distribuidos de Gauss, el algoritmo XYZ es el más rápido en promedio, como lo demostraron Smith et al. [1]". Sin embargo, cualquier información adicional es bienvenida.

Nota : otorgaré la recompensa a la respuesta más votado. ¡Vota sabiamente!

Answer 1

Conociendo la distribución de la fuente de datos, uno puede construir una buena función hash. Conociendo bien la distribución, la función hash puede ser una función hash perfecta, o casi perfecta para muchos vectores de entrada.

Dicha función dividiría una entrada de tamaño n en n bins, de modo que el elemento más pequeño se mapearía en la 1ra bandeja, y el elemento más grande se mapearía en la última bandeja. Cuando el hash es perfecto, logramos sortearlo simplemente insertando todos los elementos en los contenedores.

Insertar todos los elementos en una tabla hash, luego extraerlos por orden será O (n) cuando el hash sea perfecto (suponiendo que el costo de cálculo de la función hash es O (1), y las operaciones de estructura de datos hash subrayado son O (1) )

Usaría una matriz de montones de fibonacci para implementar la tabla hash.

Para el vector de entrada para el cual la función hash no será perfecta (pero aún así estará cerca de la perfección), aún sería mucho mejor que O (nlogn). Cuando es perfecto, sería O (n). No estoy seguro de cómo calcular la complejidad promedio, pero si se me obligara, apostaría por O (nloglogn).

Answer 2

Creo que el ciclo de clasificación cae en esta categoría. Lo usa cuando conoce la posición exacta en la que desea que termine cada elemento.

Cyclesort tiene algunas buenas propiedades: para ciertos tipos restringidos de datos, puede hacer una ordenación estable in situ en tiempo lineal, al tiempo que garantiza que cada elemento se moverá como máximo una vez.

Answer 3

La ordenación del cubo le daría un algoritmo de clasificación de tiempo lineal, siempre que pueda calcular el CDF de cada punto en O (1) tiempo.

El algoritmo, que también puede buscar en otro lugar, es el siguiente:

a = array(0, n - 1, []) // create an empty list for each bucket
for x in input:
a[floor(n * cdf(x))].append(x) // O(1) time for each x
input.clear()
for i in {0,...,n - 1}:
// this sorting step costs O(|a[i]|^2) time for each bucket
// but most buckets are small and the cost is O(1) per bucket in expectation
insertion_sort(a[i])
input.concatenate(a[i])

El tiempo de ejecución es O (n) esperado porque en expectativa hay O (n) pares (x, y) tales que xey están en la misma categoría y el tiempo de ejecución de ordenación por inserción es precisamente O (n + # pares en el mismo cubo). El análisis es similar al de hash perfecto estático FKS .

EDITAR: Si no conoce la distribución, pero sabe de qué familia es, puede estimar la distribución en O (n), en el caso de Gauss calculando la media y la varianza, y luego usar el mismo algoritmo (por cierto , computar el cdf en este caso no es trivial).

Answer 4

Los algoritmos de ordenación de computadoras se pueden clasificar en dos categorías, clasificación basada en comparación y clasificación no basada en comparación. Para la ordenación basada en la comparación, el tiempo de ordenación en el mejor de los casos es Ω (nlogn), mientras que en el peor de los casos el tiempo de clasificación puede elevarse hasta O (n2). En los últimos años, se han propuesto algunos algoritmos mejorados para acelerar la clasificación basada en la comparación, como la ordenación rápida avanzada según las características de distribución de datos. Sin embargo, el tiempo de clasificación promedio para estos algoritmos es solo Ω (nlog2n), y solo en el mejor de los casos puede llegar a O (n). A diferencia de la ordenación basada en la comparación, la clasificación no basada en la comparación, como la clasificación de conteos, la clasificación de depósitos y la ordenación de radix depende principalmente del cálculo de claves y direcciones. Cuando los valores de las claves son finitos que varían de 1 a m, la complejidad computacional de la clasificación no basada en la comparación es O (m + n). Particularmente, cuando m = O (n), el tiempo de clasificación puede alcanzar O (n). Sin embargo, cuando m = n2, n3, ...., No se puede obtener el límite superior del tiempo de ordenación lineal. Entre la ordenación no basada en la comparación, la ordenación del cubo distribuye un grupo de registros con claves similares en el "cubo" apropiado, luego se aplica otro algoritmo de clasificación a los registros en cada segmento. Con la ordenación de depósitos, la partición de registros en m bulos consume menos tiempo, mientras que solo se almacenarán unos pocos registros en cada segmento para que el algoritmo de "clasificación de limpieza" se pueda aplicar muy rápido. Por lo tanto, la ordenación del cucharón tiene el potencial de ahorrar de forma asintótica el tiempo de clasificación en comparación con los algoritmos Ω (nlogn). Obviamente, la forma de distribuir uniformemente todos los registros en cubos juega un papel fundamental en la clasificación de cubos. Por lo tanto, lo que necesita es un método para construir una función hash según la distribución de datos, que se usa para distribuir uniformemente n registros en n cubetas basados ​​en la clave de cada registro. Por lo tanto, el tiempo de clasificación del algoritmo de clasificación de cubeta propuesto alcanzará O (n) bajo cualquier circunstancia.

mira este artículo: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5170434&tag=1

Answer 5

Parece que es posible que desee leer Algoritmos de autoevaluación : logran un tiempo de ejecución esperado óptimo para distribuciones de entrada arbitrarias .

Proporcionamos estos algoritmos de autoevaluación para dos problemas: (i) ordenar una secuencia de números y (ii) calcular la triangulación de Delaunay de un conjunto de puntos planar. Ambos algoritmos logran la complejidad límite esperada óptima. Los algoritmos comienzan con una fase de entrenamiento durante la cual recopilan información sobre la distribución de entrada, seguida de un régimen estacionario en el que los algoritmos se ajustan a sus encarnaciones optimizadas.

Si ya sabe que su distribución de entrada es aproximadamente gaussiana, entonces quizás otro enfoque sea más eficiente en términos de complejidad de espacio, pero en términos de tiempo de ejecución esperado, este es un resultado bastante maravilloso.

Answer 6

Puede usar esa información en quicksort para seleccionar el valor de pivote. Creo que mejoraría la probabilidad de que el algoritmo se mantenga alejado de la complejidad del peor caso O (N ** 2).

Answer 7

Si los datos que está ordenando tienen una distribución conocida, usaría un algoritmo de clasificación de depósitos. Podría agregarle un poco de lógica adicional para que calcule el tamaño y / o las posiciones de los diferentes segmentos según las propiedades de la distribución (por ejemplo, para Gaussian, puede tener un intervalo cada (sigma / k) alejado de la media, donde sigma es la desviación estándar de la distribución).

Al tener una distribución conocida y modificar el algoritmo estándar de Clasificación de Cubo de esta manera, es probable que obtenga el algoritmo de Clasificación de Histograma o algo parecido. Por supuesto, su algoritmo sería computacionalmente más rápido que el algoritmo Histogram Sort porque probablemente no habría necesidad de hacer el primer pase (descrito en el enlace) ya que ya conoce la distribución.

Editar: dado su nuevo criterio de su pregunta, (aunque mi respuesta anterior sobre los enlaces de Histogram Sort al respetable NIST y contiene información de rendimiento), aquí hay un artículo de revista de revisión por pares de la Conferencia Internacional sobre Procesamiento en Paralelo:

Partición de datos adaptable para ordenar usando la distribución de probabilidad

Los autores afirman que este algoritmo tiene un mejor rendimiento (hasta un 30% mejor) que el popular algoritmo de clasificación rápida.