0

これはアルゴリズムの問​​題です。

私は持っていDictionary<object,Queue<object>>ます。各キューには、1つ以上の要素が含まれています。ディクショナリから要素が1つしかないすべてのキューを削除したいと思います。それを行うための最速の方法は何ですか？

擬似コード：foreach(item in dict) if(item.Length==1) dict.Remove(item);

ループでそれを行うのは簡単です（もちろん、foreachではありません）が、ここではどちらのアプローチが最速か知りたいです。

必要な理由：その辞書を使用して、オブジェクトの大規模なセットで重複する要素を検索します。辞書のキーはオブジェクトのハッシュの一種であり、値は同じハッシュで見つかったすべてのオブジェクトのキューです。複製のみが必要なので、関連付けられたキューに1つのオブジェクトがあるすべてのアイテムを削除する必要があります。

アップデート：

通常の場合、オブジェクトの大規模なセットにわずかな重複があることを知っておくことが重要な場合があります。1％以下としましょう。したがって、辞書をそのままにして、最初の辞書から選択した要素だけを使用してスクラッチから新しい辞書を作成し、最初の辞書を完全に削除する方が速い場合があります。特定のアルゴリズムで使用される計算辞書クラスのメソッドの複雑さに依存すると思います。

この問題を理論的なレベルで見たいと思っています。教師として生徒と話し合いたいからです。本当に簡単だと思うので、具体的な解決策は自分で提供しませんでした。問題は、どちらのアプローチが最良で、最速かということです。

4

3 に答える 3

2 
var itemsWithOneEntry = dict.Where(x => x.Value.Count == 1)
                            .Select(x => x.Key)
                            .ToList();

foreach (var item in itemsWithOneEntry) {
    dict.Remove(item));
}
于 2012-11-22T12:32:37.623 に答える
1

コレクションのトラバースを最適化しようとする代わりに、コレクションのコンテンツを最適化して、重複のみが含まれるようにするのはどうでしょうか。これには、代わりにコレクションアルゴリズムを次のようなものに変更する必要があります

var duplicates = new Dictionary<object,Queue<object>>;
var possibleDuplicates = new Dictionary<object,object>();
foreach(var item in original){
    if(possibleDuplicates.ContainsKey(item)){
       duplicates.Add(item, new Queue<object>{possibleDuplicates[item],item});
       possibleDuplicates.Remove(item);
    } else if(duplicates.ContainsKey(item)){
       duplicates[item].Add(item);
    } else {
       possibleDuplicates.Add(item);
    }
}
于 2012-11-22T13:50:40.013 に答える
0

コードを実際に必要以上に複雑にする前に、現実的なシナリオでパフォーマンスに対するこれの影響を測定する必要があることに注意してください。想像されるほとんどのパフォーマンスの問題は、実際にはスローコードの本当の原因ではありません。

ただし、長さ1のキューの線形検索を回避することで速度の利点が得られることがわかった場合は、インデックス作成と呼ばれる手法を使用してこの問題を解決できます。

すべてのキューを含むディクショナリと同様に、長さ1のキューのみを含むインデックスコンテナ（おそらく別のディクショナリ）を維持するため、必要な場合はすでに個別に使用できます。

これを行うには、キューの長さを変更するすべての操作を拡張して、インデックスコンテナを更新するという副作用が発生するようにする必要があります。

これを行う1つの方法は、クラスを定義することですObservableQueue。これは、キュー内のアイテムの数が変更されたときに発生するイベントQueueもあることを除いて、薄いラッパーになります。プレーンの代わりにどこでもContentsChanged使用してください。ObservableQueueQueue

次に、新しいキューを作成するときにContentsChanged、キューにアイテムが1つしかないかどうかを確認するハンドラーをそのイベントに参加させます。これに基づいて、インデックスコンテナに挿入または削除できます。

于 2012-11-22T12:47:12.537 に答える