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

[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]

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

[Gnida]

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

[Victor Gr.]

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

[Llama]

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

[michael]

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

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

[Victor Gr.]

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

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

[Berserker]

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

Если ширина диапазонов одинаковая, то метод округления частного подойдёт все равно.

[bazil]

тока бинарный поиск, IMHO

[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]

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

[Foxx]

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

[Victor Gr.]

Foxx, а у меня таких поисков диапазона несколько миллионов.

Aleksey Kondratenko, ОГРОМНОЕ спасибо вам за примеры кода! Я в Асме не слишком силён, но буду внимательно разбираться в представленном коде.

[imp3]

одним из самых быстрых методов является является "интерполяционный" метод. Думаю не секрет, что именно интерполяция всегда достигает наиболее лучших результатов:D. В этом методе используется супер навороченная формула, которую я сейчас попробую изобразить

d=цел.часть

(j-i)*(K-Ki)
-----------
Kj - Ki

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

[Foxx]

Aleksey Kondratenko, гм, есть пара вопросов. Я уже поотстал от гонки технологий, потому, может, вы поможете наверстать малую часть упущенного.
Все таки оптимизация. таки уж она имеет смысл для современных процессоров? Понимаю, что с позиции быстродействия - безусловно да, но с точки зрения стоимости затрат кодирования простых алгоритмов для простых систем (не берем realtime-системы, всякие слабые контроллеры и т. п. специфичные задачи)? Интересно ваше мнение.
ИМХО если уж и заниматься оптимизацией для машин семейства x86, то должы быть соблюдены и backward compatibilities, то есть импользование conditional mov-ов для те же первых пней невозможно. Хотел сказать, что в таком случае должен быть использован более "классический" набор команд. Потому как прирост быстродействия менее критичен и будет гораздо менее заметен при текущих вычислительных мощностях (и оптимизаторах кода), нежели на древних аппаратах.
Еще бы хотел спросить про предсказание переходов и поведение кэша при этом, но пока не знаю, как точно сформулировать свой вопрос.