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

Question

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

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

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

Answer 1

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

На практике у вас, вероятно, не хватит памяти задолго до этого!

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

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

Answer 2

См. этот вопрос - это один из первых, на которые я ответил Так:)

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

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

Надеюсь, это поможет,

EDIT:

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

Answer 3

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

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

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