Wie kann ich tun Faltung in F #?

Question

Ich möchte convolve ein diskretes Signal mit einem diskreten Filter. Das Signal und Filter sind Sequenzen des Schwimmers in F #.

Die einzige Art, wie ich herausfinden, wie es zu tun ist, mit zwei verschachtelten for-Schleifen und ein änderbaren Array um das Ergebnis zu speichern, aber es fühlt sich nicht sehr funktionell.

Hier ist, wie ich tun würde, es nicht-funktional:

conv = double[len(signal) + len(filter) - 1]
for i = 1 to len(signal)
  for j = 1 to len(filter)
    conv[i + j] = conv[i + j] + signal(i) * filter(len(filter) - j) 

Answer 1

Versuchen Sie, diese Funktion:

let convolute signal filter =
    [|0 .. Array.length signal + Array.length filter - 1|] |> Array.map (fun i ->
        [|0 .. i|] |> Array.sum_by (fun j -> signal.[i] * filter.[Array.length filter - (i - j) - 1]))

Es ist wahrscheinlich nicht die schönste Funktion Lösung, aber es sollte die Arbeit machen. Ich bezweifle, dass es eine rein funktionale Lösung besteht, die die zwingend notwendig, eine für Geschwindigkeit wird jedoch entsprechen.

Ich hoffe, das hilft.

Hinweis: Die Funktion ist derzeit nicht getestet (obwohl ich bestätigt habe es kompiliert). Lassen Sie uns wissen, wenn es nicht ganz das tut, was es soll. Beachten Sie außerdem, dass das i und j Variablen nicht auf die gleichen Dinge beziehen, wie Ihre ursprüngliche Post ist.

Answer 2

Ich weiß nicht, F #, aber ich werde einige Haskell schreiben und hoffentlich wird es nahe genug zu bedienen. (Ich habe nur VS 2005 und eine alte Version von F #, also denke ich, es wäre verwirrend zu sein, etwas zu schreiben, die auf meinem Rechner)

Lassen Sie mich zunächst eine Python-Implementierung Ihres Pseudo-Code veröffentlichen, um sicherzustellen, ich bin die richtige Antwort zu bekommen:

def convolve(signal, filter):
    conv = [0 for _ in range(len(signal) + len(filter) - 1)]
    for i in range(len(signal)):
        for j in range(len(filter)):
            conv[i + j] += signal[i] * filter[-j-1]
    return conv

Jetzt convolve([1,1,1], [1,2,3]) gibt [3, 5, 6, 3, 1]. Wenn dies falsch ist, bitte sagen Sie mir.

Das erste, was wir tun können, ist die innere Schleife in eine zipWith drehen; fügen wir im Wesentlichen eine Reihe von Zeilen in einer besonderen Art und Weise, in dem obigen Beispiel: [[3,2,1], [3,2,1], [3,2,1]]. Um jede Zeile zu erzeugen, werden wir uns i im signal mit dem Umkehrfilter zip:

makeRow filter i = zipWith (*) (repeat i) (reverse filter)

