Cerca de los algoritmos de clasificació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 me encontré con 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 las clasificaciones basadas en la comparación si puedes vivir con el hecho de que el algoritmo de clasificación hace un poco de trampa. Obtendrá una lista casi ordenada, pero también tendrá 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 ha usado alguna vez cerca de la clasificación en la práctica? Si es así, ¿en qué tipo de aplicaciones? ¿Puedes pensar en un caso de uso en el que la ordenación cercana sea lo correcto?

Answer 1

Hay muchos "codiciosos" heurística donde selecciona periódicamente el mínimo de un conjunto. La heurística codiciosa no es perfecta, por lo que incluso si elige el mínimo, no se garantiza que obtenga la mejor respuesta final. De hecho, el GRASP meta-heurístico, introduces intencionalmente un error aleatorio para que obtengas múltiples finales soluciones y seleccione la mejor. En ese caso, la introducción de algún error en su rutina de clasificación a cambio de velocidad sería una buena compensación.

Answer 2

Esta es una suposición de vuelo total, pero dada la subjetividad inherente de " relevancia " Cuando se clasifican los resultados de búsqueda, me atrevería a decir que realmente no importa si están o no perfectamente ordenados. Lo mismo podría decirse de las recomendaciones. Si puede organizar de alguna manera que todas las otras partes de su algoritmo para esas cosas sean O (n), entonces podría buscar una clasificación.

Tenga en cuenta también que, en el peor de los casos, su " casi ordenado " data no cumple con una posible idea intuitiva de "casi ordenado", que es que solo tiene un pequeño número de inversiones. La razón de esto es solo que si sus datos solo tienen inversiones de O (n), entonces puede terminar de ordenarlos en tiempo de O (n) usando la clasificación de inserción o la clasificación de cóctel (es decir, clasificación de burbuja bidireccional). De ello se deduce que no es posible que haya alcanzado este punto completamente sin clasificar, en tiempo O (n) (utilizando comparaciones). Por lo tanto, está buscando aplicaciones donde se clasifica un subconjunto mayoritario de datos y el resto está disperso, no para aplicaciones que requieren que cada elemento esté cerca de su posición correcta.

Answer 3

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

Una consulta de base de datos en un lenguaje declarativo como SQL debe traducirse en un programa paso a paso denominado "plan de ejecución". Una consulta SQL normalmente se puede traducir a varios de estos planes de ejecución, que 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 se usan 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, tal vez con un elemento aleatorio para elegir cuáles. Esto funciona, ya que generalmente hay una gran cantidad de " buena " planes, y puede que no sea tan importante encontrar el mejor; es probable que sea mejor elegir un plan de 5 segundos en lugar del plan óptimo de 2 segundos, si se requieren varios minutos de optimización para encontrar el segundo plan.

Algunos algoritmos de optimización utilizan una cola ordenada de "prometedor" Planes (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 subprocesos en un sistema de tiempo compartido, donde podría no ser importante si un determinado proceso o subproceso obtiene su intervalo de tiempo unos pocos milisegundos más tarde de lo estrictamente ordenado por prioridad.

Answer 4

Una aplicación común para la clasificación cercana es cuando un humano está haciendo la comparación por pares y no quieres tener que hacerles tantas preguntas.

Digamos que tienes muchos elementos que te gustaría que un humano clasificara a través de una comparación por pares. Puede reducir en gran medida la cantidad de comparaciones que necesita hacer si está dispuesto a aceptar que el pedido no será exacto. Por ejemplo, es posible que no le importe si los elementos adyacentes se han intercambiado durante mucho tiempo, ya que los elementos preferidos están en la parte superior.

Answer 5

En cualquier lugar

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

puedes usarlo. ¿Qué tal "no tan estricto" cola de prioridad basada en reglas? ¿Dónde sería eso útil? Tal vez la programación de subprocesos / procesos / recursos. En la programación de subprocesos / procesos, realmente no estás prometiendo que un subproceso irá primero, segundo o último, pero generalmente quieres darles a todos una oportunidad. Es posible que desee aplicar una regla flexible para que sea preventiva, priorizada, blabla ...

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

Answer 6

O (n log n) ya es bastante rápido. No creo que nadie pueda comenzar utilizando un algoritmo de clasificación cercana. Comenzaría con un código que solo hace una ordenación completa (ya que su lenguaje de programación de elección probablemente proporciona una función sort y no una función nearsort ), y cuando lo encuentra empíricamente si el ordenamiento estaba tardando demasiado, comenzaría a preguntarse si sus datos realmente necesitan estar completamente ordenados y considerar usar un ordenamiento cercano.

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