С# Бинарные деревья и словари

Ответ 1

Я думал, что BST должны были быть более эффективным с точки зрения памяти, но кажется что один node дерева требует больше байтов, чем одна запись в Словарь. Что дает? Есть ли укажите, где BST лучше, чем словари?

Я лично никогда не слышал о таком принципе. Даже тем не менее, его единственный общий принцип, а не категорический факт, выгравированный в ткани Вселенной.

Как правило, словари на самом деле просто причудливая обертка вокруг массива связанных списков. Вы вставляете в словарь что-то вроде:

LinkedList<Tuple<TKey, TValue>> list =
    internalArray[internalArray % key.GetHashCode()];
if (list.Exists(x => x.Key == key))
    throw new Exception("Key already exists");
list.AddLast(Tuple.Create(key, value));

Итак, его почти O (1) операция. Словарь использует память O (internalArray.Length + n), где n - количество элементов в коллекции.

В общем случае BST могут быть реализованы как:

• связанные списки, в которых используется O (n) пространство, где n - числовые элементы в коллекции.
• массивы, в которых используется O (2 ^h - n) пространство, где h - высота дерева и n - количество элементов в коллекции.
  • Поскольку красно-черные деревья имеют ограниченную высоту O (1.44 * n), реализация массива должна иметь ограниченное использование памяти около O (2 ^1.44n - n)

Скорее всего, C5 TreeDictionary реализован с использованием массивов, что, вероятно, отвечает за потраченное пространство.

Что дает? Есть ли смысл в том, где BST лучше словарей?

Словари имеют некоторые нежелательные свойства:

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

• Оценка хэш-функции может занимать сколь угодно большой промежуток времени. Строки, например, используют Reflector для изучения метода System.String.GetHashCode - вы заметите, что хеширование строки всегда занимает время O (n), что означает, что для очень длинных строк может потребоваться значительное время. На руке сравнение строк для неравенства почти всегда быстрее, чем хэширование, так как это может потребовать взглянуть только на первые несколько символов. Его вполне возможно, если вставки дерева будут быстрее, чем словарные вставки, если оценка хэш-кода занимает слишком много времени.

  • Метод Int32 GetHashCode - это буквально просто return this, поэтому вам будет сложно найти случай, когда хэш-таблица с ключами int медленнее, чем словарь дерева.

Деревья RB имеют некоторые желательные свойства:

• Вы можете найти/удалить элементы Min и Max в O (log n), по сравнению с O (n), используя словарь.

• Если дерево реализовано как связанный список, а не массив, дерево обычно больше пространства, чем словарь.

• Аналогично, его смешно легко писать неизменные версии деревьев, которые поддерживают вставку/поиск/удаление в O (log n) времени. Словари не приспосабливаются к неизменности, так как вам нужно скопировать весь внутренний массив для каждой операции (на самом деле, я видел некоторые массивные реализации неизменяемых пальцевых деревьев, своего рода структуру данных словаря общего назначения, но реализация очень комплекс).

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

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

Ответ 2

Имеет смысл, что для дерева node потребуется больше памяти, чем запись в словаре. Бинарное дерево node должно хранить значение и как левое, так и правое поддеревья. Общий Dictionary<TKey, TValue> реализуется как хэш-таблица, которая, как я предполагаю, либо использует связанный список для каждого ведра (значение плюс один указатель/ссылка), либо какое-то переназначение (просто значение). Я должен был бы заглянуть в Reflector, чтобы быть уверенным, но для цели этого вопроса я не думаю, что это важно.

Разброс хэш-таблицы, менее эффективный с точки зрения хранения/памяти. Если вы создаете хеш-таблицу (словарь) и инициализируете ее емкость до 1 миллиона, и заполняете ее только 10 000 элементов, то я уверен, что она будет потреблять намного больше памяти, чем BST с 10 000 узлов.

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

Если возникает вопрос: "Почему вы хотите использовать двоичное дерево вместо хеш-таблицы?" Тогда лучший ответ IMO заключается в том, что бинарные деревья упорядочены, а хеш-таблицы - нет. Вы можете искать только хеш-таблицу для ключей, которые в точности равны чему-то; с деревом вы можете искать диапазон значений, ближайшее значение и т.д. Это довольно важное различие, если вы создаете индекс или что-то подобное.

Ответ 3

Мне кажется, что вы делаете преждевременную оптимизацию.

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

Если проблема с памятью/производительностью становится проблемой (что, вероятно, не будет для 20k-номеров), вы можете создать другие реализации интерфейса и проверить, какой из них работает. Вам не нужно ничего менять в остальной части кода (кроме той, которую вы используете).

Ответ 4

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

Я всегда считал, что словарь лучше для создания вещей один раз, а затем затем много поисков. Хотя Дерево было лучше, если вы его значительно модифицировали. Тем не менее, я не знаю, откуда я выбрал эту идею.

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

Ответ 5

Вы не сравниваете "яблоки с яблоками", BST предоставит вам упорядоченное представление, в то время как словарь позволяет вам выполнить поиск по паре значений ключей (в вашем случае).

Я не ожидал бы большого размера в области памяти между двумя, но словарь даст вам гораздо более быстрый поиск. Чтобы найти элемент в BST, вы (потенциально) должны пройти по всему дереву. Но для того, чтобы выполнить простейший поиск, вы просто просматриваете на основе ключа.

Ответ 6

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

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

Другая проблема в.NET заключается в том, что существует LOH, и при достаточно большом словаре вы сталкиваетесь с фрагментацией LOH. В этом случае вы можете использовать BST, заплатив цену за больший класс алгоритмической сложности.

Короче говоря, с BST, поддерживаемым кучей распределения, вы получаете время O (log (N)) для наихудшего случая, а с хеш-таблицей вы получаете время наихудшего случая O (N).

BST стоит по цене O (log (N)) среднего времени, худшей локальности кэша и большего количества кучи, но имеет гарантии задержки и защищен от атак по словарю и фрагментации памяти.

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

Что касается объема памяти, класс.NET Dictionary'2 более эффективен, так как хранит данные в виде связанного списка без кучи, в котором хранятся только данные о значениях и смещениях. BST должен хранить заголовок объекта (так как каждый узел является экземпляром класса в куче), два указателя и некоторые дополненные данные дерева для сбалансированных деревьев. Например, красно-черному дереву понадобится логическое значение, интерпретируемое как цвет (красный или черный). Это как минимум 6 машинных слов, если я не ошибаюсь. Итак, каждый узел в красно-черном дереве в 64-битной системе имеет минимум:

3 слова для заголовка = 24 байта 2 слова для дочерних указателей = 16 байтов 1 слово для цвета = 8 байтов не менее 1 слова для значения 8+ байтов = 24 + 16 +8 +8 = 56 байтов ( +8 байт, если дерево использует указатель родительского узла).

В то же время минимальный размер словарной статьи будет всего 16 байтов.