Sto cercando un modo efficiente per implementare una struttura ad albero simultanea. Se ciò aiuta, supponiamo di avere molti più accessi in lettura che modifiche alla struttura.Albero concorrente efficiente
L'albero dovrebbe sostenere queste operazioni:
Date un'occhiata a: Concurrent-Trees sul codice di Google di un modo per modificare le strutture ad albero senza bloccare.
Il progetto fornisce gli alberi Concurrent Radix e Suffix per Java. Supporta letture e scritture simultanee e le letture sono bloccate. Funziona applicando le patch all'albero atomicamente. Anche se questi tipi di alberi potrebbero non essere esattamente ciò che si desidera, l'approccio usando "patching" come descritto in TreeDesign è utile per qualsiasi tipo di struttura ad albero.
Gli alberi sono concepiti per casi di utilizzo della maggior parte della concorrenza per lo più, dove (per esempio) un thread in background potrebbe inserire o eliminare voci dall'albero mentre molti thread in primo piano continuerebbero ad attraversarlo senza impedimenti dalle modifiche.
È possibile utilizzare un blocco lettore-scrittore nella struttura, i n un modo in cui più thread possono essere letti contemporaneamente, ma solo un thread alla volta può modificarlo. Se qualche thread tenta di modificare la struttura, non può farlo finché tutti i lettori non hanno letto le loro letture. Se un thread vuole leggerlo può solo se uno scrittore non sta già funzionando, o è sul programma di fare alcune modifiche. Forse uno sguardo a questo potrebbe aiutare:
http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html
+1 Per blocco lettura/scrittura – mishadoff
idea di base con lettura/scrittura bloccare
Per tutti scrivono metodi utilizzano seguente idioma:
someWriteMethod(){
writeLock.lock();
// logic
writeLock.unlock();
}
Per tutti leggono metodi utilizzano simili codice:
someReadMethod(){
readLock.lock();
// logic
readLock.unlock();
}
Nota: se il codice (sostituire il commento di logica sopra) può generare eccezioni, assicurarsi di rilasciare i blocchi prima di uscire dal metodo nella sezione finale.
Il blocco lettura-scrittura ha uno svantaggio: non è possibile "aggiornare" una lettura a un blocco scrittura, quindi è necessario sapere in anticipo se l'operazione modificherà l'albero. Quindi questo avrebbe bisogno di due iteratori in cui uno potrebbe bloccarsi troppo. –
Suppongo che usando gli alberi sai in anticipo quali operazioni modificano il tuo albero, non è vero? – mishadoff
Quando chiedo l'albero per un iteratore, il metodo che crea l'iteratore non può sapere se chiamerò remove() o meno. –
La struttura Java che è il più vicino a quello che potrebbe essere necessario è un ConcurrentSkipListSet (o forse ConcurrentSkipListMap).
Se è necessario un approccio più personalizzato, è possibile implementare una struttura ad albero personalizzata se si dispone di un blocco di lettura/scrittura gerarchico. Ecco un Risposta una domanda simile su come implementare un rientrante blocco di lettura-scrittura: https://stackoverflow.com/a/6154873/272388
Il CSLM non è molto vicino. È una * mappa ordinata * che ha poco a che fare con una struttura ad albero. Quindi condivide solo una proprietà comune con 'TreeMap' in quanto è una mappa ordinata, che non è rilevante qui. –
Ecco perché c'è una seconda parte della risposta in quanto non conosco nessuna struttura ad albero inclusa in Java che supporti tutte queste operazioni. Inoltre, CSLM potrebbe essere sufficiente per alcuni casi simili. – Kru
Kru è ancora corretto: è l'unica struttura dati nel runtime ufficiale che è il più vicino al mio problema. Potrei costruire l'albero usando i blocchi concurrentSkipListMaps + nidificati. –
Questo è interessante ma inutile nel mio caso d'uso. I miei alberi sono alberi reali (strutture padre-figlio), non mappe di valori-chiave. –
Eviterei di usare parole come "inutili". Questa risposta è stata fornita per aiutarti volontariamente. Se si cercano alberi in lettura per lo più simultanei, gli algoritmi lock-free possono essere una buona soluzione. Un albero radix potrebbe non essere esattamente quello che stai cercando, ma come ho detto, l'approccio di patch atomico a cui mi collego, può essere applicato a qualsiasi tipo di albero per letture prive di lock, anche se hai intenzione di scrivere la tua custom albero. Incidentalmente gli alberi radix sono ovviamente alberi, con strutture genitore-figlio. – npgall
+1 Ho migliorato il testo per rendere più chiaro il tuo intento. –