algoritmo eficiente para probar _que establece un número particular

Question

Si tengo un gran conjunto de rangos continuos (ej. [0..5], [10..20], [7..13], [- 1. .37]) y puede organizar esos conjuntos en cualquier estructura de datos que me guste, ¿cuál es la forma más eficiente de probar a la cual establece un número de prueba en particular?

He pensado en almacenar los conjuntos en un árbol binario equilibrado basado en el bajo número de un conjunto (y cada nodo tendría todos los conjuntos que tengan el mismo número mínimo de su conjunto). Esto le permitiría podar eficientemente el número de conjuntos según si el test_number que está probando contra los conjuntos es menor que el número más bajo de un conjunto, y luego pode ese nodo y todos los nodos a la derecha de ese nodo (que tener un número bajo en su rango que es mayor que el número de prueba). Creo que podaría aproximadamente el 25% de los conjuntos en promedio, pero luego tendría que buscar linealmente en el resto de los nodos en el árbol binario para determinar si el número de prueba pertenecía a esos conjuntos. (Podría optimizar aún más ordenando las listas de conjuntos en cualquier nodo por el número más alto en el conjunto, lo que me permitiría realizar búsquedas binarias dentro de una lista específica para determinar qué conjunto, si lo hay, contiene el número de prueba. Desafortunadamente, la mayoría de los conjuntos con los que trataré no tienen límites de conjunto superpuestos.)

Creo que este problema se ha resuelto en el procesamiento de gráficos ya que han descubierto maneras de probar eficientemente qué polígonos en su modelo completo contribuyen a un píxel específico, pero no conozco la terminología de ese tipo de algoritmo.

Answer 1

Su intuición sobre la relevancia de su problema para los gráficos es correcta. Considere crear y consultar un segment tree. Es particularmente adecuado para la consulta de recuento que desee. Vea también su description in Computational Geometry.

Answer 2

Creo que los organizaría de la misma manera que Mediawiki indexa páginas - como bucket sort. No sé si es el algoritmo más eficiente de, pero debe ser rápido, y es bastante fácil de implementar (¡incluso lo he logrado, y en SQL eso!).

Básicamente, el algoritmo de clasificación es

For Each SetOfNumbers 
    For Each NumberInSet 
     Put SetOfNumbers into Bin(NumberInSet) 

Luego de consulta, sólo se puede contar el número de elementos en la Papelera (MyNumber)

Este enfoque funciona bien cuando sus SetOfNumbers raramente cambia, aunque si cambian regularmente, generalmente no es demasiado difícil mantener los contenedores actualizados. Su principal desventaja es que intercambia espacio y tiempo de clasificación inicial para consultas muy rápidas.

Tenga en cuenta que en el algoritmo he ampliado los rangos en SetsOfNumbers enumerando cada número en un rango determinado.

Answer 3

Creo que la construcción de una estructura de árbol acelerará las cosas considerablemente (siempre que tenga suficientes conjuntos y números para comprobar que vale la pena el costo inicial). En lugar de un árbol binario, debería ser un árbol ternario. Cada nodo debe tener nodos izquierdo, medio y derecho, donde el nodo izquierdo contiene un conjunto que es estrictamente menor que el conjunto de nodos, el derecho es estrictamente mayor y el medio tiene solapamiento.

   Set1 
      /| \ 
      / | \ 
      / | \ 
     Set2 Set3 Set4 

Es rápido y fácil de decir si hay superposición en los juegos, ya que sólo tiene que comparar los valores mínimo y máximo para ordenarlos. En el caso simple anterior, Set2 [max] < Set1 [min], Set4 [min]> Set1 [max] y Set1 y Set3 tienen cierta superposición.Esto acelerará su búsqueda porque si el número que está buscando está en el Set1, no estará en Set2 o Set4, y no es necesario que los revise.

Solo quiero señalar que usar un esquema como este solo ahorra tiempo con respecto a la implementación ingenua de verificar cada conjunto si tiene más números para verificar que los que tiene.