¿Algún algoritmo de clasificación eficiente para una lista casi ordenada que contiene datos de tiempo?

Question

El nombre lo dice todo realmente. Sospecho que la ordenación por inserción es la mejor, ya que es la mejor opción para los datos ordenados en general en general. Sin embargo, dado que sé más acerca de los datos, existe la posibilidad de que haya otros tipos que mirar. Así que las otras piezas de información relevantes son:

1) esto es información de tiempo, lo que significa que presumiblemente podría crear un hash efectivo para ordenar los datos. 2) No todos los datos existirán a la vez. en cambio, leeré en registros que pueden contener un solo vector, o docena o cientos de vectores. Quiero dar salida todo el tiempo dentro de una ventana de 5 segundos. Entonces, es posible que un tipo que haga la ordenación a medida que inserte los datos sea una mejor opción. 3) la memoria no es un gran problema, pero la velocidad de la CPU es ya que esto puede ser un cuello de botella del sistema.

Dadas estas condiciones, ¿alguien puede sugerir un algoritmo que puede valer la pena considerar además del tipo de inserción? Además, ¿cómo se define "mayormente ordenado" para decidir cuál es una buena opción de ordenamiento? Lo que quiero decir con eso es ¿cómo veo mis datos y decidí 'esto no está tan ordenado como pensé, tal vez la ordenación por inserción ya no es la mejor opción'? Se apreciará cualquier enlace a un artículo que considere la complejidad del proceso que mejor defina la complejidad relativa a los datos de grado.

Gracias

Editar: gracias a todos por su información. Iré con un tipo fácil de inserción o fusión (lo que ya haya escrito previamente) por ahora. Sin embargo, probaré algunos de los otros métodos una vez estuvieron más cerca de la fase de optimización (ya que requieren más esfuerzo implementar). Agradezco la ayuda

Answer 1

Podría adoptar la opción (2) que sugirió - ordenar los datos mientras inserta elementos.

Utilice un skip list, ordenado según el tiempo, ascendiendo para mantener sus datos.

• Una vez que llega un nuevo plato - comprobar si es más grande que el último elemento de (fácil y rápida) si es - Simplemente lo añaden (fácil de hacer en una lista de salto). La lista de omisiones deberá agregar 2 nodos en promedio para estos casos, y será O(1) en promedio para estos casos.
• Si el elemento no es más grande que el último elemento, agréguelo a la lista de omisiones como inserción estándar op, que será O(logn).

Este enfoque se producirá O(n+klogn) algoritmo, donde k es el número de elementos insertados fuera de orden.

Answer 2

Yo lanzaría en merge sort si implementa la versión natural obtendrá una mejor carcasa de O(N) con un caso típico y el peor de O(N log N) si tiene algún problema. En la inserción se obtiene el peor caso de O(N^2) y el mejor caso de O(N).

Answer 3

Hay muchos algoritmos de clasificación adaptables que están específicamente diseñados para ordenar los datos ordenados en su mayoría. Ignorando el hecho de que está almacenando fechas, puede consultar smoothsort o ordenación de árbol cartesiano como algoritmos que pueden ordenar datos razonablemente ordenados en el peor de los casos O (n log n) y el mejor de los casos O (n) hora. Smoothsort también tiene la ventaja de requerir solo O (1) espacio, como ordenar por inserción.

Utilizando el hecho de que todo es una fecha y, por lo tanto, se puede convertir en un número entero, es posible que desee ver la ordenación binaria (clasificación de raíz MSD) utilizando una selección de pivote de la mediana de tres. Este algoritmo tiene el mejor rendimiento O (n log n), pero tiene un factor constante muy bajo que lo hace bastante competitivo. Su peor caso es O (n log U), donde U es el número de bits en cada fecha (probablemente 64), lo que no es tan malo.

Espero que esto ayude!

Answer 4

Si su biblioteca OS o C proporciona una función mergesort, es muy probable que ya maneje el caso donde los datos proporcionados están parcialmente ordenados (en cualquier dirección) ejecutándose en O (N) tiempo.

De lo contrario, puede copiar el mergesort disponible en su sistema operativo BSD favorito.

Answer 5

Sin entender completamente el problema, Timsort puede encajar en la factura ya que alega que sus datos ya están ordenados en su mayoría.

Answer 6

Puede ordenar una lista de tamaño n con k elementos fuera de lugar en O(n + k lg k) tiempo.

Ver: http://www.quora.com/How-can-I-quickly-sort-an-array-of-elements-that-is-already-sorted-except-for-a-small-number-of-elements-say-up-to-1-4-of-the-total-whose-positions-are-known/answer/Mark-Gordon-6?share=1

La idea básica es la siguiente:

• iterar sobre los elementos de la matriz, la construcción de una subsecuencia creciente (si el elemento actual es mayor o igual que el último elemento de la subsecuencia, añádala al final de la subsecuencia. De lo contrario, descarte tanto el elemento actual como el último elemento de la subsecuencia). Esto toma el tiempo O(n).
• No habrá descartado más de 2k elementos ya que k elementos están fuera de lugar.
• Ordene los elementos 2k que se descartaron mediante un algoritmo de ordenación O(k lg k) como merge sort o heapsort.
• Ahora tiene dos listas ordenadas. Combine las listas en el tiempo O(n) como lo haría en el paso de combinación de tipo de fusión.

tiempo la complejidad general = O(n + k lg k)

En general la complejidad del espacio = O(n)

(esto puede ser modificado para funcionar en O(1) espacio si se puede fusionar en O(1) espacio, pero de ninguna manera es trivial)