caxapa.ru :: Честно говоря, совсем не очевидно что "приведение к 256" чем-то лучше прямого поиска

LightElf (28.01.2021 20:29, просмотров: 662) ответил Adept на вы не поняли, ~~это другое~~ там основной массив обрабатывается методом "приведения к 256", а уже на результирующем маленьком массиве перебираем сверху вниз, пока не встретится значащий, а не нулевой байт со значением максимума. Все ухищрённые методы анализа и перебора будут в разы проигрывать прямому перебору при обработке такого маленького массива в 256 байт

Честно говоря, совсем не очевидно что "приведение к 256" чем-то лучше прямого поиска

Не надо делать мне как лучше, оставьте мне как хорошо

Ответить

- гораздо быстрее (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)

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