Puramente funzionale skip list concomitante

Question

Skip liste (Pugh, 1990) forniscono dizionari ordinati con logaritmica operazioni -time come gli alberi di ricerca, ma skip list sono molto più suscettibili di concomitante aggiornamenti .

E 'possibile creare un elenco di salto concomitante puramente funzionale efficiente? In caso contrario, è possibile creare qualsiasi tipo di dizionario ordinato concomitante puramente funzionale efficiente?

Answer 1

La proprietà di skip list che li rende bene per aggiornamenti concorrenti (vale a dire che la maggior parte delle addizioni e sottrazioni sono locali) li rende anche un male per l'immutabilità (vale a dire che un sacco di precedenti voci del punto di lista alla fine alle voci successive, e avrebbe dovuto essere modificato).

In particolare, saltare le liste costituite da strutture che assomigliano così:

NODE1 ---------------------> NODE2 ---------...
  |                           |
  V                           V
NODE1a --> NODE1b ---------> NODE2a --> NODE2b --> NODE2c --- ...

Ora, se si dispone di un aggiornamento che, per esempio, elimina NODE2b o NODE1b, si può prendere cura di esso molto a livello locale: basta punto 2a a 2c o 1a per 2a rispettivamente, e il gioco è fatto. Purtroppo, perché la foglia nodi tutti i punti uno ad un altro, non è una buona struttura per un aggiornamento funzionale (immutabile).

Quindi, strutture ad albero sono migliori per l'immutabilità (come il danno è sempre localmente limitata - solo il nodo che ti interessano e dei suoi genitori dirette attraverso la radice dell'albero)

.

aggiornamenti simultanei non funzionano bene con strutture di dati immutabili. Se ci pensate, qualsiasi soluzione funzionale ha un aggiornamento A come f(A). Se si desidera che due aggiornamenti, quella data da f e una data dal g, si deve praticamente fare f(g(A)) o g(f(A)), o si deve intercettare le richieste e creare un nuovo h = f,g operazione che è possibile applicare tutti in una volta (o si hanno a che fare varie altre cose altamente intelligente).

Tuttavia, in concomitanza legge lavoro fantasticamente bene con strutture di dati immutabili dal momento che si sono garantiti per avere alcun cambiamento di stato. Se non date per scontato che si può avere un ciclo di lettura / scrittura che consente di risolvere prima di ogni altra scrittura possono interrompere, allora non devi mai bloccarsi su di lettura.

In questo modo, le strutture di dati di scrittura-pesanti sono probabilmente meglio implementato mutably (e con qualcosa di simile a una skip list in cui hai solo bisogno di bloccare a livello locale), mentre le strutture di dati di lettura-pesanti sono probabilmente meglio implementate immutabilmente (dove un albero è un altro struttura di dati naturali).

Answer 2

La soluzione di Andrew McKinlay è il vero "vera" soluzione funzionale per un vero e proprio salto-list qui, ma ha un rovescio della medaglia. Si paga tempo logaritmico per accedere a un elemento, ma ora la mutazione di là l'elemento di testa diventa senza speranza. La risposta che si desidera è sepolto giù in innumerevoli percorsi-copie!

Possiamo fare di meglio?

Una parte del problema è che ci sono più percorsi da -infinito a vostro articolo.

Ma se si pensa attraverso gli algoritmi per la ricerca di uno skiplist, non si utilizza mai questo fatto.

Si può pensare di ciascun nodo nell'albero come avere un collegamento preferito, il collegamento più in alto ad esso da sinistra, che in un certo senso può essere pensato come 'possedere' quella voce.

Ora possiamo prendere in considerazione l'idea di un 'dito' in una struttura di dati, che è una tecnica funzionale, che consente di concentrarsi su un particolare elemento, e fornire un back percorso alla radice.

Ora possiamo iniziare con un semplice skip list

-inf-------------------> 16
-inf ------> 8 --------> 16
-inf -> 4 -> 8 -> 12 --> 16

L'espansione è per livello:

-inf-------------------> 16
  |                       |
  v                       v
-inf ------> 8 --------> 16
  |          |            |
  v          v            v
-inf -> 4 -> 8 -> 12 --> 16

Striscia fuori tutti, ma i puntatori preferiti:

-inf-------------------> 16
  |                       |
  v                       v
-inf ------> 8           16
  |          |            |
  v          v            v
-inf -> 4    8 -> 12     16

Poi si potrebbe muovere un 'dito' alla posizione 8, monitorando tutti i puntatori dovreste capovolgere per arrivarci.

-inf ------------------> 16
   ^                      |
   |                      v
-inf <------ 8           16
   |         |            |
   v         v            v
-inf -> 4    8 -> 12     16

Da lì è possibile cancellare 8, spingendo il dito da qualche altra parte, ed è possibile continuare a navigare attraverso la struttura con il dito.

Guardato in questo modo, possiamo vedere che i percorsi privilegiati in una skip list formano un albero di copertura!

Spostare 1 punto con il dito è un O (1) operazione se hai solo puntatori privilegiati nell'albero e usa "nodi magre" come questo. Se è stato utilizzato nodi di grasso, quindi il movimento del dito a sinistra / destra sarebbe potenzialmente più costosi.

Tutte le operazioni rimangono O (log n) ed è possibile utilizzare una struttura skip list-randomizzati o uno deterministico, come al solito.

Detto questo, quando si spezza lo skiplist giù in una nozione di un percorso preferenziale allora otteniamo che uno skiplist è solo un albero con alcuni collegamenti ridondanti non preferite non abbiamo bisogno per l'inserimento / Ricerca / Cancella, in modo tale che la lunghezza di ciascuno di tali percorsi dalla parte superiore a destra è o (log n) o con elevata probabilità o garantiti a seconda della strategia di aggiornamento.

Anche senza il dito è possibile mantenere O (log n) orario previsto per inserimento / aggiornamento / eliminazione in un albero con questo modulo.

Ora, la parola chiave nella vostra domanda che non ha senso è "concorrente". Una struttura di dati puramente funzionale non ha una nozione di mutazione in-posto. Si produce sempre una cosa nuova. In un certo senso gli aggiornamenti funzionali simultanei sono facili. Ognuno ottiene la propria risposta! Essi non possono vedere ogni altri.

Answer 3

Non una skip list, ma sembra corrispondere alla descrizione del problema: persistenti alberi rosso-neri di Clojure (vedi PersistentTreeMap.java ). La sorgente contiene presente avviso:

/**
 * Persistent Red Black Tree
 * Note that instances of this class are constant values
 * i.e. add/remove etc return new values
 * <p/>
 * See Okasaki, Kahrs, Larsen et al
 */

Questi alberi a mantenere l'ordine degli elementi e sono "persistenti", nel senso in cui Rich Hickey usa la parola (immutabile e in grado di mantenere le loro garanzie di prestazioni come le versioni aggiornate sono costruiti).

Nel caso in cui si desidera giocare con loro, è possibile costruire istanze nel codice Clojure con la funzione sorted-map.

Answer 4

Se avete solo bisogno di cons sul fronte della skip list, allora dovrebbe essere possibile fare una versione immutabile persistente.

Il vantaggio di questo tipo di skip list sarebbe l'accesso "random". per esempio. Si potrebbe accedere all'elemento n-esimo più velocemente di quanto si potrebbe in una normale lista collegata singola.