Clojure-日志时间中的滑动窗口最小值

Question

给定向量大小n和窗口大小k，如何有效地计算n log k时间内的滑动窗口最小值？即，对于向量[14 3 2 5 4 2]和窗口大小2，输出将为[13 2 2 4 2]。

很明显，我可以使用分区和映射来完成，但这是n*k时间。

我想我需要跟踪排序后的地图中的最小值，并在地图在窗口外时更新地图。但是，尽管我可以在日志时间内获得排序映射的最小值，但在映射中搜索任何过期的索引并不是日志时间。

谢谢。

Answer 1

您可以使用基于Clojure的优先级映射数据结构的优先级队列来解决此问题。我们用它们在向量中的位置为窗口中的值编制索引。

• 其第一个条目的值是窗口最小值
• 我们添加新的条目，并通过键/矢量位置去除最旧的条目

是一种可能的实现方式

(use [clojure.data.priority-map :only [priority-map]])
(defn windowed-min [k coll]
(let [numbered (map-indexed list coll)
[head tail] (split-at k numbered)
init-win (into (priority-map) head)
win-seq (reductions
(fn [w [i n]]
(-> w (dissoc (- i k)) (assoc i n)))
init-win
tail)]
(map (comp val first) win-seq)))

例如，

(windowed-min 2 [1 4 3 2 5 4 2])
=> (1 3 2 2 4 2)

该解决方案开发缓慢，因此可以应用于无限序列。

---

初始化后(即O(k))，函数在O(log k)时间内计算序列中的每个元素，如下所述。

Answer 2

您可以在线性时间中求解——O(n)，而不是O(n*log k)，如1所述。http://articles.leetcode.com/sliding-window-maximum/(很容易从find max变为find min)和2。https://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html

这些方法需要一个双端队列来管理以前的值，该值在大多数队列操作(即推送/弹出/查看等)中使用O(1)时间，而在使用优先级队列(即优先级映射)时使用O(log K)时间。我使用了来自https://github.com/pjstadig/deque-clojure

实现上述第一参考中代码的主要代码(针对最小值而非最大值)：

(defn windowed-min-queue [w a]
(let [
deque-init (fn deque-init [] (reduce (fn [dq i]
(dq-push-back i (prune-back a i dq)))
empty-deque (range w)))
process-min (fn process-min [dq] (reductions (fn [q i]
(->> q
(prune-back a i)
(prune-front i w)
(dq-push-back i)))
dq (range w (count a))))
init (deque-init)
result (process-min init)] ;(process-min init)]
(map #(nth a (dq-front %)) result)))

将此方法的速度与使用优先级映射的其他解决方案进行比较(注意：我喜欢其他解决方案，因为它更简单)。

; Test using Random arrays of data
(def N 1000000)
(def a (into [] (take N (repeatedly #(rand-int 50)))))
(def b (into [] (take N (repeatedly #(rand-int 50)))))
(def w 1024)
; Solution based upon Priority Map (see other solution which is also great since its simpler)
(time (doall (windowed-min-queue w a)))
;=> "Elapsed time: 1820.526521 msecs"
; Solution based upon  double-ended queue
(time (doall (windowed-min w b)))
;=> "Elapsed time: 8290.671121 msecs"

它的速度快了4倍多，考虑到PriorityMap是用Java编写的，而双端队列代码是纯Clojure的，这是非常好的(请参阅https://github.com/pjstadig/deque-clojure)

包括在双端队列上使用的其他包装器/实用程序以供参考。

(defn dq-push-front [e dq]
(conj dq e))
(defn dq-push-back [e dq]
(proto/inject dq e))
(defn dq-front [dq]
(first dq))
(defn dq-pop-front [dq]
(pop dq))
(defn dq-pop-back [dq]
(proto/eject dq))
(defn deque-empty? [dq]
(identical? empty-deque dq))
(defn dq-back [dq]
(proto/last dq))
(defn dq-front [dq]
(first dq))
(defn prune-back [a i dq]
(cond
(deque-empty? dq) dq
(< (nth a i) (nth a (dq-back dq))) (recur a i (dq-pop-back dq))
:else dq))
(defn prune-front [i w dq]
(cond
(deque-empty? dq) dq
(<= (dq-front dq) (- i w)) (recur i w (dq-pop-front dq))
:else dq))

Answer 3

我的解决方案使用两个辅助映射来实现快速性能。我将键映射到它们的值，并将值存储到排序映射中的引用。每次移动窗口时，我都会更新地图，并获得排序后的最小地图，所有这些都在日志时间内。

缺点是代码更丑陋，不懒惰，也不地道。好处是它比优先级映射解决方案高出约2倍。不过，我认为这在很大程度上可以归咎于上述解决方案的懒惰。

(defn- init-aux-maps [w v]
(let [sv (subvec v 0 w)
km (->> sv (map-indexed vector) (into (sorted-map)))
vm (->> sv frequencies (into (sorted-map)))]
[km vm]))
(defn- update-aux-maps [[km vm] j x]
(let [[ai av] (first km)
km (-> km (dissoc ai) (assoc j x))
vm (if (= (vm av) 1) (dissoc vm av) (update vm av dec))
vm (if (nil? (get vm x)) (assoc vm x 1) (update vm x inc))]
[km vm]))
(defn- get-minimum [[_ vm]] (ffirst vm))
(defn sliding-minimum [w v]
(loop [i 0, j w, am (init-aux-maps w v), acc []]
(let [acc (conj acc (get-minimum am))]
(if (< j (count v))
(recur (inc i) (inc j) (update-aux-maps am j (v j)) acc)
acc))))