11

2つのソートされた整数配列の共通部分を見つけて、それを非常に高速に実行する必要があります。

現在、次のコードを使用しています。

int i = 0, j = 0;

while (i < arr1.Count && j < arr2.Count)
{
    if (arr1[i] < arr2[j])
    {
        i++;
    }
    else
    {
        if (arr2[j] < arr1[i])
        {
            j++;
        }
        else 
        {
            intersect.Add(arr2[j]);
            j++;
            i++;
        }
    }
}

残念ながら、すべての作業を行うには数時間かかる場合があります。

それをより速くする方法は？SIMD命令が使用されているこの記事を見つけました。.NETでSIMDを使用することは可能ですか？

についてどう思いますか：

http://docs.go-mono.com/index.aspx?link=N:Mono.Simd Mono.SIMD

http://netasm.codeplex.com/ NetASM（asmコードを管理対象に挿入）

およびhttp://www.atrevido.net/blog/PermaLink.aspx?guid=ac03f447-d487-45a6-8119-dc4fa1e932e1のようなもの

 

編集：

私が数千と言うとき、私は（コードで）フォローすることを意味します

for(var i=0;i<arrCollection1.Count-1;i++)
{
    for(var j=i+1;j<arrCollection2.Count;j++)
    {
        Intersect(arrCollection1[i],arrCollection2[j])  
    }
}
4

5 に答える 5

10

アップデート

私が得た最速は、安全でないバージョン（コードの最後の部分）で、サイズが10milの配列で200ミリ秒でした。

私が行ったテスト：

var arr1 = new int[10000000];
var arr2 = new int[10000000];

for (var i = 0; i < 10000000; i++)
{
    arr1[i] = i;
    arr2[i] = i * 2;
}

var sw = Stopwatch.StartNew();

var result = arr1.IntersectSorted(arr2);

sw.Stop();

Console.WriteLine(sw.Elapsed); // 00:00:00.1926156

完全な投稿:

私はそれを行うためにさまざまな方法をテストしましたが、これが非常に優れていることがわかりました。

public static List<int> IntersectSorted(this int[] source, int[] target)
{
    // Set initial capacity to a "full-intersection" size
    // This prevents multiple re-allocations
    var ints = new List<int>(Math.Min(source.Length, target.Length));

    var i = 0;
    var j = 0;

    while (i < source.Length && j < target.Length)
    {
        // Compare only once and let compiler optimize the switch-case
        switch (source[i].CompareTo(target[j]))
        {
            case -1:
                i++;

                // Saves us a JMP instruction
                continue;
            case 1:
                j++;

                // Saves us a JMP instruction
                continue;
            default:
                ints.Add(source[i++]);
                j++;

                // Saves us a JMP instruction
                continue;
        }
    }

    // Free unused memory (sets capacity to actual count)
    ints.TrimExcess();

    return ints;
}

さらに改善するためにints.TrimExcess();、 を削除することもできます。これも大きな違いになりますが、そのメモリが必要になるかどうかを検討する必要があります。

また、交差点を使用するループを中断する可能性があり、結果を配列/リストとして保持する必要がないことがわかっている場合は、実装を反復子に変更する必要があります。

public static IEnumerable<int> IntersectSorted(this int[] source, int[] target)
{
    var i = 0;
    var j = 0;

    while (i < source.Length && j < target.Length)
    {
        // Compare only once and let compiler optimize the switch-case
        switch (source[i].CompareTo(target[j]))
        {
            case -1:
                i++;

                // Saves us a JMP instruction
                continue;
            case 1:
                j++;

                // Saves us a JMP instruction
                continue;
            default:
                yield return source[i++];
                j++;

                // Saves us a JMP instruction
                continue;
        }
    }
}

もう 1 つの改善点は、安全でないコードを使用することです。

public static unsafe List<int> IntersectSorted(this int[] source, int[] target)
{
    var ints = new List<int>(Math.Min(source.Length, target.Length));

    fixed (int* ptSrc = source)
    {
        var maxSrcAdr = ptSrc + source.Length;

        fixed (int* ptTar = target)
        {
            var maxTarAdr = ptTar + target.Length;

            var currSrc = ptSrc;
            var currTar = ptTar;

            while (currSrc < maxSrcAdr && currTar < maxTarAdr)
            {
                switch ((*currSrc).CompareTo(*currTar))
                {
                    case -1:
                        currSrc++;
                        continue;
                    case 1:
                        currTar++;
                        continue;
                    default:
                        ints.Add(*currSrc);
                        currSrc++;
                        currTar++;
                        continue;
                }
            }
        }
    }

    ints.TrimExcess();
    return ints;
}

要約すると、最も大きなパフォーマンス ヒットは if-else でした。それをスイッチケースに変えると、大きな違いが生まれました（約2倍速くなりました）.

于 2012-06-03T00:21:27.340 に答える
2

次のような簡単なことを試しましたか？

var a = Enumerable.Range(1, int.MaxValue/100).ToList();
var b = Enumerable.Range(50, int.MaxValue/100 - 50).ToList();

//var c = a.Intersect(b).ToList();
List<int> c = new List<int>();

var t1 = DateTime.Now;

foreach (var item in a)
{
    if (b.BinarySearch(item) >= 0)
        c.Add(item);
}

var t2 = DateTime.Now;

var tres = t2 - t1;

