как обрабатывать отсортированные данные в clojure эффективно?

Question

У меня есть последовательность отсортированных данных и хочу установить соседний флаг. например, для следующих данных, для любого элемента, если у какого-либо соседа есть флаг как 1, тогда установите с любым соседом, помеченным как 1 для этого элемента. Мы могли бы определить соседа, как разность seq равна < = 2, если diff < = 2, то они соседние. Может быть миллион точек данных.

(def a '({:seq 1 :flag 1} {:seq 2 :flag 0} {:seq 5 :flag 0} {:seq 8 :flag 0} {:seq 10 :flag 1} {:seq 12 :flag 1})) 

ожидаемый результат:

({:seq 1 :any-neighbor-flagged 0} {:seq 2 :any-neighbor-flagged 1} {:seq 5 :any-neighbor-flagged 0} {:seq 8 :any-neighbor-flagged 1} 
{:seq 10 :any-neighbor-flagged 1} {:seq 12 :any-neighbor-flagged 1}) 

Answer 1

Основная идея состоит в том, чтобы отобразить на 3 последовательности - оригинал один, сдвинутых на 1 влево и сдвинуты на один направо:

(defn set-flags [coll] 
    (map 
    (fn [curr {nf :flag} {pf :flag}] 
     (-> curr 
      (dissoc :flag) 
      (assoc :any-neighbor-flagged (if (or (= pf 1) (= nf 1)) 1 0)))) 
    coll 
    (concat [{}] (drop-last coll)) 
    (concat (rest coll) [{}]))) 

(set-flags a) ; => ({:any-neighbor-flagged 0, :seq 1} {:any-neighbor-flagged 1, :seq 2} {:any-neighbor-flagged 0, :seq 5} {:any-neighbor-flagged 1, :seq 8} {:any-neighbor-flagged 1, :seq 10} {:any-neighbor-flagged 1, :seq 12}) 

Иллюстрация (для простоты отображается только значение :flag):

(1 0 0 0 [1] 1) ; original seq 
--------------- 
    (1 0 0 [0] 1) ; shifted to right 
(0 0 0 1 [1]) ; shifted to left 

Теперь в функции map у нас также есть соседний и правый соседний для каждого элемента ввода (возможно, пустые карты). Исходя из этого, легко установить правильное значение для :any-neighbor-flagged.

Answer 2

С partition мы можем посмотреть коллекцию с соседним контекстом.

user=> (partition 3 1 (range 10)) 
((0 1 2) (1 2 3) (2 3 4) (3 4 5) (4 5 6) (5 6 7) (6 7 8) (7 8 9)) 

Учитывая вход в таком виде, мы можем использовать reduce накапливать результат, основанный на соседних сравнений.

user=> (pprint/pprint (reduce (fn [acc [i j k]] 
            (conj acc 
             (assoc j :any-neighbor-flagged 
               (if (or (= (:flag i) 1) 
                 (= (:flag k) 1)) 
                1 0)))) 
           [] 
           (partition 3 1 (concat [nil] a [nil])))) 
[{:any-neighbor-flagged 0, :seq 1, :flag 1} 
{:any-neighbor-flagged 1, :seq 2, :flag 0} 
{:any-neighbor-flagged 0, :seq 5, :flag 0} 
{:any-neighbor-flagged 1, :seq 8, :flag 0} 
{:any-neighbor-flagged 1, :seq 10, :flag 1} 
{:any-neighbor-flagged 1, :seq 12, :flag 1}]