c# - 長さの異なる 2 つの整数配列を比較する際のパフォーマンスを改善する

Question

基本的には序数文字列比較器ですが、整数（ushort、これは問題ではないと思いますが）配列に対して機能します。

配列の長さは異なる場合がありますが、要素 [0..n] (n は最短の配列の長さ) が一致する場合にのみ長さが問題になります。その場合、配列が長いほど「大きい」と見なされます。

1 2 3 < 1 2 4

1 2 3 5 < 1 2 4

1 2 5 3 > 1 2 4

1 2 3 4 > 1 2 3

    public int Compare(ushort[] x, ushort[] y)
    {
        int pos = 0;
        int len = Math.Min(x.Length, y.Length);
        while (pos < len && x[pos] == y[pos])
            pos++;

        return pos < len ?
            x[pos].CompareTo(y[pos]) :
            x.Length.CompareTo(y.Length);

    }

これを最適化する方法についてのアイデアはありますか?

アップデート

私がここで実際に行っていることについてのコメント投稿者への返答: 私はこれに関連してずっと前に質問をしていたことに気づきました。唯一の大きな違いはushort、キーに文字列の代わりに配列を使用していることです。これは、はるかにコンパクトであるためです。

パス全体をキーとして使用すると、部分キーを使用してソートされたセットからビューを取得できるため、サブセット クエリのパフォーマンスが向上します。インデックスを作成するときのパフォーマンスを改善しようとしています。 サブセットのインデックス検索のデータ構造

ところで、私はこれまでの回答に非常に感銘を受けました。私は何年にもわたって SO について多くの質問をしてきましたが、これは私が今まで見た中で最も思慮深く興味深い回答のコレクションです。特定の問題 (短い配列の数百万回の比較) に対する正しい答えはまだわかりませんが、それらのすべてが私が知らなかったことを教えてくれました。

Answer 1

これが私が思いついたものです。コードといくつかの並列コードの組み合わせを使用して、最大約 16 ミル (2^24) までテストしました。

public int CompareParallel(ushort[]x, ushort[] y, int len, int segLen)
{
    int compareArrLen = ( len / segLen ) + 1;
    int [ ] compareArr = new int [ compareArrLen ];
    Parallel.For ( 0 , compareArrLen , 
                   new Action<int , ParallelLoopState> ( ( i , state ) =>
    {
        if ( state.LowestBreakIteration.HasValue 
                 && state.LowestBreakIteration.Value < i )
            return;
        int segEnd = ( i + 1 ) * segLen;
        int k = len < segEnd ? len : segEnd;
        for ( int j = i * segLen ; j < k ; j++ )
            if ( x [ j ] != y [ j ] )
            {
                compareArr [ i ] = ( x [ j ].CompareTo ( y [ j ] ) );
                state.Break ( );
                return;
            }
    } ) );
    int r = compareArrLen - 1;
    while ( r >= 0 )
    {
        if ( compareArr [ r ] != 0 )
            return compareArr [ r ];
        r--;
    }
    return x.Length.CompareTo ( y.Length );
}

public int CompareSequential ( ushort [ ] x , ushort [ ] y, int len )
{
    int pos = 0;
    while ( pos < len && x [ pos ] == y [ pos ] )
        pos++;

    return pos < len ?
        x [ pos ].CompareTo ( y [ pos ] ) :
        x.Length.CompareTo ( y.Length );

}

public int Compare( ushort [ ] x , ushort [ ] y ) 
{
    //determined through testing to be the best on my machine
    const int cutOff = 4096;
    int len = x.Length < y.Length ? x.Length : y.Length;
    //check if len is above a specific threshold 
    //and if first and a number in the middle are equal
    //chose equal because we know that there is a chance that more
    //then 50% of the list is equal, which would make the overhead
    //worth the effort
    if ( len > cutOff && x [ len - 1 ] == y [ len - 1 ] 
           && x [ len/2 ] == y [ len/2 ] )
    {
        //segment length was determined to be best through testing
        //at around 8% of the size of the array seemed to have the
        //on my machine
        return CompareParallel ( x , y , len , (len / 100)*8 );
    }
    return CompareSequential ( x , y, len );
}

ここに私が書いたテストがあります：

class Program
{
    [Flags]
    private enum InfoLevel:byte
    {
        Detail=0x01, Summary=0x02
    }

    private static InfoLevel logLevel = InfoLevel.Summary;

