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

ARV

itoa чем не угодила? получите строку символов, которую можно выводить.

Реклама

Ivanoff-iv

Нужда вынудила придумать метод хранения больших величин в малом пространстве....
Делал гирлянду на тини13, в ней для задания задержки переключения шагов требуются числа от 4 до... примерно 1000, чтобы занимать поменьше места я при хранении занимал 1 байт и делал распаковку по формуле вида Y=(X+1)*4;
такое хранение занимало 8 бит и позволяло получить на выходе значения от 4 до 1028 (с шагом 4 во всём диапазоне)
меня это не очень устраивало, т.к. скорость - величина обратно пропорциональная задержке меняется очень нелинейно - в начале быстро, а затем вообще незаметно.

Спойлер

для сравнения методов я взял те-же 5 бит хранения или числа 0-31 - диапазон удручает, всего до 128...
на первом же шаге скорость падает в 2 раза! а дальше меньше, если продолжить этот ряд, то вид будет ещё печальней

Тогда решил прибегнуть к методу записи чисел с плавающей точкой, именуемому в народе Float :)))

только для тини его немного оптимизировал... сделал мини, а даже точнее микроФлоат:
запись числа производится 2 кусками: в младших 2х битах само число, в трех старших - степень числа 2, на которое надо умножить.

Код:

X&=0x1F; // обрезка старших битов - в них у меня теперь другая информация хранится
Y=(X&0x03)+4;
X>>=2;
Y<<=X;

Так всего в 5 битах хранятся значения от 4 до 896, и распределение чисел гораздо удобнее для настройки скорости.

Спойлер

Ну, тоже не идеально, но уже гораздо интереснее (а ровнее тут итак не получить.)
а главное - код получился подъёмным даже для мелкой тини!

_____

Минифлоат4x4 - занимая 4 бита под число и 4 под множитель позволяет хранить в 1 байте целые числа от 0 до 507904.
Код распаковки:

Код:

#define A 4
Y=X&(~((-1)<<(A)));
X>>=A;
if (X>0) // этот приём позволяет хранить числа от 0.
    {
    Y+=(1<<(A+1)); 
    X--;
    };
Y<<=X;

Минифлоат5x3 - занимая 5 бита под число и 3 под множитель позволяет хранить в 1 байте целые числа от 0 до 4032.
Минифлоат3x5 - занимая 3 бита под число и 5 под множитель позволяет хранить в 1 байте целые числа от 0 до 16 106 127 360. (но с бОльшим шагом)

общий вид максимального хранимого числа для переменной минифлоат(AxB) при распаковке предложенным методом будет:
Y=((2^(A+1))-1)*2^((2^B)-2).

Реклама

ARV

идея занятная, но странная... неужели работа с uint16_t создает больше проблем, чем распаковка микрофлоата?

Ivanoff-iv

У меня там длииииииииинный массив, если его элементы чар, а не инт - получается знатная экономия :hunger:

Starichok51

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

Реклама

MLX90640

Да, а еще можно посмотреть информацию о различных алгоритамх сжатия, например, LZW.

Реклама

Распродажа паяльного оборудования ATTEN!
Паяльные станции, паяльники и аксессуары по самой выгодной цене.

По промокоду radiokot скидка 10%

ARV

LZW на attiny - это было бы на самом деле незабываемо! если бы было...

Ivanoff-iv

Starichok51, какраз к флоату это имеет прямое отношение (и принцип тот-же), просто я в дробную часть не залезаю, мне это незачем. Да, и шаг там как-раз не фикситованный, в начале он равен 1, а вконце, даже в применённой мной 5 битной версии шаг уже 128...
А написал я тут потому, что оказывается это всё это может быть не настолько громоздко, как принято считать...

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

Добавлено after 2 minutes:
ПС: первый график - это как было до применения метода...

Jack_A

