сортировка по ленивой последовательности хэш-карт в clojure

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

Например:

(def population [{:id 85187153851 :name "anna" :created #inst "2012-10-23T20:36:25.626-00:00" :rank 77336}
         {:id 12595145186 :name "bob" :created #inst "2011-02-03T20:36:25.626-00:00" :rank 983666}
         {:id 98751563911 :name "cartmen" :created #inst "2007-01-13T20:36:25.626-00:00" :rank 112311}
         ...
         {:id 91514417715 :name "zaphod" :created #inst "2015-02-03T20:36:25.626-00:00" :rank 9866}]

В нормальных условиях простая sort-by работа могла бы выполнить свою работу:

(sort-by :id population)
(sort-by :name population)
(sort-by :created population)
(sort-by :rank population)

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

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

Скорость и эффективность имеют первостепенное значение, лучшее, что я нашел, - это пример быстрой сортировки из Joy Of Clojure (глава 6.4), которая выполняет достаточно работы, чтобы вернуть требуемый результат.

(ns joy.q)

(defn sort-parts
  "Lazy, tail-recursive, incremental quicksort.  Works against
   and creates partitions based on the pivot, defined as 'work'."
  [work]
  (lazy-seq
   (loop [[part & parts] work]
     (if-let [[pivot & xs] (seq part)]
       (let [smaller? #(< % pivot)]
         (recur (list*
                 (filter smaller? xs)
                 pivot
                 (remove smaller? xs)
                 parts)))
       (when-let [[x & parts] parts]
         (cons x (sort-parts parts)))))))

(defn qsort [xs]
    (sort-parts (list xs)))

Очень хорошо работает ...

(time (take 10 (qsort (shuffle (range 10000000)))))
"Elapsed time: 551.714003 msecs"
(0 1 2 3 4 5 6 7 8 9)

Здорово! Но...

Как бы я ни старался, я не могу понять, как применить это к последовательности хэш-карт.

Мне нужно что-то вроде:

(take 20 (qsort-by :created population))

hashmap clojure lazy-sequences quicksort
person adamneilson    schedule 04.09.2015    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Если вам нужны только верхние N элементов, полная сортировка будет слишком затратной (даже ленивая сортировка, как в JoC: она должна сохранить почти весь набор данных в памяти).

Вам нужно только просканировать (reduce) набор данных и сохранить на данный момент N лучших элементов.

=> (defn top-by [n k coll]
     (reduce
      (fn [top x]
        (let [top (conj top x)]
          (if (> (count top) n)
            (disj top (first top))
            top)))
      (sorted-set-by #(< (k %1) (k %2))) coll))
#'user/top-by
=> (top-by 3 first [[1 2] [10 2] [9 3] [4 2] [5 6]])
#{[5 6] [9 3] [10 2]}
person cgrand    schedule 04.09.2015
comment
Фантастика! Спасибо! - person adamneilson; 04.09.2015