Добрый день. По сути вопрос в следующем, есть алгоритм: if(x >= a && x <= b) then { something.... } т.е. проверка принадлежности числа x диапазону (a - b). Существует ли оптимально быстрая реализация этого алгоритма ?
для целых чисел в диапазоне a <= x < b if long((x-a)^(x-b)) < 0 then ... //< 0 - проверка знакового бита js
leo ^ -возведение в степень? Или это растягивается в цепочку Код (Text): mov eax,X mov ebx,X sub eax,a sub ebx,b xor eax,ebx js label
Э-э, как тебе сказать. При раздельной проверке используется два условных перехода, а при проверке несовпадения знака разностей - только один, т.к. вместо первого перехода используется XOR. Если процессор угадывает ("предсказывает") первый переход (taken\not-taken), то время выполнения будет примерно одинаковым (~2-3 такта). А если не угадывает, то возникат штраф на сброс конвеера ~10-30 тиков в зависимости от процессора
loe, если у вас есть минутка взгляните на статью http://smallcode.weblogs.us/2006/03/31/checking-if-a-point-belongs-to-the-interval/ в ней предлагается некое решение вопроса оптимизации проверки принадлежности числа к диапазону, какие у вас мысли по этому поводу ? ваше решение будет работать быстрее чем предложенное в статье и для всех типов процессоров ?
leo Не прикалываюсь, просто очень давно прошу администрацию, что бы ввели теги и чтобы не было разночтений. Хотя приспособился вводить квадраты и кубы X² (X & # 178 X³ (X & # 179
Yashin_Sergey Во-первых, в статье сравнение производится не с a и b, а c a и с=b-a, поэтому тут играет роль вычисляем ли мы разность b-a заранее или же непосредственно при сравнении. Во-вторых, оба варианта укладываются в 2-3 тика и поэтому для ловли блох в 1 тик нужно учитывать конкретную реализацию на асме или на HLL с учетом "окружения" (находятся ли числа в памяти или в регистрах, возможность распараллеливания с предыдущими инструкциями и т.д. и т.п.). Поэтому нужно либо рассматривать конкретную реализацию, либо проще\лучше "забить" на возможную разницу в 1 тик и использовать любой из вариантов по вкусу - в любом случае это будет в среднем заметно быстрее, чем вариант с двумя переходами или setcc\cmovcc PS: при ловле блох нужно иметь в виду, что современные процессоры 1) разбивают сложные инструкции на микрооперации (мопы), например sub eax,[a] разбивается на mov tmp,[a] и sub eax,tmp, где tmp - временный регистр процессора 2) могут выполнять несколько независимых мопов параллельно (в среднем 3, в пике до 6-9) Поэтому бОльшее кол-во простых инструкций могут выполняться с той же или даже более высокой скоростью, чем меньшее кол-во сложных
Yashin_Sergey Я сам использую вариант с XOR-ом, т.к. он легко расширяется на проверку попадания точки в прямоугольник или куб PS: Кстати оба варианта как-то "давным давно" здесь обсуждались и разницы в тиках выявлено не было (см.пост #16). (Эх, как молоды мы были и чушь прекрасную несли )
Еще помнится TheSvin-а более интересовала минимизация размера и "изящество" кода, нежели скорость "любой ценой"
посложнее, с нечёткой принадлежностью (a - eps)<= x <(b + eps), и двумя результатами: 1. принадлежит/не принадлежит диапазону; 2. нечётко принадлежит/не принадлежит диапазону.
UbIvItS //offtop Я не о возрасте, а об "ошибках трудных", "вопросах наивных", "азарте юном" и "спорах горячих"