    private static void LogDetail ( string content ) 
    {
        LogInfo ( InfoLevel.Detail,content );
    }

    private static void LogSummary ( string content ) 
    {
        LogInfo ( InfoLevel.Summary , content );
    }

    private static void LogInfo ( InfoLevel level , string content ) 
    {
        if ( ( level & logLevel ) == level )
            Console.WriteLine ( content );
    }

    private static void LogInfo ( InfoLevel level , string format, 
                                  params object[] arg )
    {
        if ( ( level & logLevel ) == level )
            Console.WriteLine ( format:format, arg:arg  );
    }

    private static void LogDetail ( string format , params object [ ] arg )
    {
        LogInfo ( InfoLevel.Detail , format, arg );
    }

    private static void LogSummary ( string format , params object [ ] arg )
    {
        LogInfo ( InfoLevel.Summary , format, arg );
    }

    const string _randTestResultHeader = "\r\nRandom Array Content\r\n";
    const string _equalArrayResultHeader = "Only Length Different\r\n\r\n";
    const string _summaryTestResultsHeader = 
                                "Size\t\tOrig Elps\tPara Elps\tComp Elps\r\n";
    const string _summaryBodyContent = 
                         "{0}\t\t{1:0.0000}\t\t{2:0.0000}\t\t{3:0.00000}\r\n";

    static void Main ( string [ ] args )
    {
        Console.SetOut(new StreamWriter(File.Create("out.txt")));

        int segLen = 0;
        int segPercent = 7;
        Console.WriteLine ( "Algorithm Test, Time results in milliseconds" );
        for ( ; segPercent < 13; segPercent ++ )
        {
            Console.WriteLine ( 
                      "Test Run with parallel Dynamic segment size at {0}%"
                       +" of Array Size (Comp always at 8%)\r\n" , segPercent);

            StringBuilder _aggrRandResults = new StringBuilder ( );
            StringBuilder _aggrEqualResults = new StringBuilder ( );

            _aggrRandResults.Append ( _randTestResultHeader );
            _aggrEqualResults.Append ( _equalArrayResultHeader );

            _aggrEqualResults.Append ( _summaryTestResultsHeader );
            _aggrRandResults.Append ( _summaryTestResultsHeader );


            for ( int i = 10 ; i < 25 ; i++ )
            {
                int baseLen = ( int ) Math.Pow ( 2 , i );
                segLen = ( baseLen / 100 ) * segPercent;

                var testName = "Equal Length ";
                var equalTestAverage = RandomRunTest ( testName , baseLen , 
                                                       baseLen, segLen );
                testName = "Left Side Larger";
                var lslargerTestAverage=RandomRunTest(testName,baseLen+10, 
                                                      baseLen, segLen );
                testName = "Right Side Larger";
                var rslargerTestAverage = RandomRunTest ( testName , baseLen ,
                                                        baseLen + 10, segLen );

                double [ ] completelyRandomTestAvg = new double [ 3 ];
                for ( int l = 0 ; l < completelyRandomTestAvg.Length ; l++ )
                    completelyRandomTestAvg [ l ] = ( equalTestAverage [ l ] +
                                                 lslargerTestAverage [ l ] +
                                              rslargerTestAverage [ l ] ) / 3;

                LogDetail ( "\r\nRandom Test Results:" );
                LogDetail ("Original Composite Test Average: {0}" ,
                           completelyRandomTestAvg [ 0 ] );
                LogDetail ( "Parallel Composite Test Average: {0}" ,
                            completelyRandomTestAvg [ 1 ]  );

                _aggrRandResults.AppendFormat ( _summaryBodyContent , 
                    baseLen , 
                    completelyRandomTestAvg [ 0 ] , 
                    completelyRandomTestAvg [ 1 ] , 
                    completelyRandomTestAvg [ 2 ]);

                testName = "Equal Len And Values";
                var equalEqualTest = EqualTill ( testName , baseLen , 
                                                 baseLen, segLen );

                testName = "LHS Larger";
                var equalLHSLargerTest = EqualTill ( testName , baseLen + 10 , 
                                                     baseLen, segLen );

                testName = "RHS Larger";
                var equalRHSLargerTest = EqualTill ( testName , baseLen , 
                                                     baseLen + 10, segLen );

                double [ ] mostlyEqualTestAvg = new double [ 3 ];
                for ( int l = 0 ; l < mostlyEqualTestAvg.Length ; l++ )
                    mostlyEqualTestAvg [ l ] = ( ( equalEqualTest [ l ] +
                                            equalLHSLargerTest [ l ] +
                                            equalRHSLargerTest [ l ] ) / 3 );

                LogDetail( "\r\nLength Different Test Results" );
                LogDetail( "Original Composite Test Average: {0}" , 
                           mostlyEqualTestAvg [ 0 ] );
                LogDetail( "Parallel Composite Test Average: {0}" , 
                            mostlyEqualTestAvg [ 1 ] );

                _aggrEqualResults.AppendFormat ( _summaryBodyContent , 
                                                 baseLen , 
                                                 mostlyEqualTestAvg [ 0 ] , 
                                                 mostlyEqualTestAvg [ 1 ] ,
                                                 mostlyEqualTestAvg [ 2 ]);
            }

            LogSummary ( _aggrRandResults.ToString() + "\r\n");
            LogSummary ( _aggrEqualResults.ToString()+ "\r\n");

        }
        Console.Out.Flush ( );
    }


