clojure - 延迟分区

Question

我有一个项目来源，并希望单独处理具有相同关键功能值的项目的运行。在 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值(value)并意识到它们可能会导致 OOM。

我找到了 this discussion据称以下功能(为了帖子内部的命名一致性略有修改)足够懒惰

(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 才有资格进行 GC遍历 part .

所以，我的问题是:

我对 lazy-partition-by 是否正确？还不够懒？

是否有 partition-by 的实现有保证的内存要求，前提是我不持有对以前 part 的任何引用到我开始意识到下一个的时候？

编辑:
这是 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。

Answer 1

尽管这个问题引起了关于语言设计的非常有趣的思考，但实际问题是您希望在常量内存中的分区上进行处理。实际问题可以通过一点点反演来解决。

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

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

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