Estoy escribiendo un software de procesamiento de señal, y estoy empezando por escribir un discrete convolution function.Problemas con lazy convolution fn en Clojure
Esto funciona bien para las primeras diez mil listas de valores, pero a medida que crecen (digamos, 100k), empiezo a tener errores de StackOverflow, por supuesto.
Por desgracia, estoy teniendo un montón de problemas para convertir el algoritmo de convolución imperativo que tengo a un recursiva & versión perezosa que en realidad es lo suficientemente rápido para usar (que tiene al menos un mínimo de elegancia sería bueno también)
Tampoco estoy 100% seguro de tener esta función completamente correcta, pero – por favor avíseme si me falta algo/estoy haciendo algo mal. I piensa es correcto.
(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)))))))
Yo estaría muy agradecido por cualquier tipo de ayuda: Todavía estoy orientarme en Clojure, y haciendo de este elegante y perezoso y/o recursiva sería maravilloso.
Estoy un poco sorprendido de lo difícil que es expresar un algoritmo que es bastante fácil de expresar en un lenguaje imperativo en un Lisp. ¡Pero quizás lo estoy haciendo mal!
EDIT: sólo para mostrar lo fácil que es para expresar en un lenguaje imperativo, y para dar a la gente el algoritmo que funciona muy bien y es fácil de leer, aquí está la versión de Python. Además de ser más corto, más conciso y mucho más fácil de razonar, ejecuta órdenes de magnitud más rápido que el código Clojure: incluso mi código imperativo Clojure con matrices 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
Aquí, por otro lado, está el código imperativo Clojure. También elimina los últimos valores, no completamente sumergidos, de la convolución. Además de ser lento y feo, no es 100% funcional. Ni funcional
(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)))))))))
Esto es tan desalentador. Por favor, que alguien me enseñe que me he perdido algo obvio.
Datos 3:
Aquí hay otra versión que pensé ayer, mostrando cómo me gustaría ser capaz de expresarlo (aunque otras soluciones son muy elegantes, yo sólo voy a poner otra por ahí!)
(defn convolve-2
[xs is]
(reduce #(vec-add %1 (pad-l %2 (inc (count %1))))
(for [x xs]
(for [i is]
(* x i)))))
Se utiliza esta función de utilidad 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))))
Esto no es en absoluto una respuesta a su pregunta, pero ... la implementación de la convolución mediante el uso de transformadas rápidas de Fourier reduce considerablemente el número de operaciones (consulte http://stackoverflow.com/questions/3084987/low- pass-filter-using-fft-instead-of-convolution-implementation, por ejemplo). – mtrw
No sé lo suficiente sobre los lenguajes funcionales para saber si esto ayudará, pero podría estar interesado en http://stackoverflow.com/questions/803055/how-do-i-do-convolution-in-f. – mtrw
@mtrw En producción, esto definitivamente se hará usando la FFT; por ahora, sin embargo, me encantaría tener una solución agradable y funcional. Pero no estoy seguro de lo posible que es (en Clojure). – Isaac