0x00 Предисловие

Эта статьяСерия алгоритмов больших данныхПервая статья "Принцип и реализация BitMap", идея и принцип BitMap лежат в основе многих алгоритмов, поэтому начнем с BitMap.

Поскольку мы говорим об алгоритмах больших данных, давайте сначала попробуем дать определение алгоритмам больших данных или ограничим объем этой серии статей.

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

Алгоритмы больших данных отличаются от традиционных алгоритмов:

ресурсы ограничены
временные ограничения
большие данные в качестве входных данных
Не обязательно точный алгоритм

Первые три пункта можно рассматривать как требования к алгоритму, а четвертый пункт можно рассматривать как уступку, на которую алгоритм может пойти в сценарии больших данных. Например, в данных 1 млрд.count distinctоперации, полностью точный алгоритм будет занимать очень много места, и быстро вычислить результат будет сложно. Если в это время допускается определенная ошибка, результат может быть рассчитан с небольшим количеством контента за очень короткое время, например Hyperloglog в алгоритме оценки кардинальности.

Эта серия будет включать в себя такие алгоритмы, как BitMap, Roaring BitMap, фильтр Блума, подсчет фильтра Блума, линейный подсчет, подсчет Loglog и подсчет HyperLogLog. Я пройдусь по этим алгоритмам один за другим, прочитаю статьи, напишу коды и организую учебные заметки.

Для технарей статья должна делатьГрафический и текстовый код, поэтому я постараюсь, чтобы в каждой статье было объяснение принципа и реализация примера кода.Объяснение принципа будет понято путем сопоставления картинок, а код будет иметь относительно простую демонстрацию.

0x01 Принцип

Фундаментальный

Основной принцип BitMap заключается в использовании бита для обозначения значения, соответствующего элементу, а ключ — это элемент. Поскольку один бит используется для хранения одних данных, это может значительно сэкономить место.

Мы используем конкретный пример, чтобы проиллюстрировать принцип BitMap.Предположим, мы хотим отсортировать 3 элемента (10, 17, 28) в пределах 0-31, тогда мы можем использовать метод BitMap (при условии, что эти элементы не повторяются).

Как показано на рисунке ниже, для представления 32 чисел нам нужно всего 32 бита (4 байта).Во-первых, мы открываем 4 байта пространства и устанавливаем все биты этих пробелов в 0.

Затем нам нужно добавить три числа (10, 17, 28) в BitMap, и необходимая операция — установить 0 на 1 в соответствующей позиции. Как показано на рисунке ниже, например, если вы хотите сейчас вставить элемент 10, вам нужно всего лишь изменить синий бит на 1.

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

карта строк

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

Конечно таким образомколлизия данныхПроблема, но некоторую оптимизацию можно сделать через фильтр Блума.

0x02 Реализация

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

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

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

0x03 использовать

Сценарии использования BitMap очень широки, например, BitMap используется в Oracle и Redis. Конечно, больше систем будут иметь немного более сложные алгоритмы, чем BitMap, такие как фильтр Блума, подсчет фильтра Блума, которые будут расширены один за другим позже.

Вот пример использования BitMap в алгоритме решения задачи.

Известно, что файл содержит несколько телефонных номеров, каждый номер состоит из 8 цифр, и подсчитывается количество различных номеров.

Я не буду здесь сравнивать его с другими алгоритмами, а прямо расскажу об идее BitMap.

8-битное целое число эквивалентно диапазону (0,99999999), то есть 99999999 бит, что составляет около 12 МБ памяти, что может сэкономить много места по сравнению с использованием метода, подобного HashMap. Его можно понимать как число от 0 до 99999999, каждое число соответствует биту, поэтому для представления всех 8-значных телефонов требуется всего около 12 МБ памяти.

Сделать запрос очень просто, просто подсчитайте, сколько бит равно 1.

0x04 Сводка

Идею BitMap до сих пор можно использовать для решения многих задач во время собеседований, а также во многих системах — это хороший способ решения проблем.

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

Коллизия данных. Например, при отображении строк в BitMap возникнет проблема коллизий, тогда вы можете рассмотреть возможность использования фильтра Блума для ее решения.Фильтр Блума использует несколько хеш-функций для уменьшения вероятности коллизии.
Данные скудны. Другой пример — для хранения трех данных (10,8887983,93452134) нам нужно создать BitMap длиной 99999999, но на самом деле хранится только 3 данных, в это время много неиспользуемого места. это проблема, ее можно решить, внедрив Roaring BitMap.