Хитрые, необычные алгоритмы и код

Огонёк

ПростоНуб писал(а):

С чего Вы взяли, что данный алгоритм нахождения медиан из 3 или 5 числе не универсален?

Алгоритмы лучше описывать псевдокодом, или на всем понятном Си. Разбор алгоритма на относительно новом языке должен начинаться с изучения этого языка - а оно точно надо?

Добавлено after 2 minutes:

ПростоНуб писал(а):

алгоритм нахождения медиан из 3 или 5 числе не универсален?

Универсален. Называется пузырьковая сортировка. На таких масштабах работает превосходно.

Реклама

ПростоНуб

Огонёк писал(а):

ПростоНуб писал(а):

С чего Вы взяли, что данный алгоритм нахождения медиан из 3 или 5 числе не универсален?

Алгоритмы лучше описывать псевдокодом, или на всем понятном Си.

"Отучаемся говорить за всю сеть" (с)
Я плохо представляю, насколько деформировано Ваше сознание, но сейчас полно разработчиков на МК, которые C вообще не знают, вполне себе обходясь MicroPython, JS или тем же Rust.

Огонёк писал(а):

ПростоНуб писал(а):

алгоритм нахождения медиан из 3 или 5 числе не универсален?

Универсален. Называется пузырьковая сортировка.

Ну давайте сравним. Можно даже на С.

Код:

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define BUF_SIZE 1024*1024*64
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))

int bubble(int *v) {
  int tmp;
  bool noSwap;
 
  for (int i = 4; i >= 0; i--)
  {
    noSwap = 1;
    for (int j = 0; j < i; j++)
    {
        if (v[j] > v[j + 1])
        {
            tmp = v[j];
            v[j] = v[j + 1];
            v[j + 1] = tmp;
            noSwap = 0;
        }
    }
    if (noSwap == 1)
        break;
  }
  return v[2];
}

void do_bubble_sort(int *rand_buf, int *res_buf) {
  for (int i = 0; i < BUF_SIZE - 5; i++) {
    res_buf[i] = bubble(rand_buf++);
  }
  return;
}

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 main() {
  int *rand_buf = malloc(BUF_SIZE*sizeof(int));
  int *res_buf = malloc(BUF_SIZE*sizeof(int));

  srand(time(NULL));
  for ( int i = 0; i < BUF_SIZE; i++) {
    rand_buf[i] = rand();
  }

  clock_t start = clock() ;
  do_bubble_sort(rand_buf, res_buf);
  clock_t end = clock() ;
  double bubble_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", bubble_elapsed_time, mean_elapsed_time, bubble_elapsed_time / mean_elapsed_time);
}

Без оптимизации у меня получилось: 2.797298 -- 0.619562 => 4.514961
С -O3 разница вообще катастрофическая: 2.009494 -- 0.076488 => 26.272017

Огонёк писал(а):

На таких масштабах работает превосходно.

Каких таких? У меня медианный фильтр, например, сейчас применяется при обработке потока от ADC по DMA на ESP32-C3 с SPS на 200 КГц в течении 120-130 мс (смотря когда синусоида 50 Гц ноль пересечет).
Ну да, это не 256 мегабайт, как в коде выше, а всего лишь 3.3-3.4 мегабайт. Но это тоже не мало.

Реклама

Огонёк

ПростоНуб писал(а):

Каких таких?

для

ПростоНуб писал(а):

нахождения медиан из 3 или 5 числе

ПростоНуб писал(а):

Ну давайте сравним.

Мне лень этим заниматься. Вы победили, раст круче Си и быстрее ассемблера в сортировке массива из пяти элементов.

OKF

ПростоНуб писал(а):

Так что по названию не судят

В Бельгии тоже названия режущие слух. https://i2018.otzovik.com/2018/01/12/58 ... 02143.jpeg

ПростоНуб

Огонёк писал(а):

ПростоНуб писал(а):

Каких таких?

для

ПростоНуб писал(а):

нахождения медиан из 3 или 5 числе

Поясните. Я же писал явно:

Цитата:

для быстрого медианного фильтра [...] я использую следующие функции:

А медианные фильтры применяются вообще то к сигналам, да еще и в реальном времени.

Огонёк писал(а):

ПростоНуб писал(а):

