You got me going!
- I didn’t find any way to pretty print while sorting keys
-
(array-map) ordering seems to be unstable
-
(hash-map) ordering seems to be stable
- Clojure seems to use array maps for small maps (<= 8 items) and hash maps for larger maps (>= 9 items)
My conclusions:
- You can choose not to care – you might mostly get hash maps anyway.
- If you do care, consider converting to sorted maps before starting. You can use
clojure.walk/postwalk to traverse an arbitrary nested structure and do conversion.
Converting to sorted maps in an arbitrary nested data structure:
(require '[clojure.walk])
(defn maps->sorted-maps [data]
(clojure.walk/postwalk
(fn [item]
(if (instance? clojure.lang.IPersistentMap item)
(into (sorted-map) item)
item))
data))
(-> (zipmap [1 2 3] (repeat 'n))
maps->sorted-maps
prn)
;; => {1 n, 2 n, 3 n}
(-> (zipmap [3 2 1] (repeat 'n))
maps->sorted-maps
prn)
;; => {1 n, 2 n, 3 n}
Following is what I tried at the REPL. If you want better backing for the claims, some test.check properties for this may be interesting.
REPL explorations
(require '[clojure.pprint :refer [pprint]])
;; Is the ordering stable?
;; I think it may depend on whether we get an arraymap or a hashmap.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Test 1: is (keys) ordering the same as (pprint) ordering?
(for [sample-len [3 6 9 12]]
(let [m (zipmap (range sample-len)
(repeat 'n))]
(pprint m)
(pprint (keys m))))
;; =>
;; {0 n, 1 n, 2 n}
;; (0 1 2)
;; {0 n, 1 n, 2 n, 3 n, 4 n, 5 n}
;; (0 1 2 3 4 5)
;; {0 n, 7 n, 1 n, 4 n, 6 n, 3 n, 2 n, 5 n, 8 n}
;; (0 7 1 4 6 3 2 5 8)
;; {0 n, 7 n, 1 n, 4 n, 6 n, 3 n, 2 n, 11 n, 9 n, 5 n, 10 n, 8 n}
;; (0 7 1 4 6 3 2 11 9 5 10 8)
;; Conclusion: Looks equal as far as I can tell.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Test 2: do we get the same ordering as we add more keys?
(for [sample-len [3 6 9 12 15 18]]
(let [m (zipmap (range sample-len)
(repeat 0))]
(prn `(~'range ~sample-len))
(pprint (keys m))
(println (type m))
(println)
))
;; =>
;; (range 3)
;; (0 1 2)
;; clojure.lang.PersistentArrayMap
;;
;; (range 6)
;; (0 1 2 3 4 5)
;; clojure.lang.PersistentArrayMap
;;
;; (range 9)
;; (0 7 1 4 6 3 2 5 8)
;; clojure.lang.PersistentHashMap
;;
;; (range 12)
;; (0 7 1 4 6 3 2 11 9 5 10 8)
;; clojure.lang.PersistentHashMap
;;
;; (range 15)
;; (0 7 1 4 13 6 3 12 2 11 9 5 14 10 8)
;; clojure.lang.PersistentHashMap
;;
;; (range 18)
;; (0 7 1 4 15 13 6 17 3 12 2 11 9 5 14 16 10 8)
;; clojure.lang.PersistentHashMap
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Test 3: is intmap ordering stable?
(prn (zipmap [1 2 3 4 5 6] (repeat 'n)))
;; => {1 n, 2 n, 3 n, 4 n, 5 n, 6 n}
(prn (zipmap [6 5 4 3 2 1] (repeat 'n)))
;; => {6 n, 5 n, 4 n, 3 n, 2 n, 1 n}
;; We seem to get the same order as we put the items in. So not a stable
;; ordering!
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Test 4: is hashmap ordering stable?
(prn (zipmap [1 2 3 4 5 6 7 8 9] (repeat 'n)))
;; => {7 n, 1 n, 4 n, 6 n, 3 n, 2 n, 9 n, 5 n, 8 n}
(prn (zipmap [9 8 7 6 5 4 3 2 1] (repeat 'n)))
;; => {7 n, 1 n, 4 n, 6 n, 3 n, 2 n, 9 n, 5 n, 8 n}
;; Conclusion: looks like they key ordering is stable as long as we have
;; hashmaps.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Test 5: when do we flip into hash maps?
(defn map-of-length [n]
(zipmap (range n) (repeat 'n)))
(pprint (for [n (range 12)]
[n (type (map-of-length n))]))
;; ([0 clojure.lang.PersistentArrayMap]
;; [1 clojure.lang.PersistentArrayMap]
;; [2 clojure.lang.PersistentArrayMap]
;; [3 clojure.lang.PersistentArrayMap]
;; [4 clojure.lang.PersistentArrayMap]
;; [5 clojure.lang.PersistentArrayMap]
;; [6 clojure.lang.PersistentArrayMap]
;; [7 clojure.lang.PersistentArrayMap]
;; [8 clojure.lang.PersistentArrayMap]
;; [9 clojure.lang.PersistentHashMap]
;; [10 clojure.lang.PersistentHashMap]
;; [11 clojure.lang.PersistentHashMap])
Didn’t know it was sorted as a binary.