В предыдущей статье был рассмотрен расчет оптимальных параметров фильтра Блума и его реализация.
Со статьей можно ознакомиться здесь: Фильтр Блума
Для оценки эффективности будем рассматривать сколько оперативной памяти потребляют различные структуры данных в Java 11.
Для примера будем размещать в памяти информацию о 20 миллионах ИИН и делать наблюдения через VisualVM.
ИИН представляет собой строку из 12 символов.
Хранение в ArrayList<String>
Хранение 20 миллионов ИИН в ArrayList:
Создается 20 миллионов объектов String, каждый объект String ссылается на массив байт из 12 элементов.
| Элемент | Размер | Кол-во | Общий размер |
|---|---|---|---|
| String | 20 B | 20 000 000 | 553 MB |
| byte[12] | 36 B | 20 000 000 | 687 MB |
Суммарно данный способ занимает в памяти примерно 1240 MБ.
Хранение в HashSet<String>
Хранение 20 миллионов ИИН в HashSet<String>:
Создается 20 миллионов объектов таких же как и для ArrayList, дополнительно хранятся узлы корзины HashMap.Node (под капотом HashSet находится HashMap).
| Элемент | Размер | Кол-во | Общий размер |
|---|---|---|---|
| String | 20 B | 20 000 000 | 553 MB |
| byte[12] | 36 B | 20 000 000 | 687 MB |
| HashMap.Node | 44 B | 20 000 000 | 839 MB |
Суммарно данный способ занимает в памяти примерно 2079 MБ.
Хранение в HashSet<Long>
Хранение 20 миллионов ИИН в HashSet<Long>:
Создается 20 миллионов объектов Long и HashMap.Node.
| Элемент | Размер | Кол-во | Общий размер |
|---|---|---|---|
| Long | 24 B | 20 000 000 | 458 MB |
| HashMap.Node | 44 B | 20 000 000 | 839 MB |
Суммарно данный способ занимает в памяти примерно 1297 MБ.
Хранение в ArrayList<Long>
Создается 20 миллионов объектов Long.
| Элемент | Размер | Кол-во | Общий размер |
|---|---|---|---|
| Long | 24 B | 20 000 000 | 458 MB |
Суммарно данный способ занимает в памяти примерно 458 MБ.
Хранение в long[]
Создается массив из 20 миллионов элементов типа long.
| Элемент | Размер | Кол-во | Общий размер |
|---|---|---|---|
| long | 8 B | 20 000 000 | 152 MB |
Суммарно данный способ занимает в памяти примерно 152 MБ.
Хранение в MyBloomFilter
В реализации MyBloomFilter используется BitSet, BitSet в свою очередь хранит биты в виде массива long, поэтому основную память забирает этот массив.
В нашей реализации BitSet хранит информацию о 268 435 456 битах.
В один long помещается 64 бит.
268 435 456 / 64 = 4 194 304 (кол-во элементов в массиве)
Практически нет дополнительных потерь при хранении байтов (24 байта транится на сам массив).
268 435 456 бит / 8 = 33 554 432 байт
Суммарно данный способ занимает в памяти примерно 32 MБ.
Хранение в GoogleBloomFilter
Как было рассмотрено в предыдущей статье о фильтре Блума, необходимо рассчитать оптимальное кол-во бит для хранения.
Для 20 миллионов ИИН с вероятностью ошибок 1% оптимальное кол-во бит составляет 191 701 168.
BloomFilter из набора guava для хранения бит использует AtomicLongArray, который в свою очередь использует для хранения бит также long массив (long[]).
Рассчитаем кол-во элементов в массиве:
⌈191 701 168 / 64⌉ = ⌈2 995 330.75⌉ = 2 995 331
Теперь рассчитаем размер в байтах:
191 701 168 бит / 8 = 23 962 646 байт
Суммарно данный способ занимает в памяти примерно 23 MБ.
Итоговая сравнительная таблица
| Структура данных | Потребляемая память | Примечание |
|---|---|---|
| HashSet<String> | 2079 MБ | Оптимальные операции добавления и поиска, но высокое потребление памяти |
| HashSet<Long> | 1297 MБ | Дополнительная работа с Long, из-за наличия у ИИН ведущих нулей |
| ArrayList<String> | 1240 MБ | Список должен быть отсортирован, что была возможность поиска |
| ArrayList<Long> | 458 MБ | Список должен быть отсортирован. Дополнительная работа с Long, из-за наличия у ИИН ведущих нулей. |
| long[] | 152 MБ | Фиксированный размер. |
| MyBloomFilter | 32 MБ | Неоптимальная реализация |
| Bloom Filter (Google Guava) | 23 MБ | Оптимальная реализация |
Заключение
В данной статье было рассмотрено несколько вариантов хранения информации о 20 миллионах ИИН, где вместо 1-2 гигабайт, можно обойтись 20-30 мегабайтами (экономия на порядок) при допущении заданной вероятности ошибок.
Но кол-во данных может быть гораздо больше, как и сами данные могут быть больше, и применение фильтр Блума в данных случаях будет еще заметнее.
Фильтр Блума имеет достаточно специфические варианты использования, и есть небольшая вероятность, что он вам пригодится.
Добавить комментарий