Статьи Галерея Форум Чат Файлы HowTo Ссылки Поиск
Текущее время: 17 июн 2019, 12:57




Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.
Автор Сообщение
СообщениеДобавлено: 22 апр 2006, 01:53 
Неотъемлемая часть форума
Аватара пользователя

У нас с: 13.08.2004
Сообщения: 891
Откуда: Минск
Интересно, а если ли способы, определить к какому диапазону принадлежит число, не используя сравненений (или сократив их до минимума?).

Например,
Берем числа от 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.

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

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

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

Спасибо!


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 22 апр 2006, 02:56 
Неотъемлемая часть форума

У нас с: 04.04.2004
Сообщения: 346
в первам классе исчо помню учили.
Сматри числа по десяткам

_________________
С опытом ошибки не изчезают , а умнеют


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 22 апр 2006, 03:01 
Неотъемлемая часть форума

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

_________________
С опытом ошибки не изчезают , а умнеют


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 22 апр 2006, 11:24 
Неотъемлемая часть форума
Аватара пользователя

У нас с: 13.08.2004
Сообщения: 891
Откуда: Минск
Вопрос в том, что это - не единственные возможные диапазоны.
Их может быть 256 штук, а чисел 0 - 4294967296.


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 22 апр 2006, 11:34 
Неотъемлемая часть форума
Аватара пользователя

У нас с: 06.02.2002
Сообщения: 9760
Откуда: Менск
Victor Gr., уменьшить количество сравнений можно представвив деиапазоны в чиде какого-нить дерева...

_________________
Опыт растет прямо пропорционально выведенному из строя оборудованию


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 23 апр 2006, 03:24 
Неотъемлемая часть форума

У нас с: 12.04.2004
Сообщения: 435
Откуда: г. Владивосток
Цитата:
Victor Gr., уменьшить количество сравнений можно представвив деиапазоны в чиде какого-нить дерева...


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


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 23 апр 2006, 16:52 
Неотъемлемая часть форума
Аватара пользователя

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

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

_________________
https://grinchik.com/


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 23 апр 2006, 21:47 
Неотъемлемая часть форума

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


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


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 23 апр 2006, 22:51 
Неотъемлемая часть форума

У нас с: 18.12.2003
Сообщения: 880
тока бинарный поиск, IMHO

_________________
I did a 'zcat /vmlinuz > /dev/audio' and I think I heard God...


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 29 апр 2006, 02:11 
Неотъемлемая часть форума

У нас с: 12.08.2003
Сообщения: 250
Интересный вопрос. Возможно, первый интересный вопрос в этом разделе (по моему не скромному мнению).

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

Вот кусок кода который демонстрирует идею в "скалярном" исполнении на скорую руку. Я проверял, 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. Т.е. так чтобы кусок попадал в одну строчку кеша.

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


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 29 апр 2006, 02:17 
Неотъемлемая часть форума

У нас с: 12.08.2003
Сообщения: 250
Черт, код похерило слегка.

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

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

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


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 29 апр 2006, 16:55 
Неотъемлемая часть форума

У нас с: 03.04.2004
Сообщения: 436
Похожий на 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"
пардон, так как писалось быстро, с отрицательными интервальными выражениями не работает.
или все хуже чем я думал?


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 29 апр 2006, 16:58 
Неотъемлемая часть форума

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


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 29 апр 2006, 18:10 
Неотъемлемая часть форума

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


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: 30 апр 2006, 11:30 
Неотъемлемая часть форума

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


Вернуться к началу
 Не в сети Профиль  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
[ All resources are available under GNU GPL ] [ Support ] [ Hosted by DataHata | MyCloud.by ] [ Powered by phpBB® Forum Software © phpBB Group ]

LVEE Winter LVEE Rambler's Top100