    private const string _testBody = 
                  "\r\n\tOriginal:: Result:{0}, Elapsed:{1}"
                 +"\r\n\tParallel:: Result:{2}, Elapsed:{3}"
                 +"\r\n\tComposite:: Result:{4}, Elapsed:{5}";
    private const string _testHeader = 
                  "\r\nTesting {0}, Array Lengths: {1}, {2}";
    public static double[] RandomRunTest(string testName, int shortArr1Len, 
                                         int shortArr2Len, int parallelSegLen)
    {

        var shortArr1 = new ushort [ shortArr1Len ];
        var shortArr2 = new ushort [ shortArr2Len ];
        double [ ] avgTimes = new double [ 3 ];

        LogDetail ( _testHeader , testName , shortArr1Len , shortArr2Len ) ;
        for ( int i = 0 ; i < 10 ; i++ )
        {
            int arrlen1 = shortArr1.Length , arrlen2 = shortArr2.Length;

            double[] currResults = new double [ 3 ];

            FillCompareArray ( shortArr1 , shortArr1.Length );
            FillCompareArray ( shortArr2 , shortArr2.Length );

            var sw = new Stopwatch ( );

            //Force Garbage Collection 
            //to avoid having it effect 
            //the test results this way 
            //test 2 may have to garbage 
            //collect due to running second
            GC.Collect ( );
            sw.Start ( );
            int origResult = Compare ( shortArr1 , shortArr2 );
            sw.Stop ( );
            currResults[0] = sw.Elapsed.TotalMilliseconds;
            sw.Reset ( );

            GC.Collect ( );
            sw.Start ( );
            int parallelResult = CompareParallelOnly ( shortArr1 , shortArr2, 
                                                       parallelSegLen );
            sw.Stop ( );
            currResults [ 1 ] = sw.Elapsed.TotalMilliseconds;
            sw.Reset ( );

            GC.Collect ( );
            sw.Start ( );
            int compositeResults = CompareComposite ( shortArr1 , shortArr2 );
            sw.Stop ( );                
            currResults [ 2 ] = sw.Elapsed.TotalMilliseconds;

            LogDetail ( _testBody, origResult , currResults[0] , 
                        parallelResult , currResults[1], 
                        compositeResults, currResults[2]);

            for ( int l = 0 ; l < currResults.Length ; l++ )
                avgTimes [ l ] = ( ( avgTimes[l]*i)+currResults[l]) 
                                    / ( i + 1 );
        }
        LogDetail ( "\r\nAverage Run Time Original: {0}" , avgTimes[0]);
        LogDetail ( "Average Run Time Parallel: {0}" , avgTimes[1]);
        LogDetail ( "Average Run Time Composite: {0}" , avgTimes [ 2 ] );

        return avgTimes;
    }

