7

最近スキップリストについて読んでいます。

静的データセットに対して非常に複雑なSQLクエリを実行するWebアプリケーションがあります。

SQLクエリのmd5ハッシュを生成し、コレクションに存在する場合はクエリのキャッシュされたデータセットを返すキャッシュシステムを実装したいと思います。

辞書とスキップリストのどちらのアルゴリズムが良いでしょうか？なんで？

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

4

3 に答える 3

16

SkipList<T>vsを使用する理由Dictionary<TKey,TValue>は、スキップリストがそのアイテムを順番に保持するためです。定期的にアイテムを順番に列挙する必要がある場合は、O（n）で列挙できるため、スキップリストが適しています。

順番に列挙できるようにしたいが、列挙がO（n lg n）であるかどうかを気にしない場合は、赤黒木（バランスの取れた二分木）を使用するため、a SortedSet<T>（またはおそらくa ）が必要になります。 SortedDictionary<TKey, TValue>）そしてそれらはすでに標準ライブラリにあります。

キャッシュを順番に（またはまったく）列挙する可能性は非常に低いため、スキップリスト（および同様にバイナリツリー）は不要です。

于 2010-09-13T02:48:17.930 に答える
4

Dictionary、 絶対に。2つの理由：

  • Dictionary<TKey, TValue>ハッシュテーブルを使用して、スキップリストのO（log n ）と比較してO（1）（つまり定数時間）を取得します。

  • Dictionary<TKey, TValue>すでに存在し、十分にテストされ、最適化されていますが、スキップリストクラスは私の知る限り存在しないため、独自に実装する必要があります。これは、正しくテストして徹底的にテストするのに手間がかかります。

メモリ消費量は両方でほぼ同じです（確かに同じ複雑さ、つまりO（n））。

于 2010-09-13T01:43:14.780 に答える
1

スキップリストは、すべての辞書操作の平均Log（n）を示します。アイテムの数が固定されている場合は、ロックを取り除いたハッシュテーブルが最適です。キャッシュが単語であるため、メモリ内のスプレーツリーも適しています。スプレー木は、最近アクセスしたアイテムをより速く与えます。そのため、findなどの辞書操作では; [スキップリストは、ハッシュテーブルと比較して再び遅いスプレーツリーと比較して遅かった。] [1] [1]： http： //harisankar-krishnaswamy.blogspot.in/2012/04/skip-list-runtime-on- dictionay.html

データ構造のローカリゼーションが必要な場合は、スキップリストが役立ちます。たとえば、日付の前後のフライトを検索するなどです。ただし、キャッシュはメモリ内にあるため、スプレイは問題ありません。ハッシュテーブルとスプレーツリーはローカリゼーションを提供しません。

于 2012-04-05T20:53:05.670 に答える