在 clojure 中对哈希映射的惰性序列进行排序

Question

我需要从数百万个散列映射的惰性序列中获取 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)

但我需要尽可能快地跨数百万条记录执行此操作，并且想懒惰地执行此操作，而不必实现整个数据集。

我环顾四周，发现许多算法的实现非常适合对值序列（主要是数字）进行排序，但 none 以我的方式对散列映射的惰性序列进行排序需要。

速度和效率是最重要的，我发现的最好的是 Joy Of Clojure 书中（第 6.4 章）中的快速排序示例，它所做的工作足以 return 所需的结果。

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

Answer 1

如果您只需要前 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]}

在 clojure 中对哈希映射的惰性序列进行排序

sort-by on a lazy sequence of hash-maps in clojure

clojure

hashmap

quicksort

lazy-sequences