@hirthwork

hirthwork

Меня зовут Пить
hirthwork

Всего лишь бабочка, которой снится, что она программист

Славный отзывчивый парень © https://t.me/point_im/161357

32 я читаю 94 меня читают
5780 постов
48102 комментариев
hirthwork
25 Mar 2019

Что будет если запихнуть 6 миллионов IPv4 значений в HashSet? Большинство скажут, что будет бо-бо, потому что у хэшсета на каждую ноду оверхед в 48 байт на 64-битной машине.
Более опытные разработчики скажут, что оверхед всего 24 байта, потому что java по дефолту использует -XX:UseCompressedOops (a.k.a. -Xcompressedrefs) и при размере памяти меньше 32 ГБ на каждый указатель тратится всего 4 байта.

25 Mar 2019

ты посмотрел как работает твой trie, заплакал и взял HashSet?

25 Mar 2019

Как он работает я и так знаю (божественно). Но вот при compressed refs оно ест в два раза больше памяти чем HashSet.

#mxjau/2 в ответ на /1
25 Mar 2019

потребление памяти - это одна из характеристик критерия "работает".
а чтоб сэкономить память, не пробовал реализовывать дерево на массиве из четырёхбайтовых беззнаковых? // хотя это скорость может убить.

#mxjau/3 в ответ на /2
25 Mar 2019

У меня оно и так реализовано на одном contiguous массиве интов. Асимптотически стремится к 12 байтам на запись. Но очень медленно. На 2 миллионах айпишников тратит 79 байт на запись, а на 6 миллионах — 74 байта на запись

#mxjau/4 в ответ на /3
25 Mar 2019

можно ещё в лоб жахнуть битмап на 512 метров. хотя это больше по памяти, но может работает быстрее?
ах да, на ipv6 такое взорвётся.
кстати что будет лучше для ipv6 - hashset или trie?

#mxjau/5 в ответ на /4
25 Mar 2019

можно ещё в лоб жахнуть битмап на 512 метров

Можно. Проблема в том, что придётся дополнительные преобразования делать с Inet4Address, чтобы беззнаковый индекс получить и к тому же BitSet знаковый int принимает в качестве индекса при доступе к биту.

хотя это больше по памяти

HashSet при compressed refs занимает 400 МБ.
Trie занимает 800 МБ

но может работает быстрее?

С учётом преобразований и костылей описанных выше, это будет работать примерно с той же скоростью что и HashSet (у Inet4Address ебически хороший hashCode)

кстати что будет лучше для ipv6 - hashset или trie?

Однозначно HashSet

А trie я потом использую для задачи с которой HashSet справиться не может — поиск какой из заданных подсетей принадлежит айпишник.

#mxjau/6 в ответ на /5
25 Mar 2019

не удивлюсь, если hashCode для Inet4Address просто возвращает значение адреса.

#mxjau/7 в ответ на /6
25 Mar 2019

Именно это он и делает. И это максимально хороший хэшкод из тех что можно придумать

#mxjau/8 в ответ на /7

Добавить пост

Вы можете выбрать до 10 файлов общим размером не более 10 МБ.
Для форматирования текста используется Markdown.