| |
|
  |
 вычисление медианы массива (или произвольной моды), stm32f4 + STL |
|
|
|
|
 Jul 31 2013, 10:07
|
неотягощённый злом
Группа: Свой
Сообщений: 2 746
Регистрация: 31-01-08
Из: Санкт-Петербург
Пользователь №: 34 643
|
Цитата(Tanya @ Jul 31 2013, 12:41)  Кроме того сортировка проводится не случайным образом перемешанной последовательности, а априорно известной. Таким образом, возможно, что самым лучшим для данного случая будет не самый быстрый для общего случая алгоритм. Не понял эту глубокую мысль... У нас каждый раз новая неизвестная последовательность (не важно все 10 отсчётов новых или только один из десяти (скользящее окно)). Т.е. всегда что-то новое и неизвестное. А то что мы отсортировали на прошлом шаге для нас не представляет никакой ценности на текущем шаге, т.к. наши отсчёты после сортировки теряют привязку к своей очерёдности (то бишь ко времени).
--------------------
“Будьте внимательны к своим мыслям - они начало поступков” (Лао-Цзы)
|
|
|
|
|
|
|
|
Jul 31 2013, 12:06
|
Гуру
Группа: Модераторы
Сообщений: 8 752
Регистрация: 6-01-06
Пользователь №: 12 883
|
Цитата(demiurg_spb @ Jul 31 2013, 15:06) . И никакие конденсаторы тут не спасают. Верю. Но я же написала "возможно"... Медианный фильтр нелинейный и удаляет "неправильные" выбросы. А откуда они берутся? Разрывается контакт (повисает в воздухе), а входное сопротивление АЦП не очень... Есть еще вариант - сделать ограничение скорости нарастания (тоже нелинейная штука) - при рассогласовании запомненного значения с АЦПшным оно медленно увеличивается или уменьшается (на фиксированную величину). Это будет самый быстрый способ. Я так думаю. Недостаток есть - если шаловливые ручонки непрерывно крутят туда-сюда ручки, то будет заниженное значение, если вход АЦП немного подтянут к земле.
|
|
|
|
|
|
|
|
Jul 31 2013, 12:30
|
Местный
Группа: Свой
Сообщений: 480
Регистрация: 21-11-04
Пользователь №: 1 188
|
Цитата(Tanya @ Jul 31 2013, 15:06) Недостаток есть - если шаловливые ручонки непрерывно крутят туда-сюда ручки, то будет заниженное значение, если вход АЦП немного подтянут к земле. Иногда (часто) не в ручонках дело. Типичный пример - потенциометры на педали газа автомобилей. Пример из программы ECU привести не могу - не сохранился, но когда однажды пришлось разбираться, то обнаружился вполне серьезный фильтр (насколько удалось понять после дизассемблера).
|
|
|
|
|
|
|
|
Jul 31 2013, 13:14
|
Ally
Группа: Модераторы
Сообщений: 6 232
Регистрация: 19-01-05
Пользователь №: 2 050
|
Ну что, пришло время подвести некоторые итоги.  Ниже результаты тестирования алгоритмов на платформе на основе Kinetis MK60 (Cortex-M4). Программа выполнялась из внутренней Flash, данные во внутренней RAM. Частота ядра 120 МГц, частота шины 60 МГц, частота Flash 24 МГц. Компилятор Keil ARMCC v5.03. Ключи компиляции: -c --cpu Cortex-M4.fp -D__MICROLIB -g -O3 -Otime --apcs=interwork Я проводил тестирование на интересующем меня объеме выборки. Кому надо дальше может тестировать сам. Проект выложу. Как видно абсолютный победитель - алгоритм Ekstrom . Но надо сказать, что в нем есть нюанс. В данных не должно быть числа равного символу STOPPER. В алгоритме STOPPER равен 0, значит в данных не должно быть 0, что я сделал формирую случайные данные. Если такая кривизна не устраивает, то лучший алгоритм select из рецептов на C. Код INVCPU v1.00 PCB Test Suit.
System Core Clock = 120000000 Hz
Now. System ticks = 750055l, Sysytem time = 0.006250 s
Clock check. T1= 1440076l, T2= 1560048l, Delta(tick)= 119972l, Delta(s)= 0.0010
----------------------------------------------
Algorithm 'Qsort' (standart C library ):
----------------------------------------------
Results CRC = D6EF
Number of samplles = 65
Number of iterations = 1000
Measured max. number of cycles = 67287, time(us)=560.73
Measured min. number of cycles = 23532, time(us)=196.10
Measured aver.number of cycles = 26937, time(us)=224.48
----------------------------------------------
Algorithm 'Select' (Numerical Recipes in C, 8.5 Selecting the Mth Largest p.341):
----------------------------------------------
Results CRC = D6EF
Number of samplles = 65
Number of iterations = 1000
Measured max. number of cycles = 3142, time(us)=26.18
Measured min. number of cycles = 1237, time(us)=10.31
Measured aver.number of cycles = 2087, time(us)=17.39
----------------------------------------------
Algorithm 'Selip' (Numerical Recipes in C, 8.5 Selecting the Mth Largest p.343):
----------------------------------------------
Results CRC = D6EF
Number of samplles = 65
Number of iterations = 1000
Measured max. number of cycles = 18478, time(us)=153.98
Measured min. number of cycles = 2198, time(us)=18.32
Measured aver.number of cycles = 16979, time(us)=141.49
----------------------------------------------
Algorithm 'Xenia' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1180687):
----------------------------------------------
Results CRC = D6EF
Number of samplles = 65
Number of iterations = 1000
Measured max. number of cycles = 40263, time(us)=335.53
Measured min. number of cycles = 920, time(us)=7.67
Measured aver.number of cycles = 19902, time(us)=165.85
----------------------------------------------
Algorithm 'Ekstrom' (http://embeddedgurus.com/stack-overflow/tag/median-filter/):
----------------------------------------------
Results CRC = D6EF
Number of samplles = 65
Number of iterations = 1000
Measured max. number of cycles = 1243, time(us)=10.36
Measured min. number of cycles = 1182, time(us)=9.85
Measured aver.number of cycles = 1187, time(us)=9.89
----------------------------------------------
Algorithm 'Klen' (http://electronix.ru/forum/index.php?s=&showtopic=114436&view=findpost&p=1180679)
----------------------------------------------
Results CRC = D6EF
Number of samplles = 65
Number of iterations = 1000
Measured max. number of cycles = 3517, time(us)=29.31
Measured min. number of cycles = 1732, time(us)=14.43
Measured aver.number of cycles = 2470, time(us)=20.58 Да, а Klen-у выкинуть свой компилятор.  Скомпилированное Keil-ом 127 сэмплов по его алгоритму вычисляет за 53 мкс на 120 МГц ядре против 56 мкс на 168 МГц ядре скомпилированное GCC. Если отключить опцию MICROLIB в компиляторе то алгоритм qsotr ускорится где-то в 9 раз.
|
|
|
|
|
|
|
|
Jul 31 2013, 14:10
|
Ally
Группа: Модераторы
Сообщений: 6 232
Регистрация: 19-01-05
Пользователь №: 2 050
|
Цитата(Altemir @ Jul 31 2013, 17:03) AlexandrY
"Number of samplles" - это длина массива? Какой тип чисел был во входном массиве? signed long не пробовали с длиной 128 элементов? Был использован тип unsigned intNumber of samplles - это длинна массива. Выбрана нечетной чтобы был элемент посередине. Измерялось время между подачей очередного случайного сэмпла (от 1 до 10000)в массив и получением медианы как отклика. Всего пропускалось по 1000 сэмплов. Вначале массивы инициализировались единицами (из-за особенности алгоритма Ekstrom )
|
|
|
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
