¿Un algoritmo de intersección de rango mejor que O (n)?
https://stackoverflow.com/questions/303591
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
La intersección de rango es un problema simple, pero no trivial.
Ya se ha respondido dos veces:
Las primeras soluciones son O (n) y la segunda solución es para una base de datos (que es menor que O (n), por supuesto).
Tengo el mismo problema, pero para una gran ny no estoy dentro de una base de datos.
Este problema parece ser muy similar a Almacene puntos 2D para recuperarlos rápidamente dentro de un rectángulo pero no veo cómo se mapea.
Entonces, ¿en qué estructura de datos almacenaría el conjunto de rangos, de modo que una búsqueda en un rango cuesta menos que O (n)? (Crédito adicional por usar bibliotecas disponibles para Java)
EDIT:
Quiero obtener un subconjunto de todos los rangos de intersección, lo que significa que el rango de búsqueda podría intersecar múltiples rangos.
El método que debe ser menor que O (n) en Java es:
public class RangeSet {
....
public Set<Range> intersects(Range range);
....
}
Donde Range es solo una clase que contiene un par de int start y end.
Esta no es una pregunta imposible, ya tengo la solución, solo quería ver si había una forma más estándar / simple de hacerlo
Solución
El enfoque estándar es utilizar un árbol de intervalos .
En informática, un árbol de intervalos es una estructura de datos de árbol para contener intervalos. Específicamente, le permite a uno encontrar eficientemente todos los intervalos que se superponen con cualquier intervalo o punto dado. A menudo se usa para consultas de ventanas, por ejemplo, para encontrar todas las carreteras en un mapa computarizado dentro de una ventana rectangular, o para encontrar todos los elementos visibles dentro de una escena tridimensional. Una estructura de datos similar es el árbol de segmentos.
La solución trivial es visitar cada intervalo y probar si se cruza con el punto o intervalo dado, lo que requiere un tiempo O (n), donde n es el número de intervalos en la colección. Dado que una consulta puede devolver todos los intervalos, por ejemplo, si la consulta es un intervalo grande que intersecta todos los intervalos de la colección, esto es asintóticamente óptimo; sin embargo, podemos hacerlo mejor si consideramos algoritmos sensibles a la salida, donde el tiempo de ejecución se expresa en términos de m, el número de intervalos producidos por la consulta. Los árboles de intervalo tienen un tiempo de consulta de O (log n + m) y un tiempo de creación inicial de O (n log n), mientras que limitan el consumo de memoria a O (n). Después de la creación, los árboles de intervalos pueden ser dinámicos, permitiendo la inserción y eliminación eficiente de un intervalo en O (log n). Si los puntos finales de los intervalos están dentro de un rango entero pequeño (por ejemplo, en el rango [1, ..., O (n)]), existen estructuras de datos más rápidas [1] con tiempo de preprocesamiento O (n) y tiempo de consulta O ( 1 + m) para informar intervalos m que contienen un punto de consulta dado.
Otros consejos
Editar: Parece que esta solución es más o menos un árbol de intervalos . Se puede encontrar una implementación más completa de un árbol de intervalos aquí .
class TreeNode
{
public:
long pivot;
List<Range> leaves; //Any ranges that intersect the pivot
TreeNode left; //Tree nodes that fall to the left of the pivot
TreeNode right; //Tree nodes that fall to the right of the pivot
};
Preparación O (n log n):
- Crear la lista de rangos
- Elija los puntos de pivote (posiblemente utilizando una lista ordenada de las fechas de finalización). ??
- Construye tu árbol.
Búsqueda:
- Use la búsqueda binaria para encontrar el primer pivote que es > = TestRange.End
-
Atraviesa el árbol hasta el pivote > TestRange.Start
2a. Agregue las hojas a su resultado.
Ejemplo:
Rangos:
- 0 - 2
- 1 - 2
- 2 - 3
- 1 - 4
- 2 - 4
- 0 - 5
- 4 - 5
- 2 - 6
- 3 - 7
Árbol:
4
--------------+------------------
3 | 7
| 1-4 |
| 2-4 |
| 0-5 |
| 4-5 |
---------+------ --------+--------
2 | null 6 | null
-----+---- 2-3 ----+---- 3-7
null | null null | null
0-2 2-6
1-2
Rangos no superpuestos:
Preparación O (n log n):
- Hacer una matriz / vector de los rangos.
- Ordene el vector al final del rango (rompa los lazos al ordenar por el inicio del rango)
Búsqueda:
- Utilice la búsqueda binaria para encontrar el primer rango con un valor final de > = TestRange.Start
-
Iterador comenzando en la búsqueda binaria hasta que encuentre un Start > TestRange.End:
2a. Si el rango si el rango actual está dentro de TestRange, agréguelo a su resultado.
Esto depende de su problema exacto, en la pregunta vinculada, los rangos donde son distintos, no hay una parte común, y el rango buscado podría abarcar múltiples rangos. Si su problema es el mismo, es realmente fácil: Tome una matriz de los rangos, ordénelos por sus valores más bajos (ya que no se superponen, este sería también el mismo orden que el ordenado por sus valores superiores).
Ahora solo haga un binsearch para el valor inferior de su objetivo (o más pequeño si no es exacto) y uno para el valor superior del objetivo (o más grande si no es exacto). Los índices resultantes son los rangos que están cubiertos. Debe verificar si los rangos en los índices están incluidos o excluidos, pero eso son solo 2 verificaciones. Complejidad general O (log n).
Rangos superpuestos:
Preparación O (n log n):
- Hacer una matriz / vector de los rangos.
- Ordene el vector al final del rango (rompa los lazos al ordenar por el inicio del rango)
-
Crea un segundo vector de entradas. Esto representa el punto en el que puede dejar de buscar.
int stop[size]; stop[size-1] = Ranges[size - 1].start; for (int i = size - 2; i >= 0; i--) { stop[i] = min(Ranges[i].start, stop[i+1]); }
Búsqueda:
- Utilice la búsqueda binaria para encontrar el primer rango con un valor final de > = TestRange.Start
-
Iterador comenzando en la búsqueda binaria hasta la parada [i] > TestRange.End:
2a. Si el rango si el rango actual está dentro de TestRange, agréguelo a su resultado.
Si los rangos se superponen, y uno quiere recuperar todos los rangos que se superponen (o contienen) un rango objetivo dado, la mayoría de las soluciones anteriores no parecen funcionar.
Como algunos han señalado, si (en el peor de los casos) todos los rangos se cruzan con el rango objetivo (por ejemplo, si el rango objetivo es {0..MAXINT} o similar) entonces por supuesto, se necesita O (n) para devolver los n rangos.
¿Pero no es el caso interesante y típico / promedio, donde solo un porcentaje muy pequeño de los n rangos totales se cruzan con el rango objetivo? Llame al número que do se cruzan " m " - en ese caso, es posible que pueda hacerlo tan bien como O (m). Y si n = 10 ^ 9 ym = 10, esa es una diferencia decisiva.
Considere el caso simple de un documento de texto que tiene varias regiones marcadas para su " tipo " - tal vez desee encontrar todas las unidades marcadas que contienen o intersecan un rango de texto contiguo dado (por ejemplo, un párrafo). En HTML, XML o similares, estos solo pueden ser ancestros de los nodos de texto que contienen al menos algunos caracteres del rango objetivo. En representaciones típicas con punteros principales en cada nodo, eso es O (m), mucho mejor que O (n), especialmente porque m es (para rangos objetivo cortos o sincrónicos) simplemente la profundidad de anidación del árbol, que tiende a ser incluso menor que En (n) porque los documentos XML grandes en la práctica se vuelven más frondosos que profundos.
El caso interesante es más difícil: ¿qué pasa si sus " elementos " no forma un árbol como en XML, pero puede superponerse como en MECS, CLIX, LMNL y algunos otros sistemas? Todavía desea encontrar todas las regiones / '' elementos '' que se superponen a su objetivo, pero no son tan fáciles de organizar.
Por otro lado, deberías poder hacerlo muy bien porque los rangos marcados en muchas aplicaciones son con frecuencia pequeños: hay muchas más palabras, oraciones y párrafos en un libro que capítulos. Entonces, aunque puede haber una gran cantidad de rangos que comienzan antes del objetivo y una gran cantidad que termina después de él, la intersección será muy pequeña en promedio.
Creo que a eso se refería el interrogador original, y me temo que no vi una respuesta que aborde ese problema. Si no se trata de la pregunta original, me gustaría plantearla como una nueva pregunta.
Parece que necesita una clase que implemente la interfaz SortedSet. TreeSet es la implementación que se incluye con la API principal.
Haga que un conjunto contenga los rangos ordenados por el valor más bajo y otro por el valor más alto.
Luego puede implementar el equivalente del algoritmo de la base de datos utilizando los conjuntos en memoria.
En cuanto a si esto es realmente más rápido que O (n), no podría decirlo.
Así como un árbol cuádruple funciona para un conjunto de puntos 2d, un árbol binario simple debería funcionar para este caso. Construye un árbol con tus rangos.
Para explicar más a fondo: Cada nodo en el árbol contiene dos enteros, el principio y el final del rango, y los dos hijos si no es un nodo hoja. Para encontrar los rangos que abarca su rango de entrada, luego comience en la parte superior del árbol
- if the node range intersects the input range:
- if it's a leaf node, then add the range to your result list
- if it's not a leaf node, then traverse down to the child nodes and repeat this process.
Debería ser O (logN)
Más detalles: El árbol binario se estructuraría como una versión 1-d de un árbol cuádruple. Cada nodo tendría tres enteros (lo siento, dije dos arriba, pero ahora me doy cuenta de que necesita tres), el más bajo representa el valor más bajo del rango más bajo que está debajo de este nodo, el más alto representa el valor más alto del rango más alto que está debajo de este nodo y el pivote. El hijo izquierdo abarcaría desde el nodo más bajo hasta su pivote. El elemento secundario derecho abarcaría desde el pivote de este nodo hasta el más alto de este nodo. Si solo hay un rango que va desde "más bajo" al "más alto", no tendría un pivote y esto sería una hoja. Lo ideal sería elegir los pivotes para cada nodo para mantener el árbol equilibrado.
Cuando tuve este problema, utilicé una matriz ordenada de rangos y una búsqueda binaria para buscar intersecciones. Este es (creo) rendimiento O (log n), con un poco de sobrecarga para lidiar con rangos superpuestos.
La respuesta a su pregunta es, creo, derivable del código a continuación, pero deteniéndose antes de la inserción. Presento todo el código para evitar confusiones por el contexto diferente: necesitaba insertar un rango de puntos de código Unicode en una lista de rangos de puntos de código.
- EDITAR -
Adaptar el siguiente código para determinar las intersecciones de múltiples rangos implica una búsqueda trivial hacia adelante desde el punto de inserción hasta que se encuentre un rango que ya no se cruza.
- EDICIÓN FINAL -
La clase Range contiene:
final int lower; // lower end of range
final int upper; // upper end of range
public int compareTo(Object obj) {
if(obj==null) { return -1; }
Range oth=(Range)obj;
if(lower<oth.lower) { return -1; }
if(lower>oth.lower) { return 1; }
if(upper<oth.upper) { return -1; }
if(upper>oth.upper) { return 1; }
return 0;
}
Inserción de rango:
public Builder addRange(int fir, int las) {
if(fir!=-1) { fir&=0x001FFFFF; }
if(las!=-1) { las&=0x001FFFFF; }
if(codepoints==null || codepoints.length==0) {
codepoints=new Range[]{new Range(fir,las)};
}
else {
int idx=Range.findChar(codepoints,fir);
int ins=(idx<0 ? -(idx+1) : idx);
if(idx<0) {
if (ins>0 && fir==(codepoints[ins-1].upper+1)) { idx=(ins-1); } // new range adjoins the following range (can't overlap or idx would be >=0)
else if(ins<codepoints.length && las>=(codepoints[ins ].lower-1)) { idx=ins; } // new range overlaps or adjoins the following range
}
if(idx<0) {
codepoints=(Range[])Util.arrayInsert(codepoints,ins,new Range(fir,las));
}
else {
boolean rmv=false;
for(int xa=(idx+1); xa<codepoints.length && codepoints[xa].lower<=las; xa++) {
if(las<codepoints[xa].upper) { las=codepoints[xa].upper; }
codepoints[xa]=null;
rmv=true;
}
if(codepoints[idx].lower>fir || codepoints[idx].upper<las) {
codepoints[idx]=new Range((codepoints[idx].lower < fir ? codepoints[idx].lower : fir),(codepoints[idx].upper>las ? codepoints[idx].upper : las));
}
if(rmv) { codepoints=Range.removeNulls(codepoints); }
}
}
return this;
}
Búsqueda binaria:
static int findChar(Range[] arr, int val) {
if(arr.length==1) {
if (val< arr[0].lower) { return -1; } // value too low
else if(val<=arr[0].upper) { return 0; } // value found
else { return -2; } // value too high
}
else {
int lowidx=0; // low index
int hghidx=(arr.length-1); // high index
int mididx; // middle index
Range midval; // middle value
while(lowidx<=hghidx) {
mididx=((lowidx+hghidx)>>>1);
midval=arr[mididx];
if (val< midval.lower) { hghidx=(mididx-1); } // value too low
else if(val<=midval.upper) { return mididx; } // value found
else { lowidx=(mididx+1); } // value too high
}
return -(lowidx+1); // value not found.
}
}