Ivanoff-iv Поддерживаю. Я когда-то для солидного дивайса (не помигать диодами) применил 3-байтовую самопальную плавучку, написал "плавучие" функции. Не столько памяти экономии ради, для быстродействия (очень тесные временные рамки). Тестил с Сишной плавучкой - выигрыш в 2 раза. Точности хватало.
Возражение: взять камень пошустрее (и дороже, конечно) - я уже неоднократно описывал "...должна быть экономной" - ценовую политику определял владелец бизнеса.
Возражение: в твоих прогах хрен разберётся преемник, возможны трудности с модификацией - все исходники я тщательно комментировал, не-тупой - разберётся. Насчёт модификации - понадобилось суммировать много-много мелких величин, результат получался уже другого порядка. Для этой узкоспециализированной фичи (только для неё), чтоб "мелочёвка" не терялась за пределами разрядной сетки склепал нормальную 4-байтовое суммирование и соответственный буфер. За пару часов.
Конечно, это было на асме.
"Взял бы STM32."... Ээх, конец прошлого тысячелетия...

Реклама

Starichok51

Ivanoff-iv, да, на счет фиксированного шага я поспешил ляпнуть не подумавши. хотя сам прекрасно знаю, что шаг растет с увеличением показателя степени.
я эту свою ошибку понял уже после отправки сообщения, но не стал исправлять пост.

ПростоНуб

При программировании MK на Rust новички часто сталкиваются с borrow checking.
Просто так сделать Arc<Mutex<>> проблематично, так как его ведь надо инициализировать.
Проблема легко решается макросом lazy_static!
Например, в main.rs:

Код:

lazy_static! {
    pub static ref PERIPHERALS: Arc<Mutex<Peripherals>> =
        Arc::new(Mutex::new(Peripherals::take().unwrap()));

Теперь в другом файле проекта достаточно сделать так:

Код:

use crate::PERIPHERALS;
...

    let peripherals = PERIPHERALS.clone();
    let mut peripherals = peripherals.lock();

...

Аналогичный подход работает и с пинами. Например, в main.rs:

Код:

lazy_static! {
    pub static ref GPIO10_MUTEX: Arc<Mutex<PinDriver<'static, Gpio10, Output>>> = {
        let peripherals = PERIPHERALS.clone();
        let mut peripherals = peripherals.lock();
        let pin_gpio10 =
            PinDriver::output(unsafe { peripherals.pins.gpio10.clone_unchecked() }).unwrap();
        Arc::new(Mutex::new(pin_gpio10))
    };
}

Теперь в другом файле проекта:

Код:

use crate::GPIO10_MUTEX;
...

    let power_relay = GPIO10_MUTEX.clone();
    let mut power_relay = power_relay.lock();
    power_relay.set_high().unwrap();

...

И так никакой borrow checking не будет мешать.

ARV

Если б еще хоть что-то понятно было... Слова, вроде, понятные, а смысл не понятен. Видимо, слишком хитрый алгоритм :)))

ПростоНуб

ARV писал(а):

Если б еще хоть что-то понятно было...

Это не C/C++, а Rust. Вполне себе реальный конкурент для C/C++ на МК. Как обычно, у конкурента есть и преимущества, и недостатки. Но когда первым приоритетом ставится надежность кода, Rust явно выигрывает. Даже несмотря на меньшую развитость его библиотек (крейтов).
Я уже через неделю программирования на нем ESP32-C3 вынужден был стать коммитером в esp_idf_hal. Например, вот этот код viewtopic.php?f=62&t=195410 будет работать только на master esp_idf_hal, так как мой PR смержен туда после последнего релиза.

Добавлено after 12 minutes 14 seconds:
Для медианной фильтрации, обычно, расчет медианы требуется с окном 3 или 5. Заниматься сортировкой столь небольших массивов, особенно вызывая стандартную функцию сортировки - не эффективно.
Поэтому, для быстрого медианного фильтра на Rust я использую следующие функции:

Код:

use std::cmp::{max, min};

pub fn median3(a: u16, b: u16, c: u16) -> u16 {
    max(min(a, b), min(c, max(a, b)))
}

pub fn median5(v: [u16; 5]) -> u16 {
    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])),
    )
}

По сравнению с sort() этот код выигрывает в 2-2.5 раза.

smacorp

Хороший язык программирования фамилией фашистского лётчика-нарушителя не назовут.

ПростоНуб

smacorp писал(а):

Хороший язык программирования фамилией фашистского лётчика-нарушителя не назовут.

С точки зрения любого англоговорящего, даже слово "электрощит" способно вызвать резкое отторжение

А это я сфотографировал, когда был в командировке в Швейцарии:

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

ARV

