Non-linear slowdown creating a lazy seq in Clojure

Question

I implemented a function that returns the n-grams of a given input collection as a lazy seq.

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

When I call this function with larger input collections, I would expect to see a linear increase in execution time. However, the timing I observe is worse than that:

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 is a Cons of string tokens.

What causes this behavior and how can I improve the performance?

BenMorel · Accepted Answer · 2014-01-07 12:00:23Z

5

I think your issue is with "(count coll)", which is iterating over the coll for each call to ngrams.

The solution would be to use the build in partition function:

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

Have a look in the partition source if curious about the implementation http://clojuredocs.org/clojure_core/clojure.core/partition

edited Jan 7, 2014 at 12:00

BenMorel

37k52 gold badges208 silver badges339 bronze badges

answered May 12, 2012 at 20:36

DanLebrero

8,5911 gold badge31 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Zsolt · Accepted Answer · 2013-03-24 17:41:47Z

0

I am far from a Clojure expert, but I think the cons function causes this problem. Try to use list instead:

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

I think cons construct a new seq which is more generic than a list, and therefore is slower.

Edit: and if "corpus is a Cons of string tokens", then try to make it a list...

edited Mar 24, 2013 at 17:41

answered May 12, 2012 at 17:38

Zsolt

3,2833 gold badges35 silver badges49 bronze badges

Collectives™ on Stack Overflow

Non-linear slowdown creating a lazy seq in Clojure

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related