算法 – 在clojure中有效地映射向量的一部分
|
我想知道如何在Clojure中以惯用和有效的方式完成这项工作：
1)给出一个包含n个整数的向量：[A0 A1 A2 A3 … An] 2)将最后的x项增加1(假设x为100),这样矢量将变为：[A0 A1 A2 A3 …(An-99 1)(An-98 1)…(An-1 1 )(An 1)] 一个天真的实现看起来像： (defn inc-last [x nums]
(let [n (count nums)]
(map #(if (>= % (- n x)) (inc %2) %2)
(range n)
nums)))
(inc-last 2 [1 2 3 4])
;=> [1 2 4 5]
在此实现中,基本上您只需通过检查每个项目来查看是否需要增加整个向量到另一个向量. 但是,这是一个O(n)操作,而我只想更改向量中的最后x项.理想情况下,这应该在O(x)而不是O(n)中完成. 我正在考虑使用像split-at / concat这样的函数来实现它,如下所示： (defn inc-last [x nums]
(let [[nums1 nums2] (split-at x nums)]
(concat nums1 (map inc nums2))))
但是,我不确定这个实现是O(n)还是O(x).我是Clojure的新手,并不确定Clojure中持久数据结构上的concat / split-at等操作的时间复杂度. 所以我的问题是： 1)第二次实施的时间复杂度是多少？ 2)如果它仍然是O(n),是否有任何惯用且有效的实现只需要Clojure中的O(x)来解决这个问题？ 任何评论表示赞赏.谢谢. 更新： noisesmith的回答告诉我,split-at会将矢量转换为列表,这是我之前没有意识到的事实.由于我将对结果进行随机访问(在处理向量后调用nth),我希望有一个有效的解决方案(O(x)时间),同时保持向量而不是列表,否则第n个也将减慢我的程序. 解决方法
inc-last是一个使用瞬态的实现,它允许在恒定时间内获得可修改的“就地”向量并返回持久性！矢量也在恒定时间内,允许在O(x)中进行更新.最初的实现使用了命令式的doseq循环,但是,如评论中所提到的,瞬态操作可以返回一个新对象,因此最好以功能方式继续执行操作.
我添加了一个doall来调用inc-last-2,因为它返回一个懒惰的seq,但是inc-last和inc-last-3返回一个向量,所以doall需要能够比较它们. 根据我做的一些快速测试,inc-last和inc-last-3在性能方面实际上没有太大差异,甚至对于巨大的矢量(10000000个元素)也没有.然而,对于inc-last-2实现,即使对于1000个元素的向量,仅修改最后10个元素,它也会有相当大的差异,它会慢大约100倍.对于较小的向量或当n接近(计数nums)时,差异并不是那么大. (感谢Micha?Marczyk的有用评论) (def x (vec (range 1000)))
(defn inc-last [n x]
(let [x (transient x)
l (count x)]
(->>
(range (- l n) l)
(reduce #(assoc! %1 %2 (inc (%1 %2))) x)
persistent!)))
(defn inc-last-2 [x nums]
(let [n (count nums)]
(map #(if (>= % (- n x)) (inc %2) %2)
(range n)
nums)))
(defn inc-last-3 [n x]
(let [l (count x)]
(reduce #(assoc %1 %2 (inc (%1 %2))) x (range (- l n) l))))
(time
(dotimes [i 100]
(inc-last 50 x)))
(time
(dotimes [i 100]
(doall (inc-last-2 10 x))))
(time
(dotimes [i 100]
(inc-last-3 50 x)))
;=> "Elapsed time: 49.7965 msecs"
;=> "Elapsed time: 1751.964501 msecs"
;=> "Elapsed time: 67.651 msecs"
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |