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

https://stackoverflow.com/questions/2151747

23-09-2019
|

Вопрос

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

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

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

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

Решение

Я думал, что 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.Длина + n) памяти, где n - количество элементов в коллекции.

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

связанные списки, которые используют O (n) пробел, где n - количество элементов в коллекции.
массивы, которые используют O(2^h - n) пробел, где h - высота дерева, а n - количество элементов в коллекции.
- Поскольку красно-черные деревья имеют ограниченную высоту O (1,44 * n), реализация массива должна иметь ограниченное использование памяти около O (2^1,44н - 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.Если вам нужен заказанный пакет или у вас медленно работает хэш-функция, воспользуйтесь TreeDictionary.

Другие советы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow