Tutte le strutture dati immutabili in Scala sono persistenti? In caso contrario, quali sono e quali no? Quali sono le caratteristiche comportamentali di quelle che sono persistenti? Inoltre, come si confrontano con le strutture di dati persistenti in Clojure?Strutture dati persistenti in Scala
Le strutture di dati immutabili di Scala sono tutte persistenti, nel senso che il vecchio valore viene mantenuto da un'operazione di 'aggiornamento'. In realtà, non conosco una differenza tra immutabile e persistente; per me i due termini sono alias.
Due delle strutture di dati immutabili 2,8 di Scala sono vettori e tentativi di hash, rappresentati come alberi 32-ary. Questi sono stati originariamente progettati da Phil Bagwell, che stava lavorando con il mio team all'EPFL, poi adottato per Clojure, e ora finalmente adottato per Scala 2.8. L'implementazione di Scala condivide una radice comune con l'implementazione Clojure, ma non è certamente una sua porta.
Per l'ultima parte della tua domanda, ricordo Rich Hickey che ha menzionato in una presentazione che le strutture dati Clojure sono state trasferite su Scala. Inoltre, Michael Fogus cita i piani per Scala 2.8 di adottare alcune delle strutture dati di Clojure in this interview. Spiacente questo è così corto nei dettagli ... Non sono sicuro di quale sia lo stato dei piani di Scala 2.8 sopra menzionati, ma mi sono ricordato che Rich e Michael hanno menzionato questo e pensato che potrebbe essere una cosa interessante per te google per se sei interessato.
Si prega di dare un'occhiata a questi eccellenti articoli di Daniel Spiewak:
http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala
http://www.codecommit.com/blog/scala/more-persistent-vectors-performance-analysis
è anche riferimento alla realizzazione Clojure.
Elenco, Vector, HashMap e HashSet sono tutti permanenti su Scala 2.8. Esistono altre strutture di dati persistenti, ma queste che coprono tutti gli usi principali, non sono sicuro che sia necessario elencarle tutte.
Significa che il metodo + di HashMap è O (1)? –
@MartinKonicek "Efficace" O (1), il che significa che alcune ipotesi devono essere valide per essere O (1). Vedi i documenti sulle collezioni [caratteristiche delle prestazioni] (http://docs.scala-lang.org/overviews/collections/performance-characteristics.html). –
Grazie @Daniel C. Sobral! –
Bene, la mia comprensione è che "persistente" si riferisce a un'implementazione in cui l'aggiornamento di un valore immutabile restituisce un valore che condivide la sottostruttura con l'originale anziché fare un clone completo. Ciò può dare collezioni immutabili con prestazioni vicine alle loro controparti mutabili: non è necessario copiare elementi vecchi di 10k per aggiungerne uno nuovo. –
Non credo che la condivisione dei dati (al contrario della copia) sia un prerequisito per la persistenza in quanto il termine è normalmente utilizzato. (http://en.wikipedia.org/wiki/Persistent_data_structure) –
Ho trovato questo paragrafo in http://akka.io/docs/akka/1.2/scala/stm.html: "Scala fornisce i cosiddetti datastructures persistenti che rende veloce il lavoro con collezioni immutabili, sono immutabili ma con accesso e modifica costanti al tempo, usano la condivisione strutturale e un inserto o aggiornamento non rovina la vecchia struttura, quindi "persistente", rende veloce il lavoro con tipi compositi immutabili. le strutture dati attualmente consistono in una mappa e un vettore ". - Lo trovo un po 'sconcertante alla luce di questa risposta. Probabilmente ho appena frainteso qualcosa. –