Clojure：减少大型懒惰收集会占用内存

Question

我是Clojure的新手。我有以下代码，它创建了一个无限懒惰的数字序列：

(defn generator [seed factor]
  (drop 1 (reductions 
            (fn [acc _] (mod (* acc factor) 2147483647))
            seed 
            ; using dummy infinite seq to keep the reductions going
            (repeat 1))))

序列中的每个数字都取决于先前的计算。我正在使用reductions，因为我需要所有中间结果。

然后我实例化两个生成器，如下所示：

(def gen-a (generator 59 16807))
(def gen-b (generator 393 48271))

然后我想比较这些序列的n连续结果，对于大n，并返回它们相等的次数。

起初我做了类似的事情：

(defn run []
  (->> (interleave gen-a gen-b)
       (partition 2)
       (take 40000000)
       (filter #(apply = %))
       (count)))

这花了太长时间，我看到该程序的内存使用量飙升至约4GB。对于一些printlns，我看到在大约1000万次迭代之后它变得非常慢，所以我想可能count需要将整个序列存储在内存中，所以我将其更改为使用reduce：

(defn run-2 []
  (reduce
    (fn [acc [a b]]
      (if (= a b)
        (inc acc)
        acc))
    0
    (take 40000000 (partition 2 (interleave gen-a gen-b)))))

尽管如此，它还是分配了大量内存并在前几千万之后显着放缓。我很确定它将整个懒惰序列存储在内存中，但我不知道为什么，所以我试图手动扔掉头部：

(defn run-3 []
  (loop [xs (take 40000000 (partition 2 (interleave gen-a gen-b)))
         total 0]
    (cond
      (empty? xs) total
      (apply = (first xs)) (recur (rest xs) (inc total))
      :else (recur (rest xs) total))))

同样，结果相同。这让我很难过，因为我读到我用来创建xs序列的所有函数都是懒惰的，因为我只使用当前项目，所以我期望它使用常量内存。

来自Python背景我基本上试图模仿Python Generators。我可能错过了一些明显的东西，所以我真的很感激一些指针。谢谢！

Answer 1

生成器不是（懒惰）序列。

你在这里坚持：

(def gen-a (generator 59 16807))
(def gen-b (generator 393 48271))

qazxsw poi和qazxsw poi是全球变量，指的是头部序列。

你可能想要这样的东西：

gen-a

或者，将gen-b和

(defn run []
  (->> (interleave (generator 59 16807) (generator 393 48271))
       (partition 2)
       (take 40000000)
       (filter #(apply = %))
       (count)))

定义为函数：

gen-a

Answer 2

您可以直接构建一个惰性序列，而不是使用gen-b。这个答案使用

(defn gen-a
  []
  (generator 59 16807)))
...

(defn run []
  (->> (interleave (gen-a) (gen-b))
       (partition 2)
       (take 40000000)
       (filter #(apply = %))
       (count)))

reductions（你也可以使用lazy-cons）。

from the Tupelo library

结果：

use lazy-seq from clojure.core

请注意，执行时间大约快4倍，因为我们已经删除了我们实际上并没有真正使用的生成器函数。

Answer 3

你可以在Clojure

(ns tst.demo.core
  (:use tupelo.test)
  (:require
    [tupelo.core :as t]  ))

(defn rand-gen
  [seed factor]
  (let [next (mod (* seed factor) 2147483647)]
    (t/lazy-cons next (rand-gen next factor))))

(defn run2 [num-rand]
  (->> (interleave
         ; restrict to [0..99] to simulate bad rand #'s
         (map #(mod % 100) (rand-gen 59 16807))
         (map #(mod % 100) (rand-gen 393 48271)))
       (partition 2)
       (take num-rand)
       (filter #(apply = %))
       (count)))

(t/spyx (time (run2 1e5))) ; expect ~1% will overlap => 1e3
(t/spyx (time (run2 1e6))) ; expect ~1% will overlap => 1e4
(t/spyx (time (run2 1e7))) ; expect ~1% will overlap => 1e5

中获得Python风格的生成器函数。只需使用

"Elapsed time:   90.42 msecs"  (time (run2   100000.0)) =>   1025 
"Elapsed time:  862.60 msecs"  (time (run2  1000000.0)) =>   9970
"Elapsed time: 8474.25 msecs"  (time (run2      1.0E7)) => 100068

和using the Tupelo library：

lazy-gen

结果：

yield