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

Question

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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