Clojureで怠惰なseqを生成する非線形の減速

Question

与えられた入力コレクションのnグラムを怠惰なseqとして返す関数を実装しました。

(defn gen-ngrams 
    [n coll] 
    (if (>= (count coll) n) 
    (lazy-seq (cons (take n coll) (gen-ngrams n (rest coll)))))) 

この関数を大きな入力コレクションで呼び出すと、実行時間が直線的に増加することが予想されます。しかし、私が観察するタイミングはそれよりも悪いです：

user> (time (count (gen-ngrams 3 (take 1000 corpus)))) 
"Elapsed time: 59.426 msecs" 
998 
user> (time (count (gen-ngrams 3 (take 10000 corpus)))) 
"Elapsed time: 5863.971 msecs" 
9998 
user> (time (count (gen-ngrams 3 (take 20000 corpus)))) 
"Elapsed time: 23584.226 msecs" 
19998 
user> (time (count (gen-ngrams 3 (take 30000 corpus)))) 
"Elapsed time: 54905.999 msecs" 
29998 
user> (time (count (gen-ngrams 3 (take 40000 corpus)))) 
"Elapsed time: 100978.962 msecs" 
39998 

corpusは、文字列トークンのConsです。

この動作の原因とは何ですか？パフォーマンスを向上させるにはどうすればよいですか。

Answer 1

私はを反復処理され、「（コルをカウント）」あなたの問題がでていると思う：

編集ngramsへの各コールのcoll。

ソリューションは、パーティション機能でビルドを使用することです：

user=> (time (count (gen-ngrams 3 (take 20000 corpus)))) 
"Elapsed time: 6212.894932 msecs" 
19998 
user=> (time (count (partition 3 1 (take 20000 corpus)))) 
"Elapsed time: 12.57996 msecs" 
19998 

は、パーティションのソースで見てみると実装について興味 http://clojuredocs.org/clojure_core/clojure.core/partition

Answer 2

私はClojureのエキスパートからは遠いですが、私はcons関数がこの問題を引き起こすと思います。 代わりにリストを使用してみてください：

(defn gen-ngrams 
    [n coll] 
    (if (>= (count coll) n) 
    (lazy-seq (list (take n coll) (gen-ngrams n (rest coll)))))) 

私は短所をリストより汎用的であるため、遅くなる新しい配列を構築すると思います。その後、および「コーパスは、文字列トークンの短所である」場合、それリストにしよう...