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

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

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

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

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

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

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

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

Answer 2

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

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

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

---

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

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

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

Answer 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 байтов.