按clojure中的哈希映射的懶惰序列排序

Question

我需要從數百萬哈希映射的惰性序列中獲取20個結果，但是需要基於對hashmaps中的各種值進行排序的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) 

太好了！但...

但是我嘗試了很多，我似乎無法解決如何將這個應用於hashmaps序列。

我需要這樣的東西：

(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]}