Clojure - Раздвижное окно Минимум в журнале Время

Question

Учитывая размер и размер n окна, как я могу эффективно вычислить минимальное скольжение окна в n log k time? т.е. для вектора [1 4 3 2 5 4 2] и размера окна 2, выход будет [1 3 2 2 4 2].

Очевидно, что я могу сделать это, используя раздел и карту, но это время n * k.

Мне кажется, мне нужно отслеживать минимум на сортированной карте и обновлять карту, когда она находится за окном. Но хотя я могу получить мин сортированной карты в лог-времени, поиск по карте, чтобы найти какие-либо индексы, срок действия которых истек, - это не время регистрации.

Спасибо.

Answer 1

Вы можете решить это с помощью очереди приоритетов на основе структуры данных Clojure's priority map. Мы индексируем значения в окне с их позицией в векторе.

• Значение его первой записи - минимальное окно.
• Мы добавляем новую запись и избавляемся от самой старой из ключевых/векторных позиций.

Возможная реализация

(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 (вход к) время, как было отмечено here.

Answer 2

Мое решение использует две вспомогательные карты для достижения высокой производительности. Я сопоставляю ключи с их значениями, а также сохраняю значения для их вхождений на сортированной карте. При каждом перемещении окна я обновляю карты и получаю минимум отсортированной карты, все время журнала.

Недостаток кода является намного более уродливым, а не ленивым, а не идиоматическим. Положительным моментом является то, что он превосходит решение приоритетной карты примерно на 2x. Я думаю, что многие из них, хотя, можно обвинить в лени вышеизложенного решения.

(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)))) 

Answer 3

Вы можете решить линейное время -О (п), а не O (п * лог к)), как описано 1. http://articles.leetcode.com/sliding-window-maximum/ (легко перейти от найти Макс найти мин) и 2. https://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html

Подходы требуют очереди с двойным завершением для управления предыдущими значениями, использующими время O (1) для большинства операций с очередями (то есть push/pop/peek и т. Д.), А не O (log K) при использовании очереди приоритетов (т.е. Приоритетная карта).Я использовал Двухстороннюю очередь из https://github.com/pjstadig/deque-clojure

Основного кода для реализации коды в 1-е ссылки выше (для мин, а не макс):

(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))