Encontrar el número de eventos simultáneos dadas las horas de inicio y finalización

Question

Tengo un conjunto masivo de eventos (~ 10) caracterizado por una hora de inicio y finalización. Con un tiempo, quiero encontrar cuántos en esos eventos estaban en curso en ese momento.

¿Qué tipo de estructura de datos sería útil en esta situación? Las operaciones que necesito para ser rápido son:

1. Inserción de nuevos eventos, por ejemplo, {start: 100000 milliseconds, end: 100010 milliseconds}.
2. Consultando el número de eventos concurrentes en un momento dado.

---

Actualización: Alguien puso una bandera geometría computacional en esto, por lo que figura que debería reformular esto en términos de geometría computacional. Tengo un conjunto de intervalos de 1 dimensión y quiero calcular cuántos de esos intervalos se cruzan con un punto dado. La inserción de nuevos intervalos debe ser rápida.

Answer 1

Está buscando interval tree.

• construcción: O(n log n), donde n es el número de intervalos
• Consulta: O(m+log n), donde m es el número de resultados de la consulta y n es el número de intervalos
• Espacio: O(n)

Answer 2

Supongamos que tenemos un conjunto ordenado (por ejemplo, una estructura de datos balanced binary search tree o skip list) con N elementos. Además, supongamos que el conjunto ordenado tiene O (log N) Tiempo de búsqueda, O (log N) Tiempo de de inserción, y O el uso de espacio (N) (estos son supuestos razonables, ver red-black tree, por ejemplo).

Una posibilidad es tener dos conjuntos ordenados, bystart y byend, respectivamente, ordenados por los tiempos de inicio y fin de los eventos.

Para encontrar el número de eventos que están en curso en el momento t, piden byend para el primer intervalo de tiempo, cuyo fin es mayor que t: una operación de búsqueda O (log N). Llame a la hora de inicio de este intervalo left. Ahora, pregunte bystart por el número de intervalos cuyo tiempo de inicio es mayor o igual que left y menor que t. Esto es O (registro N + M), donde M es el número de dichos intervalos. Por lo tanto, el tiempo total para una búsqueda es O (registro N + M).

La inserción fue O (registro N) para conjuntos ordenados, que tenemos que hacer una vez para cada conjunto ordenado. Esto hace que el tiempo total para la operación de inserción O (registro N).

construcción de esta estructura a partir de cero justo consiste en N operaciones de inserción, por lo que el tiempo total de construcción es O (N log N).

el uso del espacio es O (N) para cada conjunto ordenado, por lo que el uso de espacio total es O (N).

Resumen:

• Insertar: O (log N), en donde N es el número de intervalos de
• Construct: O (N log N)
• Consulta: O (registro N + M), donde M es el número de resultados
• Spac e: O (N)

Answer 3

sólo para añadir a las otras respuestas, dependiendo de la longitud de tiempo y el nivel de detalle deseado, simplemente podría tener una serie de contadores. Por ejemplo, si el período de tiempo es de 24 horas y la granularidad deseada es de 1 milisegundo, habrá 86,400,000 celdas en el conjunto. Con un byte de 4 bytes por celda (que es suficiente para contener 10^9), eso será menos de 700 MB de RAM, frente a las soluciones basadas en árboles que tomarían al menos (8 + 8 + 4 + 4) * 10^9 = 24 GB de RAM para dos punteros más dos entradas por nodo de árbol (ya que 32 bits de memoria direccionable son insuficientes, necesitaría 64 bits por puntero). Puede usar swap, pero esto ralentizará algunas consultas considerablemente.

También puede utilizar esta solución si solo le importan las últimas 24 horas de datos, por ejemplo, al usar la matriz como un búfer circular. Además de la limitación de tiempo y granularidad, el otro inconveniente es que el tiempo de inserción de un intervalo es proporcional a la duración del intervalo, por lo que si la duración del intervalo no tiene límites, podría tener problemas. Las consultas, por otro lado, son una única búsqueda de matriz.

Answer 4

(Ampliación de las respuestas de tskuzzy y la bola de nieve)

Un árbol binario de búsqueda equilibrado tiene sentido, excepto que los requisitos de memoria sería excesivo para establecer sus datos. Un B-tree sería mucho más eficiente con la memoria, aunque más complicado a menos que pueda usar una biblioteca.

Mantenga dos árboles, uno de los tiempos de inicio y uno de los tiempos de finalización. Para insertar un evento, agregue la hora de inicio al árbol de horas de inicio y la hora de finalización al árbol de tiempos finales. Para consultar el número de eventos activos en el tiempo T, busque el árbol de inicio para averiguar cuántos tiempos de inicio son menores que T, y busque en el árbol de tiempo final para averiguar cuántos tiempos finales son menores que T. Reste el número de horas de finalización desde el número de horas de inicio, y esa es la cantidad de eventos activos.

Las inserciones y las consultas deben tomar el tiempo O (log N).

Algunos comentarios:

• La forma en que han expresado la pregunta, sólo se preocupan por el número de eventos activos, no el que los acontecimientos estaban activos. Esto significa que no necesita realizar un seguimiento de la hora de inicio de la hora de finalización. Esto también hace que sea más fácil evitar el término "+ M" en las consultas citadas por respuestas anteriores.

• Tenga cuidado con la semántica exacta de su consulta. En particular, ¿un evento cuenta como activo en el tiempo T si comienza en el tiempo T? Si termina en el momento T? Las respuestas a estas preguntas afectan si usa < o < = en ciertos lugares.

• Do no utilice una estructura de datos "establecida", porque casi seguramente desea permitir y contar duplicados. Es decir, más de un evento podría comenzar y/o finalizar al mismo tiempo. Un conjunto típicamente ignoraría los duplicados. Lo que está buscando es un "multiset" (a veces llamado "bolsa").

• Muchos árboles de búsqueda binaria no son compatibles con las consultas de "número de elementos < T" de fábrica. Pero es fácil agregar esta funcionalidad almacenando un tamaño en cada nodo.