Xenia 46 30 июля, 2013 Опубликовано 30 июля, 2013 · Жалоба Вы будете смеяться Xenia, но ваш алгоритм в 4 раза! медленней по сравнению с применением библиотечной функции qsort на unsigned short. А на unsigned int в 4.5 раза. А какой длины массив использовался при проверке? Ведь qsort там не пузырьковый, у него логарифмическая скорость. А следовательно на больших массивах эта фора обязательно скажется. Однако в сфере МК память ОЗУ обычно невелика, а потому невелики и массивы. Обычно редко кто ищет медиану в массивах, более длинных чем 1024 элемента. А при такой длине поиск медианы на основе функции qsort врядли даст заметное преимущество. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Axel 1 31 июля, 2013 Опубликовано 31 июля, 2013 · Жалоба Мне тоже стало интересно... Попробовал фильтр Ekstrom'а для обработки сигналов touch screen (5 - 15 отсчетов). Понравилось (время не измерял). Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
demiurg_spb 0 31 июля, 2013 Опубликовано 31 июля, 2013 · Жалоба Обычно редко кто ищет медиану в массивах, более длинных чем 1024 элемента. Тут я поддержу Ксению, т.к. в моих задачах (не связанных с применением DSP) средняя глубина медианной фильтрации варьируется от 5 до 31 отсчёта. Давайте определимся с правилами игры. Предлагаю предоставлять результаты своих замеров для следующих глубин фильтра: 10, 100, 1K и 10K Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Tanya 4 31 июля, 2013 Опубликовано 31 июля, 2013 · Жалоба варьируется от 5 до 31 отсчёта. Давайте определимся с правилами игры. Вот тоже скажу... Нет никакого смысла в оцифровке скрипящего потенциометра последовательностью в 100 точек. Не более 10, если не слишком часто... Кроме того сортировка проводится не случайным образом перемешанной последовательности, а априорно известной. Таким образом, возможно, что самым лучшим для данного случая будет не самый быстрый для общего случая алгоритм. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
demiurg_spb 0 31 июля, 2013 Опубликовано 31 июля, 2013 · Жалоба Кроме того сортировка проводится не случайным образом перемешанной последовательности, а априорно известной. Таким образом, возможно, что самым лучшим для данного случая будет не самый быстрый для общего случая алгоритм.Не понял эту глубокую мысль... У нас каждый раз новая неизвестная последовательность (не важно все 10 отсчётов новых или только один из десяти (скользящее окно)). Т.е. всегда что-то новое и неизвестное. А то что мы отсортировали на прошлом шаге для нас не представляет никакой ценности на текущем шаге, т.к. наши отсчёты после сортировки теряют привязку к своей очерёдности (то бишь ко времени). Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Tanya 4 31 июля, 2013 Опубликовано 31 июля, 2013 · Жалоба Не понял эту глубокую мысль... Поясню. Последовательность не произвольная, а реальная - две полочки, а между ними выбросы. Или одна полочка без выбросов. Возможно, что со всем этим можно легко справиться с помощью одного резистора и одного конденсатора. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
demiurg_spb 0 31 июля, 2013 Опубликовано 31 июля, 2013 · Жалоба Не всегда. У меня есть разработка - тахометр, который используют в весьма разболтанных системах (люфты страшные) + метки на колесе неоднородно размещены бывают, так для нормального функционирования приходится и медианный фильтр и фнч 2 порядка ставить. И никакие конденсаторы тут не спасают. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
KRS 1 31 июля, 2013 Опубликовано 31 июля, 2013 · Жалоба А ведь если фильтр скользящий, на этапе добавление очередного измерения, уже есть отсортированный массив. Но из него удаляется один элемент, при этом он остается отсортированным, надо просто вставить новый на нужное место. Ту сортировка вставками будет самой быстрой. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Xenia 46 31 июля, 2013 Опубликовано 31 июля, 2013 · Жалоба Давайте определимся с правилами игры. Предлагаю предоставлять результаты своих замеров для следующих глубин фильтра: 10, 100, 1K и 10K Да-да! И тогда я победю Клёна! :) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Tanya 4 31 июля, 2013 Опубликовано 31 июля, 2013 · Жалоба . И никакие конденсаторы тут не спасают. Верю. Но я же написала "возможно"... Медианный фильтр нелинейный и удаляет "неправильные" выбросы. А откуда они берутся? Разрывается контакт (повисает в воздухе), а входное сопротивление АЦП не очень... Есть еще вариант - сделать ограничение скорости нарастания (тоже нелинейная штука) - при рассогласовании запомненного значения с АЦПшным оно медленно увеличивается или уменьшается (на фиксированную величину). Это будет самый быстрый способ. Я так думаю. Недостаток есть - если шаловливые ручонки непрерывно крутят туда-сюда ручки, то будет заниженное значение, если вход АЦП немного подтянут к земле. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Axel 1 31 июля, 2013 Опубликовано 31 июля, 2013 · Жалоба Недостаток есть - если шаловливые ручонки непрерывно крутят туда-сюда ручки, то будет заниженное значение, если вход АЦП немного подтянут к земле. Иногда (часто) не в ручонках дело. Типичный пример - потенциометры на педали газа автомобилей. Пример из программы ECU привести не могу - не сохранился, но когда однажды пришлось разбираться, то обнаружился вполне серьезный фильтр (насколько удалось понять после дизассемблера). Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
AlexandrY 3 31 июля, 2013 Опубликовано 31 июля, 2013 · Жалоба Ну что, пришло время подвести некоторые итоги. Ниже результаты тестирования алгоритмов на платформе на основе 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 раз. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
AltemirX 0 31 июля, 2013 Опубликовано 31 июля, 2013 · Жалоба AlexandrY "Number of samplles" - это длина массива? Какой тип чисел был во входном массиве? signed long не пробовали с длиной 128 элементов? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
AlexandrY 3 31 июля, 2013 Опубликовано 31 июля, 2013 · Жалоба AlexandrY "Number of samplles" - это длина массива? Какой тип чисел был во входном массиве? signed long не пробовали с длиной 128 элементов? Был использован тип unsigned int Number of samplles - это длинна массива. Выбрана нечетной чтобы был элемент посередине. Измерялось время между подачей очередного случайного сэмпла (от 1 до 10000)в массив и получением медианы как отклика. Всего пропускалось по 1000 сэмплов. Вначале массивы инициализировались единицами (из-за особенности алгоритма Ekstrom ) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
demiurg_spb 0 31 июля, 2013 Опубликовано 31 июля, 2013 · Жалоба А ведь если фильтр скользящий, на этапе добавление очередного измерения, уже есть отсортированный массив. Но из него удаляется один элемент, при этом он остается отсортированным, надо просто вставить новый на нужное место. Ту сортировка вставками будет самой быстрой. Это понятно, но вы посмотрите на размер кода такого алгоритма 'Ekstrom'. Я это тоже изобретал, но отверг по причинам невпихуемости результирующей прошивки. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
