Tengo un conjunto de intervalos de tiempo In = (an, bn). Necesito funcionar con un montón de escritos mira donde me dan un tiempo t y la necesidad de volver rápidamente los intervalos que contienen t, por ejemplo, los intervalos tales que un < = t = bn <.Estructura de datos para búsqueda de intervalo de tiempo rápido
¿Qué es una buena estructura de datos o algoritmo para esto?
si importa, en mi caso el un y bn son enteros.
Lo que estás buscando es un Interval Tree (que es un tipo de Range Tree).
Estos tienen un tiempo de búsqueda logarítmica como otras estructuras de árbol (por ejemplo, árboles RB), por lo que debería ver un rendimiento comparable a utilizar algo como un mapa de árbol de Java o un mapa de STL.
Hay una implementación en C++ de un árbol de intervalos en http://www.mit.edu/~emin/source_code/cpp_trees/index.html, enlazado desde http://stackoverflow.com/questions/212808/help-finding-c-interval-tree-algorithm-implementation –
Nice. Gracias por el enlace! – tgamblin
El enlace para [Implementación de C#] (http://www.emilstefanov.net/Projects/RangeSearchTree.aspx) ya no funciona. – krlzlx
Esto es básicamente una pregunta de partición de espacio. Tiene un gran espacio con contenedores y un punto específico en ese espacio, ¿a qué contenedores toca? Muchos juegos tienen que resolver este problema, por lo que no sería una mala idea comenzar allí. Busque artículos sobre "detección de colisión de fase amplia".
La forma más sencilla de hacerlo es dividir el espacio de números en un número constante de piezas. Cada pieza sabe qué conjuntos se cruzan con ella, algo que usted calcula cada vez que se agrega un nuevo conjunto. Ahora, en lugar de probar cada conjunto individual cuando tiene un punto, solo necesita verificar los conjuntos contenidos en la pieza en la que se encuentra el punto.
Otro algoritmo general y eficiente utilizado es Partición de espacio binario. Este algoritmo subdivide tu espacio en dos lados. Cada lado sabría qué conjuntos se cruzan con él. Puede repetir este proceso recursivamente con la precisión deseada (aunque no tiene sentido crear una subdivisión más pequeña que el rango de su conjunto más pequeño).
Su problema es unidimensional, por lo que es un poco más simple que los problemas de particionamiento de espacio que se encuentran en la mayoría de los juegos. Puede tener solo una BST simple y en cada hoja recordar la lista de intervalos a la izquierda de la hoja.
si tenía intervalos A (0, 10) y B (5, 15), entonces las hojas del árbol serían (0 con lista vacía), (5 con A), (10 con A, B) y (15 con B).
Le invitamos a revisar la C# implementation I've posted on CodePlex for IntervalTree que solucionan este problema exactamente.
Ido.
¿Restricciones de memoria? – ChaosPandion
Sin restricciones de memoria –
Soluciones Java: https://stackoverflow.com/questions/13399821/data-structures-that-can-map-a-range-of-keys-to-a-value – Vadzim