Алгоритм определения принадлежности числа диапазону (бы)

Все о программировании под *nix
Аватара пользователя
Victor Gr.
Неотъемлемая часть форума
Сообщения: 891
Зарегистрирован: 13 авг 2004, 15:39
Откуда: Минск
Контактная информация:

Алгоритм определения принадлежности числа диапазону (бы)

Сообщение Victor Gr. »

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

Например,
Берем числа от 0 до 99. Делим на 10 диапазонов по 10 чисел.

1: 0-9
2: 10-19
3: 20-29
4: 30-39
5: 40-49
6: 50-59
7: 60-69
8: 70-79
9: 80-89
10: 90-99

И набор случайных чисел: 1, 25, 94, 18, 21, 33.

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

Но сравнение и условия на современных процессорах - вещь очень неэффективная.

А есть ли способ проще? (возможно на ассемблере?, какими-нибудь битовыми масками)? Поскольку, желательно это как можно ускорить.

Спасибо!

Gnida
Неотъемлемая часть форума
Сообщения: 346
Зарегистрирован: 04 апр 2004, 22:38

Сообщение Gnida »

в первам классе исчо помню учили.
Сматри числа по десяткам
С опытом ошибки не изчезают , а умнеют

Gnida
Неотъемлемая часть форума
Сообщения: 346
Зарегистрирован: 04 апр 2004, 22:38

Сообщение Gnida »

тоесть делаете результат деления int и делете число на 10 палучаете номер вашева диапазона/дисятка
--
я сам сабой даволен как я просто придумал :oops:
С опытом ошибки не изчезают , а умнеют

Аватара пользователя
Victor Gr.
Неотъемлемая часть форума
Сообщения: 891
Зарегистрирован: 13 авг 2004, 15:39
Откуда: Минск
Контактная информация:

Сообщение Victor Gr. »

Вопрос в том, что это - не единственные возможные диапазоны.
Их может быть 256 штук, а чисел 0 - 4294967296.

Аватара пользователя
Llama
Неотъемлемая часть форума
Сообщения: 9749
Зарегистрирован: 06 фев 2002, 11:40
Откуда: Менск

Сообщение Llama »

Victor Gr., уменьшить количество сравнений можно представвив деиапазоны в чиде какого-нить дерева...
Опыт растет прямо пропорционально выведенному из строя оборудованию

michael
Неотъемлемая часть форума
Сообщения: 434
Зарегистрирован: 12 апр 2004, 11:00
Откуда: г. Владивосток
Контактная информация:

Сообщение michael »

Victor Gr., уменьшить количество сравнений можно представвив деиапазоны в чиде какого-нить дерева...
То есть сперва делишь весь интервал на два, определяешь в каком из этих интевалов твое число, затем делишь этот интервал снова на два и т. д. пока не дойдешь до требуемого диапазона.
Пример: числа от 0 до 100 разбить на четыре интервала: 0-25, 26-50, 51-75, 76-100. Достаточно двух сравнений: n>50 и, в зависимости от предыдущего результата, n>25 или n>75.

Аватара пользователя
Victor Gr.
Неотъемлемая часть форума
Сообщения: 891
Зарегистрирован: 13 авг 2004, 15:39
Откуда: Минск
Контактная информация:

Сообщение Victor Gr. »

Llama, michael,
да, так и думал. Вообще, этим как правило занимается компилятор... Представляет линейный switch case в бинарное дерево.

Ладно, спасибо, буду делать так )

Berserker
Неотъемлемая часть форума
Сообщения: 279
Зарегистрирован: 23 апр 2005, 21:13
Откуда: minsk

Сообщение Berserker »

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

bazil
Неотъемлемая часть форума
Сообщения: 879
Зарегистрирован: 18 дек 2003, 23:56

Сообщение bazil »

тока бинарный поиск, IMHO
I did a 'zcat /vmlinuz > /dev/audio' and I think I heard God...

Aleksey Kondratenko
Неотъемлемая часть форума
Сообщения: 250
Зарегистрирован: 12 авг 2003, 03:55
Контактная информация:

Сообщение Aleksey Kondratenko »

Интересный вопрос. Возможно, первый интересный вопрос в этом разделе (по моему не скромному мнению).

Действительно сделать поиск в небольшого размера множестве диапазонов можно линейно. Т.е. без условных переходов о которых ты правильно сказал, что они в общем случае дорогие.

Вот кусок кода который демонстрирует идею в "скалярном" исполнении на скорую руку. Я проверял, gcc действительно генерирует линейный код.
Kомпилировать рекомендую с "gcc -O3 -march=i686 -S -fverbose-asm".
-march в данном случае необходим т.к. пользуем инструкции семейства cmov, которые появились в x86-ых начиная с P6.

Код: Выделить всё


struct range {
	unsigned left,right;
};

static inline
unsigned cmp1(unsigned what, struct range *candidate, unsigned res, unsigned where)
{
	res = (what >= candidate->left) ? res : 0;
	res = (what <candidate>right) ? res : 0;
	return where | res;
}

static inline
unsigned cmp4(unsigned what, struct range *candidates, unsigned res, unsigned where)
{
	where = cmp1(what, candidates, res, where);
	where = cmp1(what, candidates+1, res<<1, where);
	where = cmp1(what, candidates+2, res<<2, where);
	where = cmp1(what, candidates+3, res<<3, where);
	return where;
}