このコードは、21,474,836個の要素の1つの配列と、21,474,786個の要素を持つもう1つの配列を取ります。

私が使用する場合、私var c = a.Intersect(b).ToList();はOutOfMemoryException

結果の積は、ネストされたforeachを使用した461,167,507,485,096回の反復になります。

しかし、この単純なコードでは、交差はTotalSeconds = 7.3960529で発生しました（1つのコアを使用）

今はまだ不満なので、これを並行して壊してパフォーマンスを上げようとしています。終わったらすぐに投稿します

于 2012-06-03T00:48:02.070 に答える
1

Yorye Nathan は、最後の「安全でないコード」メソッドを使用して、2 つの配列を最速で交差させる方法を教えてくれました。残念ながら、それでも私には遅すぎました。配列の交差の組み合わせを作成する必要があり、最大で 2^32 の組み合わせになりました。以下の修正と調整を行い、時間が 2.6 倍速くなりました。何らかの方法で確実に実行できるように、事前に最適化を行う必要があります。実際のオブジェクトやID、またはその他の抽象的な比較の代わりに、インデックスのみを使用しています。したがって、たとえば、このような大きな数と交差する必要がある場合

着 1: 103344、234566、789900、1947890、着 2: 150034、234566、845465、23849854

すべてを入れて配列する

到着1: 103344、234566、789900、1947890、150034、845465、23849854

交差には、結果配列の順序付きインデックスを使用します

Arr1Index: 0、1、2、3 Arr2Index : 1、4、5、6

これで、他の素敵な配列を構築できる人数が減りました。Yorye からメソッドを取得した後に行ったことは、Arr2Index を取得して、理論的にはブール配列、実際にはバイト配列に展開したことです。これは、メモリ サイズの影響から、次のようになります。

Arr2IndexCheck: 0、1、0、0、1、1、1

これは多かれ少なかれ、2番目の配列に含まれているインデックスを教えてくれる辞書です。次のステップでは、時間のかかるメモリ割り当てを使用しませんでした。代わりに、メソッドを呼び出す前に結果配列を事前に作成したため、組み合わせを見つけるプロセス中に何もインスタンス化することはありませんでした。もちろん、この配列の長さは個別に処理する必要があるため、どこかに保存する必要があるかもしれません。

最後に、コードは次のようになります。

    public static unsafe int IntersectSorted2(int[] arr1, byte[] arr2Check, int[] result)
    {
        int length;

        fixed (int* pArr1 = arr1, pResult = result)
        fixed (byte* pArr2Check = arr2Check)
        {
            int* maxArr1Adr = pArr1 + arr1.Length;
            int* arr1Value = pArr1;
            int* resultValue = pResult;

            while (arr1Value < maxArr1Adr)
            {
                if (*(pArr2Check + *arr1Value) == 1)
                {
                    *resultValue = *arr1Value;
                    resultValue++;
                }

                arr1Value++;
            }

            length = (int)(resultValue - pResult);
        }

        return length;
    }

結果の配列サイズが関数によって返されることがわかります。次に、必要なことを行います（サイズを変更して保持します）。明らかに、結果の配列には、少なくとも arr1 と arr2 の最小サイズが必要です。

大きな改善点は、最初の配列のみを反復処理することです。これは、2 番目の配列よりも小さいサイズにするのが最適であるため、反復回数が少なくなります。反復が少ないということは、CPU サイクルが少ないということですよね?

したがって、ここに 2 つの順序付けられた配列の非常に高速な交差があります。

于 2015-10-20T14:27:52.210 に答える
0

C# は SIMD をサポートしていません。さらに、理由はまだわかりませんが、SSE を使用する DLL は、C# から呼び出された場合、SSE 以外の同等の関数よりも高速ではありません。また、私が知っているすべての SIMD 拡張機能は、とにかく分岐、つまり「if」ステートメントでは機能しません。

.net 4.0 を使用している場合、複数のコアがある場合は Parallel For を使用して速度を上げることができます。それ以外の場合は、.net 3.5 以下であれば、マルチスレッド バージョンを作成できます。

あなたに似た方法は次のとおりです。

    IList<int> intersect(int[] arr1, int[] arr2)
    {
        IList<int> intersect = new List<int>();
        int i = 0, j = 0;
        int iMax = arr1.Length - 1, jMax = arr2.Length - 1;
        while (i < iMax && j < jMax)
        {
            while (i < iMax && arr1[i] < arr2[j]) i++;
            if (arr1[i] == arr2[j]) intersect.Add(arr1[i]);
            while (i < iMax && arr1[i] == arr2[j]) i++; //prevent reduntant entries
            while (j < jMax && arr2[j] < arr1[i]) j++;
            if (arr1[i] == arr2[j]) intersect.Add(arr1[i]);
            while (j < jMax && arr2[j] == arr1[i]) j++; //prevent redundant entries
        }
        return intersect;
    }

これにより、エントリが 2 回表示されることも防止されます。サイズが 1000 万の 2 つの並べ替えられた配列では、約 1 秒で完了しました。Forステートメントでarray.Lengthを使用する場合、コンパイラは配列境界チェックを削除することになっていますが、それがwhileステートメントで機能するかどうかはわかりません。

于 2012-06-03T00:17:27.593 に答える
0

整数の配列のコレクションarrCollection1ですか? arrCollection2この場合、2 番目のループを から開始するi+1のではなく、0

于 2012-06-03T00:15:51.417 に答える