Как мне выполнить свертку в F #?
-
03-07-2019 - |
Вопрос
Я бы хотел свернуться дискретный сигнал с дискретным фильтром.Сигнал и фильтр представляют собой последовательности чисел с плавающей запятой в F #.
Единственный способ, которым я могу понять, как это сделать, - использовать два вложенных цикла for и изменяемый массив для хранения результата, но он кажется не очень функциональным.
Вот как я бы сделал это нефункциональным:
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 #, поэтому я думаю, было бы более запутанно публиковать что-то, что работает на моей машине)
Позвольте мне начать с публикации реализации вашего псевдокода на 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 #.Это было написано с использованием серьезно устаревшей версии (1.9.2.9) на VS2005, так что будьте осторожны.Также я не смог найти 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
модули, а также варианты объединения трех списков в тройки (zip3
).Если вы хотите, чтобы tom ore, как правило, заархивировал (или "свернул") n списков в список из n кортежей, тогда вам нужно будет написать свою собственную функцию, но это довольно просто.
(Я проходил мимо это описание кстати, о свертке - скажите мне, если вы имеете в виду что-то другое.)
В принципе, должна быть возможность использовать (Быстрое) преобразование Фурье или связанное с ним (Дискретное) косинусоидальное преобразование для достаточно эффективного вычисления свертки двух функций.Вы вычисляете БПФ для обеих функций, умножаете их и применяете обратное БПФ к результату.
Такова теория.На практике вам, вероятно, лучше всего найти математическую библиотеку, которая реализует это за вас.