Comments 12
Прошу прощения, вопрос скорее всего очень глупый (учитывая что я не понял почти ничего из того, что ниже хабраката), но если исходить из «пары проблем», то почему-бы не использовать битовую маску на 2^32 (4294967296) бита (512 мегабайт), где каждый бит соответствует одному адресу?
Если адреса в массиве не уникальны, то можно использовать ещё одну такую-же маску (+512 мегабайт) чтобы полностью обойти это ограничение.
Если адреса в массиве не уникальны, то можно использовать ещё одну такую-же маску (+512 мегабайт) чтобы полностью обойти это ограничение.
0
Представьте, что у вас нет 512 Мб, а есть только 1 Кб.
+3
Да, можно, но такой метод требует слишком много памяти. Идея в том, как пожертвовать немного точностью, чтобы получить алгоритм, который использует всего пару килобайт. Кроме того, если длина адреса вырастет до 64 бит, первый метод совсем отвалится.
0
Из постановки задачи никак не следует, что для нее допустимо решение с погрешностью 300%.
+13
Не следует. Задача определяет цель, к которой мы стремимся. В следующем абзаце я анонсирую, что будет рассказано. В частности, что в точной формулировке задача не имеет решения.
В конце поста я расскажу, почему точные детерминированные алгоритмы требуютпамяти.
0
Немного оффтоп, но… Чем для вас является точность? Абсолютная цель или ресурс, которым можно пожертвовать?
0
Не поймите меня неправильно, я ни в коем случае не оспариваю необходимость вероятностных алгоритмов, но чем является точность — зависит не от моего личного мнения, а только от задачи. Если нужно показать красивый график — конечно, она не так важна. А если, например, по результатам этого подсчета будет составляться план модернизации сети и закупаться оборудование — то сами понимаете, троекратная переплата может оказаться неприемлемой.
+3
Ага, т.е. вас больше всего беспокоит то, что алгоритм гуляет с 300% ошибкой, которую еще и нельзя регулировать. Это действительно проблема, но решаемая.
Есть усиление этого алгоритма, которое для произвольного
возвращает ответ в пределах
с вероятностью
и использует памяти примерно
. Можно посмотреть тут. Я думал про неё написать, но пост будет перегруженным.
Если будет большой интерес, могу написать пост про усиление.
Есть усиление этого алгоритма, которое для произвольного
Если будет большой интерес, могу написать пост про усиление.
+4
Спасибо за статью!
Совершенно случайно не знаете, используют ли какие-то сетевые железки именно этот алгоритм для подсчета количества соединений?
И если да, то какие?
Совершенно случайно не знаете, используют ли какие-то сетевые железки именно этот алгоритм для подсчета количества соединений?
И если да, то какие?
0
Спасибо вам! :)
У меня нет знакомых железячников, но в целом, когда речь заходит о поиске аномалий в сетевом траффике на этот результат ссылаются. Причем ссылаются скорее как на первичную идею, которую потом активно допиливали. Обычно используют HyperLogLog или что-то близкое к нему.
Знаю соц. сеть, которая считает лайки HyperLogLog-ом. =)
У меня нет знакомых железячников, но в целом, когда речь заходит о поиске аномалий в сетевом траффике на этот результат ссылаются. Причем ссылаются скорее как на первичную идею, которую потом активно допиливали. Обычно используют HyperLogLog или что-то близкое к нему.
Знаю соц. сеть, которая считает лайки HyperLogLog-ом. =)
0
Sign up to leave a comment.
Сколько чисел в массиве