如何将树状图用于二维键？

Question

我想映射大量元组。我的地图看起来像：

{[1 2] :thing}

除了可能有几百万。我有一种感觉，树形图可能是一个很好的测试对象，所以我正在努力让它发挥作用。我似乎无法正确使用比较功能。

(defn compare 
  [[x y] [xx yy]]
  (cond
   (and (= x xx) (= y yy)) 0
   (and (<= x xx) (<= y yy)) -1
   (and (<= x xx) (> y yy)) -1
   (and (> x xx) (<= y yy)) 1
   (and (> x xx) (> y yy)) 1))

一些微不足道的输入似乎有效

user=> (compare [1 1] [1 1])
0
user=> (compare [1 1] [2 2])
-1
user=> (compare [1 2] [2 1])
-1
user=> (compare [2 1] [1 2])
1

但如果我创建涵盖所有组合的输入，地图应该将它们视为不同的。

(def inputs
    "All tuples of [0-4, 5-10]."
    (clojure.math.combinatorics/cartesian-product
      (range 0 4) 
      (range 5 10)))

(def input-pairs
     "All possible pairs of tuples"
     (clojure.math.combinatorics/cartesian-product inputs inputs))

如果我测试比较函数，它 returns 零只有当两个向量在结构上相同时。

user=> (doseq [[a b] input-pairs]
  #_=>   (when (zero? (compare a b)) (prn a b)))
(0 5) (0 5)
(0 6) (0 6)
(0 7) (0 7)
(0 8) (0 8)
(0 9) (0 9)
(1 5) (1 5)
etc

所以我认为我的比较功能是正确的。然而，在树图中使用它会产生一些奇怪的结果：

(def inputs-kvs
    "Inputs in the format that the hash-map and sorted-map constructor understand"
    (mapcat #(vector % (apply str %))
            (clojure.math.combinatorics/cartesian-product
              (range 0 4) 
              (range 5 10))))

将这些放在哈希图中给出正确答案

(count (apply assoc (hash-map) inputs-kvs))
=> 20

但是将它们放入具有给定比较的树图中：

(def structure (sorted-map-by compare))
(count (apply assoc structure inputs-kvs))
=> 4

(apply assoc structure inputs-kvs)
=> {(0 5) "25", (1 6) "36", (2 7) "37", (3 5) "39"}

“25”已存储在 (0 5) 槽中。但是比较函数并没有说 (0 5) 和 (2 5) 相同：

=> (compare [0 5] [2 5])
-1

我做错了什么？我可以做这个工作吗？将二维 space 投影到一维上是否有意义？

（为了避免您可能遇到的问题，是的，我已经尝试过二维结构，例如 (sorted-map 1 (sorted-map 2 :value))，但我正在尝试寻找性能更好的替代方案）

Answer 1

我刚刚添加了 (vec %) 以保留元组向量 - 不应更改任何内容。

如您所见，它在这里有效。

可能是你有一些旧的 REPL 东西在身边 - 特别是因为你别名 clojure.core/compare ？

; using your compare function
(def inp (mapcat #(vector (vec %) (apply str %)) 
  (clojure.math.combinatorics/cartesian-product (range 0 4) (range 5 10))))
; => ([0 5] "05" [0 6] "06" [0 7] "07" [0 8] "08" ...
(count inp) 
; => 40 
(apply assoc structure inp)
; => {[0 9] "09", [0 8] "08", [0 7] "07", [0 6] "06", ....
(count (apply assoc structure inp))
; => 20

Answer 2

Clojure 已经自带 compare:

user=> (doc compare)
-------------------------
clojure.core/compare
([x y])
  Comparator. Returns a negative number, zero, or a positive number
  when x is logically 'less than', 'equal to', or 'greater than'
  y. Same as Java x.compareTo(y) except it also works for nil, and
  compares numbers and collections in a type-independent manner. x
  must implement Comparable

其行为与 OP 自身的功能相同，但很可能效率更高：

user=> (compare [1 1] [1 1])
0
user=> (compare [1 1] [2 2])
-1
user=> (compare [2 1] [1 2])
1

行为记录在 Section about Vectors (IPersistentVector) in the Data Structures docs:

Vectors are compared first by length, then each element is compared in order.

所以你可以只使用来自核心的 sorted-map-by compare，或者因为这是默认值，所以只是 sorted-map 用于你的数据结构：

user=> (def m (into {} (let [r #(- (rand-int 10) (rand-int 10))] (for [a (range -1 2) b (range -1 2)] [[(r) (r)] (str a b)]))))
#'user/m
user=> (>pprint m)
{[-7 -4] "10",
 [-3 5] "01",
 [-5 -7] "00",
 [5 2] "11",
 [-3 1] "-10",
 [7 -4] "-11",
 [0 -6] "0-1",
 [3 1] "-1-1",
 [-8 -1] "1-1"}
nil
user=> (>pprint (into (sorted-map-by compare) m))
{[-8 -1] "1-1",
 [-7 -4] "10",
 [-5 -7] "00",
 [-3 1] "-10",
 [-3 5] "01",
 [0 -6] "0-1",
 [3 1] "-1-1",
 [5 2] "11",
 [7 -4] "-11"}
nil
user=> (>pprint (into (sorted-map) m))
{[-8 -1] "1-1",
 [-7 -4] "10",
 [-5 -7] "00",
 [-3 1] "-10",
 [-3 5] "01",
 [0 -6] "0-1",
 [3 1] "-1-1",
 [5 2] "11",
 [7 -4] "-11"}
nil
user=> (assert (= (into (sorted-map-by compare) m) (into (sorted-map) m)))
nil

如何将树状图用于二维键？

How do I use a treemap for a 2 dimensional keys?

clojure

data-structures

clojure-core