0

次のような単純な「キャッシュ」インフラストラクチャがあります。

Dictionary<string, object> cache = new Dictionary<string, object>();

(objectここでは値の型として使用していますが、実際にはより具体的な型です。)

アイデアは、多くの計算された値 (実際には、SQL データベースからの結果) を tis ディクショナリに名前で格納することです。ほとんどの場合、単一の要素に対して、高速の挿入と取得を行う必要があります。

使用してみると、特定の文字列で始まるすべてのエントリを削除して、一部のエントリを無効にする必要がある場合があることがわかりました。私の素朴な実装は次のようになります。

cache.Keys.Where(key => key.StartsWith(name)).ToList().ForEach(cache.Remove);

おそらく最善の解決策ではないことを知っているので、.NET Framework を調べて、これをより効率的に実行できるデータ構造を探しています。

よりも適したクラスはありDictionary<>ますか?

4

2 に答える 2

1

文字列の先頭に対応する要素を見つける必要がある場合は、Trieを検討してください。これは事実上、各頂点に文字があるグラフ (ツリー) です。コードは、文字列の最初の文字を含むルートの 1 つからグラフをたどり、対応する 2 番目のノードを持つリンクされたノードに移動します。

基本クラス ライブラリで提供される実装はありません。サンプルの実装については、 http: //geekyisawesome.blogspot.com.au/2010/07/c-trie.htmlを参照してください。

于 2012-09-13T13:46:27.333 に答える
0

akton が言ったように、トライはおそらくぴったりです。フレームワーク クラスに固執する場合は、次の選択肢があります。

  • 辞書: X で始まる O(1) 挿入、O(1) 検索、O(n) 削除要素
  • SortedList: O(log(n)) 個の挿入、O(log(n)) 個の検索、O(n) 個の X で始まる要素の削除 (削除された要素の数が要素の総数に比べて少ないと仮定)。
于 2012-09-13T13:48:40.297 に答える