Сколько чисел в массиве

[EighthMayer]

Прошу прощения, вопрос скорее всего очень глупый (учитывая что я не понял почти ничего из того, что ниже хабраката), но если исходить из «пары проблем», то почему-бы не использовать битовую маску на 2^32 (4294967296) бита (512 мегабайт), где каждый бит соответствует одному адресу?

Если адреса в массиве не уникальны, то можно использовать ещё одну такую-же маску (+512 мегабайт) чтобы полностью обойти это ограничение.

[ripatti]

Представьте, что у вас нет 512 Мб, а есть только 1 Кб.

[SeptiM]

Да, можно, но такой метод требует слишком много памяти. Идея в том, как пожертвовать немного точностью, чтобы получить алгоритм, который использует всего пару килобайт. Кроме того, если длина адреса вырастет до 64 бит, первый метод совсем отвалится.

[impwx]

Из постановки задачи никак не следует, что для нее допустимо решение с погрешностью 300%.

[SeptiM]

Не следует. Задача определяет цель, к которой мы стремимся. В следующем абзаце я анонсирую, что будет рассказано. В частности, что в точной формулировке задача не имеет решения.

В конце поста я расскажу, почему точные детерминированные алгоритмы требуют памяти.

[SeptiM]

Немного оффтоп, но… Чем для вас является точность? Абсолютная цель или ресурс, которым можно пожертвовать?

[impwx]

Не поймите меня неправильно, я ни в коем случае не оспариваю необходимость вероятностных алгоритмов, но чем является точность — зависит не от моего личного мнения, а только от задачи. Если нужно показать красивый график — конечно, она не так важна. А если, например, по результатам этого подсчета будет составляться план модернизации сети и закупаться оборудование — то сами понимаете, троекратная переплата может оказаться неприемлемой.

[SeptiM]

Ага, т.е. вас больше всего беспокоит то, что алгоритм гуляет с 300% ошибкой, которую еще и нельзя регулировать. Это действительно проблема, но решаемая.

Есть усиление этого алгоритма, которое для произвольного возвращает ответ в пределах с вероятностью и использует памяти примерно . Можно посмотреть тут. Я думал про неё написать, но пост будет перегруженным.

Если будет большой интерес, могу написать пост про усиление.

[datacompboy]

Надавата будет.

[ishevchuk]

Спасибо за статью!
Совершенно случайно не знаете, используют ли какие-то сетевые железки именно этот алгоритм для подсчета количества соединений?
И если да, то какие?

[SeptiM]

Спасибо вам! :)

У меня нет знакомых железячников, но в целом, когда речь заходит о поиске аномалий в сетевом траффике на этот результат ссылаются. Причем ссылаются скорее как на первичную идею, которую потом активно допиливали. Обычно используют HyperLogLog или что-то близкое к нему.

Знаю соц. сеть, которая считает лайки HyperLogLog-ом. =)

[AlexWinner]

Считаем им уникальных посетителей (правда, сами не реализовывали, просто грузим лог в ElasticSearch, по примерно 1млрд запросов в сутки).