Здравствуйте, netch80, Вы писали:

S>>>Скорости всегда мало — представь что запросов миллионы в секунду. И каждый IP нужно как-то обработать. Естественно нейтивно поддерживаемый процессором тип будет на порядки быстрее.
N>ChatGPT такой ChatGPT
N>Этот ответ не учитывает, что поиск по такой памяти чудовищно дорогой по энергии.
Я процитировал не полный ответ, про энергозатратность в ответе говориться.

BFE>>От себя добавлю, что если для поиска использовать B-Tree с ключом в байт, то разница между 8-байтовым адресом и 16 байтовым адресом будет всего 8 операций сложения и 8 операций сравнения, что не выглядит чем-то из-за чего стоит переживать.
N>Что-то очень странное и неадекватное говоришь.
N>Во-первых, в B-Tree ключи используются полной длины. Ты с Trie не перепутал? Там частичные ключи таки структурированы мелкими порциями, по биту или байту.
В B-Tree не обязательно хранить копии ключей, если для спуска на следующий уровень достаточно части.
ChatGPT называет похожую структуру Multibit Trie. Да, наверное так правильнее, так как в B-Tree для коротких префиксов будут храниться пустые поля, что не имеет смысла...

N>Во-вторых, 8 дополнительных лукапов на скорости нормального современного магистрального раутера могут уложиться в доступные временны́е рамки только при определённых ограничениях,
8 дополнительных шагов потребуются, если ключ разбивать по 8 бит и всего два шага, если ключ разбивать по 32 бита. Разница будет в скорости перестройки дерева при изменении таблицы маршрутизации.

N>из которых чуть ли не первое это неиспользование DRAM. Возьми ценник на память, умножь на 10 (объективно за счёт того, что на 1 бит не 1 транзистор, а почти десяток) и ещё на 3 (накрутка производителя раутера), посмотри, сколько её нужно на современные потребности (меньше 128MB не рассматриваем) и оцени, сколько нефти придётся выложить провайдеру на такую железяку.
N>И тогда пролетавшие тут рядом цены типа 47 миллионов деревянных перестают удивлять.

А какую задачу мы обсуждаем? Диспетчеризацию магистрального роутера или же поиск по IP-адресам из черного списка? У этих задач ведь немного разные требования ?

Цена в 47 миллионов меня не удивляет, так как товар специфичный и мелкосерийный.
И вообще, в чём сложность алгоритма для магистрального маршрутизатора? Сколько у такого маршрутизатора подключений ? сотня? две сотни? в чём алгоритмическая сложность разбить 128 битное данное на 200 выходов?