VD
Мне в голову один раз приходило сделать на int map или типа того.
Size: a a a
2021 March 04
VD
Заодно можно будет не аллоцировать всю память заранее даже.
JS
на расстоянии вытянутой руки, кажется, только IntMap
JS
ещё в природе есть https://en.wikipedia.org/wiki/Finger_tree
JS
Seq построен на finger tree, но обещает только логарифмические чтение и запись
VD
Смотрю на intmap и получается insert за min(n, W), где n - кол-во элементов в мапе, W - кол-во бит в int. Т.к. у меня предполагается 2^15 элементов максимум, то получается будет по W.
VD
А была бы полиморфная BitMap, то можно было было бы и Word16 заюзать для ключа и иметь W в два раза меньше.
VD
Вообще нормально, запишу себе в черную книжицу intmap на случай, если попа опять сгорит от Array.(!): invalid index.
VD
А Data.Array здравомыслящие люди получается вообще не используют или есть какие-то случаи, когда предпочтительнее чем vector?
MK
не используют
JS
Смотрю на intmap и получается insert за min(n, W), где n - кол-во элементов в мапе, W - кол-во бит в int. Т.к. у меня предполагается 2^15 элементов максимум, то получается будет по W.
min (2^15) 64 = 64
O(64) = O(1)
O(64) = O(1)
VD
По всей строгости определения O таки да, но O(16) все равно лучше O(64).
JS
А была бы полиморфная BitMap, то можно было было бы и Word16 заюзать для ключа и иметь W в два раза меньше.
возможно, имеет значение только ширина машинного слова, и делать ключ меньше машинного слова нет смысла
JS
но это неточно
VD
Ну почему ж. Если Word16 вместо Int, то в два раза больше ключей в одну и ту же память влезет.
VD
Если там еще ключи как-нибудь линейным массивом хранить, то в кеш больше влезет и будет быстрее искаться
VD
Но я не настоящий байтоёб, так что да, "это неточно".
JS
можно попробовать форкнуть IntMap, заменить там type Key = Word16 и побенчмаркать
JS
Если там еще ключи как-нибудь линейным массивом хранить, то в кеш больше влезет и будет быстрее искаться
там вроде ключи не хранятся вообще, по индексам битовые маски рассчитываются
JS
а, да, хранится общий префикс ключа