Ну давайте сравним.

Мне лень этим заниматься. Вы победили, раст круче Си и быстрее ассемблера в сортировке массива из пяти элементов.

Ну если Вы код на С, который я привел для сравнение производительности, не можете отличить от кода на Rust...

Реклама

smacorp

ПростоНуб писал(а):

сейчас полно разработчиков на МК, которые C вообще не знают, вполне себе обходясь MicroPython, JS или тем же Rust

Если это так, то это жопа - искусство программирования стагнирует в ремесло.

Реклама

ARV

Поэтому универсальных и алгоритмов не так уж и много.
А хитрые, как правило, работают на узкой платформе.

А вот я придумал, как на 1 ногу МК повесить кнопку и светодиод, чтобы они работали независимо. Имхо, такого варианта, вроде, не было. Из накладных расходов 1 резистор аппаратно... И это будет работать на любых МК, допускающих вытекающий ток светодиода на своем пине.

Итак: на пин анодом ставится светодиод с резистором. Так же на пин ставится кнопка на общий с последовательным резистором в 1К. Регистр "направления" пина, использую AVRовскую терминологию, DDRn управляет свечением светодиода, регистр подтяжки PORTn всегда 1 (если у МК есть регистр выхода пина, то туда выводим тоже 1). По прерыванию (или в момент иного опроса кнопки) DDRn ставится в 0, и производится опрос регистра ввода PINn, если там 0, то кнопка нажата. А потом DDRn снова принимает уровень, нужный для светодиода (0 не горит, 1 горит). На время опроса пина светодиод не горит, но, т.к. длится это буквально 3-4 такта, этого не заметно.

Что скажете?

Добавлено after 4 minutes:
Основная идея алгоритма основана на том, что подтяжка пина не способна обеспечить светодиод достаточным для свечения током. Например, у AVR подтяжка эквивалентна примерно 70К. Так же, нажатие кнопки шунтирует светодиод резистором 1К, что не перегружает пин и не влияет на яркость светодиода, но однозначно просадит подтяжку, когда DDRn переведется на ввод.

Adrift

ARV писал(а):

Основная идея алгоритма основана на том, что подтяжка пина не способна обеспечить светодиод достаточным для свечения током. Например, у AVR подтяжка эквивалентна примерно 70К.

У STM32 подтяжка 25-55К и светодиод чуть светится, по крайней мере в темноте будет видно.

ARV

Питание 3.6в, на светодиоде падает 1,3в, подтяжка 55К, значит, ток 2,3/55=42 мкА. И при таком токе светодиод светится?!

Применяйте АЛ307 :)))

Реклама

Adrift

Питание 3.3V, подтяжка типикал 40К и зеленый светодиод чуть светится.

Добавлено after 2 minutes 52 seconds:

ARV писал(а):

Применяйте АЛ307 :)))

Я просто возьму мк у которого хватает ног )

ARV

И что вы делаете в теме про хитрые извраты, если проблемы решаете брутфорсом?! :)))

Огонёк

ПростоНуб писал(а):

медианные фильтры применяются вообще то к сигналам, да еще и в реальном времени.

Эти нюансы заботят только программиста. Для МК же всё равно, что там и как - задача чисто математическая: отсортировать несколько значений и выбрать среднее.

ПростоНуб

smacorp писал(а):

ПростоНуб писал(а):

сейчас полно разработчиков на МК, которые C вообще не знают, вполне себе обходясь MicroPython, JS или тем же Rust

Если это так, то это жопа - искусство программирования стагнирует в ремесло.

Когда то, свыше полувека назад, Кнут для своей книги "Искусство программирования" использовал даже не С, а абстрактный MIX ассемблер. 20 лет назад он отказался от него в пользу RISC ассемблера. Следует ли из этого, что искусство программирования возможно только на ассемблере?
То есть на C или Rust искусство программирования уже невозможно? А создать что-то вроде VS Code или Apache Airfow уже не искусство?
Пока Вы будете писать HTTP(S) или MQTT сервер на ассемблере, он станет уже никому не нужен, в связи с развитием технологий. На гитхабе валяются несколько подобных заброшенных проектов для ESP8266, ставших ненужными после выхода ESP32 и, тем более, после перехода Espressif c Tensilica на RISC-V.
Даже для ESP32 эффективный ассемблерный код стал резко проигрывать C и Rust с появлением в ESP32-S3 SIMD инструкций. Потому что код на языке высокого уровня достаточно просто перекомпилировать, а вот ассемблерный код нужно переписывать.
Боюсь, Ваша терминология и семантика слова "искусство" очень далеки от общепринятых. Искусство программирования - это разработка эффективной архитектуры решения с выбором наиболее подходящих средств для её реализации. И без разницы, какие языки там будут использоваться. Java для Kafka, Erlang для MQTT, JS для WebApi или Rust с ассемблерными вставками в HAL.

