Нелинейное замедление, создающее ленивую последовательность в Clojure

Я реализовал функцию, которая возвращает n-граммы заданной коллекции ввода как ленивую последовательность.

(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 строковых токенов.

Что вызывает такое поведение и как я могу улучшить производительность?


clojure lazy-sequences
person jgre    schedule 12.05.2012    source источник

Ответы (2)


arrow_upward
5
arrow_downward

Я думаю, ваша проблема связана с "(count coll)", который повторяется по coll для каждого вызова ngrams.

Решением было бы использовать встроенную функцию разделения:

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

person DanLebrero    schedule 12.05.2012

arrow_upward
0
arrow_downward

Я далек от эксперта по Clojure, но думаю, что эту проблему вызывает функция cons. Попробуйте вместо этого использовать список:

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

Я думаю, что cons создают новый seq, который является более общим, чем список, и, следовательно, медленнее.

Изменить: и если «корпус - это минусы строковых токенов», попробуйте сделать его списком ...

person Zsolt    schedule 12.05.2012