7

「脱交差」と思われることをしようとしています (適切な名前が何であるかはわかりませんが、EpicGames の Tim Sweeney が古い UnrealEd で呼んだものです)

// foo and bar have some identical elements (given a case-insensitive match)
List‹string› foo = GetFoo();
List‹string› bar = GetBar();

// remove non matches
foo = foo.Where(x => bar.Contains(x, StringComparer.InvariantCultureIgnoreCase)).ToList();
bar = bar.Where(x => foo.Contains(x, StringComparer.InvariantCultureIgnoreCase)).ToList();

その後、元のデータから結果を差し引いて、どの要素を削除したかを確認します。.Except() を使用すると超高速なので、問題はありません。

どちらのリストにも (文字列の) ~30,000 の要素があると、これはかなりパフォーマンスが悪いため、これを行うためのより高速な方法が必要です。できれば、このステップとその後のステップを一気に行う方法が望ましいでしょう。.Contains() の代わりに .Exists() を使用してみましたが、少し遅くなります。少し太い気がしますが、.Except() と .Intersect() および/または .Union() の組み合わせで可能になると思います。

4

5 に答える 5

6

この操作は、対称差分と呼ぶことができます。

ハッシュ テーブルのような別のデータ構造が必要です。それに両方のセットの交点を追加してから、各セットの交点を差します。

アップデート：

これをコードで試す時間が少しありました。HashSet<T>2 から 10 文字の長さの 50,000 個の文字列のセットを使用して、次の結果を得ました。

オリジナル：79499ミリ秒

ハッシュセット: 33 ミリ秒

ところで、HashSet にはメソッドが呼び出されSymmetricExceptWith、それが機能すると思っていましたが、実際には両方のセットの異なる要素が、メソッドが呼び出されたセットに追加されます。おそらく、最初の 2 つのセットを変更せずにそのままにしておくよりも、これが必要であり、コードはより洗練されたものになるでしょう。

コードは次のとおりです。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        // foo and bar have some identical elements (given a case-insensitive match)
        var foo = getRandomStrings();
        var bar = getRandomStrings();

        var timer = new Stopwatch();
        
        timer.Start();
        // remove non matches
        var f = foo.Where(x => !bar.Contains(x)).ToList();
        var b = bar.Where(x => !foo.Contains(x)).ToList();
        timer.Stop();

        Debug.WriteLine(String.Format("Original: {0} ms", timer.ElapsedMilliseconds));

        timer.Reset();

        timer.Start();
        var intersect = new HashSet<String>(foo);
        intersect.IntersectWith(bar);

        var fSet = new HashSet<String>(foo);
        var bSet = new HashSet<String>(bar);

        fSet.ExceptWith(intersect);
        bSet.ExceptWith(intersect);
        timer.Stop();

        var fCheck = new HashSet<String>(f);
        var bCheck = new HashSet<String>(b);

        Debug.WriteLine(String.Format("Hashset: {0} ms", timer.ElapsedMilliseconds));

        Console.WriteLine("Sets equal? {0} {1}", fSet.SetEquals(fCheck), bSet.SetEquals(bCheck)); //bSet.SetEquals(set));
        Console.ReadKey();
    }

    static Random _rnd = new Random();

    private const int Count = 50000;

    private static List<string> getRandomStrings() 
    {
        var strings = new List<String>(Count);

        var chars = new Char[10];

        for (var i = 0; i < Count; i++)
        {
            var len = _rnd.Next(2, 10);

            for (var j = 0; j < len; j++)
            {
                var c = (Char)_rnd.Next('a', 'z');
                chars[j] = c;
            }

            strings.Add(new String(chars, 0, len));
        }

        return strings;
    }
}
于 2009-03-12T23:44:58.207 に答える
3

intersect を使用すると、次のようになります。

var matches = ((from f in foo 
                select f)
              .Intersect(
                  from b in bar 
                  select b, StringComparer.InvariantCultureIgnoreCase))
于 2009-03-12T23:52:02.773 に答える
1

要素が各リスト内で一意である場合は、HashSetの使用を検討する必要があります

HashSet(T) クラスは、高性能のセット操作を提供します。セットは、重複する要素を含まず、要素が特定の順序になっていないコレクションです。

于 2009-03-12T23:47:06.313 に答える
1

ソートされたリストでは、バイナリ検索を使用できます。

于 2009-03-19T02:15:10.467 に答える
0

リストの内容は O(N) 操作です。ソートされたリストや Dictionary などの別のデータ構造を使用すると、時間を大幅に短縮できます。ソートされたリスト内のキーへのアクセスは、通常 O(log N) 時間であり、ハッシュでは通常 O(1) 時間です。

于 2009-03-12T23:45:25.990 に答える