реклама на сайте
подробности

 
 
4 страниц V  < 1 2 3 4 >  
Reply to this topicStart new topic
> вычисление медианы массива (или произвольной моды), stm32f4 + STL
KRS
сообщение Jul 31 2013, 14:19
Сообщение #31


Профессионал
*****

Группа: Модераторы
Сообщений: 1 951
Регистрация: 27-08-04
Из: Санкт-Петербург
Пользователь №: 555



Цитата(AlexandrY @ Jul 31 2013, 17:14) *
Как видно абсолютный победитель - алгоритм Ekstrom .

Это можно было бы понять и без тестов, как я и писал выше он использует то, что при добавление очередного элемента и удалении предыдущего массив уже отсортирован!

Но как видно минимально возможное время все таки у алгоритма Xenia! И во многих случаях для реальных измерений с АЦП он будет давать лучшее время!
А физический смысл для рандомного массива применять медианный фильтр не очень понятный!
Go to the top of the page
 
+Quote Post
demiurg_spb
сообщение Jul 31 2013, 14:28
Сообщение #32


неотягощённый злом
******

Группа: Свой
Сообщений: 2 746
Регистрация: 31-01-08
Из: Санкт-Петербург
Пользователь №: 34 643



Цитата(KRS @ Jul 31 2013, 18:19) *
Но как видно минимально возможное время все таки у алгоритма Xenia! И во многих случаях для реальных измерений с АЦП он будет давать лучшее время!
Ещё огромным плюсом алгоритма Xenia является то, что он не портит исходный массив и не требует его копирования, что тоже и время и расход ОЗУ!


--------------------
“Будьте внимательны к своим мыслям - они начало поступков” (Лао-Цзы)
Go to the top of the page
 
+Quote Post
KRS
сообщение Jul 31 2013, 14:37
Сообщение #33


Профессионал
*****

Группа: Модераторы
Сообщений: 1 951
Регистрация: 27-08-04
Из: Санкт-Петербург
Пользователь №: 555



Для определенных измерений его еще можно улучшить, например изначально беря за индекс медианы предыдущий индекс и двигаться по кольцу...
Go to the top of the page
 
+Quote Post
Tanya
сообщение Jul 31 2013, 16:04
Сообщение #34


Гуру
******

Группа: Модераторы
Сообщений: 8 752
Регистрация: 6-01-06
Пользователь №: 12 883



Цитата(KRS @ Jul 31 2013, 18:19) *
Но как видно минимально возможное время все таки у алгоритма Xenia! И во многих случаях для реальных измерений с АЦП он будет давать лучшее время!

"Мой" алгоритм еще быстрее. Вот только имеет ли тут смысл говорить о скорости...
Цитата(KRS @ Jul 31 2013, 18:19) *
А физический смысл для рандомного массива применять медианный фильтр не очень понятный!

Вот по этой самой причине. Тем более, что массив вполне себе не массив, а последовательность с вполне понятными особенностями.
Go to the top of the page
 
+Quote Post
AlexandrY
сообщение Aug 1 2013, 07:45
Сообщение #35


Ally
******

Группа: Модераторы
Сообщений: 6 232
Регистрация: 19-01-05
Пользователь №: 2 050



Цитата(Tanya @ Jul 31 2013, 19:04) *
"Мой" алгоритм еще быстрее. Вот только имеет ли тут смысл говорить о скорости...

Вот по этой самой причине. Тем более, что массив вполне себе не массив, а последовательность с вполне понятными особенностями.


Говорить не надо, надо только измерить. wink.gif
Если имеете исходник, то выкладывайте.

Хотя меня в этой теме больше привлекает возможность помериться оценить компиляторы, но медиана сама по себе применяется именно на зашумленных произвольных сигналах.
И что там за понятные особенности никак не пойму.

Медиану с успехом применял для декодеров частотно модулированных сигналов.
Вот ниже график сигналов с которыми я имею дело при проектировании силовой электроники.
Вверху исходный сигнал. посередине зашумленный, внизу сравнение 3-х фильтров: желтый - скользящее среднее (31 отсчет), голубой - ФНЧ (Fpass=80Hz, Fstop=1000Hz, Astop=60dB ), розовый - медиана (31 отсчет)
Как видно медиана ближе всех повторяет исходный вид сигнала.
[attachment=78573:Median_vs_Average.png]
Go to the top of the page
 
+Quote Post
Tanya
сообщение Aug 1 2013, 08:13
Сообщение #36


Гуру
******

Группа: Модераторы
Сообщений: 8 752
Регистрация: 6-01-06
Пользователь №: 12 883



