複合数値の並べ替え

Question

私のプロジェクトには「複合」という構造体があります（私はC＃を使って構築します）。構造体の名前が示すように、複素数の構造体です。その構造体には、 "Modulus"と呼ばれる組み込みメソッドがあり、複素数の係数を計算することができます。これまでのことはとても簡単です。

問題は、この構造体から配列を作成し、含まれる複素数の係数にしたがって配列をソートすることです。それのための方法はありますか？ （アルゴリズムの提案は歓迎されます）

ありがとうございます！

Answer 1

Complex[] complexArray = ... 

Complex[] sortedArray = complexArray.OrderByDescending(c => c.Modulus()).ToArray(); 

Answer 2

public struct Complex: IComparable<Complex> 
{ 
    //complex rectangular number: a + bi 
    public decimal A 
    public decimal B 
    //synonymous with absolute value, or in geometric terms, distance 
    public decimal Modulus() { ... } 

    //CompareTo() is the default comparison used by most built-in sorts; 
    //all we have to do here is pass through to Decimal's IComparable implementation 
    //via the results of the Modulus() methods 
    public int CompareTo(Complex other){ return this.Modulus().CompareTo(other.Modulus()); } 

} 

あなたは今、あなたは複雑なインスタンスの任意のコレクションに選択した任意のソート方法を使用することができます。 Array.Sort（）、List.Sort（）、Enumerable.OrderBy（）（IComparableは使用しませんが、Complexが含まれているクラスのメンバーだった場合は、余分なレベルをmoduliの比較まで）など。

降順で並べ替えることを指定しました。 Modulus（）の比較結果に-1を掛け合わせて返すことを検討してください。しかし、混乱する可能性があるので、私はこれに注意します。リストを昇順で取得するには、通常降順を返すメソッドを使用する必要があります。代わりに、ほとんどのソート方法を使用すると、ソート方向、または静止IComparableを実装を利用することができますカスタム比較のいずれかを指定することができます：

//This will use your Comparison, but reverse the sort order based on its result 
myEnumerableOfComplex.OrderByDescending(c=>c); 
//This explicitly negates your comparison; you can also use b.CompareTo(a) 
//which is equivalent 
myListOfComplex.Sort((a,b) => return a.CompareTo(b) * -1); 
//DataGridView objects use a SortDirection enumeration to control and report 
//sort order 
myGridViewOfComplex.Sort(myGridViewOfComplex.Columns["ComplexColumn"], ListSortDirection.Descending); 

Answer 3

あなたはいつもSortedListのを使用することができます:)率がint型であると仮定すると：

var complexNumbers = new SortedList<int, Complex>(); 
complexNumbers.Add(number.Modulus(), number); 

Answer 4

まず、モジュラスの代わりにモジュラスの二乗を比較してパフォーマンスを向上させることができます。「sqrt（a * a + b * b）> = sqrt（c * c + d * d）」は、「a * a + b + b> = c * c」に相当します。 + d * d」となる。

次に、複素数をソートするための比較関数を記述することができます。

public class ComplexModulusComparer : 
    IComparer<Complex>, 
    IComparer 
{ 
    public static readonly ComplexModulusComparer Default = new ComplexModulusComparer(); 

    public int Compare(Complex a, Complex b) 
    { 
     return a.ModulusSquared().CompareTo(b.ModulusSquared()); 
    } 

    int IComparer.Compare(object a, object b) 
    { 
     return ((Complex)a).ModulusSquared().CompareTo(((Complex)b).ModulusSquared()); 
    } 
} 

逆コンパレータも書くことができます。より大きなものからより小さなものに変えたいからです。あなたはまた、IComparableを実装でき

public class ComplexModulusReverseComparer : 
    IComparer<Complex>, 
    IComparer 
{ 
    public static readonly ComplexModulusReverseComparer Default = new ComplexModulusReverseComparer(); 

    public int Compare(Complex a, Complex b) 
    { 
     return - a.ModulusSquared().CompareTo(b.ModulusSquared()); 
    } 

    int IComparer.Compare(object a, object b) 
    { 
     return - ((Complex)a).ModulusSquared().CompareTo(((Complex)b).ModulusSquared()); 
    } 
} 

あなたは、2つの素敵な拡張メソッドを書くことができ、配列をソートするために...あなたのコード内で次に

public static void SortByModulus(this Complex[] array) 
{ 
    Array.Sort(array, ComplexModulusComparer.Default); 
} 

public static void SortReverseByModulus(this Complex[] array) 
{ 
    Array.Sort(array, ComplexModulusReverseComparer.Default); 
} 

...

Complex[] myArray ...; 
myArray.SortReverseByModulus(); 

、もしあなたが望むなら、より正確で正式なアプローチは私の視点からIComparerを使うことです。

public struct Complex : 
    IComparable<Complex> 
{ 
    public double R; 
    public double I; 

    public double Modulus() { return Math.Sqrt(R * R + I * I); } 

    public double ModulusSquared() { return R * R + I * I; } 

    public int CompareTo(Complex other) 
    { 
     return this.ModulusSquared().CompareTo(other.ModulusSquared()); 
    } 
} 

そして、あなたがソートする必要があるときに次に比較演算

