4 
List1: {"123456", "432978", "321675", …}  // containing 100,000 members

List2: {"7674543897", "1234568897", "8899776644",…} // containing 500,000 members

最初の 6 桁が List1 メンバーからのものである List2 のすべてのアイテムを抽出したいので、最初の 6 桁が List1 の最初のアイテムからのものであるため、ここでは文字列「1234568897」が有効です。これを行う最速の方法は何ですか？

    foreach(string id in List1)
    {
    string result = List2.FirstOrDefault(x => x.Contains(id));
    if(result!=null)
      {
      //some works here
      }
}

これは 1000 未満のグループでは機能しますが、List2 項目が大きくなると時間がかかりすぎます

4

3 に答える 3

3

非常に効率的なEnumerable.Joinものを使用できます：

var match = from str1 in List1
            join str2 in List2
            on str1 equals (str2.Length < 6 ? str2 : str2.Substring(0, 6))
            select str2;

デモ

編集

@Oleksandr Pshenychnyy は、このような大きなコレクションでは非常に遅くなると想定していたため、list1 に 100000 個のランダムな文字列があり、list2 に 500000 個の文字列があり、質問と同じ範囲のデモがあります。ideone では 600 ミリ秒で実行されます。

http://ideone.com/rB6LU4

于 2013-03-06T11:51:44.267 に答える
0

必要なものを実装する最も効率的な方法は、リスト 2 の新しい要素を動的に処理する必要がある場合、 Aho-Corasickのアルゴリズムです。これは、文字列検索アルゴリズムで一般的に使用される手法であるプレフィックス ツリーに基づいています。これらのアルゴリズムは、O（すべての文字列の長さの合計）の複雑さを提供します

もう 1 つのオプションはKnuth-Morris-Prattアルゴリズムです。これは同じ複雑さを提供しますが、最初は検索する単一の文字列で動作します。

しかし、問題がなければO((list2.Count*log(list2.Count) + list1.Count*log(list1.Count))*AverageStrLength)、簡単な実装を提案できます: 両方のリストを並べ替えます。次に、それらを同時に進み、一致を選択します。

更新:既にリストをソートしている場合、この実装は問題ありません。その後、約 100ms で実行されます。しかし、並べ替え自体に 3.5 秒かかるため、最初は思ったほど実装がうまくいきませんでした。単純な実装に関しては、Tim のソリューションの方が高速です。

list1.Sort();
list2.Sort();
var result = new List<string>();
for(int i=0, j=0; i<list1.Count; i++)
{
    var l1Val = list1[i];
    for (; j < list2.Count && string.CompareOrdinal(l1Val, list2[j]) > 0; j++) ;
    for (; j < list2.Count && list2[j].StartsWith(l1Val); j++)
    {
        result.Add(list2[j]);
    }
}

これは、私が提案できる最も単純で効率的な実装です。

于 2013-03-06T12:21:26.267 に答える
0

実行しているハードウェアに大きく依存します。ただし、時期尚早の最適化に取り組んでいる可能性があります。単純にブルートフォースするだけで十分速いかもしれません。500,000 * 100,000 が比較の最大数です (つまり、何も一致しない場合)。合理的なスペックのデスクトップ PC では、それほど時間はかかりません。

目的に対して遅すぎることがわかった場合は、パフォーマンスを改善するために使用できるいくつかの手法があります。

  1. それを並列化します。これは、マルチコア ハードウェアでのみ大きな利点を示します。基本的には、List2 からの数値を、List1 での一致の検索を実行するスレッドに供給するディスパッチャー クラスが必要です。タスク並列ライブラリを参照してください。

  2. 賢くすることで比較の数を減らします。コレクションの事前分析を行って、比較ステップの特性を改善します。たとえば、List1 の項目を「バケット」のリストに入れます。各バケットには、最初の 2 つの数字が同じすべてのシーケンスが含まれます。たとえば、バケット 1 には "00" で始まるものが含まれ、バケット 2 には "01" などが含まれます。実際に比較を行う場合は、少数の文字列を比較するだけで済みます。あなたの例から、「1234568897」の場合、「12」のバケットをチェックすると、そのバケット内の文字列と完全な文字列比較を行うだけでよいことがわかります。

この種の前処理により、実際には処理が遅くなる可能性があるため、コードを確実にプロファイリングするようにしてください。

于 2013-03-06T12:05:00.183 に答える