C # Двоичные деревья и словари

Question

Я борюсь с понятием, когда использовать бинарные деревья поиска, а когда использовать словари.

В своем приложении я провел небольшой эксперимент, в котором использовалась библиотека C5 TreeDictionary (которую я считаю красно-черным двоичным деревом поиска) и словарь C #. Словарь всегда был быстрее при операциях добавления / поиска, а также всегда занимал меньше места в памяти. Например, при 16809 <int, float> записях словарь использовал 342 КиБ, в то время как дерево использовало 723 КиБ.

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

Также, в качестве дополнительного вопроса, кто-нибудь знает, существует ли более быстрая + более эффективная структура памяти для хранения пар <int, float> для доступа к словарному типу, чем любая из упомянутых структур?

Answer 1

Я думал, что BST должны быть более эффективным с точки зрения памяти, но кажется что один узел дерева требует больше байтов, чем одна запись в толковый словарь. Что дает? Есть ли Точка, в которой 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) времени, что означает, что для очень длинных строк может потребоваться значительное время. С одной стороны, сравнение строк на неравенство почти всегда быстрее, чем хеширование, поскольку может потребоваться просмотр только первых нескольких символов. Вполне возможно, что вставка в дерево будет быстрее вставки в словарь, если оценка хеш-кода занимает слишком много времени.

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

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

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

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

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

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

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

Answer 2

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

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

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

---

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

Answer 3

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

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

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

Answer 4

Сбалансированный 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 байтов.

Answer 5

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

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

Answer 6

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

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

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