static inline
unsigned cmp16(unsigned what, struct range *candidates, unsigned res, unsigned where)
{
	where = cmp4(what, candidates, res, where);
	where = cmp4(what, candidates+4, res<<4, where);
	where = cmp4(what, candidates+8, res<<8, where);
	where = cmp4(what, candidates+12, res<<12, where);
	return where;
}

/**
 * returns index of first range or -1 if all candidate ranges failed
 */
int cmp32(unsigned what, struct range *candidates)
{
	unsigned t;
	t = cmp16(what, candidates, 0x00000001, 0);
	t = cmp16(what, candidates+16, 0x0001000, t);
	return __builtin_ffs(t)-1;
}
Идея в данном случае состоит в использовании conditional move и обозначении попаданий битиками с последующим обнаружением первого "выставленного" битика инструкцией bsf.

Если этот код векторизовать (например, через MMX'ер), то может получиться очень не плохо.

С этим подходом, правда, нужно соблюдать осторожность. Т.к. в не зависимости от места попадания всегда будет исполняться весь поток инструкций. Один промах предсказания ветвлений может быть намного дешевле, чем выполнение пары десятков быстрых, но лишних инструкций.
Выйгрышность будет зависить от размера множества, реальных данных и компилятора (или человека в этом качестве). Последнее важно, т.к. этот десяток быстрых инструкций в зависимости от удачности раскладывания на конвейеры и исполнительные блоки может выполняться в разы быстрей или медленней (а это очень "эзотерическая" тема, оссобенно в области x86). Впрочем, при векторизации эти факторы слабеют, т.к. инструкций становится меньше.

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

При подборе размера "куска" IMO следует начинать с размера cache-line. Т.е. так чтобы кусок попадал в одну строчку кеша.

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

Aleksey Kondratenko
Неотъемлемая часть форума
Сообщения: 250
Зарегистрирован: 12 авг 2003, 03:55
Контактная информация:

Сообщение Aleksey Kondratenko »

Черт, код похерило слегка.

Вместо:

Код: Выделить всё

res = (what <candidate>right) ? res : 0;
Было:
res = (what < candidate->right) ? res : 0;

Как это правильно "впихнуть" в этот форум я не знаю.

Foxx
Неотъемлемая часть форума
Сообщения: 435
Зарегистрирован: 03 апр 2004, 17:05
Контактная информация:

Сообщение Foxx »

Похожий на cmp вариант. Или я немного не понял условия, или вот так можно заменить сравнение вычитанием:
myrangesample.asm

Код: Выделить всё

SECTION .data
strfmt	db '%d is in range (%d,%d]? %s',0x0a, 0
stryes  db "YES", 0
strno   db "NO", 0

SECTION .text		

extern printf

%macro stdcall 0
	push	ebp
	mov		ebp, esp
%endmacro

global subcmp
;;/*eax - num2compare, ebx - lorange, ecx - hirange */
subcmp: stdcall	
	push 	ebx
 	sub		ebx, eax
 	jnc		m1
	mov		edx, ecx
 	sub		ecx, eax
 	mov		ecx, edx
 	jc		m1
 	mov		edx, 1
lv:
	pop		ebx
	leave
 	ret
 m1:
 	xor		edx, edx
 	jmp 	lv

printcmpres: stdcall 
	cmp 	edx, 0
 	jne  	m_true
 	push 	dword strno
 	jmp	 	m_prn
 m_true:
 	push 	dword stryes
 m_prn:
 	push 	dword ecx
 	push 	dword ebx
 	push 	dword eax
 	push 	dword strfmt
 	call 	printf
	leave
	ret

%macro evaltest 3
	mov		eax, %1
	mov		ebx, %2
	mov		ecx, %3
	call 	subcmp
	call 	printcmpres
%endmacro


global main		
main: stdcall

	evaltest 25, 24, 25
	evaltest 25, 25, 26
	evaltest 25, 0, 1024
	xor		ebx,ebx
	mov		eax,1	
	int		0x80	
собирать "nasm -felf myrangesample.asm && gcc -o range myrangesample.o"
пардон, так как писалось быстро, с отрицательными интервальными выражениями не работает.
или все хуже чем я думал?

Foxx
Неотъемлемая часть форума
Сообщения: 435
Зарегистрирован: 03 апр 2004, 17:05
Контактная информация:

Сообщение Foxx »

т. е. subcmp это всего лишь пример, который надо полагать можно оптимизировать. просто cmp как было заявлено эта функция не юзает.

Aleksey Kondratenko
Неотъемлемая часть форума
Сообщения: 250
Зарегистрирован: 12 авг 2003, 03:55
Контактная информация:

Сообщение Aleksey Kondratenko »

Сравнение и вычитание выполняются одинаково и очень быстро. Задержки соответсвующих инструкций - 1 такт. Проблема не в сравнениях, а в сопуствующий им условных переходах. В коде с вычитанием это инструкция "jc". Работает этот код так же быстро (или медленно), как и код со сравнениями.

Foxx
Неотъемлемая часть форума
Сообщения: 435
Зарегистрирован: 03 апр 2004, 17:05
Контактная информация:

Сообщение Foxx »

если честно, я вообще вижу мало смысла в опупенной оптимизации кода на современных машинах

Ответить