Проблема с ленивой сверткой fn в Clojure

Вероятная причина ошибок переполнения стека заключается в том, что ленивые преобразователи становятся слишком глубокими. ( concat и map ленивы). Попробуйте обернуть эти вызовы в doall , чтобы принудительно вычислить их возвращаемые значения.

Что касается более функционального решения, попробуйте что-нибудь вроде этого:

(defn circular-convolve
  "Perform a circular convolution of vectors f and g"
  [f g]
  (letfn [(point-mul [m n]
        (* (f m) (g (mod (- n m) (count g)))))
      (value-at [n]
        (reduce + (map #(point-mul % n) (range (count g)))))]
    (map value-at (range (count g)))))

Используйте reduce для простого выполнения суммирования, а поскольку map создает ленивую последовательность, эта функция тоже ленивый.

Ничего не могу поделать с высокопроизводительной функциональной версией, но вы можете получить 100-кратное ускорение для императивной версии, отказавшись от лени и добавив подсказки типа:

(defn imp-convolve-2 [xs is]
  (let [^doubles xs (into-array Double/TYPE xs)
        ^doubles is (into-array Double/TYPE is)
        ys (double-array (dec (+ (count xs) (count is)))) ]
    (dotimes [i (alength xs)]
      (dotimes [j (alength is)]
        (aset ys (+ i j)
          (+ (* (aget xs i) (aget is j))
            (aget ys (+ i j))))))
    ys))

С xs размером 100k и - это размер 2, ваш imp-convolve-1 занимает ~ 6000 мс на моей машине, когда он заключен в doall, в то время как этот занимает ~ 35 мс.

Обновление

Вот ленивая функциональная версия:

(defn convolve 
  ([xs is] (convolve xs is []))
  ([xs is parts]
    (cond
      (and (empty? xs) (empty? parts)) nil
      (empty? xs) (cons
                    (reduce + (map first parts))
                    (convolve xs is
                      (remove empty? (map rest parts))))
      :else (cons
              (+ (* (first xs) (first is))
                (reduce + (map first parts)))
              (lazy-seq
                (convolve (rest xs) is
                  (cons 
                    (map (partial * (first xs)) (rest is))
                    (remove empty? (map rest parts)))))))))

На размерах 100k и 2 она составляет ~ 600 мс (варьируется от 450 до 750 мс) против ~ 6000 мс для imp-convolve-1 и ~ 35 мс для imp. -свернуть-2.

Так что он функциональный, ленивый и имеет приемлемую производительность. Тем не менее, это вдвое больше кода, чем императивная версия, и мне потребовалось еще 1-2 часа, чтобы найти, так что я не уверен, что вижу в этом смысл.

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

Это одна из причин, по которой я считаю, что Clojure великолепен, поскольку вы можете использовать любой подход по своему усмотрению.

Обновление 2:

Я исправлю свое «в чем смысл этого функционально», сказав, что мне нравится эта функциональная реализация (вторая, ниже) Дэвида Кабаны .

Он короткий, читаемый и время до ~ 140 мс при тех же размерах ввода, что и выше (100 000 и 2), что делает его, безусловно, наиболее эффективной функциональной реализацией из тех, что я пробовал.

Учитывая, что он функциональный (но не ленивый), не использует подсказок типов и работает со всеми числовыми типами (не только с двойными), это весьма впечатляет.

(defn convolve [xs is]
  (if (> (count xs) (count is))
    (convolve is xs)
    (let [os (dec (+ (count xs) (count is)))
          lxs (count xs)
          lis (count is)]
      (for [i (range os)]
        (let [[start-x end-x] [(- lxs (min lxs (- os i))) (min i (dec lxs))]
              [start-i end-i] [(- lis (min lis (- os i))) (min i (dec lis))]]
          (reduce + (map *
                         (rseq (subvec xs start-x (inc end-x)))
                         (subvec is start-i (inc end-i)))))))))

Можно кратко выразить ленивое функциональное решение. Увы, производительность при> 2к нецелесообразна. Мне интересно узнать, есть ли способы ускорить его, не жертвуя удобочитаемостью.

Изменить: После прочтения информативного сообщения drcabana по теме ( http://erl.nfshost.com/2010/07/17/discrete-convolution-of-finite-vectors/ ) я обновил свой код до принимать векторы разного размера. Его реализация лучше: для xs размера 3 это размер 1000000, ~ 2сек против ~ 3сек

Редактировать 2: Взяв за основу идеи drcabana о простом изменении xs и padding, я пришел к следующему:

(defn convolve [xs is]
  (if (> (count xs) (count is))
    (convolve is xs)
    (let [is (concat (repeat (dec (count xs)) 0) is)]
      (for [s (take-while not-empty (iterate rest is))]
         (reduce + (map * (rseq xs) s))))))

Это, вероятно, столь же лаконично, как и будет, но в целом все равно медленнее, вероятно, из-за длительного времени. Престижность автору блога за хорошо продуманный подход. Единственное преимущество здесь в том, что приведенное выше является действительно ленивым в том смысле, что, если я спрошу (nth res 10000), для получения результата потребуются только первые 10k вычислений.