我正在创建无序的数据元素对。@Chouser 在这个问题上的评论说哈希集是用每个节点 32 个子节点实现的，而排序集是用每个节点 2 个子节点实现的。这是否意味着如果我使用排序集而不是哈希集（假设数据元素是可比较的，即可以排序）实现它们，我的对将占用更少的空间？（我怀疑这对我来说在实践中是否重要。我只会有数百个这样的对，并且在二元素数据结构中查找，甚至在向量或列表中的顺序查找应该很快。但我很好奇。）
问问题
310 次
4 回答
1
在比较显式查看列表的前两个元素时，与使用 Clojure 的内置集合相比，我在运行它一千万次时没有发现显着差异：
user> (defn my-lookup [key pair]
(condp = key
(first pair) true
(second pair) true false))
#'user/my-lookup
user> (time (let [data `(1 2)]
(dotimes [x 10000000] (my-lookup (rand-nth [1 2]) data ))))
"Elapsed time: 906.408176 msecs"
nil
user> (time (let [data #{1 2}]
(dotimes [x 10000000] (contains? data (rand-nth [1 2])))))
"Elapsed time: 1125.992105 msecs"
nil
当然，像这样的微基准本身就有缺陷，很难真正做好，所以不要试图用它来证明一个比另一个更好。我只是想证明它们非常相似。
于 2013-11-05T22:12:59.707 回答
1
这应该是一个评论，但我的声誉太短，太渴望分享信息。如果您担心 Zachary Tellman 的性能 clj-tuple 可能比普通列表/向量快 2-3 倍，如ztellman / clj-tuple 所述。
于 2013-11-06T17:07:48.120 回答
1
如果我用无序对做某事，我通常喜欢使用地图，因为这样可以很容易地查找其他元素。例如，如果我的对是[2 7]，那么我将使用{2 7, 7 2}，并且我可以做到({2 7, 7 2} 2)，这给了我7。
至于空间，PersistentArrayMap实施实际上非常注重空间。如果您查看源代码（请参阅上一个链接），您会看到它分配了Object[]保存所有键/值对所需的确切大小。我认为这被用作所有不超过 8 个键/值对的映射的默认映射类型。
这里唯一的问题是您需要小心重复键。{2 2, 2 2}会导致异常。您可以通过执行以下操作来解决此问题：(merge {2 2} {2 2})，即(merge {a b} {b a})在可能的情况下a并b具有相同的值。
这是我的repl中的一个小片段：
user=> (def a (array-map 1 2 3 4))
#'user/a
user=> (type a)
clojure.lang.PersistentArrayMap
user=> (.count a) ; count simply returns array.length/2 of the internal Object[]
2
请注意，我array-map在上面明确调用。这与我刚才在 repl 中提出的与地图文字和 repl 相关的问题有关def：为什么绑定会影响我的地图类型？
于 2013-11-05T22:34:23.283 回答
0
我现在不打算对不同的对表示进行基准测试，但@ArthurUlfeldt 的回答和@DaoWen 的引导我这样做了。这是我使用标准bench宏的结果。源代码如下。总而言之，正如预期的那样，我测试的七个表示之间没有太大差异。但是，最快的数组映射和哈希映射以及其他的时间之间存在差距。这与道文和 Arthur Ulfeldt 的说法是一致的。
以秒为单位的平均执行时间，从最快到最慢（MacBook Pro，2.3GHz Intel Core i7）：
数组映射：5.602099
哈希图：5.787275
矢量：6.605547
排序集：6.657676
哈希集：6.746504
列表：6.948222
编辑：我添加了test-control下面的运行，它只执行所有不同其他测试的共同点。 test-control平均耗时 5.571284 秒。似乎这些表示和其他表示之间的差异-map比我想象的要大：访问两个条目的哈希映射或数组映射基本上是瞬时的（在我的计算机、操作系统、Java 等上），而对于 1000 万次迭代，其他表示大约需要一秒钟。考虑到它有 1000 万次迭代，这意味着这些操作仍然几乎是瞬时的。（我的猜测是，这test-arraymap比test-control计算机后台发生的其他事情的噪音要快。或者它可能与编译的特性有关。）
（一个警告：我忘了提到我收到了来自 criterium 的警告：“JVM 参数 TieredStopAtLevel=1 处于活动状态，并且可能会导致意外结果，因为 JIT C2 编译器可能未处于活动状态。”我相信这意味着 Leiningen 是使用适用于 -server JIT 编译器的命令行选项启动 Java，但使用默认的 -client JIT 编译器运行。所以警告是说“你认为你正在运行 -server，但你不是，所以不要指望 -server 的行为。”使用 -server 运行可能会改变上面给出的时间。）
(use 'criterium.core)
;; based on Arthur Ulfedt's answer:
(defn pairlist-contains? [key pair]
(condp = key
(first pair) true
(second pair) true
false))
(defn pairvec-contains? [key pair]
(condp = key
(pair 0) true
(pair 1) true
false))
(def ntimes 10000000)
;; Test how long it takes to do what's common to all of the other tests
(defn test-control []
(print "=============================\ntest-control:\n")
(bench
(dotimes [_ ntimes]
(def _ (rand-nth [:a :b])))))
(defn test-list []
(let [data '(:a :b)]
(print "=============================\ntest-list:\n")
(bench
(dotimes [_ ntimes]
(def _ (pairlist-contains? (rand-nth [:a :b]) data))))))
(defn test-vec []
(let [data [:a :b]]
(print "=============================\ntest-vec:\n")
(bench
(dotimes [_ ntimes]
(def _ (pairvec-contains? (rand-nth [:a :b]) data))))))
(defn test-hashset []
(let [data (hash-set :a :b)]
(print "=============================\ntest-hashset:\n")
(bench
(dotimes [_ ntimes]
(def _ (contains? data (rand-nth [:a :b])))))))
(defn test-sortedset []
(let [data (sorted-set :a :b)]
(print "=============================\ntest-sortedset:\n")
(bench
(dotimes [_ ntimes]
(def _ (contains? data (rand-nth [:a :b])))))))
(defn test-hashmap []
(let [data (hash-map :a :a :b :b)]
(print "=============================\ntest-hashmap:\n")
(bench
(dotimes [_ ntimes]
(def _ (contains? data (rand-nth [:a :b])))))))
(defn test-arraymap []
(let [data (array-map :a :a :b :b)]
(print "=============================\ntest-arraymap:\n")
(bench
(dotimes [_ ntimes]
(def _ (contains? data (rand-nth [:a :b])))))))
(defn test-all []
(test-control)
(test-list)
(test-vec)
(test-hashset)
(test-sortedset)
(test-hashmap)
(test-arraymap))
于 2013-11-06T06:30:23.323 回答