Rabestro Jul 26 2022 at 10:01

Считаем уникальные IPv4 адреса

9 min

11K

High performance*Entertaining tasksJava*Algorithms*Processing*

From sandbox

Java Season

+16

Comments 10

IvaYan Jul 26 2022 at 10:31

А почему бы не использовать что-то вроде HyperLogLog для подсчёта?

К сожалению, это не может считаться проверкой адреса на правильность, так как метод пропускает все числа за пределами допустимого диапазона от 0 до 255.

Но ведь по условию задачи, у нас все адреса корректны. Во всяком случае мы исходим из этого, когда не ловим эксепшен при вызове InetAddress::getByName.

Rabestro Jul 26 2022 at 11:17

Спасибо за ссылку на HyperLogLog! Я не знал об этом алгоритме.

По поводу «проверки» — здесь хотел сформулировать мысль, что данный код непоследовательный. Мы либо не делаем проверку совсем, либо, если нам поставят задачу проверять адреса, то нужно делать полную проверку.

Полная проверка происходит в InetAddress. При этом класс оптимизирован, работает значительно быстрее, чем первый пример.

BadDancer Jul 26 2022 at 12:06

Тестовое от ecwid, однако. Расползлось по курсам, даже файл с данными не стали менять.
vgv, возьмете автора на работу? :-)

wataru Jul 27 2022 at 14:05

Еще можно всякие фильтры Блума использовать, если хочется памяти поменьше кушать. Если взять несколько фильтров, то вероятность ложного срабатывания можно свести практически к 0.

IvaYan Jul 27 2022 at 15:10

Да, тоже про них вспомнил. Можно на входе поставить фильтр Блума и считать только те адреса, которые фильтр "не видел". Проблема в том, что у него бывают ложноположительные срабатывания, то есть фильтр скажет что видел, хотя не видел, то есть какие-то адреса не посчитаем.

Если взять несколько фильтров, то вероятность ложного срабатывания можно свести практически к 0.

Свой фильтр на подсеть?

wataru Jul 27 2022 at 15:17

Вообще, да — уменьшение наполненности уменьшает вероятность ошибки. Но я думал про использование нескольких независимых фильтров с разными хеш функциями.
Тогда вероятности ошибки перемножаются и экспоненциально уходят к 0.

IvaYan Jul 27 2022 at 15:40

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

kpmy Jul 27 2022 at 20:21

Ещё можно подумать над хранением целочисленных адресов в оптимальном виде, что-то типа RLE-кодирования.

lightln2 Jul 28 2022 at 08:01

А сколько времени в итоге занимает обработка тестового файла?
Распаковка и чтение с диска не будет занимать больше времени, чем, собственно, сам подсчет?

Rabestro Jul 28 2022 at 13:05

Чтение с жёсткого диска является бутылочным горлышком. Зависит от типа HDD. На моём компьютере обработка файла 120Gb занимала 20 минут ВНЕ ЗАВИСИМОСТИ от используемого конвертера и контейнера.

Однако, если у нас микросервис, мы будем получать данные не с жёсткого диска. Для этого случая эффективность алгоритма уже существенна.