惰性分区-按 [英] Lazy partition-by

问题描述

我有一个项源，希望单独处理具有相同键函数值的项的运行。在Python中，这将如下所示

for key_val, part in itertools.groupby(src, key_fn):
  process(key_val, part)

此解决方案完全是惰性的，即如果process不尝试存储整个part的内容，代码将在O(1)内存中运行。

Clojure解决方案

(doseq [part (partition-by key-fn src)]
  (process part))

不那么懒惰：它完全实现了每个部分。问题是，src可能有非常长的key-fn值相同的项目运行，意识到它们可能会导致OOM。

我发现this discussion声称以下函数(为POST内部的命名一致性稍作修改)足够懒

(defn lazy-partition-by [key-fn coll]
  (lazy-seq
    (when-let [s (seq coll)]
      (let [fst (first s)
            fv (key-fn fst)
            part (lazy-seq (cons fst (take-while #(= fv (key-fn %)) (next s))))]
        (cons part (lazy-partition-by key-fn (drop-while #(= fv (key-fn %)) s)))))))

然而，我不明白为什么它没有受到OOM的影响：cons单元格的两个部分都持有对s的引用，因此当process消耗part时，s被实现，但不是垃圾回收。仅当drop-while遍历part时，才有资格进行GC。

所以，我的问题是：

1. 关于lazy-partition-by不够懒的说法对吗？
2. 在开始实现下一个part时，如果我不持有对前一个part的任何引用，是否存在具有保证内存要求的partition-by实现？

编辑： 以下是Haskell中一个足够懒惰的实现：

lazyPartitionBy :: Eq b => (a -> b) -> [a] -> [[a]]
lazyPartitionBy _ [] = []
lazyPartitionBy keyFn xl@(x:_) = let
  fv = keyFn x
  (part, rest) = span ((== fv) . keyFn) xl
  in part : lazyPartitionBy keyFn rest

从span implementation、part和rest隐式共享状态可以看出。我想知道这个方法是否可以翻译成Clojure。

推荐答案

虽然这个问题引发了对语言设计的非常有趣的思考，但实际问题是您希望在常量内存中处理分区。并且实际问题是可以解决的，只要稍加反转。

将处理函数传递给生成分区的函数，而不是处理返回分区序列的函数的结果。然后，您可以以包含的方式控制状态。

首先，我们将提供一种将序列的消耗与尾部的状态融合在一起的方法。

(defn fuse [coll wick]
  (lazy-seq 
   (when-let [s (seq coll)]
     (swap! wick rest)
     (cons (first s) (fuse (rest s) wick)))))

然后是partition-by的修改版本

(defn process-partition-by [processfn keyfn coll] 
  (lazy-seq
    (when (seq coll)
      (let [tail (atom (cons nil coll))
            s (fuse coll tail)
            fst (first s)
            fv (keyfn fst)
            pred #(= fv (keyfn %))
            part (take-while pred s)
            more (lazy-seq (drop-while pred @tail))] 
        (cons (processfn part) 
              (process-partition-by processfn keyfn more))))))

注意：对于O(1)内存消耗processfn必须是心急消耗！所以当(process-partition-by identity key-fn coll)与(partition-by key-fn coll)相同时，因为identity不消耗分区，所以内存消耗不是恒定的。

---

测试

(defn heavy-seq [] 
  ;adjust payload for your JVM so only a few fit in memory
  (let [payload (fn [] (long-array 20000000))]
   (map #(vector % (payload)) (iterate inc 0))))

(defn my-process [s] (reduce + (map first s)))

(defn test1 []
  (doseq [part (partition-by #(quot (first %) 10) (take 50 (heavy-seq)))]
    (my-process part)))

(defn test2 []
  (process-partition-by 
    my-process #(quot (first %) 20) (take 200 (heavy-seq))))

so.core=> (test1)
OutOfMemoryError Java heap space  [trace missing]

so.core=> (test2)
(190 590 990 1390 1790 2190 2590 2990 3390 3790)

这篇关于惰性分区-按的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！