Цитата(AlexandrY @ Aug 1 2013, 11:45) *
Говорить не надо, надо только измерить. wink.gif
Если имеете исходник, то выкладывайте.

Хотя меня в этой теме больше привлекает возможность помериться оценить компиляторы, но медиана сама по себе применяется именно на зашумленных произвольных сигналах.
И что там за понятные особенности никак не пойму.


Как видно медиана ближе всех повторяет исходный вид сигнала.

Какой исходник? Одно сравнение и один же инкремент или декремент.
Медиана у Вас разве не задерживает сигнал?
Go to the top of the page
 
+Quote Post
AlexandrY
сообщение Aug 1 2013, 09:09
Сообщение #37


Ally
******

Группа: Модераторы
Сообщений: 6 232
Регистрация: 19-01-05
Пользователь №: 2 050



Цитата(Tanya @ Aug 1 2013, 11:13) *
Какой исходник? Одно сравнение и один же инкремент или декремент.
Медиана у Вас разве не задерживает сигнал?


Мы наверно о разном. laughing.gif

Еще раз повторил тесты уже с нормальной библиотекой C-и и с сигналом повторяющим характер зашумленного сигнала АЦП как на графике выше.
Добавил итераций для более надежной статистики.


Алгоритм Xenia оказался самым чувствительным к виду данных.
Алгоритм Ekstrom почти не чувствует изменения характера данных, а главное имеет очень маленькую дисперсию. Однако какая сила эти списки! А с виду кажутся такими громоздкими.
Где там Klen? Пора переводить на STL!

Код
INVCPU v1.00 PCB Test Suit.
System Core Clock = 120000000 Hz
Now. System ticks = 750131l, Sysytem time = 0.006251 s
Clock check. T1= 1440087l, T2= 1560069l, Delta(tick)= 119982l, Delta(s)= 0.0010
----------------------------------------------
Algorithm 'Qsort' (standart C library ):
----------------------------------------------
Results CRC = 7EC7
Number of samplles   = 65
Number of iterations = 6000
Measured max. number of cycles = 15054, time(us)=125.45
Measured min. number of cycles = 9369, time(us)=78.08
Measured aver.number of cycles = 12036, time(us)=100.30

----------------------------------------------
Algorithm 'Shell' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1181687):
----------------------------------------------
Results CRC = 7EC7
Number of samplles   = 65
Number of iterations = 6000
Measured max. number of cycles = 6370, time(us)=53.08
Measured min. number of cycles = 3640, time(us)=30.33
Measured aver.number of cycles = 5454, time(us)=45.45

----------------------------------------------
Algorithm 'Select' (Numerical Recipes in C, 8.5 Selecting the Mth Largest p.341):
----------------------------------------------
Results CRC = 7EC7
Number of samplles   = 65
Number of iterations = 6000
Measured max. number of cycles = 3129, time(us)=26.07
Measured min. number of cycles = 834, time(us)=6.95
Measured aver.number of cycles = 1621, time(us)=13.51

----------------------------------------------
Algorithm 'Selip' (Numerical Recipes in C, 8.5 Selecting the Mth Largest p.343):
----------------------------------------------
Results CRC = 7EC7
Number of samplles   = 65
Number of iterations = 6000
Measured max. number of cycles = 15714, time(us)=130.95
Measured min. number of cycles = 2224, time(us)=18.53
Measured aver.number of cycles = 14548, time(us)=121.23

----------------------------------------------
Algorithm 'Xenia' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1180687):
----------------------------------------------
Results CRC = 7EC7
Number of samplles   = 65
Number of iterations = 6000
Measured max. number of cycles = 21885, time(us)=182.38
Measured min. number of cycles = 930, time(us)=7.75
Measured aver.number of cycles = 10514, time(us)=87.62

----------------------------------------------
Algorithm 'Neiver' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1180944):
----------------------------------------------
Results CRC = 7EC7
Number of samplles   = 65
Number of iterations = 6000
Measured max. number of cycles = 8009, time(us)=66.74
Measured min. number of cycles = 1512, time(us)=12.60
Measured aver.number of cycles = 1535, time(us)=12.79

