Clojure: Reduzindo grande coleção lenta consome memória - desempenho, memória, clojure, sequência, avaliação lenta

Eu sou novo para Clojure. Eu tenho o seguinte código, que cria uma seqüência infinita de números:

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

Cada número na sequência depende do cálculo anterior. Estou a usar reductions porque eu preciso de todos os resultados intermediários.

Eu instancio então dois geradores assim:

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

Eu então quero comparar n resultados consecutivos dessas seqüências, para n grande, e retornar o número de vezes que eles são iguais.

No começo eu fiz algo como:

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

Estava demorando muito e eu vi o uso de memória do programa subir para cerca de 4GB. printlns Eu vi que depois de cerca de 10 milhões de iterações ficou muito lento, então eu estava pensando que talvez count necessário para armazenar toda a seqüência na memória, então eu mudei para usar 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)))))

Ainda assim, alocava muita memória ediminuindo significativamente após os primeiros dois milhões. Tenho certeza de que ele está armazenando toda a sequência lenta na memória, mas não sei por que, então tentei jogar fora a cabeça manualmente:

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

Mais uma vez, os mesmos resultados. Isso me impressionou porque eu estou lendo que todas as funções que eu estou usando para criar o meu xs As sequências são preguiçosas e, como estou usando apenas o item atual, estou esperando que ele use memória constante.

Vindo de um plano de fundo em Python, estou basicamente tentando imitar Geradores Python. Eu provavelmente estou perdendo algo óbvio, então eu realmente aprecio alguns ponteiros. Obrigado!

Respostas:

6 para resposta № 1

Geradores não são seqüências (preguiçosas).

Você está segurando a cabeça aqui:

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

gen-a e gen-b são gobal vars referindo-se à cabeça uma sequência.

Você provavelmente quer algo como:

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

Como alternativa, defina gen-a e gen-b como funções:

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

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

---

-1 para resposta № 2

Em vez de usar reductions, você poderia construir uma seqüência preguiçosa diretamente. Esta resposta usa lazy-cons da biblioteca Tupelo (você também pode usar lazy-seq de 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

com resultados:

"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

Note que os tempos de execução são cerca de 4x mais rápidos, uma vez que cortamos o material da função de gerador que não estávamos realmente usando de qualquer maneira.

---

-2 para resposta № 3

Você pode obter funções geradoras no estilo Python no Clojure usando a biblioteca Tupelo. Apenas use lazy-gen e yield igual a:

(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

com resultado:

"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

---