Разумный размер дерева и словаря

Question

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

Мне просто интересно, существует ли теоретический или практический предел, при котором размер дерева становится слишком большим или точка, в которой словарь становится слишком заполненным столкновением, чтобы функционировать правильно/быстро?

Общий ответ будет оценен, но C# -специфическая информация будет намного лучше!

Answer 1

В .NET максимальный либо в Дереве, либо в Словаре составляет 2^31 - 1 (и, вероятно, несколько меньше с накладными расходами).

В практическом плане у вас, вероятно, раньше не хватило памяти!

Если дерево остается сбалансированным, поиск будет оставаться ок. O (log N).

Словари более чувствительны к используемому алгоритму, например, существует множество схем хэширования с различными характеристиками.

Answer 2

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

Дерево будет замедляться по мере роста, в зависимости от вашей техники хранения и перебалансировки.

Словарь должен быть достаточно последовательным, но обязательно создайте его с размером, соответствующим количеству данных, которое вы, вероятно, будете хранить (может быть, x2 будет безопасным).

Answer 3

См this question - это один из первых я ответил на так :)

Проблема была низкая производительность построения словаря с приблизительно 900 000 пунктов. Я получил время от 10 + до 0,34 секунды.

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

Надеется, что это помогает,

EDIT:

класс Сравнения не важен, .net строки имеют очень сильную хэш-функцию и - следовательно - имеют отличную производительность в словарях. Эта проблема парней просто «ушла», если бы он использовал одиночные строки вместо пар строк.