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

Question

[PerseforeComplete]

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

Comments

[Lynn «Кофеман»]

В мире всего 2³² (≈4.3 миллиарда) уникальных IP.
Каждый занимает 4 байта.
Итого всего лишь 16 гигабайт.

[PerseforeComplete]

Lynn «Кофеман», Увы это не тот ответ, который нужен

[eegmak]

PerseforeComplete, а база данных загружается целиком в оперативку? кроме базы данных можно использовать dictionary+ настроить swap, тогда недостаток оперативы запишется на ssd/hdd. Можно пересмотреть принцип алгоритмов по примеру задачи про "ханойские башни". Или к примеру, создать файл, который будет аналогом массива и работать с файлом точно так же как с массивом (считывать по одной переменной с определенной строки)

[PerseforeComplete]

eegmak, Нет, база загружается построчно, поэтому она вообще не проблема

[eegmak]

PerseforeComplete, даже если в вашем файле будет 32 гб адресов, в структуре dictionary будет не больше чем количество уникальных адресов, т.к. дубль не будет увеличивать размер структуры

[d-stream]

Lynn «Кофеман», про ipv6 еще не в курсе? )

[Lynn «Кофеман»]

d-stream, я в курсе, а автор нет, иначе у него даже вопроса такого не было бы

[Everything_is_not_so_bad]

https://codereview.stackexchange.com/questions/259...

Answer 1

[Andrey Shatokhin]

Если вам допустима потеря точности - посмотрите на hyperloglog. Можно во много раз уменьшить потребление памяти.

Такая структура реализована, например, в redis. Там она займёт 12 Кбайт при погрешности в 0,81%.

Answer 2

[Армянское Радио]

Все IP адреса в мире легко засунутся в 16 гигабайт. Не так уж и много.
Грубо говоря, это задача про сжатие информации, и в зависимости от статистического распределения входного файла, будут хорошо работать разные алгоритмы храниения. Например, если в файле много адресов, идущих подряд, хорошо будет работать такой способ:

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

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

То есть в листьях дерева мы храним не сами адреса, а пары (база, количество)

Comments

[PerseforeComplete]

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

[Армянское Радио]

PerseforeComplete, так я описал решение, которое не будет жрать все 16 гигабайт

[PerseforeComplete]

Я это просто к уточнению о статистическом распределении входного файла

Answer 3

[Rsa97]

Для битовой таблицы достаточно 256*256*256*256/8 = 512Мб памяти.

Comments

[PerseforeComplete]

bitmap?

[Rsa97]

PerseforeComplete, Можно и так назвать.

$bitCounts = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4];
foreach ($ips as $ip) {
    $ipLong = ip2long($ip);
    $ipTable[floor($ipLong / 8)] |= (1 << ($ipLong % 8));
}
$totalCount = 0;
foreach ($ipTable as $mask) {
    $totalCount += $bitCount[$mask & 0xF] + $bitCount[($mask >> 4) &0xF];
}

Answer 4

[Иван Шумов]

Не надо меня слушать, но смеха ради это все решается работой с файловой системой) На каждый ip создаем одноименный файл, а потом просто делаем листнинг директории)

Answer 5

[Wataru]

Как уже сказали, оно все отлично помещается в память в битмапе. Но если бы не помещалось (допустим, это не 32-битные ip адреса, а 48-ми битные MAC адреса) , то нужно было бы использовать какую-либо внешнюю сортировку и получить все адреса отсортированными. А дальше за один проход легко подсчитать уникальные.

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

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

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

Answer 6

[Saboteur]

Дан файл с ip адресами. ip могут повторяться. Вес файла многократно превышает объём оперативной памяти.

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

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

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