python - recorrer - Estructura de datos para grandes rangos de enteros consecutivos

range python 3 (5)

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 determinado.

Estoy bastante seguro de que la segunda operación se resuelve trivialmente, dada la implementación correcta para la primera operación.

Cada número 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 mirando AVL, rojo-negro, y árboles de intervalo, montones binarios y tramposos. Comparar sus propiedades es abrumador. ¿Qué estructura debo usar?

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

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 entero estará en exactamente una categoría en un momento dado .

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 con la clave del número inicial. Cada nodo también contendrá una categoría de asignación de diccionario a los recuentos de todos los hijos de ese nodo.

Esos diccionarios deberían facilitar la obtención de los recuentos en el tiempo O (log). Simplemente tenemos que agregar los números correctos en las rutas al comienzo y a la parada de la secuencia en cuestión.

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

Determine la categoría actual de YO (logn)
Elimine todos los valores entre X-YO (k), pero dado que el costo de insertar esos nodos es más caro, podemos llamarlo O (1) amortizado.
Inserte un nuevo nodo en XO (log n)
Actualizar diccionarios de recuento de categorías. Solo deberíamos actualizar los padres O (log n) de las secciones afectadas, así que esto es O (log n)

En total, este es el tiempo O (log n).

Por lo que entendí, la pregunta tiene un rango [A, B] y consultas del formulario -

Asignar un rango particular a una categoría

E.g. R1 R2 C1 R3 R4 C2

Consulte un rango para la cantidad total de elementos en categorías particulares. Por ejemplo, encontrar el recuento de categorías en R1 R4

Una implementación simple usando diccionarios como se da arriba 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á que la actualización / cambios / eliminación a los rangos previamente asignados de los rangos O (N) donde N es el tamaño máximo de rango (B - A)

D [''category''] = set (of_all_the_ranges_you_have_in_category)

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

1: {"detener": 5, "categoría": "C1"}, 6: {"detener": 19, "categoría": "C23"},

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

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

Para el ejemplo anterior, el árbol de segmentos se verá algo como esto

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 una "categoría" de valor a cada nodo y obtener un intervalo que recorra el árbol dividiendo el intervalo de forma apropiada (por ejemplo, para 2500 a 4500 dividir en 2500: 3000 y 3001: 4500 y continuar en ambas direcciones hasta encontrar nodos con rangos coincidentes) .

Ahora, algo interesante es actualizar a los hijos de los nodos cuando los necesite. Por ejemplo, no continúe actualizando los hijos inmediatamente cuando realice asignaciones como 1 5000 C5555. Esto se llama propagación diferida y puede obtener más información al respecto 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 propagarse perezosamente cuando sea necesario; de lo contrario, tendrá que atravesar todo el árbol de hoja en nodo, el recuento y la complejidad se convertirán en O (norte).

Creo que puede existir una mejor solución para consultar. No viene a mi 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 nodos 1: 4 se establecerá en C1 y children_update_required se establecerá en verdadero, sus elementos secundarios no se actualizarán ahora (recuerde la actualización solo cuando sea necesario o la propagación diferida). También la categoría del nodo 5: 5 se establecerá en C1

3 4 C2

Query se propagará a lo largo del árbol hacia 3: 4 (y en el proceso para alcanzar las categorías 3: 4, 1: 2 y 3: 4 se actualizará a C1, 1: 4''s children_update_required se establecerá en false, 1: 2''s y 3 : 4 child_update_required se establecerá en verdadero) y ahora actualizará la categoría de 3: 4 a C2 según el requisito actual. A continuación, establecerá que children_update requerido de 3: 4 sea verdadero para la actualización futura de sus hijos (que ya está configurado en este caso ... sin daños).

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

Ahora considere el siguiente árbol formado a partir de los números enteros 0-7, que puedo contener como cuatro matrices, cada matriz va en sentido horizontal.

(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 una compensación en la matriz para ese nivel, simplemente cambiando el número a la derecha una cantidad dependiendo del nivel.

En cada elemento puedo poner un marcador que dice "mezclar" o da la categoría para cada elemento en o debajo de ese nodo del árbol. Puedo averiguar en qué categoría se encuentra un nodo siguiendo la ruta desde la raíz del árbol hasta una hoja, deteniéndome tan pronto como veo un nodo que no dice "mixto". Puedo cambiar la categoría por un intervalo de números en el tiempo lg n, porque tengo como máximo 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 tengas que juguetear un poco con los bordes para obtener rangos vecinos correctos, pero creo que esto funciona en tiempo lg n.

Suposiciones

Cualquier número entero puede pertenecer exactamente a una categoría, por lo que los intervalos no se pueden intersecar.
Todos los enteros en un rango entrante pertenecen a una categoría.
A veces necesitas dividir un rango para mover un subrango a una categoría diferente.

Representar rangos por (start, end, category) tuplas de (start, end, category) . Los rangos no se cruzan para que pueda construir un árbol de ellos. Es mucho más económico que un árbol de enteros individuales. Para ordenar rangos (es decir, nodos) puede simplemente 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 recorrido transversal simple en 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 resto 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 se vuelve demasiado fragmentado, podría considerar fusionar nodos que tienen rangos adyacentes. Esto siempre será un padre y un hijo resultantes de un inserto o una división; los controles y las uniones parecen ser siempre O (1).

Puede tener un diccionario de Python simple de la siguiente forma

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

Las teclas aquí son el inicio de su rango y los valores contienen el final del rango y la categoría en la que se encuentra.

Debido a que los diccionarios tienen un tiempo constante para acceder a los elementos, puede escribir un código que mueve un rango a otra categoría de manera fácil y eficiente: en el peor de los casos, tendrá que reestructurar su diccionario de alguna manera, si su rango divide los rangos anteriores en dos o 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 reúna todos los rangos deseados en 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 simple de Python con todas las claves ordenadas y el módulo bisecado. Esto ayudará a ubicar el índice en la lista para "poner" el inicio del rango en el tiempo O (logn), luego todo se puede hacer en tiempo constante, excepto por el tiempo O (n) necesario para insertar la nueva clave en el lista con bisect.insort_left.