SkipList <T> vs Словарь <TKey,TValue>

Question

Я читал о пропущенных списках в последнее время.

У меня есть веб-приложение, которое выполняет довольно сложные запросы Sql против статических наборов данных.

Я хочу реализовать систему кеширования, посредством которой я сгенерирую хэш-запрос md5 запроса sql, а затем возвращу кешированный набор данных для запроса, если он существует в коллекции.

Какой алгоритм будет лучше, словарь или SkipList? Зачем?

http://msdn.microsoft.com/en-us/library/ms379573%28VS.80%29.aspx#datastructures20_4_topic4

Answer 1

Dictionary, определенно. По двум причинам:

• Dictionary<TKey, TValue> использует хэш-таблицу, что делает извлечения O (1) (т.е. постоянная времени), по сравнению с O (журнал п) в списке пропуска.

• Dictionary<TKey, TValue> уже существует и проверен и оптимизирован, в то время как класс списка пропуска не существует, насколько мне известно, поэтому вам нужно будет реализовать свои собственные, что потребует усилий для правильного и тщательного тестирования.

потребление памяти примерно одинакова для обоих (конечно же, сложность, а именно О (п )).

Answer 2

Причина, по которой вы использовали бы SkipList<T> vs Dictionary<TKey,TValue>, заключается в том, что список пропусков сохраняет свои позиции в порядке. Если вам регулярно нужно перечислять элементы по порядку, список пропусков хорош, потому что он может перечислить в O (n).

Если вы хотите, чтобы иметь возможность перечислить в порядке, но не все равно, если перечисление О (п Л.Г. п), SortedSet<T> (или скорее SortedDictionary<TKey, TValue>) будет то, что вы хотите, потому что они используют красно- черные деревья (сбалансированные двоичные деревья), и они уже находятся в стандартной библиотеке.

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

Answer 3

Пропустить Список дает среднее значение Log (n) для всех операций со словарем. Если количество элементов фиксировано, то таблица с хэш-листом, заблокированная блокировкой, отлично справится. В игровом дереве памяти также хорошо, так как кеш - это слово. Деревья Splay дают быстрее для недавно доступного элемента. Как таковой в операции словаря, такой как find; [списки пропусков были медленными по сравнению с деревом, которые снова были медленными по сравнению с хэш-таблицами.] [1] [1]: http://harisankar-krishnaswamy.blogspot.in/2012/04/skip-list-runtime-on-dictionay.html

Если требуется локализация в структуре данных, то могут быть полезны списки пропусков. Например, поиск рейсов по дате и т. Д. Но кэш находится в памяти, поэтому проигрыш в порядке. Hashtable и деревья splay не обеспечивают локализацию.