Dlaczego wstawienie 1000 000 wartości na mapie przejściowej w Clojure daje mapę zawierającą 8 elementów?

Question

Gdy próbuję zrobić 1000 000 assoc! na przejściową wektorze Wezmę wektor 1000 000 elementów

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

Z drugiej strony, jeśli zrobić to samo z mapą, będzie miał tylko 8 elementów w nim:

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

Czy istnieje powód, dla którego tak się dzieje?

Answer 1

Operacje typów danych przejściowych nie gwarantują, że zwrócą takie same wartości referencyjne, jak te, które zostały przekazane. Czasami implementacja może zdecydować o zwrocie nowej (ale wciąż przejściowej) mapy po assoc! zamiast korzystania z tej, którą przeszedł w

ClojureDocs page on assoc! ma nice example że wyjaśnia to zachowanie.

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

chciałbym powtórzyć tę ostatnią część, ponieważ jest to bardzo ważne: oryginalna kolekcja zdałeś w sho powinny być traktowane jako mające nieokreśloną wartość. Tylko wartość zwracana jest przewidywalna.

Oto zmodyfikowana wersja kodu, który działa zgodnie z oczekiwaniami:

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

---

Na marginesie, powód zawsze otrzymasz 8 dlatego Clojure lubi używać clojure.lang.PersistentArrayMap (mapę poparte tablicą) dla map zawierających 8 lub mniej elementów. Po przejściu przez 8 przełączy się na 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 

Po ominąć 8 wpisów, Twój przemijający mapa włącza struktury danych podkład z tablicy par (PersistentArrayMap) do hashtable (PersistentHashMap), w którym momencie assoc! zwraca nową referencję zamiast po prostu aktualizowanie stary.

Answer 2

Najprostszym wyjaśnieniem jest od samego Clojure documentation (podkreślenie moje):

Transients wspierać równoległą zestaw „zmiennych” operacji, o podobnych nazwach następnie! - assoc !, conj! itp. Robią to samo, co ich trwałe odpowiedniki, z tym że same wartości zwracane są przejściowe. Należy zwrócić uwagę w szczególności na to, że transjenty nie są zaprojektowane w taki sposób, aby były rozgrywane na miejscu. Musisz przechwycić i użyć wartości zwracanej w następnym wywołaniu.