----------------------------------------------
Algorithm 'Ekstrom' (http://embeddedgurus.com/stack-overflow/tag/median-filter/):
----------------------------------------------
Results CRC = 7EC7
Number of samplles   = 65
Number of iterations = 6000
Measured max. number of cycles = 1325, time(us)=11.04
Measured min. number of cycles = 1256, time(us)=10.47
Measured aver.number of cycles = 1265, time(us)=10.54

----------------------------------------------
Algorithm 'Klen' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1180679)
----------------------------------------------
Results CRC = 7EC7
Number of samplles   = 65
Number of iterations = 6000
Measured max. number of cycles = 4405, time(us)=36.71
Measured min. number of cycles = 1595, time(us)=13.29
Measured aver.number of cycles = 2403, time(us)=20.02
Go to the top of the page
 
+Quote Post
demiurg_spb
сообщение Aug 1 2013, 09:17
Сообщение #38


неотягощённый злом
******

Группа: Свой
Сообщений: 2 746
Регистрация: 31-01-08
Из: Санкт-Петербург
Пользователь №: 34 643



Ещё можно попробовать сортировать пузырём, но не весь массив, а лишь половину (ИМХО, это будет самый компактный по объёму кода алгоритм).


--------------------
“Будьте внимательны к своим мыслям - они начало поступков” (Лао-Цзы)
Go to the top of the page
 
+Quote Post
Tanya
сообщение Aug 1 2013, 09:44
Сообщение #39


Гуру
******

Группа: Модераторы
Сообщений: 8 752
Регистрация: 6-01-06
Пользователь №: 12 883



Цитата(AlexandrY @ Aug 1 2013, 13:09) *
Мы наверно о разном. laughing.gif

Может...
Я про то, что
1. Человек не может крутить ручку с бесконечно большой скоростью.
2. Скрип возникает только в процессе верчения.
3. Выбросы поэтому будут только на фронтах и всегда в одну сторону (к нулю?).
4. Не имеет смысла часто и много все это измерять.
5. Выбросы нужно просто выбрасывать.
Ваш медианный алгоритм может давать очень большую ошибку, если более половины выборки придется на фронт с большими выбросами.
Go to the top of the page
 
+Quote Post
neiver
сообщение Aug 1 2013, 10:20
Сообщение #40


Местный
***

Группа: Участник
Сообщений: 214
Регистрация: 22-03-10
Из: Саратов
Пользователь №: 56 123



Цитата(AlexandrY @ Aug 1 2013, 13:09) *
Алгоритм Neiver-а не прошел верификацию, там получается явно не медиана.

Кстати да, там у меня ошибочка была, при не четном колчестве элементов. Сейчас поправил и чуть оптимизировал.
Код
int Median(const int *data, size_t size)
{
    int min, max, newMax, newMin;
    size_t middle = (size+1) / 2;
    min = max = data[0];
    for(size_t i = 0; i < size; i++)
    {
        max = std::max(data[i], max);
        min = std::min(data[i], min);
    }

    int medianCandidate;
    size_t less, more;
    do
    {
        medianCandidate = (min + max) / 2;
        more = less = 0;
        newMax = min;
        newMin = max;

        for(size_t i = 0; i < size; i++)
        {
            if(data[i] > medianCandidate)
            {
                more ++;
                if (data[i] < newMin)
                    newMin = data[i];
            }else if(data[i] < medianCandidate)
            {
                less ++;
                if (data[i] > newMax)
                    newMax = data[i];
            }
        }

        if (less <= middle && more <= middle)
            break;
        else if(less > middle)
        {            
            max = newMax;
        }
        else
        {
            min = newMin;
        }
    }
    while(max - min > 1);
    size_t equal = size - more - less;
    if (less >= middle) return newMax;
    else if (less + equal >= middle)
        return medianCandidate;
    else return newMin;
}
Go to the top of the page
 
+Quote Post
AlexandrY
сообщение Aug 1 2013, 10:23
Сообщение #41


Ally
******

Группа: Модераторы
Сообщений: 6 232
Регистрация: 19-01-05
Пользователь №: 2 050



Цитата(Tanya @ Aug 1 2013, 12:44) *
Может...
Я про то, что
1. Человек не может крутить ручку с бесконечно большой скоростью.
2. Скрип возникает только в процессе верчения.
3. Выбросы поэтому будут только на фронтах и всегда в одну сторону (к нулю?).
4. Не имеет смысла часто и много все это измерять.
5. Выбросы нужно просто выбрасывать.
Ваш медианный алгоритм может давать очень большую ошибку, если более половины выборки придется на фронт с большими выбросами.


А..., все про тот же резистор.
Честно говоря уже много лет на моих платах нет переменных резисторов. Ничего по существу в этой теме сказать не могу. sad.gif
Разве что предложил бы поставить сенсорный скроллер. biggrin.gif

