¿Qué estructura de datos puedo usar para almacenar y recuperar rangos de valores discretos?

Question

Tengo un programa de JavaScript en el que administraré muchos rangos de enteros. En este contexto, un rango es simplemente un valor inicial y uno final (o cualquier cosa equivalente, como un valor de inicio y un valor de longitud), con una referencia a otro objeto. Los rangos se pueden superponer y pueden ser idénticos (aunque el objeto al que se hace referencia será diferente).

Los posibles valores inicial y final están entre 0 y 4294967295 (2 - 1 ó 0xFFFFFFFF), aunque hay varios grandes "agujeros" en el dominio que nunca cubrirá ningún rango, ni siquiera parcialmente. La mayoría de los rangos serán muy pequeños en comparación con el dominio de las posibilidades: espero que la abrumadora mayoría tenga una longitud inferior a 2000.

Mi caso de uso más importante para esta estructura será buscar todos los rangos que contienen un determinado valor entero. La mayoría de las veces, espero que la búsqueda falle (no habrá rango que contenga el valor dado).

De lo contrario, obviamente también necesitaré agregarle elementos (a menudo) y borrar elementos de él (rara vez). De vez en cuando, también, necesitaré encontrar todos los rangos que se superpongan a un rango dado, en lugar de todos los rangos que contienen un solo valor.

¿Qué tipo de estructura de datos puedo usar para eso? Una búsqueda lineal en una lista de rangos no es práctica porque las búsquedas fallan la mayor parte del tiempo; y necesito hacer búsquedas muy, muy a menudo.

Answer 1

Me gusta System.Tuple para algo como esto [o F # enumera pero pocas personas saben F #].

Si el rango es continuo, hace que sea sencillo tener los enteros de inicio y fin como la tupla Tuple nums = (inicio, fin), teniendo la tupla con un inicio como la primera entrada de una tupla y el enumere ya que el segundo puede funcionar para usted, Tuple nums = ((inicio, fin), Lista).

Answer 2

Si almacena el inicio y el final de todos los rangos en una lista como un mapa de vuelta al índice de rango, puede hacerlo en orden n. es decir, mylist = [{45: rango1}, {47: rango2}, {55: rango1}, {57: rango2}] LUEGO puedes escanear la lista y establecer un booleano verdadero la primera vez que ves una etiqueta y falsa la segunda vez que lo ves cuando encuentras un número más alto que el tuyo, puedes saber en qué rango te encuentras. Puede usar bisect para insertar O (logn), mientras que las eliminaciones y las inserciones son O (n). ¡Buena suerte! ~ Ben

Answer 3

árbol binario donde la clave es el valor inicial (bajo). Una vez que encuentre una clave, podrá verla de par en par (más alta y más baja) con bastante facilidad.

Answer 4

INTENTO 1:

mantener 2 árboles binarios, uno para los valores de inicio y uno de los valores finales. Haga que sus nodos para ambos árboles (o simplemente el 'extremo') tengan una propiedad que haga referencia a rangos únicos mediante algún id (el valor de inicio del rango).

Realice una búsqueda binaria en el árbol de 'inicio' para limitar la lista a los intervalos donde el inicio es menor o igual que su valor de búsqueda. Haz lo mismo en el árbol 'final' donde el valor es mayor o igual que el valor de búsqueda. Encuentre la intersección de los nodos de ambos árboles, y esos rangos contienen su valor de búsqueda.

Puede encontrar la intersección usando un mapa/conjunto de hash para un rendimiento óptimo.

INTENTO 2:

Lo que si se mantenía una lista de hash para los intervalos en los que las claves son las primeras sin embargo la cantidad de bits que son compartidos tanto por los valores inicial y final?

Por lo tanto, si el inicio es '11001101' y el final es '11010010', la clave es '110'. Cada tecla se correlacionaría con una lista de rangos (inicio y final) que comparten la clave.

Al buscar un valor para ver en qué rangos se encuentran, por ejemplo '00101111', tendría que buscar en la lista hash para n valores diferentes más o menos, donde n es el número de bits (32 en su caso). En este caso, buscaría '00101111', '0010111', '001011', y así sucesivamente. Para cada golpe, deberías verificar que el valor de búsqueda esté dentro del rango.

A primera vista, me parece que, en promedio, por cada golpe que reciba, la mitad serán falsos positivos, pero eso no debería importar si el número de visitas es pequeño, y cuanto más grandes son las teclas menos golpes que debería obtener.

Existe un pequeño problema para, por ejemplo, un inicio de '00101110' y el final de '01100111' porque la clave sería '0', lo que significa que habrá un número significativo de 'falsos positivos'. Sería mejor si hubiera 2 claves diferentes, '001' y '01', aunque no estoy seguro del algoritmo particular que necesitaría para codificar esta optimización. Si los rangos son lo suficientemente pequeños y este problema se puede resolver o pasar por alto, entonces puede obtener búsquedas muy rápidas, ya que la mayoría de las claves serán relativamente largas y no coincidirán con las búsquedas.