algorithm - Algoritmos Cercanos de Clasificación-¿Cuándo usarlos?

language-agnostic sorting (6)

En cualquier sitio

se supone que debes reaccionar rápido,
no estás prometiendo comportamiento exacto al cliente,
pero internamente tienes algunas reglas

puedes 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, realmente 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 una regla poco estricta para que sea preventiva, priorizada, blabla ..

Un ejemplo de programación de recursos respondería a la entrega de pizzas o al 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.

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 de 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 puedes vivir con el hecho de que el algoritmo de clasificación hace trampa un poco. Obtienes una lista casi ordenada, pero también tienes que vivir con algunos errores.

Jugué con los algoritmos en un entorno de prueba, pero nunca encontré un uso para ellos.

Entonces la pregunta: ¿alguien alguna vez ha utilizado la clasificación cercana 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?

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 meta-heurí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.

Solo estoy especulando aquí, pero una cosa que imagino es la optimización de consulta en 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 usan 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 todavía estoy 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 pocos milisegundos más tarde que si se clasifica estrictamente por prioridad .

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

Supongamos que tiene muchos elementos que le gustaría que un humano clasifique 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.

O (n log n) ya es bastante rápido. No creo que nadie empiece a utilizar 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 de sort y no una función nearsort ), y cuando encontraste empíricamente que el tipo nearsort demasiado, empezarías a cuestionar si sus datos realmente necesitan ser ordenados por completo, y considere usar un método de aproximación.

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

Esta es una conjetura total, pero dada la subjetividad inherente de las medidas de "relevancia" al ordenar los resultados de búsqueda, me atrevo a aventurar 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, sus datos "casi ordenados" no cumplen con una posible idea intuitiva de "casi ordenada", que es que tiene solo 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ómputo (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, está buscando aplicaciones en las que se clasifique un subconjunto mayoritario de los datos y el resto esté disperso, no para aplicaciones que requieren que cada elemento esté cerca de su posición correcta.