F#에서 컨볼 루션을 어떻게합니까?

StackOverflow https://stackoverflow.com/questions/803055

문제

나는 원한다 말다 이산 필터가있는 이산 신호. 신호와 필터는 f#의 플로트 시퀀스입니다.

내가 그것을 수행하는 방법을 알아낼 수있는 유일한 방법은 루프 용으로 두 개의 중첩을 사용하고 결과를 저장하기 위해 변한 배열을 사용하는 것입니다. 그러나 그것은 매우 기능적이라고 느끼지 않습니다.

작동하지 않는 방법은 다음과 같습니다.

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)
도움이 되었습니까?

해결책

이 기능을 시도하십시오 :

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]))

아마도 가장 좋은 기능 솔루션은 아니지만 작업을 수행해야합니다. 그러나 속도에 대한 명령 적 솔루션과 일치하는 순전히 기능적인 솔루션이 존재한다고 의심합니다.

도움이되기를 바랍니다.

참고 :이 기능은 현재 테스트되지 않았습니다 (컴파일을 확인했지만). 그것이해야 할 일을하지 않으면 알려주세요. 또한, 그것을 관찰하십시오 i 그리고 j 변수는 원래 게시물과 동일한 것을 참조하지 않습니다.

다른 팁

나는 f#을 모르지만, 일부 Haskell을 게시 할 것이며, 사용하기에 충분히 가까워 질 것입니다. (저는 VS 2005와 고대 버전의 F#을 가지고 있기 때문에 내 컴퓨터에 작동하는 것을 게시하는 것이 더 혼란 스러울 것이라고 생각합니다).

Pseudocode의 Python 구현을 게시하여 정답을 받도록 시작하겠습니다.

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

지금 convolve([1,1,1], [1,2,3]) 주어진 [3, 5, 6, 3, 1]. 이것이 틀렸다면 말 해주세요.

우리가 할 수있는 첫 번째 일은 내부 루프를 지퍼로 바꾸는 것입니다. 우리는 본질적으로 위의 예에서 특별한 방식으로 일련의 행을 추가하고 있습니다. [[3,2,1], [3,2,1], [3,2,1]]. 각 행을 생성하려면 각각을 압축 할 것이다 i 에서 signal 반전 된 필터로 :

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

(참고 : 빠른 Google에 따르면 zipWith ~이다 map2 F#에서. 대신 목록 이해력을 사용해야 할 수도 있습니다. repeat) 지금:

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

이것을 모두 얻기 위해 i, 우리는 신호 이상을 매핑해야합니다.

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

좋은. 이제 우리는 행을 올바르게 결합하는 방법이 필요합니다. 결합이 전면에 붙어있는 첫 번째 요소를 제외하고는 기존 배열에 새 행을 추가하고 있음을 알면서이 작업을 수행 할 수 있습니다. 예를 들어:

[[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]

따라서 우리는 일반적으로이를 수행하는 코드를 작성하면됩니다.

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

이제 우리는 모든 행을 생성하는 방법과 새 행을 기존 배열과 결합하는 방법이 있으므로 두 개를 접어 두는 것입니다.

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

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

기능적 버전입니다. 당신이 이해하는 한 합리적으로 분명하다고 생각합니다. foldr 그리고 zipWith. 그러나 적어도 필수 버전과 다른 의견 제시 자와 마찬가지로 F#에서는 덜 효율적일 것입니다. 한 곳에서 모든 것이 있습니다.

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)

편집하다:

약속대로 여기에 F# 버전이 있습니다. 이것은 VS2005에서 심각한 고대 버전 (1.9.2.9)을 사용하여 작성되었으므로 조심하십시오. 또한 찾을 수 없었습니다 splitAt 표준 라이브러리에서는하지만 F#을 잘 모릅니다.

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)

실제로, 당신은 일반적으로 루프 (평범한, 중첩, 무엇이든)를 피하고 기능적 프로그래밍에서 변하는 것입니다.

F# (그리고 아마도 거의 모든 기능적 언어)에는 매우 간단한 솔루션이 있습니다.

let convolution = Seq.zip seq1 seq2

그만큼 zip 함수는 단순히 두 시퀀스를 요소를 포함하는 쌍 중 하나로 결합합니다. seq1 그리고 요소 seq2. 참고로, 비슷한 zip 함수도 있습니다. List 그리고 Array 3 개의 목록을 트리플로 결합하기위한 변형뿐만 아니라 모듈 (zip3). Tom Ore가 일반적으로 Zip (또는 "Convolute") N 목록을 N-Tuples 목록에 원한다면 자신의 기능을 작성해야하지만 매우 간단합니다.

(나는 갔다 이 설명 그건 그렇고 컨볼 루션 - 당신이 다른 것을 의미하는지 말 해주세요.)

원칙적으로, 두 기능의 컨볼 루션을 합리적으로 효율적으로 계산하기 위해 (빠른) 푸리에 변환 또는 관련 (이산) 코사인 변환을 사용하는 것이 가능해야합니다. 두 기능 모두 FFT를 계산하고 곱한 다음 결과에 역 FFT를 적용합니다.

수학적 배경

그것이 이론입니다. 실제로 당신은 아마 당신을 위해 그것을 구현하는 수학 라이브러리를 가장 잘 찾을 수있을 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top