Struttura dati per ampi intervalli di numeri interi consecutivi?

Question

Supponiamo di avere una vasta gamma di numeri interi consecutivi in ​​memoria, ognuno dei quali appartiene esattamente a una categoria. Due operazioni devono essere O (log n): spostare un intervallo da una categoria a un'altra e trovare i conteggi delle categorie per un determinato intervallo.

Sono sicuro che la seconda operazione è stata risolta in modo superficiale, vista l'implementazione corretta per la prima operazione.

Ogni intero inizia in una categoria, quindi ho iniziato con un set di BST bilanciati. Lo spostamento di un albero secondario da un BST a un altro (ad esempio, lo spostamento di un intervallo in una categoria diversa) ha un tempo di esecuzione equivalente alla fusione di due BST, che è O (n1 * n2) [1].

Questo è troppo lento (in python e C non è un'opzione) e non sono riuscito a trovare un modo per sfruttare la struttura intrinseca dei miei dati per creare un'operazione di unione BST efficiente.

Ora guardo ad AVL, rosso-nero e alberi ad intervalli, heap binari e traci. Confrontando le loro proprietà è schiacciante. Quale struttura dovrei usare?

Modifica (chiarimento problema): Sono flessibile su come memorizzare questi valori e creare le mie strutture dati. Sono inflessibile su come ricevo il mio input, che proviene da un'altra applicazione, e assomiglia al seguente: CATEGORY(cat3, I, J). La mia soluzione corrente crea un albero con un nodo per ogni intero nell'intervallo. Questo è troppo lento per la dimensione del mio set di dati, quindi sono felice di re-architect se fornito un metodo migliore.

Qualsiasi richiesta data può spostare qualsiasi intervallo possibile di numeri interi in qualsiasi categoria. In altre parole, gli intervalli si sovrappongono nel senso di CATEGORY(cat1, 1, 10) seguito da CATEGORY(cat3, 5, 15), ma non sovrapposti, nel senso che ogni numero intero si troverà esattamente in una categoria in un dato momento.

Answer 1

Per quanto ho capito la domanda che hanno una gamma [A, B] e le query della forma -

1. Assegnare un particolare intervallo a una categoria

 
E.g. 
R1 R2 C1 
R3 R4 C2 

1. Interrogare un intervallo per il numero totale di elementi in determinate categorie. E.g. trovare conte di categorie in R1 R4

Una semplice implementazione con dizionari come dato di cui sopra non avrebbe funzionato come ho descritto da questo esempio -

supponiamo di avere una gamma [1000, 5000]

e facciamo assegnazione come segue -

 
1 2 C1 
2 3 C2 
3 4 C3 
...... 
4999 5000 C4999 

Ora facciamo la seguente assegnazione

 
1 5000 C5555 

Questo renderà updation/modifiche/eliminazione di assegnare precedentemente gamme di intervalli O (N) dove N è la dimensione massima del campo (B - A)

D [ 'categoria'] = SET (of_all_the_ranges_you_have_in_category)

in questo caso soppressione delle gamme precedenti da insiemi corrispondente categorie C1, C2 ... C4999 sarà necessario per ultima assegnazione (1 5000 C5555)

O

01.235.164,106174 millions

1: { "stop": 5, "categoria": "C1"}, 6: { "stop": 19, "categoria": "C23"},

Qui updation di categoria per ogni valore iniziale (1,2,3,4 ..., 4999) sarà necessario per l'ultimo incarico (1 5000 C5555)

Un'opzione migliore che renderà l'aggiornamento degli intervalli in O (lg n) sarebbe essere alberi segmento (http://en.wikipedia.org/wiki/Segment_tree)

Per l'esempio sopra il segm ent tree sarà simile a questa

    1000:5000 
         | 
      --------------------- 
      |     | 
      1000:3000   3001:5000 
      |     | 
    ----------------  -------------------- 
    |    |  |     | 
1000:2000  2001:3000 3001:4000  4001:5000 

.................................... ............................. .................... ........................................... e così via

I nodi foglia avranno intervalli (1: 2, 2: 3, ...)

È possibile assegnare un valore "categoria" a ciascun nodo e dato un intervallo trasversale dell'albero che divide l'intervallo in modo appropriato (ad es. Per 2500 a 4500 divide in 2500: 3000 e 3001: 4500 e procede in entrambe le direzioni finché non vengono trovati nodi con intervalli di corrispondenza).

Ora una cosa interessante è aggiornare i figli dei nodi quando ne avete bisogno. Ad esempio, non procedere all'aggiornamento immediato dei bambini quando si eseguono compiti come 1 5000 C5555. Questa cosa si chiama propagazione pigra e puoi saperne di più qui (http://www.spoj.pl/forum/viewtopic.php?f=27&t=8296).

Ora per la parte di query. Se il numero di categorie è molto piccolo, è possibile mantenere una tabella di frequenza su ciascun nodo e aggiornare gli intervalli quando necessario e propagarsi pigro quando necessario altrimenti, si dovrà attraversare l'intero albero da foglia a nodo, il conteggio e la complessità diventeranno O (n).

Penso che possa esistere una soluzione migliore per l'interrogazione. Non mi viene in mente.

UPDATE Facciamo un piccolo esempio.

Intervallo [1,8]

Categorie ammesse {C1, C2}

 1:8 
    1:4   5:8 
    1:2 3:4  5:6 7:8 
1:1 2:2 3:3 4:4 5:5 6:6 7:7 8:8 

Ogni nodo avrà 3 campi [categoria, category_counts [], children_update_required = false]

1 5 C1

La query verrà divisa e i nodi 1: 4 verranno impostati su C1 e child_update_required verrà impostato su true, i relativi figli non verranno aggiornati ora (ricorda di aggiornare solo quando richiesto o propagazione pigro). Anche nodo 5: 5 della categoria sarà impostato C1

3 4 C2

Query propagarsi lungo l'albero verso 3: 4 (e nel processo per raggiungere 3: 4, 1: 2 e 3: 4 di le categorie saranno aggiornate a C1, i bambini_update_required di 1: 4 saranno impostati su false, 1: 2 e 3: 4 children_update_required sarà impostato su true) e ora aggiornerà la categoria da 3: 4 a C2 in base ai requisiti correnti. Quindi imposterà child_update richiesto di 3: 4 per essere vero per l'aggiornamento futuro dei suoi figli (che è già impostato in questo caso ... nessun danno fatto).

Answer 2

si può avere un dizionario Python pianura del seguente modulo

1 : { "stop" : 5, "category" : "C1"}, 
6 : { "stop" : 19, "category" : "C23"}, 
etc 

Le chiavi qui sono l'inizio della vostra gamma ei valori contengono la fine del campo e la categoria di questo intervallo cade.

Poiché i dizionari hanno un tempo costante per accedere agli elementi, è possibile scrivere codice che sposta un intervallo in un'altra categoria in modo semplice ed efficiente: nel peggiore dei casi, sarà necessario ristrutturare in qualche modo il dizionario, se l'intervallo si divide prima varia in due o più. Ad esempio, se si desidera assegnare il range di (4, 8) in un'altra categoria, ci si ritroverà con:

1 : { "stop" : 3, "category" : "C1"}, 
4 : { "stop" : 8, "category" : "new category"}, 
9 : { "stop" : 19, "category" : "C23"}, 
etc 

Trovare il numero di categoria è banale, basta raccogliere tutti gli intervalli desiderati in tempo costante e contare le categorie ..

MODIFICA: Per trovare con successo il tasto più basso (il più alto) per iniziare a eseguire calcoli/alterazioni, è necessario anche un semplice elenco python con tutte le chiavi ordinate e il modulo bisect. Questo aiuterà a localizzare l'indice nella lista per "mettere" l'inizio dell'intervallo nel tempo O (logn), quindi tutto può essere fatto in tempo costante, eccetto il tempo O (n) necessario per inserire la nuova chiave nel elencare con bisect.insort_left.

Answer 3

È possibile creare una struttura ad albero su array di numeri interi consecutivi abbastanza facilmente, il che dovrebbe aiutare con il fattore costante. Prima rinumerare la sequenza per iniziare da 0 e calcolare quale è la potenza minima di due che è maggiore dell'intervallo della sequenza.

Consideriamo ora il seguente albero formato dagli interi 0-7, che posso contenere come quattro matrici, ogni array che va in orizzontale.

  (all) 
    0-3  4-7 
    0-1 2-3 4-5 6-7 
0 1 2 3 4 5 6 7 

dato un numero e un livello, posso scoprire un offset nella matrice per quel livello, semplicemente spostando il giusto numero una quantità a seconda del livello.

In ciascun elemento è possibile inserire un indicatore che dice "misto" o fornisce la categoria per ogni elemento in corrispondenza o in corrispondenza di tale nodo dell'albero. Posso capire in quale categoria si trova un nodo seguendo il percorso dalla radice dell'albero ad una foglia, fermandomi non appena vedo un nodo che non dice "misto". Posso cambiare la categoria per un intervallo di numeri in time lg n, perché ho al massimo due nodi per ogni livello per rappresentare la categoria: se ne avessi tre, due avrebbero lo stesso genitore e io potrei unirli. Potresti dover armeggiare un po 'con i bordi per ottenere correzioni vicine, ma penso che funzioni in tempo reale.

Answer 4

Ipotesi:

• Qualsiasi numero intero può appartenere a esattamente una categoria, in modo da intervalli non possono intersecarsi.
• Tutti gli interi in un intervallo in entrata appartengono a una categoria.
• A volte è necessario dividere una gamma di spostare una subrange ad una categoria diversa.

Rappresenta le gamme per tuple (start, end, category). Gli intervalli non si intersecano in modo da poterne costruire un albero. È lontano più economico di un albero di singoli numeri interi. Per ordinare intervalli (ovvero nodi), puoi semplicemente utilizzare il valore iniziale, poiché è univoco e non può appartenere a un altro intervallo.

Se si deve spostare una gamma [a, b] ad un'altra categoria, si deve:

scansionare il vostro albero e aggiornare ogni nodo/ambito che è completamente incluso nel [a, b] gamma. È una semplice traversata in profondità. Durante l'attraversamento

• Se current_node.start < a or current_node.start > b, interrompere la ricerca.
• Se current_node.start >= a and current_node.end > b, si deve dividere current_node in due; [current_node.start, b] apparterrà a una nuova categoria, il resto sarà della sua categoria originale.
• Se current_node.start < a and current_node.end <= b, si divide il contrario.

La ricerca dell'albero è logaritmica e le divisioni dei nodi sono O (1).

Se il vostro albero ottiene mai troppo frammentato, si potrebbe prendere in considerazione la fusione nodi che hanno gamme adiacenti. Questo sarà sempre un genitore e un figlio risultante da un inserimento o una divisione; gli assegni e i join sembrano essere sempre O (1).

Answer 5

Siamo in grado di rappresentare gli stati attuali come qualcosa di simile:

0:cat1 200:cat2 500: cat0 700:cat6 800:cat1 

Ciò significa 0-200 è cat1, 200-500 è cat2, ecc memorizzare i valori in un albero binario di ricerca digitato sulla partenza numero. Ogni nodo conterrà anche un dizionario che associa le categorie ai conteggi per tutti i figli di quel nodo.

Quei dizionari dovrebbe rendere più facile per ottenere i conteggi in O (log) tempo. Dobbiamo semplicemente aggiungere i numeri corretti sui percorsi all'inizio e alla fine della sequenza in questione.

Cosa facciamo quando abbiamo bisogno di impostare la sequenza X-Y di categoria Z?

1. Determinare la categoria attuale della YO (log n)
2. Rimuovere tutti i valori tra X -Yo (k), ma poiché il costo dell'inserimento quei nodi è più costoso, si può chiamare O (1) ammortizzato .
3. Inserire nuovo nodo su X O (log n)
4. Dizionari di aggiornamento della categoria di aggiornamento.Dovremmo solo aggiornare i genitori O (log n) delle sezioni interessate, quindi questo è O (log n)

Complessivamente questo è il tempo O (log n).