[uquote="Ivanoff-iv",url="/forum/viewtopic.php?p=4644329#p4644329"]Тоже свой алгоритм нахождения медианы... точнее среднего от медиан массива (отсекается по 0, 1 или несколько крайних значений, а из остального находится среднее арифметическое), сам массив при этом не повреждается. Условие - числа в массиве менее половины емкости типа переменной, т.к. старший бит отдаётся под метку... алгоритм разрабатывался для обработки данных с АЦП - там это условие соблюдается.
Фильтр не портит массив, это позволяет, используя колцевой буфер, использовать результаты работы АЦП повторно (это значит, что результаты фильтрации можно получать с частотой опроса АЦП)
К сожалению исходный алгоритм фильтра остался на жетком диске дома... а это я из готового кода "быстрого АмперВольтВаттОмМетра для ЛБП на меге8" выкусил.
Спойлер
Код написан в кодевижене, прошу понять и простить 
Код: Выделить всё
unsigned int filtr (unsigned int inp[], unsigned char Length, unsigned char Median){
//inp[] массив входных данных
//Length длина массива входных данных
//Median количество отбрасываемых крайних элементов с каждой стороны, т.е. мощность медианного фильтра
unsigned int tmp;
unsigned char i,j,k,u; //счетчики и ограничители
unsigned long summ = 0; //аккумулятор для суммирования усредняемых элементов массива
k=Length-Median; //количество итераций поиска
u=k-Median; //определяем, сколько элементов нужно усреднять
while (k) {
tmp=~(1<<15); //0x7FFF - максимально допустимое для алгоритма число
i=Length;
while (i>0) //в цикле перебираем весь массив - ищем минимальный элемент
{
i--;
if (tmp >= inp[i])
{
j = i;
tmp = inp[i];
};
};
if (k<=u) summ+=tmp; //складываем в аккумулятор если обработать осталось <= требуемое для усреднения количество элементов
inp[j]|=(1<<15); //ставим метку на найденном и обработанном элементе, с ней он уже не будет минимальным
k--;
};
//----------
k=Length; //убираем все метки
do {inp[--k]&=~(1<<15);}
while (k>0);
//----------
tmp=summ/u; //находим среднее арифметическое
return (tmp); //и возвращаем его
}
Да, этот код не будет минимальным в вашей гонке, но у него задача и возможности другие - он позволяет быстро обрабатывать и выводить данные с относительно медленного (т.к. там производится серия измерений для уменьшения дискретности и шага отображения) АЦП.
Вроде всё верно выкусил, там просто ещё автокалибровка и автоподстройка 0 и сохранение этих данных в сжатом виде в служебной области массива реализованы... были...
Наверно и для моей задачи (из массива на 12 элементов отбросить по одному крайнему, а остальные усреднить) можно сделать быстрее, если делать фильтр жёстко под эту задачу, но этот код позволяет менять параметры на лету, подбирая фильтрацию под задачу.
Просто после проверки на железе это оказались оптимальные, а нормально работающий код переделывать не захотелось...
ПС не уверен, что я до среднего уровня тут присутствующих дотягиваюсь, т.к. смотрю, все уже на STMах и ESPхах катаются... а я с ними только в среде ардуино дело имел...
[/uquote]
а кто гарантирует, что
будет как минимум в два раза больше
-- поскольку иначе будет UB (неопределенное поведение).
Код: Выделить всё
tmp=~(1<<15); //0x7FFF - максимально допустимое для алгоритма число
-- почему бы тут просто не сделать
?
так же если никогда не выполнится
Код: Выделить всё
if (tmp >= inp[i])
{
j = i;
tmp = inp[i];
};
то будет снова UB -- поскольку
обратится к неинициализированной переменной.
Код: Выделить всё
tmp=summ/u; //находим среднее арифметическое
return (tmp); //и возвращаем его
-- тут можно просто сделать
Добавлено after 16 minutes 8 seconds:
[uquote="ПростоНуб",url="/forum/viewtopic.php?p=4644256#p4644256"][uquote="Adrift",url="/forum/viewtopic.php?p=4644242#p4644242"]
ПростоНуб, ловите пузырьковую и не ворованную у вас
median5 ) Алгоритм простейший: тремя перестановками передвигаем в конец наибольшее из 4-х значений, оно нам больше не нужно, то же самое повторяем для оставшихся четырех, осталось 3 значения из которых наибольшее и будет искомым. 1000 итераций для O3 выполняются за 31029 и 27050 тактов в мою пользу, с O2 вы выигрываете 33 такта )[/uquote]
Не вижу. Полностью профилирующий код опять ведь не привели.
А я привожу:
Спойлер
Код: Выделить всё
#include <algorithm>
#include <cstdint>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define BUF_SIZE 400000*77
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
#define SWAP(a,b,type) {type ttttttttt=a;a=b;b=ttttttttt;}
int median5_adrift(int* arr)
{
int a = arr[0], b = arr[1], c = arr[2], d = arr[3], e = arr[4];
if (a > b) std::swap(a, b);
if (b > c) std::swap(b, c);
if (c > d) std::swap(c, d);
if (a > b) std::swap(a, b);
if (b > c) std::swap(b, c);
if (c > e) std::swap(c, e);
if (a > b) std::swap(a, b);
return (b > c) ? b : c;
}
int median3 (int a, int b, int c) {
return MAX(MIN(a,b),MIN(c,MAX(a,b)));
}
int median5 (int *v) {
return median3(
v[4],
MAX(MIN(v[0], v[1]), MIN(v[2], v[3])),
MIN(MAX(v[0], v[1]), MAX(v[2], v[3]))
);
}
void do_only_mean(int *rand_buf, int *res_buf) {
for (int i = 0; i < BUF_SIZE - 5; i++) {
res_buf[i] = median5(rand_buf++);
}
return;
}
void adrift_do_only_mean(int *rand_buf, int *res_buf) {
for (int i = 0; i < BUF_SIZE - 5; i++) {
res_buf[i] = median5_adrift(rand_buf++);
}
return;
}
int main() {
int *rand_buf = (int*) malloc(BUF_SIZE*sizeof(int));
int *res_buf = (int*) malloc(BUF_SIZE*sizeof(int));
srand(time(NULL));
for ( int i = 0; i < BUF_SIZE; i++) {
rand_buf[i] = rand();
}
clock_t start = clock() ;
adrift_do_only_mean(rand_buf, res_buf);
clock_t end = clock() ;
double adrift_elapsed_time = (end - start) / (double)CLOCKS_PER_SEC;
start = clock() ;
do_only_mean(rand_buf, res_buf);
end = clock() ;
double mean_elapsed_time = (end - start) / (double)CLOCKS_PER_SEC;
printf("%f -- %f => %f\n", adrift_elapsed_time, mean_elapsed_time, adrift_elapsed_time / mean_elapsed_time);
}
Без оптимизации мой код выигрывает в 2 раза (gcc ./median.cpp)
1.701809 -- 0.775227 => 2.195240
С оптимизацией в 3.5 раза (gcc -O3 ./median.cpp)
0.116901 -- 0.032853 => 3.558305
На самом деле, это давно известно, что std::swap не векторизуется. Ну хоть убейся. А сравнения - легко и просто.
Если заинлайнить median3(), то median5() будет всего 16 команд.
Спойлер
Код: Выделить всё
vmovd (%rdi), %xmm2
vmovd 4(%rdi), %xmm4
vmovd 8(%rdi), %xmm0
vpminsd %xmm4, %xmm2, %xmm1
vmovd 12(%rdi), %xmm5
vpminsd %xmm5, %xmm0, %xmm3
vpmaxsd %xmm4, %xmm2, %xmm2
vpmaxsd %xmm5, %xmm0, %xmm0
vpmaxsd %xmm1, %xmm3, %xmm3
vpminsd %xmm2, %xmm0, %xmm0
vmovd 16(%rdi), %xmm1
vpmaxsd %xmm3, %xmm1, %xmm2
vpminsd %xmm3, %xmm1, %xmm1
vpminsd %xmm2, %xmm0, %xmm0
vpmaxsd %xmm1, %xmm0, %xmm0
vmovd %xmm0, %eax
ret
А портянку median5_adrift() остается на регистрах общего назначения из 34 команд
Спойлер
Код: Выделить всё
movl (%rdi), %r8d
movl 4(%rdi), %edx
movl 8(%rdi), %eax
movl 12(%rdi), %ecx
movl 16(%rdi), %esi
cmpl %edx, %r8d
jg .L2
cmpl %eax, %edx
jle .L8
movl %edx, %edi
movl %r8d, %edx
movl %edi, %r8d
.L3:
cmpl %r8d, %ecx
movl %eax, %edi
cmovg %r8d, %ecx
cmpl %edx, %eax
cmovge %edx, %eax
cmovge %edi, %edx
.L4:
cmpl %ecx, %edx
movl %ecx, %edi
cmovle %edx, %ecx
cmovle %edi, %edx
cmpl %ecx, %eax
cmovl %ecx, %eax
cmpl %edx, %esi
cmovle %esi, %edx
cmpl %edx, %eax
cmovl %edx, %eax
ret
.p2align 4
.p2align 3
.L2:
cmpl %eax, %r8d
jg .L3
cmpl %ecx, %eax
cmovle %eax, %ecx
movl %edx, %eax
movl %r8d, %edx
jmp .L4
Предвидя возражения, что используете легаси архитектуру без поддержки векторизации, предложу подумать, а что будет, когда потребуется сменить МК на более современный. Переписывать код будете?
Добавлено after 32 minutes 29 seconds:
[uquote="ARV",url="/forum/viewtopic.php?p=4644232#p4644232"]Что я вижу вокруг себя? Берут программиста-новичка, выпускника бакалавриата. И ставят задачу: мы тут 20 лет используем вот такую систему программирования - ХХХХХ - слыхал? Не слыхал? Ну ничего, разберешься. Надо, чтобы ты завтра на ней сделал сервер ИИ. Посмотри, как мы 20 лет делали сервер БД, и сделай по образцу. Сдаём через месяц. Справишься?
В итоге этот новичок, если не сбегает, выпучив глаза копипастит код из прежних проектов, ни на секунду не задумываясь, как оно устроено, иначе в сроки не уложиться. И если оно потом заработает (а рано или поздно заработает), оно становится
частью той самой базы "мы 20 лет". В итоге после года работы профессиональный рост такого программиста равен 0, но от реальности он отстал почти на бесконечность.[/uquote]
А можно уточнить, в каких системных интеграторах или IT компаниях Вы такое видите?
Вот я не вижу. Если берем стажера после бакалавриата, то в более-менее свободное плавание он допускается только через полгода, не ранее. И все отдают отчет, что в течении этого полугода такой джун - убыточен. Каждая строчка его кода проходит очень жесткий code review и его PR сливается с основной веткой, порой, чуть ли не с десятой попытки. Уж простите, но утверждать PR моя прямая задача, как лида. Поэтому знаю о чем пишу.
[uquote="ARV",url="/forum/viewtopic.php?p=4644232#p4644232"]Именно поэтому и прибегает к ИИ-генераторам кода.[/uquote]
Я же выше написал, как используются ИИ в профессиональной разработке. Если и находится разработчик, доверяющий AI, то он или очень быстро перестанет ему доверять, или я с ним расстанусь.
[uquote="ARV",url="/forum/viewtopic.php?p=4644232#p4644232"]Программист делает так код[/uquote]
Прежде чем писать код, сначала надо осмыслить постановку, найти в ней ошибки, противоречия и неоднозначности, устранить их все вместе с аналитиком и заказчикам. И именно в этом заключается львиная часть работы разработчика.
[uquote="ARV",url="/forum/viewtopic.php?p=4644232#p4644232"]Чтобы это говнище ворочалось, выпускаются более мощные процессоры. Более мощные процессоры порождают желание наговнокодить то, что вчера считалось невозможным... И круг замыкается.[/uquote]
Не для этого они выпускаются, а для того, чтобы можно было решать задачи, которые еще лет 10 назад были доступны только суперкомпьютерам, да и то не всем.
А уж кто и как свою дурь и лень при этом проявляет - отдельная тема и явно уже вне данного топика.
[uquote="ARV",url="/forum/viewtopic.php?p=4644232#p4644232"]В общем, кризис жанра полный[/uquote]
Опять видите только осколки вершины айсберга, да и то, выборочно. А ведь, если говорить об МК, то Espressif фактически совершил революцию своими дешевыми МК с WiFi и BLE.
[uquote="ARV",url="/forum/viewtopic.php?p=4644232#p4644232"]Недавно впервые зашел на сайт известного Алекса Гайвера... Увидел там проект вентилятора, который нацеливается на лицо методом распознавания лица на видео. Еще вчера это было невозможно, теперь с этим справился самодельщик. И? Ни один человек в мире не будет пользоваться таким вентилятором иначе, как хвастаясь перед другими.[/uquote]
Именно в таком применении - вряд ли кто будет. А вот себе на автоматические раздвижные ворота я бы, возможно, такую разработку поставил. Иногда идешь с тачкой, руки заняты и приходится ставить тачку и лезть в карман за мобилой или брелком, чтобы открыть ворота в пешеходном режиме. А так они будут сами открываться, причем только увидев меня, а не кого-то иного.
Это я к тому, что несмотря на то, что большинство подобных идей нежизнеспособны, именно благодаря их генерации их гор шлака выделяются жемчужины, которых иначе не возникло бы.
Я это только приветствую. Пробуйте, экспериментируйте, изобретайте. Даже если из тысячи попыток только одна окажется удачна - это уже движение вперед.[/uquote]
Код: Выделить всё
if (a > b) std::swap(a, b);
if (b > c) std::swap(b, c);
if (c > d) std::swap(c, d);
if (a > b) std::swap(a, b);
if (b > c) std::swap(b, c);
if (c > e) std::swap(c, e);
if (a > b) std::swap(a, b);
-- а это разве не
std::sort
? и после можно просто
тут вообще просто можно сделать
std::nth_element
и после тот же элемент возвращать получается, который и указан как
nth
Код: Выделить всё
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
#define SWAP(a,b,type) {type ttttttttt=a;a=b;b=ttttttttt;}
-- так же не понятно зачем это было привнесено -- есть же
std::*
такие функциональности...
Код: Выделить всё
int *rand_buf = (int*) malloc(BUF_SIZE*sizeof(int));
int *res_buf = (int*) malloc(BUF_SIZE*sizeof(int));
-- такое надо заменить на
std::vector<int>(BUF_SIZE)
Если заинлайнить median3(), то median5() будет всего 16 команд.
-- различные инструкции потребляют различное количество времени работы ЦПУ -- по этому по количеству команд нельзя судить о быстродействии. Более того следует учитывать, что в каком то другом компиляторе будет сгенерирован другой ассемблер (в том числе при других опциях компиляции).
-- ну и могу рекомендовать заменить такое везде на
std::span
или если нужна гарантированная длина массива на
std::array
а вообще если доступен c++20 -- можно удобно использовать
std::ranges::take_view
как входной аргумент с указыванием количества элементов. -- или так не получится как я хочу... хммм...
тогда можно точно указывать в std::span вторым аргументом шаблона фиксированный размер (вместо умолчательного динамического).