(Hinweis: nach einer schnellen Google ist zipWith map2 in F # Sie können eine Liste Verständnis statt repeat verwenden.) Jetzt:

makeRow [1,2,3] 1
=> [3,2,1]
makeRow [1,2,3] 2
=> [6,4,2]

Um dies zu erhalten für alle i, müssen wir über Signal zur Karte:

map (makeRow filter) signal
=> [[3,2,1], [3,2,1], [3,2,1]]

Gut. Jetzt brauchen wir nur einen Weg, um die Zeilen richtig zu kombinieren. Wir können dies tun, indem sie zu bemerken, dass die Kombination der neuen Zeile an das bestehende Array ist das Hinzufügen, außer für das erste Element, das auf der Vorderseite geklebt wird. Zum Beispiel:

[[3,2,1], [6,4,2]] = 3 : [2 + 6, 1 + 4] ++ [2]
// or in F#
[[3; 2; 1]; [6; 4; 2]] = 3 :: [2 + 6; 1 + 4] @ [2]

Wir brauchen also nur einen Code zu schreiben, der dies im allgemeinen Fall tut:

combine (front:combinable) rest =
    let (combinable',previous) = splitAt (length combinable) rest in
    front : zipWith (+) combinable combinable' ++ previous

Nun, da wir eine Möglichkeit haben, alle Zeilen zu generieren und einen Weg, um eine neue Zeile mit einem vorhandenen Array zu kombinieren, alles, was wir die beide zusammen mit einer Falte zu tun haben, wird zu bleiben:

convolve signal filter = foldr1 combine (map (makeRow filter) signal)

convolve [1,1,1] [1,2,3]
=> [3,5,6,3,1]

Damit eine funktionsfähige Version ist. Ich denke, es ist ziemlich klar, so lange wie Sie foldr und zipWith verstehen. Aber es ist zumindest so lange, wie der Imperativ Version und wie andere commenters sagte, wahrscheinlich weniger effizient in F #. Hier ist das Ganze an einem Ort.

makeRow filter i = zipWith (*) (repeat i) (reverse filter)
combine (front:combinable) rest =
    front : zipWith (+) combinable combinable' ++ previous
    where (combinable',previous) = splitAt (length combinable) rest
convolve signal filter = foldr1 combine (map (makeRow filter) signal)

Edit:

Wie versprochen, hier ist eine F # -Version. Dies wurde mit einer ernsthaft alten Version (1.9.2.9) auf VS2005 geschrieben, so vorsichtig sein. Ich kann auch nicht splitAt in der Standardbibliothek finden, aber dann weiß ich nicht, F #, das gut.

open List
let gen value = map (fun _ -> value)
let splitAt n l = 
  let rec splitter n l acc =
    match n,l with
    | 0,_ -> rev acc,l
    | _,[] -> rev acc,[]
    | n,x::xs -> splitter (n - 1) xs (x :: acc)
  splitter n l [] 
let makeRow filter i = map2 ( * ) (gen i filter) (rev filter)
let combine (front::combinable) rest =
  let combinable',previous = splitAt (length combinable) rest
  front :: map2 (+) combinable combinable' @ previous
let convolve signal filter = 
  fold1_right combine (map (makeRow filter) signal)

Answer 3

Ja, Sie wollen in der Regel Schleifen vermeiden (Normalpapier, verschachtelt, was auch immer) und alles, wandelbar in der funktionalen Programmierung.

Es geschieht eine sehr einfache Lösung in F # sein (und wahrscheinlich auch fast jede andere funktionale Sprache):

let convolution = Seq.zip seq1 seq2

Die zip Funktion einfach kombiniert die beiden Sequenzen in einem der Paare, das Element aus seq1 und das Element aus seq2 enthält. Als Hinweis, gibt es auch ähnliche Zip-Funktionen für den List und Array Module sowie Varianten für die Kombination von drei Listen in Tripel (zip3). Wenn Sie tom wollen Erz im Allgemeinen (oder „Konvolut“) zip n-Listen in eine Liste von n-Tupel, dann werden Sie benötigen, um Ihre eigene Funktion zu schreiben, aber es ist ziemlich einfach.

(Ich habe gehen von dieser Beschreibung der Faltung durch die Art und Weise -. mir sagen, wenn Sie etwas anderes bedeuten)

Answer 4

Im Prinzip soll es möglich sein, die (Fast) Fourier-Transformation zu verwenden, oder die betreffende (Discrete) Cosinus-Transformation, die Faltung von zwei Funktionen einigermaßen effizient zu berechnen. Sie berechnen die FFT für beide Funktionen, multiplizieren sie, und die inverse FFT auf das Ergebnis anwenden.

mathematischen Hintergrund

Das ist die Theorie. In der Praxis würden Sie wahrscheinlich am besten, eine Mathematik-Bibliothek finden, dass es für Sie implementiert.