    public static double [ ] EqualTill ( string testName, int shortArr1Len , 
                                       int shortArr2Len, int parallelSegLen)
    {

        const string _testHeader = 
               "\r\nTesting When Array Difference is "
               +"Only Length({0}), Array Lengths: {1}, {2}";

        int baseLen = shortArr1Len > shortArr2Len 
                          ? shortArr2Len : shortArr1Len;

        var shortArr1 = new ushort [ shortArr1Len ];
        var shortArr2 = new ushort [ shortArr2Len ];
        double [ ] avgTimes = new double [ 3 ];

        LogDetail( _testHeader , testName , shortArr1Len , shortArr2Len );
        for ( int i = 0 ; i < 10 ; i++ )
        {

            FillCompareArray ( shortArr1 , shortArr1Len);
            Array.Copy ( shortArr1 , shortArr2, baseLen );
            double [ ] currElapsedTime = new double [ 3 ];
            var sw = new Stopwatch ( );
            //See previous explaination 
            GC.Collect ( );
            sw.Start ( );
            int origResult = Compare ( shortArr1 , shortArr2 );
            sw.Stop ( );
            currElapsedTime[0] = sw.Elapsed.TotalMilliseconds;
            sw.Reset ( );

            GC.Collect ( );
            sw.Start ( );
            int parallelResult = CompareParallelOnly ( shortArr1, shortArr2, 
                                     parallelSegLen );
            sw.Stop ( );
            currElapsedTime[1] = sw.Elapsed.TotalMilliseconds;
            sw.Reset ( );

            GC.Collect ( );
            sw.Start ( );
            var compositeResult = CompareComposite ( shortArr1 , shortArr2 );
            sw.Stop ( );
            currElapsedTime [ 2 ] = sw.Elapsed.TotalMilliseconds;

            LogDetail ( _testBody , origResult , currElapsedTime[0] , 
                parallelResult , currElapsedTime[1], 
                compositeResult,currElapsedTime[2]);

            for ( int l = 0 ; l < currElapsedTime.Length ; l++ )
                avgTimes [ l ] = ( ( avgTimes [ l ] * i ) 
                                   + currElapsedTime[l])/(i + 1);
        }
        LogDetail ( "\r\nAverage Run Time Original: {0}" , avgTimes [ 0 ] );
        LogDetail ( "Average Run Time Parallel: {0}" , avgTimes [ 1 ] );
        LogDetail ( "Average Run Time Composite: {0}" , avgTimes [ 2 ] );
        return avgTimes;
    }


    static Random rand = new Random ( );
    public static void FillCompareArray ( ushort[] compareArray, int length ) 
    {
        var retVals = new byte[length];
        ( rand ).NextBytes ( retVals );
        Array.Copy ( retVals , compareArray , length);
    }

    public static int CompareParallelOnly ( ushort [ ] x , ushort[] y, 
                                            int segLen ) 
    {
       int len = x.Length<y.Length ? x.Length:y.Length;
       int compareArrLen = (len/segLen)+1;
       int[] compareArr = new int [ compareArrLen ];
       Parallel.For ( 0 , compareArrLen , 
           new Action<int , ParallelLoopState> ( ( i , state ) =>
       {
           if ( state.LowestBreakIteration.HasValue 
                    && state.LowestBreakIteration.Value < i )
               return;
           int segEnd = ( i + 1 ) * segLen;
           int k = len<segEnd?len:segEnd;

           for ( int j = i * segLen ; j < k ; j++ )
               if ( x [ j ] != y [ j ] )
               {
                   compareArr [ i ] = ( x [ j ].CompareTo ( y [ j ] ) );
                   state.Break ( );
                   return;
               }
       } ) );
       int r=compareArrLen-1;
       while ( r >= 0 ) 
       {
           if ( compareArr [ r ] != 0 )
               return compareArr [ r ];
           r--;
       }
       return x.Length.CompareTo ( y.Length );
    }

    public static int Compare ( ushort [ ] x , ushort [ ] y )
    {
        int pos = 0;
        int len = Math.Min ( x.Length , y.Length );
        while ( pos < len && x [ pos ] == y [ pos ] )
            pos++;

        return pos < len ?
            x [ pos ].CompareTo ( y [ pos ] ) :
            x.Length.CompareTo ( y.Length );

    }

    public static int CompareParallel ( ushort[] x, ushort[] y, int len, 
                                        int segLen )
    {
        int compareArrLen = ( len / segLen ) + 1;
        int [ ] compareArr = new int [ compareArrLen ];
        Parallel.For ( 0 , compareArrLen , 
            new Action<int , ParallelLoopState> ( ( i , state ) =>
        {
            if ( state.LowestBreakIteration.HasValue 
                 && state.LowestBreakIteration.Value < i )
                return;
            int segEnd = ( i + 1 ) * segLen;
            int k = len < segEnd ? len : segEnd;
            for ( int j = i * segLen ; j < k ; j++ )
                if ( x [ j ] != y [ j ] )
                {
                    compareArr [ i ] = ( x [ j ].CompareTo ( y [ j ] ) );
                    state.Break ( );
                    return;
                }
        } ) );
        int r = compareArrLen - 1;
        while ( r >= 0 )
        {
            if ( compareArr [ r ] != 0 )
                return compareArr [ r ];
            r--;
        }
        return x.Length.CompareTo ( y.Length );
    }

