Pregunta
Tengo una clase que representa un intervalo. Esta clase tiene dos propiedades '' inicio '' y "fin" de un tipo comparable. Ahora estoy buscando un algoritmo eficiente para tomar la unión de un conjunto de tales intervalos.
Gracias de antemano.
Solución
Ordénelos por uno de los términos (inicio, por ejemplo), luego verifique las superposiciones con su vecino (a la derecha) a medida que avanza por la lista.
class tp():
def __repr__(self):
return '(%d,%d)' % (self.start, self.end)
def __init__(self,start,end):
self.start=start
self.end=end
s=[tp(5,10),tp(7,8),tp(0,5)]
s.sort(key=lambda self: self.start)
y=[ s[0] ]
for x in s[1:]:
if y[-1].end < x.start:
y.append(x)
elif y[-1].end == x.start:
y[-1].end = x.end
Otros consejos
Utilice el algoritmo línea de barrido . Básicamente, clasifica todos los valores en una lista (mientras mantiene si es el comienzo o el final del intervalo junto con cada elemento). Esta operación es O (n log n). Luego, realiza un solo ciclo a lo largo de los elementos ordenados y calcula los intervalos O (n).
O (n log n) + O (n) = O (n log n)
Resulta que este problema se ha resuelto, muchas veces, en diferentes niveles de fantasía, bajo nomenclatura (s): http://en.wikipedia.org/wiki/Interval_tree , http: //en.wikipedia.org/wiki/Segment_tree , y también 'RangeTree'
(ya que la pregunta de OP implica grandes recuentos de intervalos, estas estructuras de datos son importantes)
en términos de mi propia elección de selección de biblioteca de Python:
-
De las pruebas, descubro que lo que más lo clava en términos de ser completo y actual de Python (sin descomposición de bits): las clases 'Intervalo' y 'Unión' de SymPy, vea: http://sympystats.wordpress.com/2012/03/30/simplifying-sets/
-
Otra opción atractiva, un rendimiento superior pero una opción menos rica en funciones (por ejemplo, no funcionó en la eliminación del rango de punto flotante): https://pypi.python.org/pypi/Banyan
Finalmente: busque en SO mismo, en cualquiera de IntervalTree, SegmentTree, RangeTree, y encontrará respuestas / enganches más en abundancia
El algoritmo por geocar falla cuando:
s=[tp(0,1),tp(0,3)]
No estoy muy seguro, pero creo que esta es la forma correcta:
class tp():
def __repr__(self):
return '(%.2f,%.2f)' % (self.start, self.end)
def __init__(self,start,end):
self.start=start
self.end=end
s=[tp(0,1),tp(0,3),tp(4,5)]
s.sort(key=lambda self: self.start)
print s
y=[ s[0] ]
for x in s[1:]:
if y[-1].end < x.start:
y.append(x)
elif y[-1].end == x.start:
y[-1].end = x.end
if x.end > y[-1].end:
y[-1].end = x.end
print y
También lo implementé para restar:
#subtraction
z=tp(1.5,5) #interval to be subtracted
s=[tp(0,1),tp(0,3), tp(3,4),tp(4,6)]
s.sort(key=lambda self: self.start)
print s
for x in s[:]:
if z.end < x.start:
break
elif z.start < x.start and z.end > x.start and z.end < x.end:
x.start=z.end
elif z.start < x.start and z.end > x.end:
s.remove(x)
elif z.start > x.start and z.end < x.end:
s.append(tp(x.start,z.start))
s.append(tp(z.end,x.end))
s.remove(x)
elif z.start > x.start and z.start < x.end and z.end > x.end:
x.end=z.start
elif z.start > x.end:
continue
print s
Ordenar todos los puntos. Luego, revise la lista incrementando un contador para " inicio " puntos, y decrementarlo para " fin " puntos. Si el contador alcanza 0, entonces es realmente un punto final de uno de los intervalos en la unión.
El contador nunca será negativo y llegará a 0 al final de la lista.
Para encontrar el total de la unión de intervalos en c ++
#include <iostream>
#include <algorithm>
struct interval
{
int m_start;
int m_end;
};
int main()
{
interval arr[] = { { 9, 10 }, { 5, 9 }, { 3, 4 }, { 8, 11 } };
std::sort(
arr,
arr + sizeof(arr) / sizeof(interval),
[](const auto& i, const auto& j) { return i.m_start < j.m_start; });
int total = 0;
auto current = arr[0];
for (const auto& i : arr)
{
if (i.m_start >= current.m_end)
{
total += current.m_end - current.m_start;
current = i;
}
else if (i.m_end > current.m_end)
{
current.m_end = i.m_end;
}
}
total += current.m_end - current.m_start;
std::cout << total << std::endl;
}