Да, в каждом узле всего два потомка. Они правда не разделены на правый и левый (поэтому я и называю эту структуру «что-то вроде бинарного дерева»). Посмотреть на два числа ничуть не сложнее чем на флаг, при этом флаг сложнее обновлять — нужно точно также посмотреть на числа и выставить значение.
При этом мне нужен максимальный вес в корневом элементе — т.е. всё-равно нужно пробрасывать его в корень.
Но до идеала будет далеко, т.к. многие ветви будут вырожденными — просто не будет их в реестре.
Ветвь создаётся только при добавлении IP из исходного списка. Наверно мы имеем что-то около log2(n) * n узлов в дереве, где n — это размер исходного списка.
а где находится следующая по выгоде псевдосеть с наибольшим оставшимся коэффициентом?
«стрелочка» (наибольший вес в поддереве) в родительских элементах тоже пересчитывается при движении назад. Более того, если при движении назад мы видим что есть ещё одна сеть с таким же весом, как только-что сжатая, мы сразу же начинаем сжимать её, не возвращаясь к корневому элементу.
«наибольший вес в поддереве» для корневого узла означает наибольший вес во всём дереве.
Это не так. У нас бинарное дерево (ну, нечто наподобие), причём с максимальной глубиной, равной 32. Добавление одного нового IP происходит максимум за 32 операции. При этом создаётся ровно одна псевдоподсеть. Сложность добавления нового элемента можно принять за O(n).
Большую часть времени работы скрипта занимает схлопывание сетей. Коэффициенты выгодности и так хранятся в каждом узле и пересчитываются только при изменении дочерних сетей.
При схлопывании также не нужно перебирать все сети — каждый узел имеет «стрелочку» в каком направлении находится узел с максимальным весом. Добраться до него также можно за 32 шага вглубь по дереву. Т.е. уменьшение исходного списка на n элементов выполняется за O(n) (это в худшем случае, когда одна операция схлопывания уменьшает длину списка на 1)
После схлопывания какой-либо сети, при движении назад происходит пересчёт весов родительских сетей.
Насчёт 23 маски — это любопытно. Не задумывался над этим.
Тут две разных задачи:
Оптимизация скорости выполнения скрипта
Уменьшение количества фейковых IP в результирующем списке
Первое можно существенно улучшить. Второе уже на пределе, если только не получится как-то учитывать нулевые хосты в подсетях. Даже если получится, мне кажется, это особого уменьшения количества фейковых IP не даст.
Мой любимый канал — Wintergatan Wednesdays. Швед с понятным английским, перфекционист делает сложнейшую механическую «шарманку». Много САПР и ЧПУ обработки.
Буду ждать ответной статьи. У меня не решён вопрос с тем, что некоторые IP адреса на самом деле не существуют, например 192.168.0.0 — можно в эту сторону покопать. Хотя подозреваю что сильно качество это не улучшит, всё уже на пределе! Ну и на golang конечно повеселее будет работать.
А вообще, спасибо за утилиту, без неё не с чем было бы сравнивать.
P.S. А еще у Вас не принимается во внимание, что адреса со всеми нулями и единицами в номере хоста не надо учитывать в числе «лишних», т.к. в подсети их и так нет. Но это уже сложно и неоднозначно, т.к. наше искусственное объединение адресов в подсети далеко не всегда соответствует реально существующим подсетям.
Можно не учитывать адреса, последний октет которых равен нулю или 255 — таких точно нет. Подумаю.
Родительские Кв плывут потому что не учитывают, что в объединяемых записях… уже присутствует некоторое количество фиктивных IP, попавших туда «за компанию».
Учитывают. На всякий случай перепроверил код. Объём фейковых IP для каждой сети вычисляется один раз и далее используется именно это значение. Коэффициенты плывут потому-что уменьшается экономия от схлопывания — т.е. если в сети 10 реальных IP адресов и 5 из них уже схлопнуты, тогда при схлопывании мы сможем сэкономить лишь 4 записи в списке.
Любое схлопывание можно представить как операцию на исходном списке — убрали такие-то записи, вместо них добавили одну новую. Дальше мы уже работаем с новым списком, в нём нет убранных сетей а схлопнутая сеть становится одной из записей этого списка. Поэтому все коэффициенты должны быть пересчитаны.
Пример
Если мы сожмём сеть 192.168.20.0/29, тогда мы уберём 5 записей из списка, и охватим 2 дополнительных ip.
Если сожмём 192.168.20.0/30 и 192.168.20.4/30, тогда мы уберём 4 записи из списка, и охватим тоже 2 дополнительных ip адреса.
Т.е. выгоднее сжать большую сеть, поэтому у неё выше коэффициент.
Если я правильно вас понял, то наверно нет, эффективно сжать список доменов не получится. Проблема в том что мы не знаем сколько поддоменов входит в домен, с IP всё проще — если это сеть /24 тогда в ней 256 IP адресов.
Рутер работает прекрасно, один раз настроил и забыл. Я остановился на списке из 30 000 сетей. Список хранится на raspberry, обновляется раз в час. На роутер попадает по BGP.
А насколько быстро в сравнении с родными i2c модулями, подключаемыми «паровозиком»? Сколько миллисекунд первое, сколько второе? И наверно от количества модулей тоже зависит время реакции?
В ваших i2c модулях есть пин int, подозреваю что это прерывание от устройств, т.е. реакция должна быть мгновенной. В modbus же придётся по кругу опрашивать каждое устройство, если устройств много (у меня пять i2c устройств, которые я подумываю подключить через rs485 адаптер), тогда время вообще будет неприемлемым.
Очень круто! Здорово что вы развиваетесь, главное чтобы оставалась полноценная поддержка старых устройств. Ещё раз большое спасибо за классное устройство.
Самая неприятная ситуация, в которой не хочется оказаться — это полный выход из строя контроллера в какой-нибудь праздничный день. Когда замены ждать несколько дней и непонятно как переносить настройки со сгоревшего устройства на новое. Хорошо если бы был какой-то простой способ миграции с одного wb на другой именно на такой случай.
Наверно глупый вопрос, но всё же. В wb5 никак нельзя заменить процессорный модуль на что-то помощнее?
Спасибо за ответ!
Я всегда был уверен что причина есть! Подозреваю что это из-за того что объявления побиты по городам и могут храниться в разных базах. Так? Было бы интереснее подробнее узнать про то как организовано хранилище объявлений.
Вот допустим захотел я что-то купить, при этом живу я в Пушкино а работаю в Москве. Я захожу на Авито, и начинается — включаем фильтр по Пушкино, смотрим предложения, потом по Мытищам — то же самое, по Королёву, Ивантеевке, Щёлково (они все рядом друг с другом), Москве. Я могу конечно выбрать «московская область», но предложения из Троицка меня не интересуют. При этом множественного фильтра по городам нет.
Почему его нет? Это какое-то техническое ограничение (данные так побиты что их тяжело объединить), либо считается что и так нормально?
Возможно же вообще сделать поиск товаров в радиусе N километров. Есть такое в планах?
При этом мне нужен максимальный вес в корневом элементе — т.е. всё-равно нужно пробрасывать его в корень.
Ветвь создаётся только при добавлении IP из исходного списка. Наверно мы имеем что-то около log2(n) * n узлов в дереве, где n — это размер исходного списка.
«стрелочка» (наибольший вес в поддереве) в родительских элементах тоже пересчитывается при движении назад. Более того, если при движении назад мы видим что есть ещё одна сеть с таким же весом, как только-что сжатая, мы сразу же начинаем сжимать её, не возвращаясь к корневому элементу.
«наибольший вес в поддереве» для корневого узла означает наибольший вес во всём дереве.
Это не так. У нас бинарное дерево (ну, нечто наподобие), причём с максимальной глубиной, равной 32. Добавление одного нового IP происходит максимум за 32 операции. При этом создаётся ровно одна псевдоподсеть. Сложность добавления нового элемента можно принять за O(n).
Большую часть времени работы скрипта занимает схлопывание сетей. Коэффициенты выгодности и так хранятся в каждом узле и пересчитываются только при изменении дочерних сетей.
При схлопывании также не нужно перебирать все сети — каждый узел имеет «стрелочку» в каком направлении находится узел с максимальным весом. Добраться до него также можно за 32 шага вглубь по дереву. Т.е. уменьшение исходного списка на n элементов выполняется за O(n) (это в худшем случае, когда одна операция схлопывания уменьшает длину списка на 1)
После схлопывания какой-либо сети, при движении назад происходит пересчёт весов родительских сетей.
Тут две разных задачи:
Первое можно существенно улучшить. Второе уже на пределе, если только не получится как-то учитывать нулевые хосты в подсетях. Даже если получится, мне кажется, это особого уменьшения количества фейковых IP не даст.
А вообще, спасибо за утилиту, без неё не с чем было бы сравнивать.
Тогда вес нужно считать по формуле:
weight = (in_list_records_count — 1) / net_extra_ip_volume_delta
Запилю фикс.
Можно не учитывать адреса, последний октет которых равен нулю или 255 — таких точно нет. Подумаю.
Учитывают. На всякий случай перепроверил код. Объём фейковых IP для каждой сети вычисляется один раз и далее используется именно это значение. Коэффициенты плывут потому-что уменьшается экономия от схлопывания — т.е. если в сети 10 реальных IP адресов и 5 из них уже схлопнуты, тогда при схлопывании мы сможем сэкономить лишь 4 записи в списке.
Если мы сожмём сеть 192.168.20.0/29, тогда мы уберём 5 записей из списка, и охватим 2 дополнительных ip.
Если сожмём 192.168.20.0/30 и 192.168.20.4/30, тогда мы уберём 4 записи из списка, и охватим тоже 2 дополнительных ip адреса.
Т.е. выгоднее сжать большую сеть, поэтому у неё выше коэффициент.
В ваших i2c модулях есть пин int, подозреваю что это прерывание от устройств, т.е. реакция должна быть мгновенной. В modbus же придётся по кругу опрашивать каждое устройство, если устройств много (у меня пять i2c устройств, которые я подумываю подключить через rs485 адаптер), тогда время вообще будет неприемлемым.
Самая неприятная ситуация, в которой не хочется оказаться — это полный выход из строя контроллера в какой-нибудь праздничный день. Когда замены ждать несколько дней и непонятно как переносить настройки со сгоревшего устройства на новое. Хорошо если бы был какой-то простой способ миграции с одного wb на другой именно на такой случай.
Наверно глупый вопрос, но всё же. В wb5 никак нельзя заменить процессорный модуль на что-то помощнее?
Я всегда был уверен что причина есть! Подозреваю что это из-за того что объявления побиты по городам и могут храниться в разных базах. Так? Было бы интереснее подробнее узнать про то как организовано хранилище объявлений.
Почему его нет? Это какое-то техническое ограничение (данные так побиты что их тяжело объединить), либо считается что и так нормально?
Возможно же вообще сделать поиск товаров в радиусе N километров. Есть такое в планах?