algorithm - numeros - Algoritmo rápido para encontrar rápidamente el rango al que pertenece un número en un conjunto de rangos?
rango en dfd (5)
Como alternativa a los árboles de búsqueda binaria equilibrada O (log n) (BST), podría considerar construir un trie bit a bit (comprimido). Es decir, un árbol de prefijos en los bits de los números que está almacenando.
Esto le da una búsqueda O (w), inserte y elimine el rendimiento; donde w = número de bits (por ejemplo, 32 o 64 menos la potencia de 2 en que se basan sus rangos).
No dice que funcionará mejor o peor, pero parece una alternativa verdadera en el sentido de que es diferente de BST, pero aún tiene un buen rendimiento teórico y permite consultas predecesoras como BST.
El escenario
Tengo varios rangos de números. Esos rangos no se superponen, ya que no se superponen, la consecuencia lógica es que ningún número puede formar parte de más de un rango en cualquier momento. Cada rango es continuo (no hay agujeros dentro de un solo rango, por lo que un rango de 8 a 16 realmente contendrá todos los números entre 8 y 16), pero puede haber agujeros entre dos rangos (por ejemplo, el rango comienza en 64 y va a 128, el siguiente rango comienza en 256 y va a 384), por lo que algunos números pueden no pertenecer a ningún rango (los números 129 a 255 no pertenecen a ningún rango en este ejemplo).
El problema
Obtengo un número y necesito saber a qué rango pertenece el número ... si pertenece a algún rango. De lo contrario, necesito saber que no pertenece a ningún rango. Por supuesto, la velocidad es importante; No puedo simplemente verificar todos los rangos que serían O (n), ya que podría haber miles de rangos.
Soluciones simples
Una solución simple era mantener todos los números en una matriz ordenada y ejecutar una búsqueda binaria en ella. Eso me daría al menos O (log n). Por supuesto, la búsqueda binaria debe ser algo modificada, ya que siempre debe comparar con el número más pequeño y más grande de un rango. Si el número que se busca está en el medio, hemos encontrado el rango correcto, de lo contrario debemos buscar rangos inferiores o superiores al actual. Si solo queda un rango al final y el número no está dentro de ese rango, el número está dentro de ningún rango y podemos devolver un resultado "no encontrado".
Los rangos también podrían estar encadenados juntos en algún tipo de estructura de árbol. Esto es básicamente como una lista ordenada con búsqueda binaria. La ventaja es que será más rápido modificar un árbol que un arreglo ordenado (agregar / eliminar rango), pero a diferencia de perder un poco más de tiempo en mantener el árbol equilibrado, el árbol puede desequilibrarse con el tiempo y eso conducirá a búsquedas mucho más lentas que una búsqueda binaria en una matriz ordenada.
Se puede argumentar qué solución es mejor o peor, ya que en la práctica el número de búsquedas y operaciones de modificación estará casi equilibrado (habrá un número igual de búsquedas y operaciones de agregar / eliminar realizadas por segundo).
Pregunta
¿Existe una mejor estructura de datos que una lista ordenada o un árbol para este tipo de problema? ¿Quizás uno que podría ser incluso mejor que O (log n) en el mejor de los casos y O (log n) en el peor de los casos?
Alguna información adicional que podría ayudar aquí es la siguiente: Todos los rangos siempre comienzan y terminan en múltiplos de una potencia de dos. Siempre comienzan y terminan a la misma potencia de dos (por ejemplo, todos comienzan / finalizan en un múltiplo de 4 o en un múltiplo de 8 o en un múltiplo de 16 y así sucesivamente). El poder de dos no puede cambiar durante el tiempo de ejecución. Antes de agregar el primer rango, se debe establecer la potencia de dos y todos los rangos que se hayan agregado deben comenzar / finalizar en un múltiplo de este valor hasta que finalice la aplicación. Creo que esto se puede usar para la optimización, ya que si todos comienzan en un múltiplo de, por ejemplo, 8, puedo ignorar los primeros 3 bits para todas las operaciones de comparación, los otros bits solo me dirán el rango, si alguno.
Leí sobre la sección y rangos de árboles. ¿Son estas soluciones óptimas para el problema? ¿Hay posiblemente mejores soluciones? El problema suena similar a lo que una implementación de malloc debe hacer (por ejemplo, cada bloque de memoria libre pertenece a un rango de memoria disponible y la implementación de malloc debe averiguar a cuál), entonces, ¿cómo resuelven comúnmente el problema?
Crea una lista ordenada y ordena por el margen / inicio inferior. Es más fácil de implementar y lo suficientemente rápido a menos que tenga millones de rangos (y tal vez incluso entonces).
Cuando busque un rango, encuentre el rango donde start <= position . Aquí puede usar una búsqueda binaria ya que la lista está ordenada. El número está en el rango si la position <= end .
Como se garantiza que el final de cualquier rango será más pequeño que el inicio del próximo rango, no necesita preocuparse por el final hasta que haya encontrado un rango donde la posición podría estar contenida.
Todas las otras estructuras de datos se vuelven interesantes cuando obtiene intersecciones o tiene una gran cantidad de rangos y cuando construye la estructura uno y consulta a menudo.
Si el rango total de números es bajo y tiene suficiente memoria, puede crear una tabla enorme con todos los números.
Por ejemplo, si tiene un millón de números, puede crear una tabla que haga referencia al objeto de rango.
Un árbol equilibrado y ordenado con rangos en cada nodo parece ser la respuesta. No puedo probar que sea óptimo, pero si fuera tú, no buscaría más.
Después de ejecutar varios puntos de referencia, llegué a la conclusión de que solo una estructura similar a un árbol puede funcionar aquí. Una lista ordenada muestra, por supuesto, un buen rendimiento de búsqueda - O (log n) - pero muestra un rendimiento de actualización horrible (¡las inserciones y eliminaciones son más lentas en más del factor 10 en comparación con los árboles!).
Un árbol binario equilibrado también tiene un rendimiento de búsqueda O (log n), sin embargo, es mucho más rápido de actualizar, también alrededor de O (log n), mientras que una lista ordenada es más como O (n) para actualizaciones (O (log n) a encuentre la posición para insertar o el elemento para eliminar, pero luego se deben mover hasta n elementos dentro de la lista y esto es O (n)).
Implementé un árbol AVL, un árbol rojo-negro, un Treap, un AA-Tree y varias variaciones de B-Trees (B significa Bayer Tree aquí, no Binary). Resultado: los árboles de Bayer casi nunca ganan. Su búsqueda es buena, pero su rendimiento de actualización es malo (¡ya que dentro de cada nodo de un B-Tree tiene una lista ordenada de nuevo!). Los árboles Bayer son solo superiores en los casos en que leer / escribir un nodo es una operación muy lenta (por ejemplo, cuando los nodos se leen o escriben directamente desde / hacia el disco duro), ya que un árbol B debe leer / escribir mucho menos nodos que cualquier otro árbol, entonces en tal caso ganará. Sin embargo, si tenemos el árbol en la memoria, no tiene ninguna posibilidad contra otros árboles, lo siento por todos los fans de B-Tree.
Un Treap fue más fácil de implementar (menos de la mitad de las líneas de código que necesita para otros árboles balanceados, solo el doble del código que necesita para un árbol desequilibrado) y muestra un buen rendimiento promedio para búsquedas y actualizaciones ... pero podemos hacerlo mejor que ese.
Un AA-Tree muestra un rendimiento de búsqueda increíble: no tengo idea de por qué. A veces superan a todos los demás árboles (no por lejos, pero lo suficiente como para no ser coincidentes) ... y el rendimiento de eliminación está bien; sin embargo, a menos que sea demasiado estúpido para implementarlos correctamente, el rendimiento de inserción es realmente malo (realiza mucha más rotaciones de árbol en cada inserción que cualquier otro árbol, incluso B-Trees tiene un rendimiento de inserción más rápido).
Esto nos deja con dos clásicos, AVL y RB-Tree. Ambos son bastante similares, pero después de horas de benchmarking, una cosa está clara: AVL Trees definitivamente tiene mejor rendimiento de búsqueda que RB-Trees. La diferencia no es gigantesca, pero en 2/3 de todos los puntos de referencia ganarán la prueba de búsqueda. No es demasiado sorprendente, después de todo, los árboles AVL están más estrictamente equilibrados que los árboles RB, por lo que están más cerca del árbol binario óptimo en la mayoría de los casos. No estamos hablando de una gran diferencia aquí, siempre es una carrera cerrada.
Por otro lado, RB Trees venció a AVL Trees por insertos en casi todas las pruebas y esa no es una carrera tan cerrada. Como antes, eso es esperado. Al ser RB menos estrictamente equilibrado, los árboles realizan muchas menos rotaciones de árboles en los insertos en comparación con los Árboles AVL.
¿Qué hay de la eliminación de los nodos? Aquí parece depender mucho del número de nodos. Para números de nodo pequeños (todo menos de medio millón), RB Trees posee árboles AVL otra vez; la diferencia es aún mayor que para las inserciones. Más bien inesperado es que una vez que el número de nodo crece más allá de un millón de nodos, AVL Trees parece ponerse al día y la diferencia con los árboles RB se reduce hasta que son más o menos igualmente rápidos. Sin embargo, esto podría ser un efecto del sistema. Podría tener que ver con el uso de la memoria del proceso o almacenamiento en caché de la CPU o similar. Algo que tiene un efecto más negativo en RB Trees que en AVL Trees y, por lo tanto, AVL Trees puede ponerse al día. El mismo efecto no se observa en las búsquedas (AVL suele ser más rápido, independientemente de cuántos nodos) y en las inserciones (RB suele ser más rápido, independientemente de cuántos nodos).
Conclusión:
Creo que lo más rápido que puedo obtener es usar RB-Trees, ya que el número de búsquedas será un poco más alto que el número de insertos y eliminaciones, y no importa qué tan rápido AVL esté en las búsquedas, el rendimiento general sufrirá por su peor inserción / rendimiento de eliminación.
Es decir, a menos que alguien aquí presente una estructura de datos mucho mejor que posea RB Trees a lo grande ;-)