    public static int CompareSequential(ushort [ ] x , ushort [ ] y, int len)
    {
        int pos = 0;
        while ( pos < len && x [ pos ] == y [ pos ] )
            pos++;

        return pos < len ?
            x [ pos ].CompareTo ( y [ pos ] ) :
            x.Length.CompareTo ( y.Length );

    }

    public static int CompareComposite ( ushort [ ] x , ushort [ ] y ) 
    {
        const int cutOff = 4096;
        int len = x.Length < y.Length ? x.Length : y.Length;

        if ( len > cutOff && x [ len - 1 ] == y [ len - 1 ]
                 && x [ len/2 ] == y [ len/2 ] )
            return CompareParallel ( x , y , len , (len / 100)*8 );

        return CompareSequential ( x , y, len );
    }
}

注:

最適化されたコードでビルドするようにしてください。このステップを含めなかった場合、結果は大きく異なり、並列コードは実際よりも大幅に改善されたように見えました。

私が得た結果は、同じ数の非常に長いセットの実行時間が約 33% 短縮されました。入力の増加に伴い直線的に増加しますが、速度は遅くなります。また、小さなデータ セット (私のマシンでは 4092 未満) の場合は開始が遅くなりますが、通常、かかる時間は十分に短く (私のマシンでは 0.001 ミリ秒)、取得した場合に備えて使用する価値があります。大きなほぼ等しい配列。

Answer 2

おそらく大きな違いはありませんが、最後の要素を異なるものに設定してpos < len、while ループのチェックを取り除くことができます。そして、かなり些細なpos++こと++posです。

public int Compare(ushort[] x, ushort[] y)
{
    int pos = 0;
    int len = Math.Min(x.Length, y.Length);

    // the below is probably not worth it for less than 5 (or so) elements,
    //   so just do the old way
    if (len < 5)
    {
      while (pos < len && x[pos] == y[pos])
        ++pos;

      return pos < len ?
        x[pos].CompareTo(y[pos]) :
        x.Length.CompareTo(y.Length);
    }

    ushort lastX = x[len-1];
    bool lastSame = true;
    if (x[len-1] == y[len-1])
        --x[len-1]; // can be anything else
    else
        lastSame = false;

    while (x[pos] == y[pos])
        ++pos;

    return pos < len-1 ?
        x[pos].CompareTo(y[pos]) :
        lastSame ? x.Length.CompareTo(y.Length)
                 : lastX.CompareTo(y[len-1]);
}

編集:最初から多くの要素が同じである場合にのみ、実際にパフォーマンスが向上します (pkuderov が述べたように、初期の違いがある場合はさらに悪化します)。

Answer 3

いくつかのアイデア（間違っている可能性があり、テストが必要です）：

初め。より大きな項目タイプ ( intx32 またはlongx64 の場合 - このタイプに名前を付けましょうTLong) は、より良いパフォーマンスを提供する場合があります。type itemに
複数のアイテムをパックすると (ビッグエンディアン順で!)、一度に複数のアイテムを比較できます。ただし、新しい配列 [タイプ] の最後の項目が満たされていない場合は、それを処理する必要があります。いくつかの「トリッキーなケース」があるかもしれません。今のところ何も見えませんが、わかりません。2番。さらに！場合によっては、より多くの原産地アイテムを type のアイテムに詰めることができます。タイプ の初期配列に戻りましょう:ushortTLong
TLong

TLong
ushortK- すべての配列 (つまり、並べ替えたいすべてのパス!) に存在する最大の数 (つまり、すべてのTruly:tに格納されているすべての数)。次に、every が基本数値システムの単なる「数字」であると想像してみましょう。これは、グラフ内のすべてのパス (つまり、すべての配列) が、この数値システムの数値のみを決定することを意味します。したがって、配列を操作する代わりに、次のようにする必要があります。ushortt <= KtK
ushortushort

1. K型への適合の最大の力を決定しますTLong- それが であると仮定しましょうp:

   int p = 0;
   while (Math.Exp(K, p) <= TLong.MaxValue)
       p++;
   

2. 配列の i 番目pの項目をushort取得し、基数システムで適切な数を計算し、それを型配列Kの i 番目の項目として保持します。TLong

   List<TLong> num = new List<TLong>();
   int i = 0;
   while (p * i < a.Length)
   {
       TLong y = 0;
   
       //transform from base-10 to base-K in chunks of p elements
       for (int j = p * i; j < Math.Min(p * (i + 1), a.Length); j++)
           y = y * K + a[j];
   
       num.Add(sum);
       i++;
   }
   TLong[] result = num.ToArray();
   

3. これは事前に計算された動的な変換であるため、異なる HTML ドキュメントKでは異なる可能性がありK、255 よりもはるかに少ない場合は、最初のアイデアよりも高速になります。また、事前計算された変換には線形の複雑さがあるため、パフォーマンスに大きな影響を与えることはありません。

4. K通常、配列を base- numの大きな数値に変換します。システム。配列に格納されます。それでおしまい！
5. そして、他のコメントから改善された初期ソートアルゴリズムを変更する必要はありません (とにかくチェックしてください - 私は間違っているかもしれません!)

お役に立てば幸いです。

Answer 4

長い回答で申し訳ありませんが、この質問に非常に興味を持ち、調査に数時間を費やしました。結果を共有したいと思います。私はいくつかのテストケースジェネレーターと大まかなパフォーマンステスターを書きました

内容:

1. 完全にランダムな配列を生成する
2. 3 つの比較方法の実行時間を確認する
3. 類似確率の高い配列を生成する
4. 実行時間を確認します。

私は3つの方法を使用していました

1. OP
2. マイ - アイデア - 2 つのインデックス操作をポインターのインクリメントに変更する
3. Dukeling's - Idea - 不要な比較を削除

I 短い配列 (長さ 5 ～ 15) から始めました

方法 1 は、両方のテスト バリエーションで最速でした (pkuderov によって予測されました)。

配列の長さを増やすと、状況が変わります。

これは、配列の長さが 500 から 1500 の間の場合に取得しました

Generating test cases ...
Done. (5258 milliseconds)
Compare1 took 18 milliseconds
Compare2 took 18 milliseconds
Compare3 took 33 milliseconds
Generating 'similar' test cases ...
Done. (5081 milliseconds)
Compare1 took 359 milliseconds
Compare2 took 313 milliseconds
Compare3 took 295 milliseconds

したがって、方法 2 は 1 に比べてわずかに利益があり、方法 3 は 2 に比べてわずかに利益があります。

解像度：

1.配列が十分に短い場合、および/または小さなインデックス値から始まる差異の可能性が高い場合-(提案された方法で)できることはあまりありません
2.そうでない場合は、方法2と3の組み合わせを試すことができます.

コード：

using System;
using System.Diagnostics;

