Clojure: Намаляването на голямата мързелива колекция изяжда паметта - представяне, памет, кълбо, последователност, мързелива оценка

Аз съм нов за 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 println• Видях, че след около 10 милиона повторения става много бавно, така че мислех, че може би 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 генератори, Вероятно ми липсва нещо очевидно, така че наистина оценявам някои указания. Благодаря!

Отговори:

6 за отговор № 1

Генераторите не са (мързеливи) последователности.

Вие държите главата тук:

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

gen-a и gen-b са гобални варове, отнасящи се до последователността на главата.

Вероятно искате нещо подобно:

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

Алтернативно, дефинирайте gen-a и gen-b като функции:

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

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

---

-1 за отговор № 2

Вместо да го използвате reductions, можете директно да изградите мързелива последователност. Този отговор използва lazy-cons от библиотеката Tupelo (бихте могли също употреба lazy-seq от clojure.core).

(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

с резултати:

"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

Имайте предвид, че времето за изпълнение е около 4 пъти по-бързо, тъй като сме изрязали функцията на генератора, която въобще не използвахме.

---

-2 за отговор № 3

Можете да получите генераторни функции на Python в Clojure използвайки библиотеката на Tupelo, Просто използвайте lazy-gen и yield така:

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

(defn rand-gen
[seed factor]
(t/lazy-gen
(loop [acc seed]
(let [next (mod (* acc factor) 2147483647)]
(t/yield next)
(recur next)))))

(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

с резултат:

"Elapsed time:   409.697922 msecs"   (time (run2 100000.0))   =>   1025
"Elapsed time:  3250.592798 msecs"   (time (run2 1000000.0))  =>   9970
"Elapsed time: 32995.194574 msecs"   (time (run2 1.0E7))      => 100068

---