Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Оцените реализацию алгоритма свертки.

Автор: inamozov 2.5.2012, 01:00

Здравствуйте! Краткое описание: Передо мной стояла задача реализовать алгоритм дискретной свертки двух сигналов, не прибегая к какой-либо внешней помощи. Я свел задачу к вычислению всех диагоналей произвольной (в общем случае) матрицы и получил решение. Я новичек и было бы здорово услышать Вашу оценку и критику Алгоритм: Имеются два одномерных числовых массива(arrayX, arrayH) произвольной длины (N и M), которые почленно (x1 * (h1, h2, ..., hm), x2 * (h1, h2,...,hm), ...) перемножаются в матрицу размера [NxM]. Таким образом матрица будет содержать все слагаемые для свертки (в процессе свертки каждый элемент одного массива перемножается с каждым элементом другого массива). Таким образом каждая диагональ получившейся матрицы будет представлять собой элемент свертки, так что задача как раз сводится, в моем случае, к вычислению всех диагоналей данной матрицы. Подсчет диагоналей осуществляется от левого верхнего элемента, то есть, если мы имеем матрицу: 1 2 3 4 5 6 7 8 9 То диагонали будут соответственно: 1, 2 + 4, 3 + 5 + 7, 6 + 8, 9     Код // 1. Matrix of results: for(int i = 0; i < n; i++) {     for(int j = 0; j < m; j ++)     {         matrix[i][j] = arrayX[i]*arrayH[j];     } } // 2. Calculate upper left diagonals: for(int j = 0; j < m; j ++)     {         k = j;         for(int i = 0; i < n; i ++)         {             if((i == 0) && (j == 0))             {                 sum[j] = matrix[i][j];                 break;             }             else if((i == 0) && !(j == m))             {                 sum[j] = matrix[i][j];             }             else             {                 if(((j - 1) >= 0) && (i <= j) && (k > 0))                 {                     k--;                     sum[j] = sum[j] + matrix[i][k];                 }                 else                 {                     break;                 }             }         }     } Примечания: В тексте кода расчитываются не все диагонали матрицы, а только верхняя их часть. Для расчета диагоналей нижней части и получения полного решения, достаточно транспонировать имеющуюся матрицу и  снова применить к ней этот же алгоритм.

Автор: ksili 2.5.2012, 03:32

Цитата(inamozov @  2.5.2012,  05:00 ) не прибегая к какой-либо внешней помощи Топик на этом форуме является обращением к внешней помощи    Цитата(inamozov @  2.5.2012,  05:00 ) перемножаются в матрицу размера [NxM] Зачем промежуточные произведения сводить в матрицу, забивать память? Суммируй их сразу.

Автор: inamozov 2.5.2012, 15:42

ksili,  хех, спасибо! Вообще меня более всего интересует, насколько хорош выбранный мной путь решения такой задачи? А, в целом, сведение аналитиеской задачи к операциям над матрицей довольно распространенная практика... Но не могу не согласиться что вставлять промежуточную матрицу в код это была лишняя нагрузка. Думаю, стоит такие действия выполнять на бумаге, а в код забивать уже более концентрированную идею.

Автор: volatile 2.5.2012, 23:59

inamozov, не вникал в алгоритм. Просто брасается в глаза. Цитата(inamozov @  2.5.2012,  01:00 ) else if((i == 0) && !(j == m)) Здесь j никогда не будет равно m

Автор: inamozov 3.5.2012, 00:15

volatile, спасибо, это (!(j == m)) надо вообще убирать. надеюсь скоро довести до одного общего, без транспонирования довел

Автор: volatile 3.5.2012, 23:37

Цитата(inamozov @  3.5.2012,  00:15 ) надеюсь скоро довести до одного общего, без транспонирования  inamozov, я вам помогу, чуток, ок? Код double sum [m + n - 1] = {0};  // Обнулить массив for (int i = 0; i < n; ++ i)    for (int j = 0; j < m; ++ j)       sum [i + j] += matrix[i][j]; В итоге в массиве  sum [] у нас сумма всех диагоналей. Цитата(inamozov @  2.5.2012,  01:00 ) Я свел задачу к вычислению всех диагоналей произвольной (в общем случае) матрицы и получил решение.

Автор: ksili 4.5.2012, 09:19

Цитата(inamozov @  3.5.2012,  04:15 ) надеюсь скоро довести до одного общего, без транспонирования зачем без транспонирования? можно вообще без матрицы.

