Комментарии 29
А список FDNS или URL таким образом схлопывать не пробовали?
Можно уменьшить любой список IP адресов, при условии, что вас устраивают дополнительные адреса, которые войдут в получившийся список.
Можно — то можно. Весь вопрос в том, как это реализовать?
В случае IP-адресов мы имеем строго определенное число октетов строго определенной длины. И порядок старшинства и октетов и двоичных цифр в них совпадает — уменьшается слева направо.
В случае FDNS начинается уже свистопляска. Зоны, домены, поддомены — имеют разную длину имен. В их иерархии старшей является зона. Но она находится справа FDNS. Но естественный порядок сортировки каждой части — сначала по левым символам. Уже заставляет задуматься.
Возможно ли в этом случае создание подобного эффективного подхода?
В случае IP-адресов мы имеем строго определенное число октетов строго определенной длины. И порядок старшинства и октетов и двоичных цифр в них совпадает — уменьшается слева направо.
В случае FDNS начинается уже свистопляска. Зоны, домены, поддомены — имеют разную длину имен. В их иерархии старшей является зона. Но она находится справа FDNS. Но естественный порядок сортировки каждой части — сначала по левым символам. Уже заставляет задуматься.
Возможно ли в этом случае создание подобного эффективного подхода?
Делал для блокировки рекламы из разных список в unbound.
Смысл такой: Если в списке присутсвует domain.com, то из списка нужно исключить subdomain.domain.com, потому что блокировка происходит по
Только для доменов. За код пардоньте. Писалось давно и в питоне не силен.
использование:
Работает не очень шустро, но быстрее чем на bash. Другой вопрос что обновляются списки очень не часто (я раз в полгода примерно запускаю) и не всем нужно 500к рекламных доментов в блокировку.
Проц Intel® Atom(TM) CPU D2550 @ 1.86GHz
Смысл такой: Если в списке присутсвует domain.com, то из списка нужно исключить subdomain.domain.com, потому что блокировка происходит по
кусок ads.conf для unbound
local-zone: «dimain.com» redirect
local-data: «dimain.com A 0.0.0.0»
local-data: «dimain.com A 0.0.0.0»
Только для доменов. За код пардоньте. Писалось давно и в питоне не силен.
ads-domain-filter.py
#!/usr/bin/env python
from fileinput import input
data = []
result = []
for x in input():
d = x[::-1]
if d[1] != ".":
data.append(d)
else:
data.append(d[2:])
data.sort()
i = 0
while i < len(data)-1:
dom = data[i]
j = i+1
while j < len(data)-1:
if data[j].startswith(dom+"."):
data.pop(j)
else: break
i = i+1
for y in data:
print y[::-1]
использование:
ads-domain-filter.py input.txt | egrep -v "^$" | sort | uniq > output.txt
Работает не очень шустро, но быстрее чем на bash. Другой вопрос что обновляются списки очень не часто (я раз в полгода примерно запускаю) и не всем нужно 500к рекламных доментов в блокировку.
Проц Intel® Atom(TM) CPU D2550 @ 1.86GHz
Заголовок спойлера
[14:10:18] Remove duplicate entries in 509271 domains.
[14:24:15] Generating result config. Total 292359 domains
[14:24:15] Generating result config. Total 292359 domains
В статье нет ответа на главный вопрос™ завис ли роутер MikroTik hAP ac lite (кончилось ли место на его диске) после группировки адресов таким образом?
Сжимаем список IP-адресов наилучшим образом
Первая ассоциация, пока не прочел про авторство поста — что это Роскомнадзор блог на Хабре запилил и профильный текст написал.
Интересно, если бы РКН такое захотел сделать, ему бы предоставили скидку на оплату? А иммунитет кармы дали бы, просто чтобы люди не сбежали сразу же? *смайлик*
Печальный опыт Ksenzov показывает, что вряд ли.
Пытаюсь разобраться с «коэффициентами выгоды»…
Что-то не ладнов Датском королевстве с ними.
Родительские Кв плывут потому что не учитывают, что в объединяемых записях (если они не отдельные хосты с маской 32 или изначально заданные подсети представляют, а уже «схлопнутые» ранее) уже присутствует некоторое количество фиктивных IP, попавших туда «за компанию».
Если это учитывать, то окажется, что новое схлопывание добавит не так уж много новых лишних IP по сравнению с ранее добавленными предыдущими схлопываниями, т.е. для него Кв будет выше, чем на приведенных рисунках.
Может быть удастся даже таким образом вычислять родительские Кв, что они совсем не будут изменяться при схлопывании «деток».
Но для этого надо в каждой схлопнутой записи хранить не только IP/MASK, но и число подпадающих под нее «лишних» адресов.
Что-то не ладно
Родительские Кв плывут потому что не учитывают, что в объединяемых записях (если они не отдельные хосты с маской 32 или изначально заданные подсети представляют, а уже «схлопнутые» ранее) уже присутствует некоторое количество фиктивных IP, попавших туда «за компанию».
Если это учитывать, то окажется, что новое схлопывание добавит не так уж много новых лишних IP по сравнению с ранее добавленными предыдущими схлопываниями, т.е. для него Кв будет выше, чем на приведенных рисунках.
Может быть удастся даже таким образом вычислять родительские Кв, что они совсем не будут изменяться при схлопывании «деток».
Но для этого надо в каждой схлопнутой записи хранить не только IP/MASK, но и число подпадающих под нее «лишних» адресов.
Любое схлопывание можно представить как операцию на исходном списке — убрали такие-то записи, вместо них добавили одну новую. Дальше мы уже работаем с новым списком, в нём нет убранных сетей а схлопнутая сеть становится одной из записей этого списка. Поэтому все коэффициенты должны быть пересчитаны.
Пример
Если мы сожмём сеть 192.168.20.0/29, тогда мы уберём 5 записей из списка, и охватим 2 дополнительных ip.
Если сожмём 192.168.20.0/30 и 192.168.20.4/30, тогда мы уберём 4 записи из списка, и охватим тоже 2 дополнительных ip адреса.
Т.е. выгоднее сжать большую сеть, поэтому у неё выше коэффициент.
Если мы сожмём сеть 192.168.20.0/29, тогда мы уберём 5 записей из списка, и охватим 2 дополнительных ip.
Если сожмём 192.168.20.0/30 и 192.168.20.4/30, тогда мы уберём 4 записи из списка, и охватим тоже 2 дополнительных ip адреса.
Т.е. выгоднее сжать большую сеть, поэтому у неё выше коэффициент.
Если мы сожмём сеть 192.168.20.0/29, тогда мы уберём 5 записей из списка ...
Корректнее было бы говорить «уберем 6 записей из списка и добавим одну». Результат тот же, но суть действий описана точнее.
Насчет пересчета коэффициентов еще раз поясню. Возможно, пересчитывать и надо, но совсем по другому.
Вот после схлопывания сетей 192.168.20.0/30 и 192.168.20.4/30 имеем такую структуру-кандидата на следующее схлопывание:
192.168.20.0/29 (станет 8 IP из них 2 лишних)
192.168.20.0/30 (4 IP из них 1 лишний)
192.168.20.4/30 (4 IP из них 1 лишний)
Но на самом деле при схлопывании этой структуры этих двух лишних адресов не появится — они и так уже были лишними в подсетях 192.168.20.0/30 и 192.168.20.4/30.
И наше новое объединение позволило объединить 2 IP в один без дальнейшего увеличения числа лишних IP. Т.е. Кв такого схлопования будет Inf.
P.S. А еще у Вас не принимается во внимание, что адреса со всеми нулями и единицами в номере хоста не надо учитывать в числе «лишних», т.к. в подсети их и так нет. Но это уже сложно и неоднозначно, т.к. наше искусственное объединение адресов в подсети далеко не всегда соответствует реально существующим подсетям.
Я вас понял. Отличное замечание, спасибо!
Тогда вес нужно считать по формуле:
weight = (in_list_records_count — 1) / net_extra_ip_volume_delta
Запилю фикс.
Можно не учитывать адреса, последний октет которых равен нулю или 255 — таких точно нет. Подумаю.
Тогда вес нужно считать по формуле:
weight = (in_list_records_count — 1) / net_extra_ip_volume_delta
Запилю фикс.
P.S. А еще у Вас не принимается во внимание, что адреса со всеми нулями и единицами в номере хоста не надо учитывать в числе «лишних», т.к. в подсети их и так нет. Но это уже сложно и неоднозначно, т.к. наше искусственное объединение адресов в подсети далеко не всегда соответствует реально существующим подсетям.
Можно не учитывать адреса, последний октет которых равен нулю или 255 — таких точно нет. Подумаю.
Родительские Кв плывут потому что не учитывают, что в объединяемых записях… уже присутствует некоторое количество фиктивных IP, попавших туда «за компанию».
Учитывают. На всякий случай перепроверил код. Объём фейковых IP для каждой сети вычисляется один раз и далее используется именно это значение. Коэффициенты плывут потому-что уменьшается экономия от схлопывания — т.е. если в сети 10 реальных IP адресов и 5 из них уже схлопнуты, тогда при схлопывании мы сможем сэкономить лишь 4 записи в списке.
Ладно, ладно. Challenge accepted.
Буду ждать ответной статьи. У меня не решён вопрос с тем, что некоторые IP адреса на самом деле не существуют, например 192.168.0.0 — можно в эту сторону покопать. Хотя подозреваю что сильно качество это не улучшит, всё уже на пределе! Ну и на golang конечно повеселее будет работать.
А вообще, спасибо за утилиту, без неё не с чем было бы сравнивать.
А вообще, спасибо за утилиту, без неё не с чем было бы сравнивать.
Почему не существует? Хороший адрес. В зависимости от маски подсети. Так же и .255 существуют.
Да, все верно.
Если маска не /24, а, к примеру, /23, то вполне могут существовать хосты с адресами 192.168.1.0 и 192.168.0.255.
Так что, лучше не заморачиваться с этими адресами, а попытаться ускорить работу за счет эффективного хранения данных. Например, в виде перестраиваемого дерева.
Если маска не /24, а, к примеру, /23, то вполне могут существовать хосты с адресами 192.168.1.0 и 192.168.0.255.
Так что, лучше не заморачиваться с этими адресами, а попытаться ускорить работу за счет эффективного хранения данных. Например, в виде перестраиваемого дерева.
Насчёт 23 маски — это любопытно. Не задумывался над этим.
Тут две разных задачи:
Первое можно существенно улучшить. Второе уже на пределе, если только не получится как-то учитывать нулевые хосты в подсетях. Даже если получится, мне кажется, это особого уменьшения количества фейковых IP не даст.
Тут две разных задачи:
- Оптимизация скорости выполнения скрипта
- Уменьшение количества фейковых IP в результирующем списке
Первое можно существенно улучшить. Второе уже на пределе, если только не получится как-то учитывать нулевые хосты в подсетях. Даже если получится, мне кажется, это особого уменьшения количества фейковых IP не даст.
Вот поэтому и не стоит заморачиваться с нулевыми хостами. Все равно объединение в подсети в данной утилите является искусственным и может не соответствовать реальным подсетям. Если в реале такой подсети нет, то нулевой (или со всеми единицами в номере хоста) адрес в искусственно введенной подсети вполне допустим.
А вот насчет повышения скорости вполне стоит подумать. Я не разбирался с алгоритмом, но как мне кажется, при добавлении нового адреса в список происходит его сравнение со всеми адресами из этого списка на предмет выявления наилучшего совпадения. Т.е. временная сложность уже не менее O(n^2).
Но на самом деле список еще и пополняется псевдоподсетями, с которыми этот новый IP тоже будет сравниваться. Таким образом производительность будет еще хуже. Как бы не O(log(n)*n^2).
Надо подумать о структуре данных, которая бы позволила хранить коэффициенты выгодности, быстро искать максимальные и корректировать их «на лету» при схлопывании.
А вот насчет повышения скорости вполне стоит подумать. Я не разбирался с алгоритмом, но как мне кажется, при добавлении нового адреса в список происходит его сравнение со всеми адресами из этого списка на предмет выявления наилучшего совпадения. Т.е. временная сложность уже не менее O(n^2).
Но на самом деле список еще и пополняется псевдоподсетями, с которыми этот новый IP тоже будет сравниваться. Таким образом производительность будет еще хуже. Как бы не O(log(n)*n^2).
Надо подумать о структуре данных, которая бы позволила хранить коэффициенты выгодности, быстро искать максимальные и корректировать их «на лету» при схлопывании.
Т.е. временная сложность уже не менее O(n^2).
Это не так. У нас бинарное дерево (ну, нечто наподобие), причём с максимальной глубиной, равной 32. Добавление одного нового IP происходит максимум за 32 операции. При этом создаётся ровно одна псевдоподсеть. Сложность добавления нового элемента можно принять за O(n).
Большую часть времени работы скрипта занимает схлопывание сетей. Коэффициенты выгодности и так хранятся в каждом узле и пересчитываются только при изменении дочерних сетей.
При схлопывании также не нужно перебирать все сети — каждый узел имеет «стрелочку» в каком направлении находится узел с максимальным весом. Добраться до него также можно за 32 шага вглубь по дереву. Т.е. уменьшение исходного списка на n элементов выполняется за O(n) (это в худшем случае, когда одна операция схлопывания уменьшает длину списка на 1)
После схлопывания какой-либо сети, при движении назад происходит пересчёт весов родительских сетей.
Насчет вставки — пожалуй что соглашусь. Если не список, а бинарное дерево, то эффективность будет несколько выше. Но до идеала будет далеко, т.к. многие ветви будут вырожденными — просто не будет их в реестре.
А вот «стрелочка» внушает мне опасения…
Вот мы схлопнули псевдосеть с наибольшим коэффициентом выгодности… а где находится следующая по выгоде псевдосеть с наибольшим оставшимся коэффициентом? В какой ветви и подветви? Как нам эта стрелочка поможет? Она ведь знала только где находилась наибольшая, но ее уже нет.
А вот «стрелочка» внушает мне опасения…
Вот мы схлопнули псевдосеть с наибольшим коэффициентом выгодности… а где находится следующая по выгоде псевдосеть с наибольшим оставшимся коэффициентом? В какой ветви и подветви? Как нам эта стрелочка поможет? Она ведь знала только где находилась наибольшая, но ее уже нет.
Но до идеала будет далеко, т.к. многие ветви будут вырожденными — просто не будет их в реестре.
Ветвь создаётся только при добавлении IP из исходного списка. Наверно мы имеем что-то около log2(n) * n узлов в дереве, где n — это размер исходного списка.
а где находится следующая по выгоде псевдосеть с наибольшим оставшимся коэффициентом?
«стрелочка» (наибольший вес в поддереве) в родительских элементах тоже пересчитывается при движении назад. Более того, если при движении назад мы видим что есть ещё одна сеть с таким же весом, как только-что сжатая, мы сразу же начинаем сжимать её, не возвращаясь к корневому элементу.
«наибольший вес в поддереве» для корневого узла означает наибольший вес во всём дереве.
Ага… Т.е. при рекурсивном подъеме после «схлопывания» мы не только корректируем собственные коэффициенты выгодности в каждом узле, но и переписываем в них информацию о положении и величине наибольшего коэффициента выгодности в их подветвях?
Именно так. Это простая операция
self.max_child_weight = 0
for Child in self.children:
self.max_child_weight = max(self.max_child_weight, Child.weight, Child.max_child_weight)
Из данного фрагмента кода видно, что вычисляется наибольший вес, но не видно, какому потомку или самому узлу он принадлежит. А, следовательно, при попадании в узел все равно придется просматривать всех потомков, чтобы определить, по какой именно ветви следует продолжить поисковый спуск.
Можно подумать вот над чем: Не хранить в узле его собственный вес и дополнительно лучший вес, а только лучший вес и флаг, где он лежит:
0 — лучший вес принадлежит этому узлу (узел является листом и не имеет потомков);
1 — лучший вес находится в левой ветви;
2 — лучший вес находится в правой ветви;
3 — лучший вес принадлежит этому узлу (узел не является листом и имеет 1 или 2 потомка).
Надеюсь, под словами «бинарное дерево» вы понимаете именно то, что каждый узел имеет не более двух потомков, жестко разделенных на «правый» и «левый»?
Тогда процедура рекурсивного подъема с корректировкой чуть усложнится, но общая структура будет проще и сам рекурсивный спуск с поиском будет проще.
Можно подумать вот над чем: Не хранить в узле его собственный вес и дополнительно лучший вес, а только лучший вес и флаг, где он лежит:
0 — лучший вес принадлежит этому узлу (узел является листом и не имеет потомков);
1 — лучший вес находится в левой ветви;
2 — лучший вес находится в правой ветви;
3 — лучший вес принадлежит этому узлу (узел не является листом и имеет 1 или 2 потомка).
Надеюсь, под словами «бинарное дерево» вы понимаете именно то, что каждый узел имеет не более двух потомков, жестко разделенных на «правый» и «левый»?
Тогда процедура рекурсивного подъема с корректировкой чуть усложнится, но общая структура будет проще и сам рекурсивный спуск с поиском будет проще.
Да, в каждом узле всего два потомка. Они правда не разделены на правый и левый (поэтому я и называю эту структуру «что-то вроде бинарного дерева»). Посмотреть на два числа ничуть не сложнее чем на флаг, при этом флаг сложнее обновлять — нужно точно также посмотреть на числа и выставить значение.
При этом мне нужен максимальный вес в корневом элементе — т.е. всё-равно нужно пробрасывать его в корень.
При этом мне нужен максимальный вес в корневом элементе — т.е. всё-равно нужно пробрасывать его в корень.
Старое доброе бинарное дерево? Добавление элемента в дерево будет простым, а для обхода всё равно по всему списку придётся бегать в поисках коэффициентов. Но схлопывание и корректировка будут вполне быстры.
(на правах шутки) А если у нас есть много памяти, то можно все адреса развернуть в линейную область памяти и обращаться к нужным весам простой математической операцией!
______
Надо было обновить комментарий. Оказалось, что так оно и есть.
(на правах шутки) А если у нас есть много памяти, то можно все адреса развернуть в линейную область памяти и обращаться к нужным весам простой математической операцией!
______
Надо было обновить комментарий. Оказалось, что так оно и есть.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сжимаем список IP-адресов наилучшим образом