Просто в теме об алгоритмах надо бы говорить о том, что имеет смысл для большинства, а не популяризировать экзотику. Про раст завели бы отдельную тему, чтобы те, кому оно в нос не упёрлось, зря не заходили...

Adrift

ARV писал(а):

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

Первые два алгоритма в этой теме были написаны на ассме для AVR, третий - на ассме для MSP430, четвертый - на асме для х51 )

ПростоНуб

ARV писал(а):

Просто в теме об алгоритмах надо бы говорить о том, что имеет смысл для большинства, а не популяризировать экзотику. Про раст завели бы отдельную тему, чтобы те, кому оно в нос не упёрлось, зря не заходили...

С какого перепугу тема про алгоритмы должна быть привязана к конкретному языку?
Если бы я вложил тут код на ассемблере Padauk или того же ESP32-C3 (RISC-V), Вы бы тоже стали возмущаться, потому что подавляющее большинство с ними не знакомо?
Я не раз переписывал на язык текущего проекта для своих нужд алгоритмы с Fortran, C#, Java, Go, Python, JS и даже такой экзотики, как R или Lisp. Какая разница на каком языке алгоритм?

ARV

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

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

Например, джаваскрипт позволяет складывать строки и числа, но можно ли это назвать универсальным?!

ПростоНуб

ARV писал(а):

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

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

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

Для медианной фильтрации, обычно, расчет медианы требуется с окном 3 или 5. Заниматься сортировкой столь небольших массивов, особенно вызывая стандартную функцию сортировки - не эффективно.
Поэтому, для быстрого медианного фильтра на Rust я использую следующие функции:

Код:

use std::cmp::{max, min};

pub fn median3(a: u16, b: u16, c: u16) -> u16 {
    max(min(a, b), min(c, max(a, b)))
}

pub fn median5(v: [u16; 5]) -> u16 {
    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])),
    )
}

По сравнению с sort() этот код выигрывает в 2-2.5 раза.

ARV писал(а):

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

Экзотика возникает в голове, если не пытаться разобраться в том, что написано. А если разобраться, то фраза

Код:

Просто так сделать Arc<Mutex<>> проблематично, так как его ведь надо инициализировать.
Проблема легко решается макросом lazy_static!

становится понятной для любого языка.
На каком бы языке в среде FreeRTOS Вы не писали, решение в ленивой инициализации мьютексов на ресурсы является довольно удачным. Мне что ли надо было расписывать это на всех языках, как здесь: https://en.wikipedia.org/wiki/Lazy_initialization

ARV писал(а):

Например, джаваскрипт позволяет складывать строки и числа, но можно ли это назвать универсальным?!

А в чем проблема? На том же ESP32 он вполне универсален https://www.espruino.com/ESP32
И если на МК преимущественная нагрузка оказывается через WebApi или WebSocket, то JS в этом случае может оказаться весьма удобен.
Или ESP32 по Вашему уже не MK?

Хочу всё же уточнить свою позицию.
С одной стороны, я вполне понимаю ARV или smacorp, так как меня самого достали некоторые токсичные представители Rust сообщества, пытающиеся агрессивной рекламой, демагогией и флеймом впихивать свой любимый Rust везде и всюду. От Linux Kernel до GUI. Ничем подобным я здесь заниматься не собираюсь.
С другой стороны, Rust позволяет почти полностью снять с программиста управление динамической памятью, причем без издержек в виде сборщика мусора. Поэтому я и считаю, что у Rust есть своя область применения. Так же, как и у других языков программирования, на которых мне приходилось что-то кодировать за последний год: С#, C, Python, Java, JS, C++, Perl,
В частности, я считаю применение Rust на MK в среде FreeRTOS вполне оправданным, так как избавляет от необходимости при отладке выискивать утечки памяти. Это относится к ESP32 и старшим STM32, располагающими сотнями килобайт оперативной памяти и мегабайтами программной..
Например, ESP32-C3 при стоимости меньше $2 позволяет поднять HTTP(S) сервер, который способен потянуть до десятка активных соединений.
Ну не знаю, может это у меня руки кривые, но на C/С++ при написании асинхронных обработчиков событий (например, запросов к HTTP серверу), я выискиванием утечек памяти занимался неоднократно. И многие мои коллеги - тоже.

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

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