Любой фильтр даст ошибку если его применить вне его полосы.
Кстати, знаете что у медианного фильтра можно измерить частотную характеристику?
Go to the top of the page
 
+Quote Post
Altemir
сообщение Aug 1 2013, 10:36
Сообщение #42


Местный
***

Группа: Свой
Сообщений: 249
Регистрация: 2-05-06
Из: Россия, Поволжье
Пользователь №: 16 686



AlexandrY
Могу скромно попросить на той же платформе проверить медианку на основе сортировки Шелла? rolleyes.gif Заранее благодарю.

CODE

#define compGT(a, B ) (a > B )

//------------------------------------------------------------------------------
//! Медианный фильтр с сортировкой Шелла
//------------------------------------------------------------------------------
int Med_Shell_Sort(int *a, int ub){
int n, h, i, j;
int t;

// compute largest increment
n = ub + 1;
h = 1;
if (n < 14) h = 1;
else
if (sizeof(tblIndex) == 2 && n > 29524) h = 3280;
else
{
while (h < n) h = 3*h + 1;
h /= 3;
h /= 3;
}

while (h > 0)
{
// sort-by-insertion in increments of h
for (i = h; i < ub; i++)
{
t = a[i];
for (j = i-h; (j >= 0) && compGT(a[j], t); j -= h) a[j+h] = a[j];
a[j+h] = t;
}
// compute next increment
h /= 3;
}

return ((ub+1)/2);
}
Go to the top of the page
 
+Quote Post
AlexandrY
сообщение Aug 1 2013, 10:54
Сообщение #43


Ally
******

Группа: Модераторы
Сообщений: 6 232
Регистрация: 19-01-05
Пользователь №: 2 050



Цитата(neiver @ Aug 1 2013, 13:20) *
Кстати да, там у меня ошибочка была, при не четном колчестве элементов. Сейчас поправил и чуть оптимизировал.


Да теперь правильно.
Обновил в таблице результатов в предыдущем посте.

Ого! Уже и алгоритм Neiver обошел (по некоторым параметрам) алгоритмы из Рецептов .
Значит рецепты пора выбрасывать в утиль. wink.gif

Цитата(Altemir @ Aug 1 2013, 13:36) *
Могу скромно попросить на той же платформе проверить медианку на основе сортировки Шелла? rolleyes.gif Заранее благодарю.


Да, мог бы если скажете где взять sizeof(tblIndex) и что там за магические числа типа 29524 и 3280
Go to the top of the page
 
+Quote Post
Altemir
сообщение Aug 1 2013, 11:09
Сообщение #44


Местный
***

Группа: Свой
Сообщений: 249
Регистрация: 2-05-06
Из: Россия, Поволжье
Пользователь №: 16 686



Цитата(AlexandrY @ Aug 1 2013, 14:54) *
Да, мог бы если скажете где взять sizeof(tblIndex) и что там за магические числа типа 29524 и 3280


Код
typedef int tblIndex;


Упс. Прошу прощения. sizeof(tblIndex) - это я не всё заменил, чтобы выложить сюда. В моём примере следует использовать 4 - размерность элемента входного массива, байт. 29524 и 3280 - это действительно, магические числа. Брал пример очень давно из какого-то учебника, не вспомнить. Если правильно понимаю, сии числа ограничивают элементарный блок сортировки и шаг при работе с очень большими массивами, чтобы оптимизировать эффективность. Вроде, в книжке был целый ряд магических чисел для ещё бОльших длин, но я не использую у себя массивы, превышающие 1000 элементов, так что указанная часть кода неактуальна. Если найду источник этого примера, скину ссылку.

Ага. Нашёл: http://www.info-system.ru/library/algo/sortsearch.pdf
И отдельные файлы реализации, откуда выдирал:
http://www.cs.auckland.ac.nz/~jmor159/PLDS...emann/s_shl.txt
http://epaperpress.com/sortsearch/txt/shl.txt
Видно, что h может быть получен разными способами.
Go to the top of the page
 
+Quote Post
AlexandrY
сообщение Aug 1 2013, 11:22
Сообщение #45


Ally
******

Группа: Модераторы
Сообщений: 6 232
Регистрация: 19-01-05
Пользователь №: 2 050



Цитата(Altemir @ Aug 1 2013, 14:09) *
Упс.


Добавил. См. пост №37
Go to the top of the page
 
+Quote Post

4 страниц V  < 1 2 3 4 >
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 11th July 2025 - 15:02
Рейтинг@Mail.ru


Страница сгенерированна за 0.01529 секунд с 7
ELECTRONIX ©2004-2016