public class ReverseComparer<T> : 
    IComparer<T> 
{ 
    private IComparer<T> comparer; 

    public static readonly ReverseComparer<T> Default = new ReverseComparer<T>(); 

    public ReverseComparer<T>() : 
     this(Comparer<T>.Default) 
    { 
    } 

    public ReverseComparer<T>(IComparer<T> comparer) 
    { 
     this.comparer = comparer; 
    } 

    public int Compare(T a, T b) 
    { 
     return - this.comparer.Compare(a, b); 
    } 
} 

のあらゆる種類に適用することができReverseComparerを書くことができます....

Complex[] array ...; 
Array.Sort(array, ReverseComparer<Complex>.Default); 

か、別のIComparerを持っている場合...

Complex[] array ...; 
Array.Sort(array, new ReverseComparer<Complex>(myothercomparer)); 

RE-編集 -

[OK]を私はいくつかの速度テスト計算を行いました。 C＃4.0でリリースモードでコンパイルされ、Visual Studioのすべてのインスタンスが閉じられました。

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

namespace TestComplex 
{ 
    class Program 
    { 
     public struct Complex 
     { 
      public double R; 
      public double I; 

      public double ModulusSquared() 
      { 
       return this.R * this.R + this.I * this.I; 
      } 
     } 

     public class ComplexComparer : 
      IComparer<Complex> 
     { 
      public static readonly ComplexComparer Default = new ComplexComparer(); 

      public int Compare(Complex x, Complex y) 
      { 
       return x.ModulusSquared().CompareTo(y.ModulusSquared()); 
      } 
     } 

     private static void RandomComplexArray(Complex[] myArray) 
     { 
      // We use always the same seed to avoid differences in quicksort. 
      Random r = new Random(2323); 
      for (int i = 0; i < myArray.Length; ++i) 
      { 
       myArray[i].R = r.NextDouble() * 10; 
       myArray[i].I = r.NextDouble() * 10; 
      } 
     } 

     static void Main(string[] args) 
     { 
      // We perform some first operation to ensure JIT compiled and optimized everything before running the real test. 

      Stopwatch sw = new Stopwatch(); 

      Complex[] tmp = new Complex[2]; 
      for (int repeat = 0; repeat < 10; ++repeat) 
      { 
       sw.Start(); 
       tmp[0] = new Complex() { R = 10, I = 20 }; 
       tmp[1] = new Complex() { R = 30, I = 50 }; 
       ComplexComparer.Default.Compare(tmp[0], tmp[1]); 
       tmp.OrderByDescending(c => c.ModulusSquared()).ToArray(); 
       sw.Stop(); 
      } 

      int[] testSizes = new int[] { 5, 100, 1000, 100000, 250000, 1000000 }; 

      for (int testSizeIdx = 0; testSizeIdx < testSizes.Length; ++testSizeIdx) 
      { 
       Console.WriteLine("For " + testSizes[testSizeIdx].ToString() + " input ..."); 

       // We create our big array 

       Complex[] myArray = new Complex[testSizes[testSizeIdx]]; 

       double bestTime = double.MaxValue; 

       // Now we execute repeatCount times our test. 

       const int repeatCount = 15; 

       for (int repeat = 0; repeat < repeatCount; ++repeat) 
       { 
        // We fill our array with random data 

        RandomComplexArray(myArray); 

        // Now we perform our sorting. 

        sw.Reset(); 
        sw.Start(); 
        Array.Sort(myArray, ComplexComparer.Default); 
        sw.Stop(); 

        double elapsed = sw.Elapsed.TotalMilliseconds; 
        if (elapsed < bestTime) 
         bestTime = elapsed; 
       } 

       Console.WriteLine("Array.Sort best time is " + bestTime.ToString()); 

       // Now we perform our test using linq 
bestTime = double.MaxValue; // i forgot this before 
       for (int repeat = 0; repeat < repeatCount; ++repeat) 
       { 
        // We fill our array with random data 

        RandomComplexArray(myArray); 

        // Now we perform our sorting. 

        sw.Reset(); 
        sw.Start(); 
        myArray = myArray.OrderByDescending(c => c.ModulusSquared()).ToArray(); 
        sw.Stop(); 

        double elapsed = sw.Elapsed.TotalMilliseconds; 
        if (elapsed < bestTime) 
         bestTime = elapsed; 
       } 

       Console.WriteLine("linq best time is " + bestTime.ToString()); 

       Console.WriteLine(); 
      } 

      Console.WriteLine("Press enter to quit."); 
      Console.ReadLine(); 
     } 
    } 
} 

そして、ここでの結果：

For 5 input ... 
Array.Sort best time is 0,0004 
linq best time is 0,0018 

For 100 input ... 
Array.Sort best time is 0,0267 
linq best time is 0,0298 

For 1000 input ... 
Array.Sort best time is 0,3568 
linq best time is 0,4107 

For 100000 input ... 
Array.Sort best time is 57,3536 
linq best time is 64,0196 

For 250000 input ... 
Array.Sort best time is 157,8832 
linq best time is 194,3723 

For 1000000 input ... 
Array.Sort best time is 692,8211 
linq best time is 1058,3259 

Press enter to quit. 

私のマシンは、Intel I5、64ビットのWindows 7です。 申し訳ありません私は前の編集で小さな愚かなバグをしました！ARRAY.SORT OUTPEFORMS LINQは、ごくわずかですが、疑わしいものとして、この量はnとともに増加しますが、それほど線形ではないようです。それは私にコードオーバヘッドとメモリの問題（キャッシュミス、オブジェクト割り当て、GC ...知らない）の両方のようです。