caxapa.ru :: Если ваш массив не упорядочен, не имеет еще каких-то особенностей, а совершенно случайный, то ни чего лучше не найдете. Возможна только оптимизация самого процесса перебора, но проще доверить это компилятору.

AlexBi (26.01.2021 19:07, просмотров: 399) ответил Tpoeшник на Си. AVR. Ищу самый быстрый во вселенной алгоритм поиска максимального числа в огромном массиве char.

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

Ответить

- Массив совершенно случайный. Особенностей нет никаких. - Tpoeшник(26.01.2021 19:09)
  - Молитва о чуде говорят помогает в таких случаях. - Codavr(26.01.2021 19:13)
  - Тады без вариантов. Для N чисел будет (N-1) операций сравнения - LightElf(26.01.2021 19:12)
    - Вдогонку еще один вопрос. Возможно немного глупый: если массив состоит из 1млр значений и записан на внешнюю флешку, карту и тд. АВР может посоревноваться с ПК в скорости поиска максимального? - Tpoeшник(26.01.2021 19:14)
      - Разве что найти исключительно тормозную флешку. Даже очень плохая uSD легко отдает 10МБ/с на чтение. AVR столько просто не прожует, а писюк - вполне - LightElf(26.01.2021 19:39)
        
        отдать то может она и отдаст, вот только кто их примет! даж с 16к буфером посчитате накладные расходы! у меня получается правда с STM, с буфером 8к spi флеш с обработкой получается порядка 800К в сек! - Aleksey_75(27.01.2021 01:13)
        
        То есть: если я буду тащить из файла данные и сравнивать с максимальным, то получу 10МБ/с? Можно ведь написать код например на Си и определить время за сколько код найдет максимальное значение. И получится что за 1 сек ПК 10М раз выполнит if с байтом очередным!? Или 10МБ/с это переброс по шине в ОЗУ?! - Tpoeшник(26.01.2021 19:53)
        
        Типа того. Но это должна быть реально плохая/древняя флешка или очень древний/унылый контроллер SD. Скорее и карта и контроллер умеют в 50МГц и выдадут порядка 20МБ/с, что для писюка - несущественная мелочь. Для оценки дури современных писюков: Core i7-9700K одним ядром сжимает данные алгоритмом LZ4 (а это нифига не максимум найти) со скоростью 780МБ/с. - LightElf(29.01.2021 21:27)
        
        при условии уже наличия массива данных в памяти, быстрый ~~беспонтовый~~ линейный код на иксмеге@32МГц не дотягивает и до 5МБайт/сек, увы:(( Более красивый и хоть как-то полезный циклический - при тех же условиях - чуть меньше 3,5Мбайт/сек. Однако в свете последних достижений :)) удалось достичь почти 8,8МБайт/сек :) - Adept(27.01.2021 18:35, ссылка, ссылка)
        
        LightElf фсе врет, если винда в это время начнет обновляться, то в АВРку можно отчасового кварца тактировать, и то она быстрее успеет :) - Codavr(27.01.2021 00:05)
        
        В условиях задачи винды не было :) - LightElf(27.01.2021 05:10)
      - Нет. У ПК шина быстрее, регистры длиннее, куча ядер и есть SIMD. Ничего из этого нет у AVR - lloyd(26.01.2021 19:16)
        
        Да, понимаю. Но при поиске максимального тормозить ведь носитель будет, не ядра и регистры. Ну типа вычитать 100 байт с дикового носителя ПК и вычитать 100 байт АВРкой с флешки резвой. Не сопоставимо!? - Tpoeшник(26.01.2021 19:19)
        
        А что, в AVR уже положили PCIe? - lloyd(26.01.2021 19:20)
        
        Ну ок. Прямо вот реально если записать на диск ПК один млр. значений. Потом запустить программу которая потянет с винта данные и начнет их перебирать. Будет много быстрее чем АВР с флешки (или другого максимально быстрого носителя для архитектуры) то же самое сделает? - Tpoeшник(26.01.2021 19:24)
        
        На PC можно распараллелить работу по ядрам, видеокарту задействовать - Ruslan(26.01.2021 19:27)
        
        Да я в некотором смысле понимаю. Я о том что скорость физ.доступа к данным на ПЗУ наверное не сильно то отличается. Выигрыш у ПК в том что он втягивает в ОЗУ все, в кеши всяки там и уже работает с данными в поле быстрого доступа к инфе. Но если последовательная цепочка и алгоритм сканит на лету поток, то АВРка не сильно хуже может быть. Хотя звучит конечно странно) - Tpoeшник(26.01.2021 19:31)
        
        1 млрд байт это меньше гигабайта. Массив можно загрузить в память видеокарты и распараллелить поиск по ядрам. Авр такое и не снилось :) Ну можно попробовать собрать кластер на авр :) - Ruslan(26.01.2021 19:32)
        
        Стоп. Я о ПЗУ говорил. В память видео карты это о другом. Вставляете в ПК USB флешку, запускаете код который ищет максимум в файле бинарном например. Вместо флешки диск ,SSD может быть - Tpoeшник(26.01.2021 19:35)
        
        "Слушай, ты за меня или за медведя?" - Ruslan(26.01.2021 19:39)
        
        У моего бюджетного SSD максимальная скорость чтения - 3 гигабайта в секунду. Чтобы AVR успевала обрабатывать такие данные ей нужно работать на частоте 3ГГц - lloyd(26.01.2021 19:38)

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