Блог

Главная - Вопросы по программированию - Как эффективно пересечь две карты Roaringbit и получить карту Roaringbit с соответствующими позициями

Как эффективно пересечь две карты Roaringbit и получить карту Roaringbit с соответствующими позициями

#java #bitmap

Вопрос:

Каков наилучший с точки зрения производительности способ вычисления растрового изображения совпадающих позиций из двух растровых изображений?! Давайте приведем пример:

 First bitmap contains:  [1, 2, 3, 4, 5, 6, 7, 8, 9]
Second bitmap contains: [      3, 4,       7,    9]

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

 Wanted result:          [      2, 3,       6,    8]

Всегда верно, что растровое изображение 2 является подмножеством растрового изображения 1 (т. Е. каждое число в растровом изображении 2 также присутствует в растровом изображении 1).

Моя текущая реализация заключается в:

 final RoaringBitmap bitmap1 = ...;
final RoaringBitmap bitmap2 = ...;
final RoaringBitmapWriter<RoaringBitmap> resultWriter = RoaringBitmapWriter.writer().constantMemory().runCompress(false).get();
final IntIterator allIt = bitmap1.getBatchIterator().asIntIterator(new int[8192]);
bitmap2.forEach(new IntConsumer() {
    private int position = -1;

    @Override
    public void accept(int filteredId) {
        while (allIt.hasNext()) {
              position;
            final int allId = allIt.next();
            if (filteredId == allId) {
                resultWriter.add(  position);
                break;
            }
        }
    }
});
final int[] result = resultWriter.get().toArray();

Но он состоит из двух полных сканирований с использованием итератора / пакетного итератора, и я чувствую, что с помощью магии RoaringBitmap это может быть намного эффективнее.

Метки: