0

vb6 を扱う前にこの種の質問をしたことはわかっていますが、遅すぎたため、この仕事には C# を使用することにしました。同じコードが 2 倍の速度で実行されるようになりましたが、それでも遅すぎます。

遅い理由は、すべての行をチェックする各列の終わりから辞書式ソートを開始するためです。

これを高速化すると信じているのは、最初の列からすべての行をチェックしてソートプロセスを開始し、その列の最初のバイトごとに最下位の行を検出し、同じ最初の下位バイトを持つ複数の行を検出し、次のステップのためにそれらをグループ化する場合ですこれは、2 番目の (次の) 列をチェックし、2 番目のバイトのどちらが最下位バイトであるかを調べます。それらが両方とも同じである場合は、次の列に移動します。次の行のバイトが異なる場所を検出すると、列コードが実行されます。最初のバイトと2番目に低いバイトを見つけることに進みます..実際には、このプロセスが適切な速度向上を得るために機能するはずだと思っていました.. .

現在のコードは、すべての行を並べ替える最後の列から力ずくで並べ替えることによって機能します。次に、1 つの列を左に移動し、すべての行を再度並べ替えます。最初の列に到達して並べ替えるまで、これを繰り返します。明らかな理由もなく反復を行うため、これは遅いです。

256 列と 256 行、合計 65,536 の配列要素があるとします。現在のコードを使用すると、各行が適切な並べ替え順序になるまで、各行を複数回並べ替える必要があるとします。列ごとに 65,536 回の反復が必要になる可能性があります。したがって、関数を呼び出すたびに、合計で 256*65536 = 16,777,216回の反復が見積もられます。これが実際に遅い理由です。

私はこれを求めることがたくさんあることを知っていますが、誰かが自由な時間を持っていて、おそらく以前にこれをやったことがあれば、私を助けてくれることに感謝します.

ここに私がこれまでに作業しなければならないコードがあります。

byte[] sortArrayOfArraysLexicoGraphically(ref byte[] data) {
    byte[] lexicoGraphicalIndexes;
    long dataSize = data.Length;
    long squareRootMinusOne;
    int squareRoot;
    int row = 0;
    bool rowSwapped;
    byte[] tmpRow;

    squareRoot = (int)Math.Sqrt(dataSize);
    tmpRow = new byte[squareRoot];
    squareRootMinusOne = squareRoot - 1;
    lexicoGraphicalIndexes = new byte[squareRoot];

    for(short column = 0; column < lexicoGraphicalIndexes.Length; column++) {
        lexicoGraphicalIndexes[column] = (byte)column;
    }

    for(long column = squareRootMinusOne; column >= 0; column -= 1) {
        do {
            rowSwapped = false;
            do {
                if(data[(row * squareRoot) + column] > data[((row + 1) * squareRoot) + column]) {
                    //Swaps a full row in a few copies.
                    //Copies full row to tmpRow
                    Buffer.BlockCopy(data, (row * squareRoot), tmpRow, 0, squareRoot);
                    //Replace first row with second row.
                    Buffer.BlockCopy(data, ((row + 1) * squareRoot), data, (row * squareRoot), squareRoot);
                    //Replace second row with tmpRow
                    Buffer.BlockCopy(tmpRow, 0, data, ((row + 1) * squareRoot), squareRoot);
                    swapBytes(ref lexicoGraphicalIndexes, row, row + 1);
                    rowSwapped = true;
                }
                row++;
            } while (row < squareRootMinusOne);
            row = 0;
        } while (rowSwapped != false);
    }
    return lexicoGraphicalIndexes;
}

public void swapBytes(ref byte[] data, long firstIndex, long secondIndex) {
    byte tmpFirstByte = data[firstIndex];
    data[firstIndex] = data[secondIndex];
    data[secondIndex] = tmpFirstByte;
}
4

2 に答える 2

2

あなたのソートアルゴリズムは非常に悪いと言わざるを得ません。最適化を行わなくても、基本的な linq を使用すると、数十倍の速度が得られます。

N=200 のサイズ N*N のデータを使用してテストを行いました (以下のコードがあなたのものと正確に一致し、100% 正しいかどうかはわかりませんが、少なくとも結果を試してみてください)

List<byte[]> result = data.Batch(N)
                          .OrderBy(b => b, new ArrayComparer())
                          .Select(b => b.ToArray())
                          .ToList();

編集

インプレースソートはさらに高速です。

var list = data.Batch(N).Select(x => x.ToArray()).ToList();
list.Sort(new ArrayComparer());

-

public class ArrayComparer : IComparer<IEnumerable<byte>>
{
    public int Compare(IEnumerable<byte> x, IEnumerable<byte> y)
    {
        var xenum = x.GetEnumerator();
        var yenum = y.GetEnumerator();
        while (xenum.MoveNext() && yenum.MoveNext())
        {
            if (xenum.Current != yenum.Current) 
                   return xenum.Current - yenum.Current;
        }
        return 0;
    }
}

PS: morelinqBatchの拡張メソッドです

于 2012-09-02T10:01:28.867 に答える