Как эффективно найти отсортированный, большой, прямой буфер в Java?

Question

У меня есть прямой буфер, содержащий целые числа, которые уже отсортированы (т.е. 1,1,3,3,3,3,7,7, ....).Большинство значений будет встречаться несколько раз.Я хочу найти первую позицию значений, которые я ищу.

1. Существует ли функция поиска, работающая непосредственно с буферами, встроенными в Java?(ничего не смог найти)
2. Если нет, то есть ли приличная библиотека, предоставляющая такую ​​функциональность?

3. Если нет, какой алгоритм поиска порекомендовал бы для реализации, учитывая, что:

   • Обычно в моем буфере будут миллионы записей
   • Скорость очень важна
   • Это должно вернуть первое вхождение искомого числа
   • Я бы предпочел, чтобы он не изменял данные, поскольку впоследствии мне понадобятся исходные данные

РЕДАКТИРОВАТЬ: Спасибо всемплакаты с предложением Arrays.binarySearch(), но, насколько мне известно, прямые буферы обычно не имеют резервного массива.Вот почему я искал реализацию, которая непосредственно работает с буфером.

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

Answer 1

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

Пример кода в ссылке возвращает крайнюю правую точку;вам нужно заменить > на >= в строке nums[guess] > check, чтобы получить крайнюю левую точку.Это спасает вас от потенциально дорогостоящего обратного линейного поиска или использования «обратного» * ​​1008 *, который требует обернуть ваши int в Integer объекты.

Answer 2

Использование Алгоритм двоичного поиска

ByteBuffer buffer = createByteBuffer();
IntBuffer intBuffer = buffer.asIntBuffer();

Если байтовый массив можно преобразовать в массив int, используйте:

int [] array = intBuffer.array();
int index = java.util.Arrays.binarySearch(array,7);

Answer 3

Вам, вероятно, придется написать собственный двоичный поиск: тот, который всегда перемещается влево, если проверенное значение равно искомому.

Таким образом, вместо x, вы будете искать x-ε. Ваш алгоритм всегда будет делать ровно logn (или logn + 1) шагов, так как он всегда будет «терпеть неудачу», но он даст вам индекс первого элемента, который больше x-ε. Все, что вам нужно сделать, это проверить, является ли этот элемент x, и если это так, вы нашли свое соответствие, если нет, в вашем буфере нет x.

Answer 4

Я не знаю о встроенной функциональности для буферов (Arrays.binarySearch(...) потребует от вас преобразования буфера в массив), но как для 3 .: так как буфер уже отсортирован, может быть полезен двоичный поиск. Если вы нашли значение, вы можете проверить предыдущие значения, чтобы получить начало этой последовательности.