Самый быстрый способ проверки условия l+1<r для int l,r в Java
-
06-07-2019 - |
Вопрос
Какой самый быстрый способ проверить состояние
l + 1 < r
для int l,r
на Яве?
l
и r
не постоянны, и я это знаю l <= r
.Сравнение является условием остановки while
цикл в реализации двоичного поиска.Я, конечно, проверяю свой код как в отдельном тесте (поиск в большом массиве), так и в коде, который его использует.
Я полагаю, что мне нужна какая-то битовая операция, которая была бы быстрее, чем текущее состояние.Но я не знаю.
Решение
Я думаю, что это, вероятно, так быстро, как и собирается. Это приведет к очень простому байт-коду, а JIT (компилятор точно в срок), вероятно, уменьшит это до очень простой встроенной реализации.
(Несвязанный: интересно видеть, что «количественный разработчик» использует Java. Между прочим, это случается не так часто)
Другие советы
Такая микрооптимизация почти всегда является плохой идеей; Ваша производительность для такого небольшого бита будет полностью зависеть от того, как компилятор горячей точки оптимизирует ваш код, и от незаметных эффектов кэша, связанных с окружающим кодом.
Ну, базовое сравнение должно либо:
прибавьте 1 к l, сравните результат с r
или
вычтите 1 из r и сравните результат с l
Все современное оборудование будет иметь одинаковую производительность для любой операции (где сложение и вычитание любого собственного типа данных имеет одинаковую производительность с точки зрения количества циклов завершения и побочных эффектов конвейера).
Единственный способ, которым это будет иметь какой-либо эффект, это если:
одна из l или r — известные константы во время компиляции.например.
l + 1 < 5
5 + 1 < r
в этом случае плохой оптимизирующий компилятор может не осознавать, что может преобразовать первое в l < 4
но все компиляторы Java должны заметить, что второй случай 6 < r
Другой — если типы данных l и r различны.
Операция:
- сложение/вычитание с плавающей запятой, а затем сравнение с целым числом
стихи - целое сложение/вычитание, то сравнение с двойным может быть другим.
Справедливо сказать, что вероятность того, что это станет серьезной проблемой в вашем приложении, незначительна, поскольку стоимость цикла любого из них ничтожна по сравнению с попаданием в конвейер любых неверных прогнозов ветвей, связанных с решением.
Кроме того, приличный JIT может выполнять всевозможные оптимизации по отношению к окружающему коду, которые перевешивают выполненную микрооптимизацию.
Иметь переменную 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 & amp; X > = A [ я + 512]) я + = 512;
Что все эти ребята сказали. Компилятор собирается оптимизировать это для вас. Напишите его так, чтобы он выглядел и читался правильно, и двигайтесь дальше.
Лучше всего настроить JVM, а не код, учитывая, что это ваше узкое место.
Попробуйте запустить jvm с аргументами -server -XX: + AggressiveOpts
.
Как насчет перемещения теста на равенство за пределы цикла while, поэтому вы проверяете .equals () только после завершения. Между прочим, я не смог найти ни одного сложного способа проверить, действительно ли l + 1 < r. Если известно, что длина вашего массива меньше определенного размера, что если вы используете другой тип данных для индексов? символ / короткие / байты? Р>