Ho una serie di articoli rigorosamente ordinati in tempo. Ogni elemento può essere singolo (no successivo, nessun precedente) o parte di uno span (con 1 o 2 ulteriori endpoint). Ad esempio nell'immagine A fa parte di un intervallo di 3 elementi 1 - > 4 - > 5, B fa parte di un intervallo di 2 elementi 2 - > 3 e C fa parte di un intervallo di 2 elementi 6 - > 16. Come puoi vedere, gli span possono sovrapporsi l'un l'altro (start2 > start1, end1 > end2).
Quello che voglio fare è elaborare un algoritmo veloce per trovare quali span (o individui) si intersecano in un dato intervallo Min - > Max.
Il mio approccio ingenuo è semplicemente testare ogni singolo oggetto nel set, con qualcosa del tipo:
for(auto const & e : items)
{
if(e.Previous)
{
// Middle or last item in a set (already been tested).
continue;
}
auto t1 = e.Time, t2 = e.Time;
if(e.Next)
{
if(e.Next.Next)
{
// Part of a 3 item span (start, middle, end).
t2 = e.Next.Next.Time;
}
else
{
// Part of a 2 item span (start, end).
t2 = e.Next.Time;
}
}
if(t1 > MaxTime || t2 < MinTime)
{
// Does not intersect the span.
continue;
}
... Do something with the item, such as draw it.
}
Questo non funziona molto male con 250.000 oggetti in realtà ma inizia ad essere piuttosto lento quando entri in milioni.
Ho un sacco di tempo a disposizione all'avvio per ottenere uno std: futuro attivo e funzionante per pre-processare queste cose in una struttura più utile se questo aiuta. Devo anche essere in grado di aggiungere alla fine del set, pur mantenendo un ordine temporale rigorosamente crescente (ad esempio now () > = items.last (). Time).
Qualche cosa succede a qualcuno?