Автор: DRUID3 17.5.2012, 22:25

Сколько не видел FFT, FWT и прочих реализаций матпреобразований - все они в чем-то разные, а ведь кажется математика это нечто общее для всех...    математика то общее, а ее восприятие у каждого свое... Одномерную свертку я представляю так как когда-то ее объяснил один преподаватель "радиотехнических сигналов и систем" - берем два графика, один обращаем вспять(как если бы перевернули лист на другую сторону) и поточечно перемножаем и суммируем(вот почему умножение с накоплением основная операция в DSP). Сдвигаем графики навстречу друг другу на одну точку  и снова повторяем... И так бесконечно.  .  Прилагаю маленький проектик FIR-фильтра(та же свертка). P.S.: ...я не говорю, что у топикстартера идея/реализация неверно(я не проверял   ) просто он видит так, а я эдак. Проект мой скорее учебный (не особо оптимизированный, да и свертку влоб профи часто заменяют перемножением в частотной области или в вейвлетотображении) но зато с тестом - можно проверять свои реализации.  P.P.S.: если в комментах грамматические оПшиПки - сообщите - это да, грамАта ниККаДДа не Пыла мАим сильным местАм

Автор: ksili 18.5.2012, 04:24

Цитата(DRUID3 @  18.5.2012,  02:25 ) И так бесконечно. Бесконечно - это в циклической свёртке. А так, длина результирующей последовательности равна N+M-1.

Автор: inamozov 18.5.2012, 06:27

