¿Estructura de datos para grandes rangos de enteros consecutivos?

Supongamos que tiene un gran rango de enteros consecutivos en la memoria, cada uno de los cuales pertenece exactamente a una categoría. Dos operaciones deben ser O (log n): mover un rango de una categoría a otra, y encontrar los recuentos de categorías para un rango dado.

Estoy bastante seguro de que la segunda operación se resuelve de manera trivial dado una implementación correcta para la primera operación.

Cada entero comienza en una categoría, así que comencé con un conjunto de BST balanceadas. Mover un subárbol de una BST a otra (por ejemplo, mover un rango a una categoría diferente) tiene un tiempo de ejecución equivalente a la combinación de dos BST, que es O (n1 * n2) [ 1 ].

Esto es demasiado lento (en Python, y C no es una opción), y no pude encontrar una manera de aprovechar la estructura inherente de mis datos para crear una operación de fusión BST eficiente.

Ahora estoy viendo AVL, rojo-negro y árboles de intervalo, montones binarios y invitaciones. La comparación de sus propiedades es abrumadora. ¿Qué estructura debo usar?

    Editar (aclaración del problema) : soy flexible en cuanto a cómo almaceno estos valores y creo mis estructuras de datos. Soy inflexible sobre cómo recibo mi aporte, que proviene de otra aplicación, y se parece a lo siguiente: CATEGORY(cat3, I, J) . Mi solución actual crea un árbol con un nodo para cada entero en el rango. Esto es demasiado lento para el tamaño de mi conjunto de datos, por lo que me complace volver a diseñar si se me da un método mejor.

    Cualquier solicitud dada puede mover cualquier rango posible de enteros a cualquier categoría. En otras palabras, los rangos se superponen en el sentido de CATEGORY(cat1, 1, 10) seguido de CATEGORY(cat3, 5, 15) , pero no se superponen en el sentido de que cada número entero estará exactamente en una categoría en un momento dado .

    Hasta donde entendí la pregunta, tiene un rango [A, B] y consultas del formulario –

    1. Asignar un rango particular a una categoría
     P.ej
     R1 R2 C1
     R3 R4 C2
    
    1. Consulte un rango para el número total de elementos en categorías particulares. Por ejemplo, encontrar el número de categorías en R1 R4

    Una implementación simple que use los diccionarios como se indicó anteriormente no funcionaría como describo en este ejemplo:

    Supongamos que tenemos un rango [1000, 5000]

    y hacemos la asignación de la siguiente manera:

     1 2 C1
     2 3 C2
     3 4 C3
     ......
     4999 5000 C4999
    

    Ahora hacemos la siguiente tarea.

     1 5000 C5555
    

    Esto hará una actualización / cambios / eliminación a rangos previamente asignados de los rangos O (N) donde N es el tamaño máximo del rango (B – A)

    D [‘category’] = set (of_all_the_ranges_you_have_in_category)

    En este caso, la eliminación de los rangos anteriores de los conjuntos correspondientes en las categorías C1, C2 … C4999 será necesaria para la última asignación (1 5000 C5555)

    O

    1: {“stop”: 5, “category”: “C1”}, 6: {“stop”: 19, “category”: “C23”},

    Aquí se requerirá la actualización de la categoría para cada valor de inicio (1,2,3,4 …, 4999) para la última asignación (1 5000 C5555)

    Una mejor opción que hará la actualización de rangos en O (lg n) sería árboles de segmentos ( http://en.wikipedia.org/wiki/Segment_tree )

    Para el ejemplo anterior, el árbol de segmentos se verá así.

      1000:5000 | --------------------- | | 1000:3000 3001:5000 | | ---------------- -------------------- | | | | 1000:2000 2001:3000 3001:4000 4001:5000 

    ………………………………………….. …………… …………………………….. ………………………. y así

    Los nodos de hoja tendrán rangos (1: 2, 2: 3, …)

    Puede asignar un “categoría” de valor a cada nodo y, dado un intervalo, recorrer el árbol que divide el intervalo de manera adecuada (por ejemplo, para una división de 2500 a 4500 en 2500: 3000 y 3001: 4500 y proceder en ambas direcciones hasta que se encuentren nodos con rangos coincidentes) .

    Ahora, una cosa interesante es actualizar los hijos de los nodos cuando los necesite. Por ejemplo, no proceda a actualizar a los hijos inmediatamente cuando realice tareas como 1 5000 C5555. Esto se denomina propagación diferida y puede obtener más información aquí ( http://www.spoj.pl/forum/viewtopic.php?f=27&t=8296 ).

    Ahora para la parte de consulta. Si el número de categorías es muy pequeño, puede mantener una tabla de frecuencias en cada nodo y actualizar los rangos cuando sea necesario y la propagación perezosa cuando sea necesario, tendrá que atravesar todo el árbol de hoja a nodo, el conteo y la complejidad se volverán O (norte).

    Creo que puede existir una mejor solución a la consulta. No me viene a la mente.

    ACTUALIZAR Tomemos un pequeño ejemplo.

    Rango [1,8]

    Categorías permitidas {C1, C2}

      1:8 1:4 5:8 1:2 3:4 5:6 7:8 1:1 2:2 3:3 4:4 5:5 6:6 7:7 8:8 

    Cada nodo tendrá 3 campos [category, category_counts [], children_update_required = false]

    1 5 C1

    La consulta se dividirá y la categoría de los nodos 1: 4 se establecerá en C1 y la de children_update_required se establecerá en verdadera, sus hijos no se actualizarán ahora (recuerde actualizar solo cuando sea necesario o una propagación diferida). También la categoría del nodo 5: 5 se establecerá en C1

    3 4 C2

    La consulta se propagará a lo largo del árbol hacia 3: 4 (y en el proceso para alcanzar 3: 4, las categorías 1: 2 y 3: 4 se actualizarán a C1, 1: 4 children_update_required se establecerá en false, 1: 2’s y 3 : 4’s children_update_required se establecerá en verdadero) y ahora actualizará la categoría de 3: 4 a C2 de acuerdo con el requisito actual. A continuación, establecerá children_update requerido de 3: 4 para que sea verdadero para la actualización futura de sus hijos (que ya está configurado en este caso … no hay daño).

    Puede construir una estructura de árbol en matrices de enteros consecutivos con bastante facilidad, lo que debería ayudar con su factor constante. Primero, vuelva a numerar la secuencia para que comience en 0 y determine cuál es la potencia más pequeña de dos que es mayor que el rango de la secuencia.

    Ahora considere el siguiente árbol formado a partir de los números enteros 0-7, que puedo mantener como cuatro arrays, cada arreglo va horizontalmente.

      (all) 0-3 4-7 0-1 2-3 4-5 6-7 0 1 2 3 4 5 6 7 

    Dado un número y un nivel, puedo encontrar un desplazamiento en la matriz para ese nivel, simplemente al desplazar el número una cantidad correcta dependiendo del nivel.

    En cada elemento puedo poner un marcador que dice “mezclado” o que da la categoría para cada elemento en o debajo de ese nodo del árbol. Puedo averiguar en qué categoría está un nodo siguiendo la ruta desde la raíz del árbol a una hoja, deteniéndome tan pronto como veo un nodo que no dice “mixto”. Puedo cambiar la categoría para un intervalo de números en el tiempo lg n, porque tengo a lo sumo dos nodos en cada nivel para representar la categoría: si tuviera tres, dos de ellos tendrían el mismo padre y podría fusionarlos. Puede que tenga que jugar un poco con los bordes para que los rangos adyacentes sean correctos, pero creo que esto funciona en tiempo de lg n.

    Suposiciones

    • Cualquier entero puede pertenecer exactamente a una categoría, por lo que los rangos no se pueden intersectar.
    • Todos los enteros en un rango entrante pertenecen a una categoría.
    • A veces es necesario dividir un rango para mover un subintervalo a una categoría diferente.

    Representa los rangos por (start, end, category) tuplas. Los rangos no se intersecan, así que puedes construir un árbol de ellos. Es mucho más económico que un árbol de enteros individuales. Para ordenar rangos (es decir, nodos), solo puede usar el valor de inicio, ya que es único y no puede pertenecer a otro rango.

    Si tiene que mover un rango [a, b] a otra categoría, debe:

    Escanee su árbol y actualice cada nodo / rango que esté completamente incluido en el rango [a, b] . Es un simple recorrido de profundidad. Durante el recorrido

    • Si current_node.start < a or current_node.start > b , detenga la búsqueda.
    • Si current_node.start >= a and current_node.end > b , debe dividir current_node en dos; [current_node.start, b] pertenecerá a una nueva categoría, el rest será de su categoría original.
    • Si current_node.start < a and current_node.end <= b , se divide al revés.

    La búsqueda de árbol es logarítmica y las divisiones de nodo son O (1).

    Si su árbol alguna vez se fragmenta demasiado, podría considerar fusionar nodos que tengan rangos adyacentes. Este siempre será un padre y un hijo como resultado de una inserción o una división; Las comprobaciones y uniones parecen ser siempre O (1).

    Podemos representar los estados actuales como algo así como:

     0:cat1 200:cat2 500: cat0 700:cat6 800:cat1 

    Esto significa que 0-200 es cat1, 200-500 es cat2, etc. Almacenamos los valores en un árbol de búsqueda binario tecleado en el número inicial. Cada nodo también contendrá categorías de mapeo de diccionario para los conteos de todos los hijos de ese nodo.

    Esos diccionarios deberían facilitar la obtención de los conteos en tiempo O (log). Simplemente debemos agregar los números correctos en las rutas al inicio y al final de la secuencia en cuestión.

    ¿Qué hacemos cuando necesitamos establecer la secuencia XY en la categoría Z?

    1. Determine la categoría actual de YO (logn)
    2. Elimine todos los valores entre X -YO (k), pero como el costo de insertar esos nodos es más costoso, podemos llamarlo O (1) amortizado.
    3. Insertar nuevo nodo en XO (log n)
    4. Actualizar diccionarios de categorías. Solo deberíamos actualizar los padres O (log n) de las secciones afectadas para que sea O (log n)

    En total, esto es O (log n) tiempo.

    Puedes tener un diccionario de python plano de la siguiente forma

     1 : { "stop" : 5, "category" : "C1"}, 6 : { "stop" : 19, "category" : "C23"}, etc 

    Las claves aquí son el comienzo de su rango y los valores contienen el final del rango y la categoría a la que pertenece este rango.

    Debido a que los diccionarios tienen un tiempo constante para acceder a los elementos, puede escribir un código que mueva un rango a otra categoría de manera fácil y eficiente: en el peor de los casos, tendrá que reestructurar de alguna manera su diccionario, si su rango divide los rangos anteriores en dos o más. Más. Por ejemplo, si desea asignar el rango de (4, 8) a otra categoría, terminará con:

     1 : { "stop" : 3, "category" : "C1"}, 4 : { "stop" : 8, "category" : "new category"}, 9 : { "stop" : 19, "category" : "C23"}, etc 

    Encontrar el recuento de categorías es trivial, simplemente recopile todos los rangos deseados en un tiempo constante y cuente las categorías.

    EDITAR: para encontrar con éxito la tecla más baja (más alta) para comenzar a realizar cálculos / alteraciones, también necesita una lista de python con todas las teclas ordenadas y el módulo bisect. Esto ayudará a ubicar el índice en la lista para “poner” el inicio del rango en tiempo O (logn), luego todo se puede hacer en tiempo constante, excepto el tiempo O (n) necesario para insertar la nueva clave en el Lista con bisect.insort_left.