Linux.by
https://forum.linux.by/

Алгоритм определения принадлежности числа диапазону (бы)
https://forum.linux.by/viewtopic.php?f=6&t=7508
Страница 1 из 2

Автор:  Victor Gr. [ 22 апр 2006, 01:53 ]
Заголовок сообщения:  Алгоритм определения принадлежности числа диапазону (бы)

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

Например,
Берем числа от 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 [ 22 апр 2006, 02:56 ]
Заголовок сообщения: 

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

Автор:  Gnida [ 22 апр 2006, 03:01 ]
Заголовок сообщения: 

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

Автор:  Victor Gr. [ 22 апр 2006, 11:24 ]
Заголовок сообщения: 

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

Автор:  Llama [ 22 апр 2006, 11:34 ]
Заголовок сообщения: 

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

Автор:  michael [ 23 апр 2006, 03:24 ]
Заголовок сообщения: 

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


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

Автор:  Victor Gr. [ 23 апр 2006, 16:52 ]
Заголовок сообщения: 

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

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

Автор:  Berserker [ 23 апр 2006, 21:47 ]
Заголовок сообщения: 

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


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

Автор:  bazil [ 23 апр 2006, 22:51 ]
Заголовок сообщения: 

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

Автор:  Aleksey Kondratenko [ 29 апр 2006, 02:11 ]
Заголовок сообщения: 

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

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

Вот кусок кода который демонстрирует идею в "скалярном" исполнении на скорую руку. Я проверял, 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 [ 29 апр 2006, 02:17 ]
Заголовок сообщения: 

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

Вместо:
Код:
res = (what <candidate>right) ? res : 0;

Было:
res = (what &lt; candidate-&gt;right) ? res : 0;

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

Автор:  Foxx [ 29 апр 2006, 16:55 ]
Заголовок сообщения: 

Похожий на 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 [ 29 апр 2006, 16:58 ]
Заголовок сообщения: 

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

Автор:  Aleksey Kondratenko [ 29 апр 2006, 18:10 ]
Заголовок сообщения: 

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

Автор:  Foxx [ 30 апр 2006, 11:30 ]
Заголовок сообщения: 

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

Страница 1 из 2 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/