Вот вариант, от 2.05.2012, где происходит подсчет диагоналей (гипотетической  ) матрицы свертки. В итоге цельный алгоритм реализован путем обхода по матрице слева направо а потом сверху вниз. Код         for(int j = 0; j <= s; j ++)             {                 k = j;                 for(int i = 0; i < n; i ++)                 {                     if(i == 0)                     {                         t = j;                     }                     g = i;                     // begins from left to right                     // very first element:                     if((i == 0) && (j == 0))                      {                         sum[j] = matrix[i][j];                         break;                     }                      // every top first element while going from left to right:                     else if((i == 0) && (j < m))                      {                         sum[j] = matrix[i][j];                     }                     // all elements except top first while going from left to right:                     else if((j < m) && (i > 0) && (k > 0))                      {                         k--;                         sum[j] = sum[j] + matrix[i][k];                     }                     // calculated all elements on the top, now need to go down on the right                     // 1st element while going down from the right end:                     else if((i == 0) && (j >= m) && !(j == s))                      {                         //g++;                         sum[j] = matrix[i + 1][j - 1];                         t --;                                              }                     // all other elements after first while going down from the right end:                     else if ((i > 0) && (j >= m) && !(j == s) && ((g+1) < n))                     {                         g++;                         t--;                         sum[j] = sum[j] + matrix[g][t];                     }                     // last element                     else if (j == s)                     {                         sum[j] = matrix[n-1][m-1];                     }                     // End cycle cryteria                     else                     {                         break;                     }                 }             }

Автор: volatile 19.5.2012, 00:55

Цитата(inamozov @  18.5.2012,  06:27 ) Вот вариант, от 2.05.2012, Есть такое понятие, http://ru.wikipedia.org/wiki/%D0%91%D1%80%D0%B8%D1%82%D0%B2%D0%B0_%D0%9E%D0%BA%D0%BA%D0%B0%D0%BC%D0%B0, соблюдение которого еще никому никогда не помешало. Зачем здесь столько нагорожено? Нужно быть проще, задача то элементарная. (см. мой пост выше.) Сами не разберетесь в своем коде через пару месяцев. К тому-же, чисто по опыту скажу: очень вероятно, что в такой мешанине не один баг зарыт.

Автор: inamozov 19.5.2012, 05:40

volatile, стараюсь придерживаться принципа доводить начатое до конца. Ваш алгоритм: Код double sum [m + n - 1] = {0};  // Обнулить массив for (int i = 0; i < n; ++ i)    for (int j = 0; j < m; ++ j)       sum [i + j] += matrix[i][j]; замечательно прост и красив, только еще не было времени "разобраться" с ним. Спасибо.

Автор: volatile 19.5.2012, 23:00

Цитата(inamozov @  19.5.2012,  05:40 ) еще не было времени "разобраться" с ним. inamozov, на самом деле, там много времени не нужно. Попробую объяснить. Например, возьмем ячейку sum[0] В ней будет сумма тех элементов, чьи индексы дают в сумме 0. Таких элементов, как не трудно догадаться, всего один, это matrix[0][0]; это наша первая диагональ, которая состоит из одной клетки (0,0) возьмем ячейку sum[1] В ней будет сумма тех элементов, чьи индексы дают в сумме 1. Таких элементов, уже два, это matrix[0][1], и matrix[1][0]; это наша 2-я диагональ, которая состоит из 2-ух клеток (0,1) (1,0) возьмем ячейку sum[2] В ней будет сумма тех элементов, чьи индексы дают в сумме 2. Таких элементов, уже 3, это matrix[0][2], matrix[1][1], и matrix[2][0]; это наша 3-я диагональ, которая состоит из 3-ех клеток (0,2) (1,1) (2,0) Ну и так далее...  Для матрицы 4*4, например вся картина будет такой: Код sum[0] = matrix[0][0] sum[1] = matrix[0][1] + matrix[1][0] sum[2] = matrix[0][2] + matrix[1][1] + matrix[2][0] sum[3] = matrix[0][3] + matrix[1][2] + matrix[2][1] + matrix[3][0] sum[4] = matrix[1][3] + matrix[2][2] + matrix[3][1] sum[5] = matrix[2][3] + matrix[3][2] sum[6] = matrix[3][3] Все ведь просто. Цитата(volatile @  3.5.2012,  23:37 )   sum [i + j] += matrix[i][j];

Автор: inamozov 21.5.2012, 12:09

volatile, у меня возник к Вам вопрос: получается, что Ваш алгоритм оперирует не самой реализацией матрицы - ее елементами (как делал я), а, скорее, на уровне свойств этой матрицы - в данном случае порядковых номеров элементов. Посоветовали бы вы при операциях над матрицами строить алгоритмы на уровне свойтв этих сущностей не "опускаясь" до их реализации?

Автор: volatile 22.5.2012, 01:08

Цитата(inamozov @  21.5.2012,  12:09 ) получается, что Ваш алгоритм оперирует не самой реализацией матрицы - ее елементами (как делал я), а, скорее, на уровне свойств этой матрицы  Ну почему же. Алгоритм оперирует именно элементами. Проходит их все, от первого до последнего. Ну и да, при этом использует свойство индексов.    Цитата(inamozov @  21.5.2012,  12:09 ) Посоветовали бы вы при операциях над матрицами строить алгоритмы на уровне свойтв этих сущностей не "опускаясь" до их реализации?  Даже не знаю что ответить... Единого рецепта видимо нет. Больше программируйте, больше изучайте чужие программы. С опытом придет понимание что лучше в конкретном случае.

Автор: ksili 22.5.2012, 05:51

inamozov, я в разных книгах видел описание свёртки и НИГДЕ не приводится всё к матрице. Обычно - рисунок, или формула, которые сводятся к тому алгоритму (коду), который привёл volatile. Так что мне кажется, это вы всё усложняете, а не volatile.

Автор: DRUID3 23.5.2012, 02:54

Цитата(inamozov @  21.5.2012,  11:09 ) Посоветовали бы вы при операциях над матрицами строить алгоритмы на уровне свойтв этих сущностей не "опускаясь" до их реализации? 1)А кто сказал, что свертка это матричная операция? В непрерывных сигналах там ее вообще нет. Матрицу просто вводят для удобства - причем удобства понимания, причем (  ) людей с хорошим математическим бэкграундом. Свертка двух функций на выходе дает функцию. Дискретная - дискретную. 2) первая задача при написании матопераций их верификация(обязательно), вторая их оптимизация(тем ценнее алгоритм). Свертка задача - однозначная. Потому писать ее нужно как можно проще, не добавляя новых сущностей. Кстати еще - в Вашем коде много if()-ов а они сбрасывают кэш, а это замедляет работу программы на порядки!!! Правда у Вас джава, а я не знаю какова там внутренняя кухня.  Цитата(ksili @  18.5.2012,  03:24 ) Бесконечно - это в циклической свёртке.А так, длина результирующей последовательности равна N+M-1. http://www.dsplib.ru/content/conv/conv.html. Препод кстати об обычной рассказывал - интегрируем то мы откуда докуда? Просто ненулевой результат будет для N+M-1 конечно. P.S.: никто так и не скачал мой фильтр, а я то думал послать код в "эпл" и затребовать миллион...

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)