Newsgroup: it.comp.lang.c++
Titolo: [OT] RB-alberi di intervalli

Salve a tutti,
scusate l'OT, ma sono fermo da più di una settimana su questo problema
e non riesco a cavarne un ragno dal buco, quindi ho deciso di
rivolgermi al ng, visto che molti dei frequentatori sono degli
esperti.
Il problema è il seguente: ho un RB-albero di intervalli, e devo
trovare una funzione di complessità O(1) che mi restituisca il massimo
numero di intervalli sovrapposti; inoltre l' introduzione di tale
funzione non deve aumentare il costo di inserimento e cancellazione,
che devono rimanere O(logN).
Non vi chiedo di scrivermi l'algoritmo, ma solo qualche suggerimento
che mi porti sulla strada giusta.
Grazie per l'attenzione
Alberto Griggio

che mi porti sulla strada giusta.
Questa è la vera definizione del problema. Domanda: perchè dici "massimo
numero
di intervalli sovrapposti"? Se i dati sono conosiuti il numero di
intervalli 
sovrapposti non è un valore univocamente calcolabile ( cioè x=k per
qualche k e 
non k1 < x < k2 ) ?
Mi chiarisci, informaticamente, cos'è un intervallo? Parli di intervallo
aritmetico ?
Ovvero qualcosa riducibile a:
struct {
	int lo, hi;
};
Cosa consideri numero di intervalli sovrapposti ? Per esempio con queste
tuple-intervallo:
{0-2}
{1-3}
{4-6}
{5-7}
{8-9}
e con:
{0-1}
{1-2}
{3-6}
{4-8}
{5-7}
{6-9}
-- 
Posted from 
adsl-21-135.38-151.net24.it
 [151.38.135.21] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG


per intervallo intendo appunto un intervallo aritmetico, ad esempio
[3,5]={x|3<=x<=5}
Per intervalli sovrapposti intendo semplicemente questo: due
intervalli i e i' si sovrappongono se e solo se i->lo<=i'->hi e
i'->lo<=i->hi.
Per quanto riguarda le due sequenze, nella prima il massimo numero di
intervalli sovrapposti e' 2, nella seconda e'4.
Per quanto riguarda l'uso di un algoritmo indipendente dalla struttura
usata, non credo che sia possibile trovarne uno di complessita'
costante che non si avvantaggi della particolare gestione dei dati.
Infine, se può essere utile, ho dimenticato di scrivere che i dati
sono ordinati nell'albero considerando come chiave l'estremo inferiore
dell' intervallo stesso.
Alberto Griggio

intervalli sovrapposti e' 2, nella seconda e'4.
Per la prima ok. sono {a,b} e {c,d} che si sovrappongono. Questo 
chiarisce che ti interessa in numero delle sovrapposizioni e non il 
numero degli intervalli che si sovrappongono (altrimenti sarebbe stato 
quattro).
Però devi spiegarmi meglio il secondo caso. Le sovrapposizioni sono
ovviamente {a,b} dato che la relazione è d'ordine largo nonchè {c,d},
{c,e}, {d,e}, {d,e}, {d,f}, {e,f}. Totale 6 e non 4, quindi tu non 
conti in questo modo. Prova a spiegarmelo meglio Magari graficamente:
 0123456789
a.*
b *.
c   ....
d    .....
e     ...
f      ....
Ho evidenziato la sovrapposizione fra a e b. Quali sono le altre 3 ?
Comunque mi sa che siamo OT. Purtroppo ho verificato che non c'e' un
gruppo sugli algoritmi nella gerarchia it. 



