ВходНаше всё Теги codebook 无线电组件 Поиск Опросы Закон Пятница
29 марта
1072338 Топик полностью
Adept (26.01.2021 21:14 - 27.01.2021 00:50, просмотров: 816) ответил Tpoeшник на Си. AVR. Ищу самый быстрый во вселенной алгоритм поиска максимального числа в огромном массиве char.
там у вас всё сожрут IO-процедуры c носителями информации, сам алгоритм - это 5 команд на ассемблере :)) 

так что выбирайте оптимизируйте подсистему хранения данных и доступа к ним

а "огромный массив" это что ?? Кому и кобыла невеста 1K огромный, а некоторым и 100Гиг - так себе :))

Основные накладные затраты - адресация и жонглирование адресными регистрами. Если не шибко жирное что, то можно попробовать достучаться ко внешней памяти через DMA. Но вообще всё тут сильно аппаратно-зависимо и в первую голову важен носитель информации, какой он.


а так-то задачка плёвая ведь. Не ?:))


грузим как угодно в память, хоть через DMA, хоть "врукопашную" побайтово (насколько хватает памяти) кусок данных, и в "в путь"

(можно и "на лету" поточно-побайтово сравнивать, есличо)

более быстрое сейчас для АВР-а чего-то не придумывается (возможно через DMA можно что-то замутить быстрее, в иксмеге, к примеру, но не уверен (даж башку ломать не буду сейчас :))


// 9 тактов на байт (3,4МБайт/сек на XMEGA@32MHz)
WorkCycle:
	ld	TMP2,X+		;читаем очередной байт массива
	cp	TMP,TMP2	;если не больше максимума
	brcc	nextCycle	;то следующий цикл чтения/сравнения
	mov	TMP,TMP2	;  иначе сохраняем новый максимум
nextCycle:
//	cpi	TMP,0x0ff	;опционально сравниваем с максимально возможным
//	breq	BREAK_		;досрочный выход, если уже максимально возможное
	cp	XL,YL		;сравнение с границей массива (дошли ли до конца)
	cpc	XH,YH		;Если не дошли до конца, 
	brcs	WorkCycle	;  то продолжаем цикл чтения/сравнения
BREAK_:
	STOP

//TMP, TMP2 - есс-но регистры, по выходу из процедуры - в TMP - максимум :))
//в Y - верхняя адресная граница массива ОЗУ который шерстим (в Х в начале есс-но нужно загрузить адрес начала массива).
А если закидывать данные блоками по 256 байт и отказаться от 16-битной адресации, то ещё можно немного сэкономить, выкинув 16-битное (cpc XH,YH) сравнение из цикла. а если уж нужно сферического коня в вакууме быстрый, но малополезный алгоритм, то можно с прибитыми гвоздями фиксированными адресами, вообще всё вытянуть в линейную процедуру, размер будет охрененный, зато быстрота линейного кода :))


максимально быстрая, но малополезная (6,3 такта на байт, т.е. 4,84МБай/с на XMEGA@32MHz)
//железобетонный тупой линейный код, для примера на 10 байт:))
#define	StartAddress	0x2500
	;
	lds	TMP,StartAddress
	;
	lds	TMP2,StartAddress+1
	cp	TMP,TMP2
	brcc	next1
	mov	TMP,TMP2
next1:	//В TMP максимум на текущий момент
	lds	TMP2,StartAddress+2
	cp	TMP,TMP2
	brcc	next2
	mov	TMP,TMP2
next2:	//В TMP максимум на текущий момент
	lds	TMP2,StartAddress+3
	cp	TMP,TMP2
	brcc	next3
	mov	TMP,TMP2
next3:	//В TMP максимум на текущий момент
	lds	TMP2,StartAddress+4
	cp	TMP,TMP2
	brcc	next4
	mov	TMP,TMP2
next4:	//В TMP максимум на текущий момент
	lds	TMP2,StartAddress+5
	cp	TMP,TMP2
	brcc	next5
	mov	TMP,TMP2
next5:	//В TMP максимум на текущий момент
	lds	TMP2,StartAddress+6
	cp	TMP,TMP2
	brcc	next6
	mov	TMP,TMP2
next6:	//В TMP максимум на текущий момент
	lds	TMP2,StartAddress+7
	cp	TMP,TMP2
	brcc	next7
	mov	TMP,TMP2
next7:	//В TMP максимум на текущий момент
	lds	TMP2,StartAddress+8
	cp	TMP,TMP2
	brcc	next8
	mov	TMP,TMP2
next8:	//В TMP максимум на текущий момент
	lds	TMP2,StartAddress+9
	cp	TMP,TMP2
	brcc	next9
	mov	TMP,TMP2
next9:	//В TMP максимум на текущий момент
	lds	TMP2,StartAddress+10
	cp	TMP,TMP2
	brcc	next10
	mov	TMP,TMP2
next10:	//В TMP максимум на текущий момент
	;
	STOP
...делать нужно так, как нужно. А как ненужно - делать не нужно (С) Винни-Пух :)