Algoritmos cercanos a la ordenación: ¿cuándo usarlos?

Question

De vez en cuando navego por la web y busco algoritmos y estructuras de datos interesantes para poner en mi bolsa de trucos. Hace un año encontré la estructura de datos Soft Heap y aprendí acerca de la clasificación cercana.

La idea detrás de esto es que es posible romper la barrera O (n log n) de los géneros basados ​​en comparación si puede vivir con el hecho de que el algoritmo de clasificación hace trampas. Obtienes una lista casi ordenada, pero también tienes que vivir con algunos errores.

He jugado con los algoritmos en un entorno de prueba, pero nunca he encontrado un uso para ellos.

Entonces, la pregunta: ¿Alguien ha usado alguna vez la práctica de la clasificación en la práctica? De ser así, ¿en qué tipo de aplicaciones? ¿Puedes pensar en un caso de uso en el que la clasificación cercana es lo correcto?

Answer 1

Hay muchas heurísticas "codiciosas" en las que periódicamente se selecciona el mínimo de un conjunto. La heurística codiciosa no es perfecta, por lo que incluso si elige el mínimo, no está garantizado que obtenga la mejor respuesta final. De hecho, la metaheurística GRASP, introduce intencionalmente un error aleatorio para que obtenga múltiples soluciones finales y seleccione la mejor. En ese caso, introducir un error en su rutina de clasificación a cambio de velocidad sería una buena compensación.

Answer 2

Esta es una conjetura total, pero dada la subjetividad inherente de las medidas de "relevancia" al ordenar los resultados de búsqueda, me atrevería a decir que realmente no importa si están perfectamente ordenados o no. Lo mismo podría decirse de las recomendaciones. Si de alguna manera puede organizar que cada otra parte de su algoritmo para esas cosas sea O (n), entonces podría tratar de evitar una clasificación.

Tenga en cuenta también que en el peor de los casos los datos ordenados "casi" no lo hace se encuentran una posible idea intuitiva de "casi ordenadas", que es que tiene sólo un pequeño número de inversiones. La razón de esto es solo que si sus datos solo tienen O (n) inversiones, entonces puede terminar de clasificarlo en O (n) tiempo utilizando ordenación de inserción o clasificación de cóctel (es decir, clasificación de burbuja bidireccional). De esto se desprende que no es posible que haya llegado a este punto completamente desordenado, en el tiempo O (n) (utilizando comparaciones). Por lo tanto, busca aplicaciones donde un subconjunto mayoritario de los datos está ordenado y el resto está disperso, no para aplicaciones que requieren que cada elemento esté cerca de su posición correcta.

Answer 3

Solo especular aquí, pero una cosa que imagino es la optimización de la consulta de la base de datos.

Una consulta de base de datos en un lenguaje declarativo como SQL tiene que traducirse en un programa paso a paso llamado "plan de ejecución". Una consulta SQL generalmente se puede traducir a varios de dichos planes de ejecución, todos los cuales dan el mismo resultado pero pueden tener un rendimiento muy variable. El optimizador de consultas tiene que encontrar el más rápido, o al menos uno que sea razonablemente rápido.

Los optimizadores de consultas basados ​​en costos tienen una "función de costo", que utilizan para estimar el tiempo de ejecución de un plan determinado. Los optimizadores exhaustivos pasan por todos los planes posibles (por algún valor de "todos los posibles") y seleccionan el más rápido. Para consultas complicadas, la cantidad de planes posibles puede ser prohibitivamente grande, lo que lleva a tiempos de optimización demasiado largos (¡incluso antes de comenzar la búsqueda en la base de datos!), Por lo que también hay optimizadores no exhaustivos. Solo miran algunos de los planes, quizás con un elemento aleatorio al elegir cuáles. Esto funciona, ya que generalmente hay una gran cantidad de planes "buenos", y puede que no sea tan importante encontrar el mejor: probablemente sea mejor elegir un plan de 5 segundos en lugar del plan óptimo de 2 segundos. , si requiere varios minutos de optimización para encontrar el plan de 2 segundos.

Algunos algoritmos de optimización utilizan una cola ordenada de planes "prometedores" (parciales). Si realmente no importa si encuentra el mejor plan, ¿tal vez podría usar una cola casi ordenada?

Otra idea (y sigo especulando) es un programador de procesos o hilos en un sistema de tiempo compartido, donde podría no ser importante si un determinado proceso o hilo obtiene su intervalo de tiempo unos milisegundos más tarde que si estrictamente ordenado por prioridad.

Answer 4

cualquier lugar

1. que se supone que reaccionar rápido,
2. no aseguras comportamiento exacto al cliente,
3. pero internamente tiene algunas reglas

que pueden usarlo . ¿Qué tal una cola de prioridad basada en reglas "no tan estricta"? ¿Dónde sería eso útil? Tal vez la programación de hilos/procesos/recursos. En la programación de subprocesos/procesos, en realidad no promete que un solo subproceso va a ir primero, segundo o último, pero generalmente quiere darles a todos una oportunidad. Es posible que desee aplicar reglas sueltas para que sean preventivas, prioritarias, blabla ..

Un ejemplo de programación de recursos respondería a la entrega de pizza o el envío de cajas de libros a personas, etc. No puede usarlo donde se espera un resultado determinista , pero hay muchos ejemplos en la vida real donde las cosas no son tan deterministas/predecibles.

Answer 5

Una aplicación común para near-sorting es cuando un humano está haciendo la comparación por parejas y no quiere tener que hacer tantas preguntas.

Supongamos que tiene muchos elementos que desea que un ser humano ordene por comparación de pares. Puede reducir en gran medida la cantidad de comparaciones que necesita que haga si está dispuesto a aceptar que el pedido no será exacto. Es posible que, por ejemplo, no se preocupe si los elementos adyacentes se han intercambiado por mucho tiempo, ya que los elementos preferidos están en la parte superior.

Answer 6

O (n log n) ya es bastante rápido. No creo que nadie pueda comenzar usando un algoritmo near-sort. Comenzarías con un código que solo hace una ordenación completa (ya que tu lenguaje de programación de elección probablemente proporciona una función sort y no una función nearsort), y cuando encontraste empíricamente que el tipo tardaba demasiado, empezarías a cuestionar si sus datos realmente deben ser ordenados por completo, y considere el uso de una ordenación cercana.

Básicamente, nunca consideraría usar una especie cercana a menos que descubriera que la clasificación es un cuello de botella grave en su programa.