Я пишу какое-то программное обеспечение для обработки сигналов и начинаю с написания дискретной функции свертки .
Это нормально работает для первых десяти тысяч или около того списка значений, но когда они становятся больше (скажем, 100k), я, конечно, начинаю получать ошибки StackOverflow.
К сожалению, яУ меня много проблем с преобразованием алгоритма императивной свертки, который у меня есть, в рекурсивную и ленивую версию , которая на самом деле достаточно быстра для использования (иметь хотя бы немного элегантности было бы неплохо, так какЧто ж).
Я также не уверен на 100%, что у меня есть эта функция полностью правильная, но, пожалуйста, дайте мне знать, если я что-то упускаю / делаю что-то неправильноЯ думаю это правильно.
(defn convolve
"
Convolves xs with is.
This is a discrete convolution.
'xs :: list of numbers
'is :: list of numbers
"
[xs is]
(loop [xs xs finalacc () acc ()]
(if (empty? xs)
(concat finalacc acc)
(recur (rest xs)
(if (empty? acc)
()
(concat finalacc [(first acc)]))
(if (empty? acc)
(map #(* (first xs) %) is)
(vec-add
(map #(* (first xs) %) is)
(rest acc)))))))
Я был бы очень признателен за любую помощь: я все еще ориентируюсь в Clojure, и создание этого элегантного, ленивого и / или рекурсивного было бы замечательно.
Я немного удивлен, насколько сложно выразить алгоритм, который довольно легко выразить на императивном языке в Лиспе.Но, возможно, я делаю это неправильно!
РЕДАКТИРОВАТЬ: Просто чтобы показать, как легко выразить на императивном языке, и дать людям алгоритм, который работает хорошо и легкочитайте, вот версия Python.Помимо того, что он короче, лаконичнее и гораздо проще рассуждать, он выполняет на несколько порядков быстрее, чем код Clojure: даже мой императивный код Clojure с использованием массивов Java.
from itertools import repeat
def convolve(ns, ms):
y = [i for i in repeat(0, len(ns)+len(ms)-1)]
for n in range(len(ns)):
for m in range(len(ms)):
y[n+m] = y[n+m] + ns[n]*ms[m]
return y
Здесь, с другой стороны,это императивный код Clojure.Он также сбрасывает последние, не полностью погруженные значения из свертки.Так что, кроме того, что он медленный и уродливый, он не на 100% функционален.Ни функционально.
(defn imp-convolve-1
[xs is]
(let [ys (into-array Double (repeat (dec (+ (count xs) (count is))) 0.0))
xs (vec xs)
is (vec is)]
(map #(first %)
(for [i (range (count xs))]
(for [j (range (count is))]
(aset ys (+ i j)
(+ (* (nth xs i) (nth is j))
(nth ys (+ i j)))))))))
Это так печально.Пожалуйста, кто-нибудь покажет мне, что я что-то упустил очевидное.
РЕДАКТИРОВАТЬ 3:
Вот еще одна версия, которую я придумал вчера, показывающий, как бы я хотел ее выразить (хотя другие решения довольно элегантны; яя просто добавляю еще один!)
(defn convolve-2
[xs is]
(reduce #(vec-add %1 (pad-l %2 (inc (count %1))))
(for [x xs]
(for [i is]
(* x i)))))
Используется эта служебная функция vec-add:
(defn vec-add
([xs] (vec-add xs []))
([xs ys]
(let [lxs (count xs)
lys (count ys)
xs (pad-r xs lys)
ys (pad-r ys lxs)]
(vec (map #(+ %1 %2) xs ys))))
([xs ys & more]
(vec (reduce vec-add (vec-add xs ys) more))))
(vec (reduce vec-add (vec-add xs ys) more))))