Perché inserire 1000.000 valori in una mappa transitoria in Clojure produce una mappa con 8 elementi al suo interno?

Question

Se provo a fare 1000 000 assoc! su un vettore transitoria, vado a prendere un vettore di 1000 000 elementi

(count 
    (let [m (transient [])] 
    (dotimes [i 1000000] 
     (assoc! m i i)) (persistent! m))) 
; => 1000000 

d'altra parte, se faccio la stessa cosa con una mappa, si avrà solo 8 articoli in esso

(count 
    (let [m (transient {})] 
    (dotimes [i 1000000] 
     (assoc! m i i)) (persistent! m))) 
; => 8 

C'è un motivo per cui questo sta accadendo?

Answer 1

Le operazioni dei tipi di dati transitori non garantiscono che restituiranno lo stesso riferimento di quello passato. A volte l'implementazione potrebbe decidere di restituire una nuova (ma ancora transitoria) mappa dopo un assoc! anziché utilizzare quella che approvata nel

il ClojureDocs page on assoc! ha un nice example che spiega questo comportamento:.

;; The key concept to understand here is that transients are 
;; not meant to be `bashed in place`; always use the value 
;; returned by either assoc! or other functions that operate 
;; on transients. 

(defn merge2 
    "An example implementation of `merge` using transients." 
    [x y] 
    (persistent! (reduce 
       (fn [res [k v]] (assoc! res k v)) 
       (transient x) 
       y))) 

;; Why always use the return value, and not the original? Because the return 
;; value might be a different object than the original. The implementation 
;; of Clojure transients in some cases changes the internal representation 
;; of a transient collection (e.g. when it reaches a certain size). In such 
;; cases, if you continue to try modifying the original object, the results 
;; will be incorrect. 

;; Think of transients like persistent collections in how you write code to 
;; update them, except unlike persistent collections, the original collection 
;; you passed in should be treated as having an undefined value. Only the return 
;; value is predictable. 

mi piacerebbe ripetere che l'ultima parte, perché è molto importante: collezione originale che avete passato in sho essere trattati come aventi un valore indefinito. Solo il valore restituito è prevedibile.

Ecco una versione modificata del codice che funziona come previsto:

(count 
    (let [m (transient {})] 
    (persistent! 
     (reduce (fn [acc i] (assoc! acc i i)) 
       m (range 1000000))))) 

---

Come nota a margine, la ragione si ottiene sempre 8 è perché Clojure ama usare un (una mappa clojure.lang.PersistentArrayMap supportato da un array) per mappe con 8 o meno elementi. Una volta superato 8, passa a clojure.lang.PersistentHashMap.

user=> (type '{1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a}) 
clojure.lang.PersistentArrayMap 
user=> (type '{1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a}) 
clojure.lang.PersistentHashMap 

volta passato 8 iscrizioni, la mappa transitoria commuta la struttura di dati di supporto da una matrice di coppie (PersistentArrayMap) a una tabella hash (PersistentHashMap), a questo punto assoc! restituisce un nuovo riferimento invece di aggiornamento del vecchia.

Answer 2

La spiegazione più semplice è dal Clojure documentation stesso (sottolineatura mia):

transitori supportano un insieme parallelo di 'cambiamento' operazioni, con nomi simili seguiti da! - assoc !, conj! ecc. Questi fanno le stesse cose delle loro controparti persistenti, eccetto che i valori di ritorno sono essi stessi transitori. Si noti in particolare che i transienti non sono progettati per essere colpiti sul posto. È necessario acquisire e utilizzare il valore restituito nella prossima chiamata.