Warum führt das Einfügen von 1000 000 Werten in eine transiente Karte in Clojure zu einer Karte mit 8 Elementen?

Question

Wenn ich versuche, 1000 000 assoc! auf einem transienten Vektor zu tun, werde ich einen Vektor von 1000 000 Elementen

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

auf der anderen Seite bekommen, wenn ich das gleiche mit einer Karte zu tun, wird es nur haben 8 Artikel darin

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

Gibt es einen Grund, warum das passiert?

Answer 1

Die Operationen der transienten Datentypen garantieren nicht, dass sie dieselbe Referenz wie die übergebene zurückgeben. Manchmal kann die Implementierung eine neue (aber immer noch vorübergehende) Karte nach einer assoc! zurückgeben, anstatt die Sie zu verwenden bestanden in

die ClojureDocs page on assoc! ein nice example hat, die dieses Verhalten erklärt.

;; 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. 

ich möchte den letzten Teil wiederholen, weil es sehr wichtig ist: die ursprüngliche Sammlung, die Sie in sho bestanden Sie müssen so behandelt werden, als hätten sie einen undefinierten Wert. Nur der Rückgabewert ist vorhersehbar.

Hier ist eine modifizierte Version des Codes, der wie erwartet funktioniert:

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

---

Als Randbemerkung, der Grund, warum Sie immer 8 erhalten ist, weil Clojure eine clojure.lang.PersistentArrayMap (eine Karte verwenden, mag von einem Array unterstützt) für Karten mit 8 oder weniger Elementen. Sobald Sie über 8 hinaus kommen, wechselt es zu 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 

Sobald Sie letzte 8 Einträge erhalten, Ihre vorübergehende Karte schaltet die Trägerdatenstruktur aus einer Vielzahl von Paaren (PersistentArrayMap) zu einer Hash-Tabelle (PersistentHashMap), an welchem ​​Punkt assoc! eine neue Referenz zurückgibt, anstatt nur die Aktualisierung alte.

Answer 2

Die einfachste Erklärung ist von der Clojure documentation selbst (Hervorhebung von mir):

Transienten einen parallelen Satz von sich ändernden 'Operationen unterstützen, mit ähnlichen Namen, gefolgt von! - assozi !, conj! usw. Diese machen die gleichen Dinge wie ihre hartnäckigen Gegenstücke, außer dass die Rückgabewerte selbst vorübergehend sind. Beachten Sie insbesondere, dass Transienten nicht direkt angeschlagen werden. Sie müssen den Rückgabewert beim nächsten Aufruf erfassen und verwenden.