SkipList<T> против словаря<TKey, TValue>

Question

В последнее время я читаю о Skip Lists.

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

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

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

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

Answer 1

Dictionaryопределенно Две причины:

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

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

Потребление памяти примерно одинаково для обоих (безусловно, одинаковой сложности, а именно O(n)).

Answer 2

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

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

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

Answer 3

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

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