Forse mi sono spiegato male: per punto di massima sovrapposizione
intendo un punto che appartiene al massimo numero di intervalli. Ad
esempio, per la seconda sequenza, tale punto e' 6, in quanto
appartiene a 4 intervalli: quindi il massimo numero di intervalli
sovrapposti e' 4.
Per quanto riguarda l'OT, pensavo che it.comp.programmare fosse il ng
giusto, ma poi ho dato un'occhiata e mi sono accorto che e' talmente
generale che un problema come questo passerebbe inosservato :(
Alberto Griggio

sovrapposti e' 4.
Adesso ho capito. Ti rispondo subito che una funzione esterna alla
struttura dell'albero che calcola il tuo massimo non è difficile 
ma ovviamente esegue in O(n) dato che come minimo deve attraversare
l'albero una volta. Dal tuo vecchio post vuoi che la cosa sia O(1)
quindi deve essere implementata nell'albero stesso "trappando" 
inserimenti e cancellazioni che infatti dicevi dovevano rimanere
di costo O(logN). Di più: per essere O(1) la funzione non deve 
accedere ai nodi (salvo eventualmente alla radice), quindi il 
risultato deve essere precalcolato e salvato o come decorazione 
dell'albero o come decorazione della radice.
Ovviamente ci devo pensare su un pochino. Ti chiedo ancora qualche 
delucidazione sul motivo della scelta di usare l'albero e quindi 
sugli altri usi che ne fai. Per esempio, se creassimo un qualche 
cosa di diverso con inserimenti e cancellazioni di intervalli in
tempo O(logN) e possibilità di un traversamento, basterebbe?
In altre parole, che cos'altro fai con l'albero oltre a inserimenti, 
cancellazioni e ricerca del punto di massima sovrapposizione? Se
fai un traversamento è necessario che sia in ordine per valore 
minore degli intervalli o quel criterio di ordinamento è stato 
scelto a caso?


-- 
Il considerare l'estremo inferiore dell'intervallo come criterio di
ordinamento e' il piu' naturale, credo, e non dovrebbe creare
problemi.
Comunque avevo anche pensato di usare un trucco: per ogni intervallo
gestito, inserire due nodi: uno con l'intervallo normale, un altro con
l'intervallo costituito solo dall'estremo superiore: in questo modo il
numero di intervalli sovrapposti ad uno dato e' il numero di
intervalli che iniziano prima (cioe' il rango di tale intervallo
nell'insieme) meno il numero di intervalli che si sono gia' chiusi,
che si puo' ottenere usando appunto questi nodi "speciali". Sono
riuscito a trovare una funzione O(logN) che mi dice il numero di
intervalli sovrapposti ad un intervallo dato, ma non riesco ad andare
oltre.
Forse questa e' la strada giusta, ma io non riesco a proseguirla... :(
Ciao e grazie ancora per l'interessamento
Alberto Griggio

Faccio un tentativo.
1) partiamo dal presupposto che la struttura contenitore 
sia un albero binario e che siano definite per ogni nodo 
le funzioni up() per il padre, left() per il figlio sinistro 
right() per il figlio destro, isLeft(), isRight(), isRoot() 
per sapere che tipo di relazione corre fra il nodo e il suo 
genitore.
2) Ogni intervallo sara' rappresentato da due nodi. Un nodo
avra' come chiave di ordinamento l'estremo inferiore 
dell'intervallo e l'altro avra' come chiave di ordinamento 
l'estremo superiore. L'ordine si suppone crescente. Chiameremo
 questi due nodi, relativamente all'intervallo che rappresentano, 
nodo in e nodo out. Per ciascun nodo avremo le funzioni isIn() e 
isOut() che ci informeranno sul tipo di nodo. ATTENZIONE: dato che
i nodi non sono omogenei, ovvero possono rappresentare due cose 
diverse (in/out) la funzione d'ordine dell'albero deve essere fatta
in modo da tenere conto di questa differenza. In particolare a 
parita' di valore dell'estremo un nodo out sara' sempre maggiore di
un nodo in. Per esempio un intervallo nullo (ovvero con estremi 
coincidenti) avra' il suo nodo in sempre precedente al suo nodo 
out. Supponendo che la relazione d'ordine sia stata implementata
in maniera da supportare l'operatore <= applicato ai nodi, 
l'invariante di albero per ogni nodo n sara':
if ( n.left() )
  assert( n.left() <= n );
if ( n.right() )
  assert( n <= n.right() );
