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

[IvaYan]

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

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

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

[Rabestro]

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

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

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

[BadDancer]

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

[wataru]

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

[IvaYan]

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

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

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

[wataru]

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

[IvaYan]

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

[kpmy]

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

[lightln2]

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

[Rabestro]

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

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