SkipList <T> vs Słownik <TKey,TValue>

Question

Czytałem ostatnio o listach pomijania.

Mam aplikację internetową, która wykonuje dość złożone kwerendy SQL przeciwko statycznym zbiorom danych.

Chcę zaimplementować system buforowania, za pomocą którego generuję hash md5 zapytania sql, a następnie zwracam buforowany zestaw danych dla zapytania, jeśli istnieje on w kolekcji.

Który algorytm będzie lepszy, Słownik lub lista kontrolna? Czemu?

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

Answer 1

Dictionary, zdecydowanie. Z dwóch powodów:

• Dictionary<TKey, TValue> wykorzystuje tabeli mieszania, co pobierania O (1) (to jest stałą czasową), w porównaniu do O (log n) na liście pominięcia.

• Dictionary<TKey, TValue> już istnieje i jest dobrze przetestowany i zoptymalizowany, podczas gdy klasa listy pominięć nie istnieje zgodnie z moją wiedzą, więc musiałbyś zaimplementować swój własny, co wymaga wysiłku, aby go dobrze i przetestować dokładnie.

wymagania dotyczące pamięci są w przybliżeniu takie same dla obu (oczywiście samo trudność, a mianowicie O (n)).

Answer 2

Powodem, dla którego warto użyć SkipList<T> w stosunku do Dictionary<TKey,TValue> jest to, że lista pominięć utrzymuje pozycje w kolejności. Jeśli regularnie trzeba wyliczyć elementy w kolejności, lista pominięć jest dobra, ponieważ może wyliczyć w O (n).

Jeśli chcesz być w stanie wyliczyć w porządku, ale nie obchodzi mnie, czy wyliczenie jest O (n lg n), A SortedSet<T> (lub bardziej prawdopodobne SortedDictionary<TKey, TValue>) byłoby to, czego chcesz, ponieważ korzystają one red- czarne drzewa (zrównoważone drzewa binarne) i są już w standardowej bibliotece.

Ponieważ jest bardzo mało prawdopodobne, że będziesz chciał zliczyć pamięć podręczną w kolejności (lub w ogóle), lista pominięć (i podobnie jak drzewo binarne) jest niepotrzebna.

Answer 3

Lista pomijania przedstawia średnią log (n) dla wszystkich operacji słownika. Jeśli liczba elementów jest ustalona, ​​to tablica haszowana z blokadą będzie świetna. Drzewo zapisu w pamięci jest również dobre, ponieważ pamięć podręczna to słowo. Rozgałęzione drzewa dają szybciej dostęp do ostatnio dostępnego przedmiotu. Jako takie w operacji słownikowej, takiej jak find; [listy pomijane były powolne w porównaniu do drzewa odtwarzania, które znów były powolne w porównaniu do tablic mieszających.] [1] [1]: http://harisankar-krishnaswamy.blogspot.in/2012/04/skip-list-runtime-on-dictionay.html

Jeśli potrzebna jest lokalizacja w strukturze danych, przydatne mogą być listy pomijania. Na przykład, znalezienie lotów wokół daty itp. Ale pamięć podręczna jest w pamięci, więc gra jest w porządku. Hashtable i splay drzewa nie zapewniają lokalizacji.