Сортировка комплексных чисел

Question

В моем проекте есть структура "Complex" (я создаю ее с использованием C #), и, как следует из названия структуры, это структура для комплексных чисел.Эта структура имеет встроенный метод под названием «Модуль», так что я могу вычислить модуль комплексного числа.До сих пор все довольно просто.

Дело в том, что я создаю массив из этой структуры и хочу отсортировать массив по модулю содержащихся комплексных чисел (от большего к меньшему).Есть ли способ для этого?(Любые предложения алгоритма будут приветствоваться.)

Спасибо !!

Answer 1

Complex[] complexArray = ...

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

Answer 2

Прежде всего, вы можете увеличить производительность, сравнивая квадрат модуля вместо модуля.Вам не нужен квадратный корень: «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());
    }
}

И тогда вы можете написать ReverseComparer, который может применяться к любому виду сравнения

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

Затем, когда вам нужно отсортировать ....

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

или в случае, если у вас есть другой IComparer ...

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

RE-EDIT-

Хорошо, я выполнил некоторые расчеты теста скорости.Скомпилировано с 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-битнаяокна семь.Сожалею!Я сделал небольшую глупую ошибку в предыдущем редактировании!РЕЗУЛЬТАТЫ ARRAY.SORT LINQ, да, на очень небольшую величину, но, как подозревают, эта величина растет с n, кажется, не столь линейным образом.Мне кажется, что это и накладные расходы кода, и проблема с памятью (потеря кэша, выделение объектов, сборщик мусора ... не знаю).

Answer 3

Вы всегда можете использовать SortedList :) Предполагая, что модуль равен int:

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

Answer 4

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