Заявление об авторских правах: эта статья является оригинальной статьей блоггера и соответствует соглашению об авторских правах CC 4.0 BY-SA. Пожалуйста, приложите ссылку на оригинальный источник и это заявление для перепечатки.
Ссылка на эту статью:Гу Депэн.GitHub.IO/note/2019/1…
1. Введение в растровое изображение
1: Алгоритм растрового изображения также известен как алгоритм растрового изображения, Его принцип заключается в использовании индексов вместо числовых значений или конкретных значений и использовании этого бита как 0 или 1 для представления того, существует ли функция.
2: Алгоритм Bitmap обладает характеристиками высокой эффективности и экономии места и подходит для дедупликации, запроса и т. д. большого объема данных, поскольку бит занимает в компьютере только один бит, а тип int занимает 32 бита. , поэтому место экономится 32 раза.
2. Сценарии использования
Если есть группа информации о толпе, вам нужно пометить эту группу людей, например, вам нужно пометить некоторых людей как участников, и вам нужно пометить людей, которые приобрели товары в течение 30 дней. Вы можете пометить каждого человека, поэтому, когда вы получаете набор членов, вам нужно пройтись по каждому человеку, чтобы определить, содержит ли он тег члена, что требует слишком больших вычислительных ресурсов.
Можно подумать по-другому, у нас 10 человек, поэтому мы определим 10-значный массив, мы можем установить id каждого человека по типу автоинкремента (начиная с 0), и тогда каждому соответствует человек , используйте 0,1, чтобы определить, есть ли у человека этот ярлык.会员标签 |0|1|1|1|0|0|0|1|0|0|
Таким образом, мы можем очень интуитивно запрашивать сотрудников с идентификаторами 1, 2, 3 и 7. Далее продолжаем бить человека, купившего товар в течение 30 дней.30天内购买过商品的人 |1|1|0|0|0|0|0|0|0|0|
Интуитивно видно, что id человека, купившего товар в течение 30 дней, равен 0,1. Затем мы хотим узнать участников, которые приобрели продукт в течение 30 дней, нам нужно только выполнить операцию И (&).会员标签 |0|1|1|1|0|0|0|1|0|0|30天内购买过商品的人 |1|1|0|0|0|0|0|0|0|0|30天内购买过商品的会员 |0|1|0|0|0|0|0|0|0|0|
Затем мы хотим узнать продукт или участника, который был куплен в течение 30 дней, нам нужно только выполнить операцию ИЛИ (|).会员标签 |0|1|1|1|0|0|0|1|0|0|30天内购买过商品的人 |1|1|0|0|0|0|0|0|0|0|30天内购买过商品的会员 |1|1|1|1|0|0|0|1|0|0|
Тогда вы должны сказать, я могу сделать это, создав карту, зачем использовать битовую карту.
Потому что в компьютере 1 int занимает 4 байта или 32 бита, а для использования Bitmap требуется только 1/32 памяти.
Вы можете сказать, что тогда у меня есть толпа в 100 000 человек, тогда мне нужно создать столько 100 000-битных битов, сколько у меня есть, но если у меня будет только один человек, который соответствует этому тегу, это будет тратить много ресурсов, и тогда я Расскажу, как решить эту проблему в конкретном методе использования.
3. Конкретный метод реализации
Здесь мы в основном объясняем два основных метода использования, первый — EWAHCompressedBitmap (реализация Bitmap от Google), второй —RoaringBitmap(Это также используется большинством основных приложений, таких как Spark, Hive, Kylin и т. д.).
1.EWAHCompressedBitmap
EWAH хранит Bitmap в длинном массиве, каждый элемент можно рассматривать как 64-битное двоичное число, также называемое словом в EWAH, инициализация EWAH составляет 4 слова, когда все слова заняты, это будет расширение. Когда добавленный диапазон данных велик, EWAH создаст RLW (слово текущей длины). RLW делится на две части. Младшие 32 бита указывают, сколько пустых слов охватывает текущее слово, а старшие 32 бита указывают, сколько пустых слов слова находятся за текущим RLW. последовательные слова. Это решает проблему, заключающуюся в том, что пролет очень велик и открывается много места.
2.RoaringBitmap
Roaring Bitmap делит 32-битное целое число на от 2 до 16 целых блоков данных, чтобы разделить одни и те же 16 старших битов. Используйте специальный контейнер для хранения их 16 младших битов. Когда блок целых чисел не содержит более 4096 целых чисел, используйте упорядоченный массив 16-битных целых чисел (используя массивы коротких типов в java). При наличии более 4096 целых чисел используются растровые изображения размером 2^16 бит (массивы типа long в java). Итак, у нас есть два типа контейнеров: ArrayContainer для разреженных фрагментов и BitmapContainer для плотных фрагментов. Пороговое значение 4096 гарантирует уровень контейнера, при котором каждое целое число использует не более 16 бит. При использовании контейнера растровых изображений используйте 2^16 для представления более 4096 (=2^12) целых чисел, менее 16 бит/целое число (2^16 / 2^12 = 2^4 = 16, если значения все заполнить длинный массив, в идеале 1 бит/целое число). Используйте точные 16 бит/целое число при использовании контейнеров массива.
Почему стоит выбрать порог 4096? Потому что, когда он меньше 4096, размер контейнера растрового изображения может превышать 16 бит/целое число. пробел, очевидно, больше, чем 2 ^ 16, меньшая 16-битная емкость представления числа. Одним словом, когда целочисленная база мала, использование массива экономит место, а когда база велика, использование растрового изображения экономит место.
Эти контейнеры хранятся в динамическом массиве с общими 16 старшими битами: они действуют как индексы первого уровня. Используйте массив, чтобы упорядочить старшие 16 бит. Мы считаем, что первичные индексы, как правило, невелики. При n=1 000 000 он содержит не более 16 объектов. Поэтому он должен храниться в кеше процессора. Сам контейнер не должен занимать более 8 КБ.
Вот статья о сравнении производительности:
Ни.UCSD.Сумма/Боюсь, содержание/…
4. Как использовать RoaringBitmap
1. Введение в мавен
<dependencies>
<dependency>
<groupId>org.roaringbitmap</groupId>
<artifactId>RoaringBitmap</artifactId>
<version>0.8.12</version>
</dependency>
</dependencies>2. Использование метода
public static void main(String[] args) {
RoaringBitmap rb = RoaringBitmap.bitmapOf(1,2,3,4,7,33,55);
//select 返回第几位的值
System.out.println(rb.select(1));
//rank 返回小于等于参数的值得个数
System.out.println(rb.rank(55));
//contains 是否包含参数
System.out.println(rb.contains(56));
//contains 是否包含参数
System.out.println(rb.contains(5L,56L));
//add 添加从左闭到右开区间内的值
rb.add(10L,15L);
System.out.println(rb);
RoaringBitmap rb1 = RoaringBitmap.bitmapOf(2,3,4,44);
System.out.println(rb1);
//取两个bitmap的并集
RoaringBitmap rb1or2=RoaringBitmap.or(rb,rb1);
System.out.println(rb1or2);
//取两个bitmap的交集
RoaringBitmap rb1and2=RoaringBitmap.and(rb,rb1);
System.out.println(rb1and2);
rb.and(rb1);
System.out.println(rb);
//获取第一位
System.out.println(rb.first());
}