Добавлено after 9 minutes 11 seconds:

Огонёк писал(а):

ПростоНуб писал(а):

медианные фильтры применяются вообще то к сигналам, да еще и в реальном времени.

Эти нюансы заботят только программиста. Для МК же всё равно, что там и как - задача чисто математическая: отсортировать несколько значений и выбрать среднее.

Сотни тысяч раз в секунду. Еще раз, это надо делать в реальном времени при обработке сигнала. Вы своей пузырьковой сортировкой, проигрывающей эффективному вычислению медианы на порядок, в ряде случаев вообще не успеете фильтровать сигнал.
Причем, если код пузырьковой сортировки на ESP32-S3 не может быть реализован SIMD инструкциями, то мой код LLVM backend замечательно генерирует с использованием SIMD. В последнем случае, разница в производительности уже приближается к двум порядкам.

Огонёк

ПростоНуб писал(а):

пузырьковой сортировкой, проигрывающей эффективному вычислению медианы на порядок

При работе с большими массивами это верно. При работе с пятью переменными - вряд ли. Уж точно не на порядок.

ПростоНуб

Огонёк писал(а):

ПростоНуб писал(а):

пузырьковой сортировкой, проигрывающей эффективному вычислению медианы на порядок

При работе с большими массивами это верно. При работе с пятью переменными - вряд ли. Уж точно не на порядок.

При чем тут массивы? Вы вообще знаете что такое медианный фильтр? Это вычисление медианы по заданному окну для каждого мгновенного значения сигнала. Если медианный фильтр применяется к потоку по DMA от ADC с SPS 400 КГц, то эта самая медиана с пятью переменными должна вычисляться 400 тысяч раз секунду. Если не будете успевать, то рано или поздно любой буфер переполнится.

Starichok51

ПростоНуб писал(а):

искусство программирования возможно только на ассемблере?

да, и еще тысячу раз да!
ни один компилятор с языка высокого уровня с любой оптимизацией не сравнится с программированием на ассемблере.
на ассемблере можно делать такие "чудеса", на которые не способен никакой компилятор с языка высокого уровня.
к тому же, рабочий код (хекс) с ассемблера в несколько раз короче аналогичного кода на Си.

jcxz

Starichok51 писал(а):

на ассемблере можно делать такие "чудеса", на которые не способен никакой компилятор с языка высокого уровня.

Можно, да. Но с каждым годом становится всё меньше и меньше человеков на это способных...

Поэтому скоро ваша фраза будет звучать как: на ассемблере теоретически можно делать такие "чудеса", на которые не способен никакой компилятор с языка высокого уровня.

КРАМ

jcxz писал(а):

можно делать такие "чудеса", на которые не способен никакой компилятор.

К сожалению, чаще всего у этих человеков на выходе получается АСМ-спагетти-код.
Потому что в погоне за беспонтовой компактностью и никчемной скоростью получается откроенная каша, поддерживать которую невозможно ни сейчас, ни в будущем.
АСМ имеет смысл для написания самых критичных функций библиотек, которые в конце концов будут использованы в Си коде.

Огонёк

А не надо ничего поддерживать. Написал один раз идеальный код, и он потом сам нормально работает, не требуя правок и дополнений.

КРАМ

Огонёк писал(а):

А не надо ничего поддерживать. Написал один раз идеальный код, и он потом сам

Бред сивой кобылы. Поддержка кода - это не исправление ошибок. Это возможность его модернизации под дополнительные задачи в существующем изделии, либо при использовании кода в другом изделии с иными вводными, что требует модификации кода.

Хитрые, необычные алгоритмы и код

Кто сейчас на форуме