1
我需要从数百万哈希映射的惰性序列中获取20个结果,但是需要基于对hashmaps中的各种值进行排序的20个结果。按clojure中的哈希映射的懒惰序列排序
例如:
(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))
太棒了!谢谢! – adamneilson