@PerseforeComplete

Какую структуру данных надо использовать что бы посчитать уникальные ip в огромном количестве?

Дан файл с ip адресами. ip могут повторяться. Вес файла многократно превышает объём оперативной памяти. Надо посчитать количество уникальных ip. Простое решение, не учитывающее объём задачи - загнать все ip в хештаблицу и количество элементов в ней будет ответом. Вот только проблема - такая хештаблица не влезет в оперативку. Надо какую-то другую структуру данных использовать. Какую? И вообще, что почитать на тему highload задач и алгоритмов?
  • Вопрос задан
  • 235 просмотров
Решения вопроса 2
Если вам допустима потеря точности - посмотрите на hyperloglog. Можно во много раз уменьшить потребление памяти.

Такая структура реализована, например, в redis. Там она займёт 12 Кбайт при погрешности в 0,81%.
Ответ написан
gbg
@gbg
Баянист. Тамада. Услуги.
Все IP адреса в мире легко засунутся в 16 гигабайт. Не так уж и много.
Грубо говоря, это задача про сжатие информации, и в зависимости от статистического распределения входного файла, будут хорошо работать разные алгоритмы храниения. Например, если в файле много адресов, идущих подряд, хорошо будет работать такой способ:

Делаем древовидную структуру, например по октетам.
Если взять первые два октета, нам потребуется всего 65536 бакетов.

В каждом бакете у нас будет 256 слотов, в каждом слоте - еще 256 отрезков адресов. Если нам повстречались все 256 вариантов самого младшего октета, у нас весь отрезок аккуратно схлопнется.

То есть в листьях дерева мы храним не сами адреса, а пары (база, количество)
Ответ написан
Пригласить эксперта
Ответы на вопрос 4
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Для битовой таблицы достаточно 256*256*256*256/8 = 512Мб памяти.
Ответ написан
inoise
@inoise
Solution Architect, AWS Certified, Serverless
Не надо меня слушать, но смеха ради это все решается работой с файловой системой) На каждый ip создаем одноименный файл, а потом просто делаем листнинг директории)
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Как уже сказали, оно все отлично помещается в память в битмапе. Но если бы не помещалось (допустим, это не 32-битные ip адреса, а 48-ми битные MAC адреса) , то нужно было бы использовать какую-либо внешнюю сортировку и получить все адреса отсортированными. А дальше за один проход легко подсчитать уникальные.

Сортировать можно разными способами. Например, читать кусками сколько помещается в память, отсортировать как угодно, записать на диск. Потом получившиеся отсортированные куски можно объединять, как в сортировке слиянием.

Еще можно использовать radix sort.

Если есть еще и ограничения на использование места на диске, и в память оно не помещается, то можно воспользоваться фильтром Блума. Заведите его на сколько у вас там памяти хватит. Возьмите много хеш функций. Ну и потом за один проход проверяйте, есть ли уже считанный адрес в фильтре. Если нет - добавляйте и увеличивайте счетчик. Вот только это вероятностый метод и он может недосчитать чего-то из-за ложноположительных срабатываний блум фильтра.
Ответ написан
saboteur_kiev
@saboteur_kiev
software engineer
Дан файл с ip адресами. ip могут повторяться. Вес файла многократно превышает объём оперативной памяти.

Сколько оперативки?

Надо посчитать количество уникальных ip.
Простое решение, не учитывающее объём задачи - загнать все ip в хештаблицу и количество элементов в ней будет ответом.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы