Самый быстрый способ проверки условия l + 1 <r для int l, r в Java

Question

Какой самый быстрый способ проверки состояния

l + 1 < r

для int l,r на Java?

l и r не постоянны, и я знаю, что l <= r. Сравнение является условием остановки цикла while в реализации двоичного поиска. Конечно, я проверяю свой код как в отдельном тесте (поиск в большом массиве), так и в коде, который его использует.

То, что я ищу, я думаю, это какая-то небольшая операция, которая была бы быстрее, чем текущее состояние. Но я не знаю.

Answer 1

Этот вид микрооптимизации почти всегда является плохой идеей; Ваша производительность для такого небольшого бита будет полностью зависеть от того, как компилятор hotspot оптимизирует ваш код, и от незаметных эффектов кэша, связанных с окружающим кодом.

Answer 2

Я думаю, что это, вероятно, так быстро, как он собирается получить. Это приведет к очень простому байт-коду, а JIT (компилятор точно в срок), вероятно, уменьшит это до очень простой нативной реализации.

(Не имеет отношения: интересно видеть, что «количественный разработчик» использует Java. Кстати, такое случается не часто)

Answer 3

Имеет переменную lr1, которая всегда равна (l - r + 1). Всякий раз, когда вы увеличиваете или уменьшаете l, делайте то же самое с lr1. Аналогично для r.

Тогда ваш тест становится (lr1 < 0), и инструкции по изменению lr1 выполняются не чаще, чем необходимо.

Я чувствую себя немного глупо, давая вам микрооптимизацию, которая в большинстве случаев глупа, глупа. Например, если вы сравниваете строки, этот тест полностью затопит.

ДОБАВЛЕНО: Поскольку вы выполняете бинарный поиск, я бы упомянул о крутой развертывании Джона Бентли бинарного поиска. Сначала вы дополняете стол A до степени 2, например, 1024. Затем вы пишете что-то вроде этого:

i = 0;
if (X >= A[i+512]) i += 512;
if (X >= A[i+256]) i += 256;
   . . .
if (X >= A[i+  1]) i +=   1;

и, наконец, проверьте, если (X == A[i]). Или, если вы не хотите дополнять его, пусть операторы if будут выглядеть примерно так:
if (i+512 < N && X >= A[i+512]) i += 512;

Answer 4

Ну базовое сравнение должно либо:

добавьте 1 к l, сравните результат с r

или

вычтите 1 из r и сравните результат с l

Все современные аппаратные средства будут иметь одинаковую необработанную производительность для любой операции (где сложение и вычитание любого собственного типа данных имеет одинаковую производительность с точки зрения циклов выполнения и передачи побочных эффектов).

Единственный способ, которым это будет иметь какой-либо эффект, если:

одна из l или r является известной константой во время компиляции. например.

l + 1 < 5
5 + 1 < r

в этом случае плохой оптимизирующий компилятор может не осознавать, что может преобразовать первый в l < 4

но все Java-компиляторы должны определить, что второй случай 6 < r

Другой вариант, если типы данных l и r отличаются.

Операция:

1. сложение / вычитание с плавающей запятой, затем сравнение с int
   стихи
2. интегральное сложение / вычитание, тогда сравнение с двойным может отличаться.

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

Также приличный JIT может выполнять все виды оптимизаций по отношению к окружающему коду, которые перевешивают выполненную микрооптимизацию.

Answer 5

Как насчет перемещения теста на равенство за пределы цикла while, поэтому вы проверяете .equals () только после завершения. Между прочим, я не смог найти ни одного сложного способа проверить, есть ли l + 1

Answer 6

Лучше всего настроить JVM, а не код, учитывая, что это ваше узкое место.

Попробуйте запустить jvm с аргументами -server -XX:+AggressiveOpts.

Answer 7

Что все эти ребята сказали. Компилятор собирается оптимизировать это для вас. Напишите его так, чтобы он выглядел и читался правильно, и двигайтесь дальше.