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

V>>А там разве не рекурсия?
V>>(руки не дошли взять полный код, пока справшиваю словами)
S>Неа. Там цепочка типов. Внизу лежит LeafNode<int>, над ними — BranchNode<LeafNode<int>, int>, над ними — BranchNode<BranchNode<LeafNode<int>, int>, int>, и так далее.

Тогда на верхнем уровне в любом случае виртуальность.


V>>В крайнем случае это можно сделать ручками, но при малой фактической вложенности (единицы десятков, те самые 20-30 максимум) смысла обычно нет.
V>>И да, я когда-то более 15 лет назад сравнивал бинарные деревья с N-арными, ну вот 2-4 элемента в узле давали максимум производительности, т.е. увеличение кол-ва элементов в узле ничего не давало. Гораздо больше дал кастомный аллокатор узлов, но вряд ли это поможет в случае дотнета.
S>Ну вот 16 мне дали объехать и 2, и 8 элементов.

Что странно.


V>>(Кстате, не увидел у тебя балансировки, но может не весь код смотрел)
S>Там она просто выкинута, чтобы sharplab.io не тормозил.

Попробую найти время, посмотреть на балансировку.
Точная балансировка тем дороже, чем больше арность, потому что приходится создавать более дорогие копии при каждом изменении дерева.
И еще вести учёт реально занятого кол-ва ячеек в узле.
А в бинарном дереве ячека содержит ровно одно значение, никакого учёта.


V>>Еще, если заменить в твоей реализации _dataX на inplace-массив, то через одну константу арности можно легко менять кол-во элементов в узле, т.е. задешево сравнить сетку реализаций с отличающейся арностью.
S>Не получится, т.к. inplace-массив бывает только встроенных типов.

Да, потом увидел, что у тебя для произвольных T.


S>Не очень понятно, как делать иммутабельный сценарий на хеш-таблице. Ведь каждая вставка должна порождать копию — а это очень дорого для мало-мальски заметных объёмов таблицы.

Ну вот как раз ради случая хеш-таблицы в хеш-таблицах всё и затевалось.
Capacity каждой хеш-таблицы относительно невелик (23, 19, 17, 13, 11), пересоздавать при изменении достаточно одну таблицу, а не всю цепочку их до корневого узла, как оно есть в иммутабельных деревьях при балансировке.

Т.е., ввиду того, что вложенные хеш-таблицы имеют разный размер, балансировка отсутствует, т.к. такое хранилище не может выродиться в связанный список.

Эта структура всё-равно не подходит для реализации твоего упорядоченного по индексу списка, просто меня неприятно поразил сам факт проседания быстродействия в этой схеме.


S>Стандартом в наши дни является случайное подсаливание хеша. То есть в пределах запуска VM одинаковые данные получают одинаковый хеш, но после перезапуска — уже нет.
S>Всё это потому, что случайно нарваться на такое распределение данных, которое перегружает хеш, маловероятно.

В дотнетной реализации тупо происходит рост capacity с последующим перекешированием (писал про этот случай, он второй в списке), т.е. capacity таблицы может быть во многие разы больше кол-ва реальных данных.
Для небольшого кол-ва данных это приемлимо, для большого нет.

Под большие наборы данных надо писать свои хеш-таблицы.
Самый простой вариант — складывать конфликты в упорядоченный список (массив конфликтующих значений).