如何在Clojure中快速移除向量中的元素?
我试图从Clojure向量中移除元素:
请注意,我正在使用Kotlin的Clojure操作
val set = PersistentHashSet.create("foo") val vec = PersistentVector.create("foo", "bar") val seq = clojure.`core$remove`.invokeStatic(set, vec) as ISeq val resultVec = clojure.`core$vec`.invokeStatic(seq) as PersistentVector
这相当于下面的Clojure代码:
(remove #{"foo"} ["foo" "bar"])
代码工作正常,但我注意到,从seq创建一个向量非常慢。 我写了一个基准,结果如下:
| Item count | Remove ms | Remove with converting back to vector ms| ----------------------------------------------------------------- | 1000 | 51 | 1355 | | 10000 | 71 | 5123 |
你知道我怎么可以将remove
操作产生的seq
转换回vector
而没有苛刻的性能损失?
如果这是不可能的,是否有替代方法来执行remove
操作?
你可以尝试补充操作remove
,返回一个向量:
(filterv (complement #{"foo"}) ["foo" "bar"])
请注意filterv
的使用。 v
表示它从头开始使用矢量,并返回一个矢量,所以不需要转换。 它在幕后使用transient
矢量,所以它应该相当快。
我使用complement
否定谓词,所以我可以使用filterv
,因为没有removev
。 remove
只是被定义为filter
的complement
,所以它基本上是你已经在做的,只是严格的。
你试图做的根本上表现不好。 矢量用于快速索引读/写,并且O(1)访问右端。 要做其他任何事情,你必须分开载体,并重新构建一个O(N)操作。 如果您需要这样的操作来提高效率,则必须使用不同的数据结构。
为什么不是PersistentHashSet? 快速删除,虽然没有命令。 我隐约记得Clojure也有一个排序集,以防万一需要。
您已经将接受remove
的惰性结果的错误等同于转换回向量的具体结果。 比较(remove ...)
的惰性结果和(remove ...)
(count (remove ...))
隐含的具体结果。 你会看到,它比稍稍慢一点(vec (remove ...))
。 另外,对于真正的速度关键应用程序,没有什么比使用本地Java ArrayList
:
(ns tst.demo.core (:require [criterium.core :as crit] ) (:import [java.util ArrayList])) (def N 1000) (def tgt-item (/ N 2)) (def pred-set #{ (long tgt-item) }) (def data-vec (vec (range N))) (def data-al (ArrayList. data-vec)) (def tgt-items (ArrayList. [tgt-item])) (println :lazy) (crit/quick-bench (remove pred-set data-vec)) (println :lazy-count) (crit/quick-bench (count (remove pred-set data-vec))) (println :vec) (crit/quick-bench (vec (remove pred-set data-vec))) (println :ArrayList) (crit/quick-bench (let [changed? (.removeAll data-al tgt-items)] data-al))
结果:
:lazy Evaluation count : 35819946 time mean : 10.856 ns :lazy-count Evaluation count : 8496 time mean : 69941.171 ns :vec Evaluation count : 9492 time mean : 62965.632 ns :ArrayList Evaluation count : 167490 time mean : 3594.586 ns