0

それで、これが取引です。(私の現在のユースケースは C# ですが、一般的なアルゴリズムのケースにも興味があります) オブジェクトの 2 つの配列が与えられます (残念ながら、これらの配列を作成するコードを変更することはできません)。各オブジェクトには (その一部として) .Name プロパティ、つまり文字列があります。これらの文字列はオブジェクトごとに一意であり、他のオブジェクトに一致する文字列が 0 個または 1 個あります。私がする必要があるのは、その文字列に基づいてこれらのオブジェクトを効率的にペアリングし、ペアリングされたオブジェクトにアクセスできる何らかのコレクションにすることです。一致と見なされるには文字列が正確に一致する必要があるため、Upper や CaseInsensitive などは必要ありません。残念ながら、これらのリストはソートされていません。リスト自体はおそらく 30 ～ 50 個のアイテムですが、これらの数千の配列ペアに対してアルゴリズムを繰り返し実行する必要があるため、効率が重要です。

0 または 1 つの一致があることがわかっており、それらのほとんどが 1 つの一致になることがわかっているので、x*y (x の foreach アイテム、y の foreach アイテム、x=y の場合) よりも効率的なアルゴリズムがあるように感じます。 x と y は一致します)

最も可能性の高いオプションは次のとおりだと思います。

並べ替えられていないリストを保持し、x*y を実行しますが、アイテムが見つかったらリストから削除するため、既に見つかったアイテムはチェックしません。OR: 両方を辞書に変換し、それぞれに対してインデックス付きルックアップを実行します (array2 [currentArray1Item]) OR: リストを自分で並べ替え (Array.Sort())、並べ替えられた配列を使用して、B のインデックスにジャンプするなどの賢い操作を行うことができます (A のどこにいても) ）そして、文字列が見つかるか、あるべき場所を通過するまで、文字列に基づいて上下に移動します。

それが完了したら、それを格納する方法を理解する必要があります。オブジェクト A と B だけを保持するカスタム ObjectPair クラスを作成できると思います。ペアで ForEach を実行するだけなので、ここでは特別なことをする必要はありません。 .

質問は次のとおりです。上記のアルゴリズムのいずれかがこれを行うための最速の方法ですか (そうでない場合は何ですか?)、見つかったペアを便利に保持する既存の C# 構造はありますか?

編集: Array.Sort() は存在するメソッドであるため、配列を List に変換して並べ替える必要はありません。知っておくと良い。上記を更新しました。

4

2 に答える 2

3

私が持っている質問は、両方の入力配列をソートする必要がある場合、特別な処理からどれだけの効率が得られるかということです。Array.Sortのドキュメントによると、平均O(n log n)しO(n ^ 2)て最悪の場合（クイックソート）です。両方の配列を並べ替えるとO(n)、最初の配列をループする必要があるため、別の作業量が発生します。

これは、ソートしてから処理するために必要な反復回数のために、全体的な作業量が実際に増加する可能性があることを意味すると解釈します。もちろん、最初にソートされた配列を保証できれば、これは別の話になりますが、あなたが言ったように、それはできません。（プロパティを使用することを認識できるようにIComparer<T>、渡すカスタム実装を作成する必要があることにも注意する必要があります。これは実行時の作業ではありませんが、引き続き機能します:-)Array.Sort.Name

LINQ結合の使用を検討することもできます。これは、内部配列を1回だけ反復します（疑似コードについては、ここを参照してください）。foreachこれは、外部配列の各要素に対して内部配列を反復するネストされたステートメントとは対照的です。これは、一般的な場合とほぼ同じくらい効率的であり、提案した特別な処理の複雑さをもたらすものではありません。

実装例は次のとおりです。

var pairs =
    from item1 in array1
    join item2 in array2 on item1.Name equals item2.Name
    select new { item1, item2 };

foreach(var pair in pairs)
{
    // Use the pair somehow
}

これは、データで何をしているのかを非常に明確に示しており、各ペアを表す匿名型も提供します（したがって、ペアを作成する必要はありません）。もしあなたが別のルートに行くことになった場合、私はそれがこのアプローチとどのように比較されるかに興味があります。

于 2012-06-18T17:48:11.603 に答える
1

メソッドを使用して2番目の配列を並べ替えてから、を使用しArray.Sortて2番目のオブジェクトを照合します。ArrayBinary Search Algorithm

一般に、30〜50のアイテムの場合、これはブルートフォースx*yよりも少し速くなります。

于 2012-06-18T16:29:10.550 に答える