3) Ogni nodo sara' decorato con due valori: opened e closed. A 
livello semantico opened rappresenta il numero di nodi in nel
sotto albero sinistro al nodo (incluso se e' un nodo in) e
closed rappresenta il numero di nodi out nel sotto albero sinistro 
al nodo (incluso se e' un nodo out).
4) ogni nodo rappresenta un "punto" ben preciso nell'ipotetica 
retta su cui proiettiamo i vari intervalli. Data l'invariante 
di albero non e' difficile partendo da un nodo e utilizzando 
opened e closed calcolare il numero di sovrapposizioni in quel 
preciso punto. Se il nodo e' un figlio sinistro di suo padre, 
la risposta e' banale: opened-closed. Eventualmente corretto di 
uno nel caso che che il nodo sia un nodo out. Se il nodo e' un 
figlio destro la cosa e' leggermente piu' difficile dato che tocca 
risalire l'albero fino ad un figlio sinistro. Ma comunque siamo 
sempre O(log(n)). Se osservi che inserendo i dati in questo modo 
tutti i possibili sub-intervalli (e quindi sovrapposizioni) sono 
rappresentati non dovrebbe esserti molto difficile neppure 
accumulare un terzo valore che rappresenta il numero massimo di 
sovrapposizioni nel sottoalbero sinistro di un nodo (nodo incluso). 
Tutte queste decorazioni possono essere tenute aggiornate in 
O(log(n)) dato che richiedono, nel caso peggiore, una risalita 
dal nodo modificato alla radice. A questo punto il calcolo della 
massima sovrapposizione lo puoi fare in O(log(n)) scendendo dalla
radice verso l'estrema foglia destra.
A questo punto pero' ti chiedo: tutte queste operazioni si possono 
eseguire in O(log(n)) ma certamente appesantiscono parecchio il 
lavoro. se f(n) e' O(log(n)) anche k f(n) e' O(log(n)). Ma non e' 
certo piu' veloce. La tua richiesta di avere l'update dell'albero 
in O(log(n)) e il calcolo del massimo overlap in solo O(1) e' un 
pochino incongruente. Con quanto sopra ottieni il massimo overlap 
in O(log(n)) e puoi ridurlo a O(1) ammortizzato con un semplice 
meccanismo di cache. Ma al costo di appesantire l'update 
dell'albero, anche se restando O(log(n)).
Se la sequenza degli avvenimenti prevede che aggiornamenti 
all'albero e ricerche del massimo overlap siano relativamente 
intervallati allora una ricerca del massimo di ordine O(log(n)) 
e' sufficiente e la richiesta di O(1) non ha senso. Se invece le
modifiche non sono intervallate con le interrogazioni, allora ti
conviene semplificare la gestione dell'albero e implementare un 
calcolo del massimo di sovrapposizioni di complessita' O(n) e poi
una cache per ammortizzarlo con limite a O(1).



GRAZIE!
E pensare che anch'io avevo usato due nodi per ogni intervallo, ma non
riuscivo a trovare la maniera giusta di utilizzare questa comodita'.
Ciao, 
Alberto Griggio

l'intervallo costituito solo dall'estremo superiore: in questo modo il
...
Un approccio completamente diverso che che potrebbe
essere interessante nel caso che il range degli estremi
sia ragionevolmente limitato (es. 0..999) potrebbe essere
il seguente:
   int dt[MAX_VALUE+1]; // Gli estremi sono sempre fra 0 e MAX_VALUE-1
   void AddInterval(int low,int high)
   {
     ...
     dt[low]++; dt[high+1]--;
   }
   void RemoveInterval(int low,int high)
   {
     ...
     dt[low]--; dt[high+1]++;
   }
   int FindMaxStackedIntervals()
   {
     int t=0,mx=0;
     for (i=0; i<MAX_VALUE; i++)
     {
       t+=dt[i];
       if (t>mx) mx=t;
     }
     return mx;
   }
Ovviamente questo sistema e' conveniente se il numero di
intervalli e' molto grande, vengono fatte molte
inserzioni/rimozioni fra una valutazione e la successiva
e se il range e' discreto e ragionevolmente limitato.
HTH
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff


Si. Ci avevo pensato. Ma vale solo per gli interi e se il dominio
e' "relativamente" limitato. 
Avrai letto nella mia proposta la mia opinione sul richiedere
inserimenti/cancellazioni O(log(n)) e il calcolo 0(1) senza 
verificare il "peso" assoluto delle operazioni. 
La mia opinione e' e resta che probabilmente rivedendo le 
specifiche del problema si puo' ottenere una soluzione generica con
efficienza accettabile. Ovvero:
1) inserire/rimuovere dall'albero entrambe gli estremi modificando
la funzione d'ordine come detto nel mio precedente post. O(log(n)).
2) NON decorare ulteriormente l'albero (bastano gli inserimenti)
3) gestire il calcolo della massima sovrapposizione con una cache
che viene azzerata da un inserimento/rimozione e quando il valore
viene richiesto, se non e' presente, ricalcolarlo con un 
attraversamento infisso dell'albero (il tipo di nodo permette di
incrementare/decrementare una variabile, in pratica lo stesso 
algoritmo che hai usato tu). O(log(n)) ammortizzata con limite O(1).
Questa soluzione vale con qualunque intervallo comunque definito, 
anche non numerico, purche' esista una relazione d'ordine e vale per
qualunque contenitore anche diverso da un albero, purche' ordinato
e attraversabile in ordine crescente rispetto alla relazione d'ordine.
