Войти
ФлеймФорумПрограммирование

[C++] Быстрая проверка вхождения числа в интервал на CPU

Страницы: 1 2 3 4 5 6 Следующая »
#0
23:41, 14 мар. 2019

Проверка на CPU. Речь о беззнаковых целых числах в 4 байта.

unsigned int value;
unsigned int lowerLim;
unsigned int upperLim;

//нужна такая проверка
if(value >= lowerLim && value <= upperLim)
{
}
Есть какой-то грязный хак для ускоренной проверки? Битовая маска тут не поможет...  Приветствуются любые способы, SSE, ASM и пр...


#1
(Правка: 23:56) 23:55, 14 мар. 2019

Думаешь есть какое-то хитрое сравнение на больше-меньше, о котором компилятор не знает, а тут мы такие врываемся с секретным асмом?

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

#2
0:05, 15 мар. 2019

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

#3
(Правка: 0:37) 0:30, 15 мар. 2019

™­•-=MASTER=-•™

SSE4.1, AVX2, AVX-512: min(upper, x) == max(lower, x)

Правка: исправил версию SSE.

#4
0:33, 15 мар. 2019

™­•-=MASTER=-•™
> unsigned int value;
> unsigned int lowerLim;
> unsigned int upperLim;

> if(value >= lowerLim && value <= upperLim)
> {
> }

if(value-lowerLim<=upperLim-lowerLim)
если что это шутка. хоть и работающая на некоторых диапазонах.

#5
(Правка: 0:46) 0:41, 15 мар. 2019

™­•-=MASTER=-•™
сколько чисел? скольким диапазонам нужно проверить принадлежность для одного числа? максимальная distance(lower, upper)? нужно ли сортировать lower и upper? может еще какие особенности задачи? например все числа нужно проверять на проверку одному диапазону? или все диапазоны одному числу? или числа или диапазоны отсортированы. не перекрываются диапазоны?

#6
0:44, 15 мар. 2019
if(value-lowerLim<=upperLim-lowerLim) {/*...*/}
#7
0:48, 15 мар. 2019

FordPerfect
мне вариант второго призрака больше нравится. это вроде относительно бессмысленная тема

#8
1:01, 15 мар. 2019

Если upperLim и lowerLim - константы, компилятор сам такое делает.
Если переменные - помогает (для нескольких тестов).

#9
1:06, 15 мар. 2019

https://godbolt.org/z/wIdp_P

#10
(Правка: 1:17) 1:16, 15 мар. 2019

Версия с разностью работает для всех интервалов где lowerLim<=upperLim (иначе надо явно проверять).
Версия с min(upper, x) == max(lower, x) - для совсем всех.

#11
1:27, 15 мар. 2019

https://fgiesen.wordpress.com/2015/09/24/intervals-in-modular-arithmetic/

#12
6:04, 15 мар. 2019

FordPerfect
> if(value-lowerLim<=upperLim-lowerLim) {/*...*/}

Это же просто нерабочий вариант. Эквивалентно value <= upperLim , нижний предел не проверяется вообще.

#13
6:15, 15 мар. 2019

™­•-=MASTER=-•™
> //нужна такая проверка
> if(value >= lowerLim && value <= upperLim)

Наверное тут стоит применять старинный подход - "разделяй и властвуй".
Надо просто разбить задачу на подзадачи.
Здесь по первому размышлению всё прекрасно бьётся на 4 подзадачи:
1. найти как быстро выполнить сравнение больше-или-равно
2. найти как быстро выполнить сравнение меньше-или-равно
3. найти какой нибудь скоростной хак для операции &&
4. ускорить выполнение оператора if
В принципе решение даже одной из этих подзадач уже должно дать ускорение.

#14
6:16, 15 мар. 2019

Ogra
> Это же просто нерабочий вариант. Эквивалентно value <= upperLim , нижний предел
> не проверяется вообще.
А вот и нет, если value<lowerLim и модуль разницы невелик, то Unsigned(value-lowerLim) близко к  max(Unsigned) - должна сработать проверка по верхнему пределу.

Страницы: 1 2 3 4 5 6 Следующая »
ФлеймФорумПрограммирование