caxapa.ru :: кто бы мог подумать, что в результате придём к скорострельности 3,5 такта на байт ?:)))

Adept (27.01.2021 20:11, просмотров: 627) ответил Tpoeшник на Си. AVR. Ищу самый быстрый во вселенной алгоритм поиска максимального числа в огромном массиве char.

кто бы мог подумать, что в результате придём к скорострельности 3,5 такта на байт ?:)))

http://caxapa.ru/1072613/

3..4 такта для блока данных 2К. в случае использования алгоритма основанного на приведении "большого пребольшого массива байт" к 256-битному результирующему массиву в котором делается финальный поиск.

3 - в наилучшем (если найдём ответ сразу при анализе выходного массива 256 байт)

4 - в наихудшем (если найдём ответ в конце анализа 256 байт результирующего массива)

...делать нужно так, как нужно. А как ненужно - делать не нужно (С) Винни-Пух :)

Ответить

- по 3 и 4 хорошо бы подключить мат. анализ и стат.анализ ну и теорию вероятности например. Искать не перебором сверху вниз или наоборот, а допустим от центра в обе стороны и каждый участок с двух сторон навстречу друг другу. klown1(557 знак., 27.01.2021 21:34)
  - п.с. klown1(369 знак., 27.01.2021 21:39)
    - вы не поняли, ~~это другое~~ там основной массив обрабатывается методом "приведения к 256", а уже на результирующем маленьком массиве перебираем сверху вниз, пока не встретится значащий, а не нулевой байт со значением максимума. Все ухищрённые методы анализа и перебора будут в разы проигрывать прямому перебору при обработке такого маленького массива в 256 байт - Adept(27.01.2021 21:50)
      - Честно говоря, совсем не очевидно что "приведение к 256" чем-то лучше прямого поиска - LightElf(28.01.2021 20:29)
        
        гораздо быстрее (3 такта на байт данных) - Adept(28.01.2021 21:49)
        
        Я, кагбэ, ~~не знал~~ забыл ассемблер AVR, но что-то больно удивительно, что пара чтение/запись выполняется быстрее, чем пара чтение/сравнение. Ну и специально подготовленные условия (массив выровнен на 256 байт) - читерство чистой воды :) - LightElf(29.01.2021 00:31)
        
        дело в том, что не пара чтение/сравнение, а цикл: чтение/сравнение/запись/переход по условию а в "приведении к 256" чтение/запись включает в себя "скрытое сравнение", т.к. потом, в результирующем массиве 256байт Adept(1047 знак., 29.01.2021 01:16, ссылка)
        
        Просто я XMEGA не застал, а во времена оны инструкция LightElf(204 знак., 29.01.2021 20:56)
        
        да, всё так. st - один такт, ld - два, всего три такта на операцию чтения-записи (а их в цикле 256 друг за дружкой, потом проверка условия выхода и опять в цикл. По выходу - поиск ненулевого байта в результирующем массиве 256 байт. в итоге в среднем 3,5 такта на байт при блоке данных 2к Adept(183 знак., 30.01.2021 00:54)
        
        Ну ещё не забудьте, что массив 256 байт надо обнулить перед использованием, а цикл со сравнением можно и развернуть. - LightElf(30.01.2021 09:26)
        
        После использования, если его обнулять на этапе INIT. - ILYAUL(30.01.2021 09:44)
        
        А если массив 0xffff значений и встретим на первой итерации 0xff? Получается что тогда такой алгоритм быстрее? Tpoeшник(64 знак., 29.01.2021 13:10)
        
        не занимайтесь шулерством :) по условию задачи - "поиск максимального числа в огромном массиве char" :))) Adept(348 знак., 29.01.2021 13:40 - 13:43)
        
        Повторяю: меня абсолютно не интересует ничего кроме красоты языка программирования. В данном случае Си. Но не только это. Сами алгоритмы, мысли, идеи доставляют. Если в вашем случае нет проверки на 0xff, то "мой" алгоритм может оказаться в тысячи раз быстрее. Так не пойдет. - Tpoeшник(29.01.2021 13:42)
        
        описывайте корректно условие задачи и и будет Вам Щастье :)) ну и допустим разницу в быстродействии Вы завысили в несколько десятков раз :) не не суть - не нравится шагами по 256 байт - вариант с побайтовым сравнением и 9 тактов на байт - (но таки как раз предлагаемый алгоритм с приведением к 256 красив и эффективен именно на больших массивах (в соответствии с условием задачи) Adept(203 знак., 29.01.2021 13:49)
        
        Почему завысил? Разница в скорости может достигнуть и миллионов раз. Я на первой итерации выйду и распечатаю максимальное, а вы? К условию задачи мне нечего добавить. Ну разве что напомнить что речь шла о Си. Хотя я ничего против АСМ не имею, но код писать уже на нем не буду никогда вероятно. - Tpoeшник(29.01.2021 13:53)
        
        ассемблер незаменим в эксклюзивных задачах достижения максимальной эффективности и компактности, но такие, к счастью , встречаются крайне редко, но они бывают, и камень "пожирнее" не всегда есть возможность выбрать (вот, к примеру у меня в одном проекте ATtiny10 стоит и другой не поставить по габаритам/стоимости :)) Adept(776 знак., 30.01.2021 01:07)
        
        Открой секрет получения "огромного массива" авром??? все остальное онанизм!!! - Aleksey_75(29.01.2021 20:59)
        
        С внешнего параллельного АЦП, на пример.:-)) - Boвa(30.01.2021 09:56)
        
        Ну с этим проще. В таком случае сразу формируете массив 256 байт. - ILYAUL(30.01.2021 10:58)
        
        Это при условии , что он 0хFF первый (повезло) , а если последний? И как уже было сказано , зачем городить огород с массивом 0xFFFF, если для Вашей задачи (найти максимум) при условии что вы же и получаете данные , вполне хватит 256 байт. Хоть на Си , хоть на asm. При этом свой 0xFF, Вы найдете с первого шага . - ILYAUL(29.01.2021 17:12)
        
        Всё так. Совместить проверку на 255 с разворачиванием цикла. И волки сыты, и овцы целы. - SciFi(29.01.2021 13:48)
      - нуда, хороший вариант. А как насчет условия по уникальности максимального значения, по условиям задачи оно единственное и повторяться не может, так ? - klown1(27.01.2021 22:01)
        
        Да пусть оно хоть 1000 раз будет максимальное, надо найти его значение, а не количество - ILYAUL(27.01.2021 22:46)
- Вот. А даже старая C66x DSP сделает 8 байт за такт (инструкция MAXU4 на юнитах L1 и L2) - lloyd(27.01.2021 20:35)

Микроконтроллеры AVR