Qual è l'implementazione più efficiente degli array con aggiornamenti funzionali?

Question

Ho bisogno di una struttura dati di tipo array con l'aggiornamento funzionale più veloce possibile. Ho visto alcune diverse implementazioni di array flessibili che mi forniscono questa proprietà (Braun, Random Access Lists) ma mi chiedo se c'è un'implementazione che è specificatamente ottimizzata per il caso quando non siamo interessati ad aggiungere o anteporre - solo aggiornamenti.

Answer 1

Jean-Cristophe Filliâtre dispone di a very nice implementation di matrici persistenti, che è descritto in the paper collegato alla stessa pagina (che riguarda la ricerca unione permanente, di cui gli array persistenti sono un componente principale). Il codice è direttamente disponibile there.

L'idea è che "l'ultima versione" della matrice è rappresentato come un array di consueto, con O(1) accesso e operazioni di aggiornamento, e versioni precedenti sono rappresentate come quest'ultima versione, e un elenco delle differenze. Se si tenta di accedere a una versione precedente della struttura, la matrice viene "riregolata" per applicare l'elenco delle differenze e presentare di nuovo la rappresentazione efficiente.

Ovviamente questo non sarà O (1) in tutti i flussi di lavoro (se si accede e si modificano costantemente versioni non correlate della struttura, si pagheranno di frequente i costi di riavvio), ma per il flusso di lavoro comune principalmente con una versione, e di tanto in tanto tornando indietro a una versione precedente che diventa di nuovo "l'ultima versione" e ottiene gli aggiornamenti, questo è molto efficiente. Un ottimo uso della mutabilità nascosto sotto un'interfaccia puramente visiva.

Answer 2

Quale lingua stai utilizzando? In Haskell è possibile utilizzare mutable arrays con la monade di stato e in Mercury è possibile utilizzare matrici mutevoli mediante il threading dello stato IO. Ocaml ha anche un modulo array, che purtroppo non mantiene la trasparenza referenziale, se questo è ciò che si sta cercando.

Answer 3

Ho un'esperienza molto buona con repa (nice demo). Ottime prestazioni, parallelismo automatico, multidimensionale, polimorfico. Consigliato di provare

Answer 4

Avevo bisogno anche di array funzionali e mi sentivo su questa domanda di SO alcuni giorni fa. Non ero soddisfatto della soluzione proposta da Gasche poiché la creazione di un nuovo array è un'operazione costosa e ho bisogno di accedere a versioni più vecchie dell'array piuttosto frequentemente (ho intenzione di usarlo per un'implementazione AI alpha/beta su un array).

(Quando dico costoso, suppongo che sia O (n * h) dove h è la dimensione della cronologia perché nel peggiore dei casi solo una cella è stata aggiornata ripetutamente ed è necessario passare attraverso l'intero elenco di aggiornamenti per ogni cella. Prevedo anche che la maggior parte delle celle non venga aggiornata quando devo reindirizzare l'array).

Ecco perché propongo un altro approccio, forse posso ottenere un feedback qui. La mia idea è di immagazzinare l'array come in un B-Tree, tranne per il fatto che non essendo mutabile, posso accedere e aggiornare qualsiasi valore per indice abbastanza facilmente.

Ho scritto una piccola introduzione sul repository del progetto: https://github.com/shepard8/ocaml-ptarray. L'ordine è scelto in modo tale da avere anche profondità e ordine dell'albero, così posso ottenere delle belle complessità che dipendono solo dall'ordine per le operazioni get/set, ovvero O (k^2).

Con k = 10 è possibile memorizzare fino a 10^10 valori. In realtà i miei array non dovrebbero contenere più di 200 valori, ma questo è per mostrare quanto sia solida la mia soluzione.

Qualsiasi consiglio benvenuto!