namespace ConsoleExamples
    {
        class ArrayComparePerformance
        {
            static readonly int testArraysNum = 100000;
            static readonly int maxArrayLen = 1500;
            static readonly int minArrayLen = 500;
            static readonly int maxValue = 10;

            public static void RunTest()
            {
                //Generate random arrays;
                ushort[][] a = new ushort[testArraysNum][];
                ushort[][] b = new ushort[testArraysNum][];

                Random rand = new Random();

                Console.WriteLine("Generating test cases ... " );

                Stopwatch sw = new Stopwatch();
                sw.Start();

                for (int i = 0; i < testArraysNum; i++)
                {
                    int len = rand.Next(maxArrayLen) + 1;
                    a[i] = new ushort[len];
                    for (int j = 0; j < len; j++)
                    {
                        a[i][j] = (ushort) rand.Next(maxValue);
                    }



                    len = rand.Next(maxArrayLen) + 1;
                    b[i] = new ushort[len];
                    for (int j = 0; j < len; j++)
                    {
                        b[i][j] = (ushort) rand.Next(maxValue);
                    }



                }

                sw.Stop();
                Console.WriteLine("Done. ({0} milliseconds)", sw.ElapsedMilliseconds);


                //compare1
                sw.Restart();
                for (int i = 0; i < testArraysNum; i++)
                {
                    int result = Compare1(a[i], b[i]);
                }
                sw.Stop();
                Console.WriteLine("Compare1 took " + sw.ElapsedMilliseconds.ToString() + " milliseconds");

                //compare2
                sw.Restart();
                for (int i = 0; i < testArraysNum; i++)
                {
                    int result = Compare2(a[i], b[i]);
                }
                sw.Stop();
                Console.WriteLine("Compare2 took " + sw.ElapsedMilliseconds.ToString() + " milliseconds");

                //compare3
                sw.Restart();
                for (int i = 0; i < testArraysNum; i++)
                {
                    int result = Compare3(a[i], b[i]);
                }
                sw.Stop();
                Console.WriteLine("Compare3 took " + sw.ElapsedMilliseconds.ToString() + " milliseconds");


                //Generate "similar" arrays;

                Console.WriteLine("Generating 'similar' test cases ... ");

                sw.Restart();

                for (int i = 0; i < testArraysNum; i++)
                {
                    int len = rand.Next(maxArrayLen - minArrayLen) + minArrayLen -1;
                    a[i] = new ushort[len];
                    for (int j = 0; j < len; j++)
                    {
                        if (j < len/2)
                            a[i][j] = (ushort)j;
                        else
                            a[i][j] = (ushort)(rand.Next(2)  + j);
                    }



                    len = rand.Next(maxArrayLen - minArrayLen) + minArrayLen - 1;
                    b[i] = new ushort[len];
                    for (int j = 0; j < len; j++)
                    {
                        if (j < len/2)
                            b[i][j] = (ushort)j;
                        else
                            b[i][j] = (ushort)(rand.Next(2)  + j);
                    }
                }

                sw.Stop();
                Console.WriteLine("Done. ({0} milliseconds)", sw.ElapsedMilliseconds);


                //compare1
                sw.Restart();
                for (int i = 0; i < testArraysNum; i++)
                {
                    int result = Compare1(a[i], b[i]);
                }
                sw.Stop();
                Console.WriteLine("Compare1 took " + sw.ElapsedMilliseconds.ToString() + " milliseconds");

                //compare2
                sw.Restart();
                for (int i = 0; i < testArraysNum; i++)
                {
                    int result = Compare2(a[i], b[i]);
                }
                sw.Stop();
                Console.WriteLine("Compare2 took " + sw.ElapsedMilliseconds.ToString() + " milliseconds");

                //compare3
                sw.Restart();
                for (int i = 0; i < testArraysNum; i++)
                {
                    int result = Compare3(a[i], b[i]);
                }
                sw.Stop();
                Console.WriteLine("Compare3 took " + sw.ElapsedMilliseconds.ToString() + " milliseconds");


                Console.ReadKey();
            }

            public static int Compare1(ushort[] x, ushort[] y)
            {
                int pos = 0;
                int len = Math.Min(x.Length, y.Length);
                while (pos < len && x[pos] == y[pos])
                    pos++;

                return pos < len ?
                    x[pos].CompareTo(y[pos]) :
                    x.Length.CompareTo(y.Length);
            }

            public unsafe static int Compare2(ushort[] x, ushort[] y)
            {
                int pos = 0;
                int len = Math.Min(x.Length, y.Length);
                fixed (ushort* fpx = &x[0], fpy = &y[0])
                {
                    ushort* px = fpx;
                    ushort* py = fpy;
                    while (pos < len && *px == *py)
                    {
                        px++;
                        py++;
                        pos++;
                    }
                }

                return pos < len ?
                    x[pos].CompareTo(y[pos]) :
                    x.Length.CompareTo(y.Length);
            }

            public static int Compare3(ushort[] x, ushort[] y)
            {
                int pos = 0;
                int len = Math.Min(x.Length, y.Length);

                // the below is probably not worth it for less than 5 (or so) elements,
                //   so just do the old way
                if (len < 5)
                {
                    while (pos < len && x[pos] == y[pos])
                        ++pos;

                    return pos < len ?
                      x[pos].CompareTo(y[pos]) :
                      x.Length.CompareTo(y.Length);
                }

                ushort lastX = x[len - 1];
                bool lastSame = true;
                if (x[len - 1] == y[len - 1])
                    --x[len - 1]; // can be anything else
                else
                    lastSame = false;

                while (x[pos] == y[pos])
                    ++pos;

                return pos < len - 1 ?
                    x[pos].CompareTo(y[pos]) :
                    lastSame ? x.Length.CompareTo(y.Length)
                             : lastX.CompareTo(y[len - 1]);
            }
        }
    }