排序複雜數字

Question

我的項目中有一個名爲「Complex」的結構（我使用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是包含類的成員，則可以通過Complex成員對包含的類進行排序，而不必去額外的水平下來比較模數）等等

你說你想按降序排序;您可以考慮在返回之前將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

您可以隨時使用排序列表:)假設模量爲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()); 
    } 
} 

你也可以寫反向比較器，因爲你從更大到更小的希望。

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()); 
    } 
} 

要數組排序，那麼你可以寫兩個很好的擴展方法...

在你的代碼

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(); 

您也可以實現IComparable，如果你願意，但更正確和正式的方法是從我的角度來使用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-編輯 -

好吧，我進行了一些速度測試計算。 在釋放模式下與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 ...不知道）。