Сортировка массива двойников с NaN в нем

Question

Это скорее вопрос типа «Можете ли вы объяснить это», чем что-либо еще.

Я столкнулся с проблемой на работе, когда мы использовали значения NaN в таблице, но когда таблица была отсортирована, это получилось очень странным, странным образом.Я подумал, что NaN что-то испортил, поэтому я написал тестовое приложение, чтобы проверить, правда ли это.Это то, что я сделал.

static void Main(string[] args)
{
    double[] someArray = { 4.0, 2.0, double.NaN, 1.0, 5.0, 3.0, double.NaN, 10.0, 9.0, 8.0 };

    foreach (double db in someArray)
    {
        Console.WriteLine(db);
    }

    Array.Sort(someArray);
    Console.WriteLine("\n\n");
    foreach (double db in someArray)
    {
        Console.WriteLine(db);
    }

    Console.ReadLine();
}

Что дало результат:

До:

4,2,NaN,1,5,3,NaN,10,9,8

После:

1,4,NaN,2,3,5,8,9,10,NaN

Так что да, NaN каким-то образом сделал отсортированный массив странным образом.

Цитировать Фрая;«Почему эти вещи?»

Answer 1

Я верю, что это потому, что

a < NaN == false
a > NaN == false
a == NaN == false

так что сравнение по ним не работает, и это отбрасывает весь сорт.

Answer 2

Редактировать (заключение. Финал. Конец.): это ошибка.

См. Отчет об ошибке Ошибка в списке.Sort () [.NET35] в списке, который содержит double.NaN и идет, чтобы дать Ханс Пассанту право голоса на Почему .NET 4.0 сортирует этот массив иначе, чем .NET 3.5? изкоторый я разорвал по ссылке.

Исторические размышления

[Смотрите пост: Почему .NET 4.0 сортирует этот массив иначе, чем .NET 3.5? , где, как мы надеемся,Более полезное обсуждение этого конкретного вопроса можно выяснить по-настоящему.Я также отправил туда этот ответ.]

Поведение, указанное Филом в .NET4, определено в CompareTo.См. double.CompareTo для .NET4.Это то же самое поведение, что и в .NET35, однако должно быть согласованным в обеих версиях, согласно документации метода ...

Array.Sort(double[]): не похожеиспользуя CompareTo(double[]), как и ожидалось, и это может быть ошибкой - обратите внимание на разницу в Array.Sort (object []) и Array.Sort (double []) ниже .Я хотел бы получить разъяснения / исправления по следующим вопросам:

В любом случае ответы с использованием > и < и == объясняют, почему эти операторы не работают , но не может объяснить , почему Array.Sort приводит к неожиданному выводу.Вот некоторые из моих выводов, какими бы скудными они ни были.

Во-первых, double.CompareTo(T) документация по методу - этот порядок четко определен в соответствии с документацией :

Меньше нуля : этот экземпляр меньше значения.-или- Этот экземпляр не является числом (NaN), а значение является числом.

Ноль : этот экземпляр равен значению.-или- И этот экземпляр, и значение не являются числом (NaN), PositiveInfinity или NegativeInfinity.

Больше нуля : этот экземпляр больше значения.-или- Этот экземпляр является числом, а значение не является числом (NaN).

В LINQPad (3.5 и 4 оба имеют одинаковые результаты):

0d.CompareTo(0d).Dump();                  // 0
double.NaN.CompareTo(0d).Dump();          // -1
double.NaN.CompareTo(double.NaN).Dump();  // 0
0d.CompareTo(double.NaN).Dump();          // 1

Использование CompareTo(object) дает те же результаты:

0d.CompareTo((object)0d).Dump();                  // 0
double.NaN.CompareTo((object)0d).Dump();          // -1
double.NaN.CompareTo((object)double.NaN).Dump();  // 0
0d.CompareTo((object)double.NaN).Dump();          // 1

Так что это не проблема.

Теперь из Array.Sort(object[]) документации - нет смысла >, < или == (согласно документации) - просто CompareTo(object).

Сортирует элементы ввсего одномерного массива с использованием IComparable реализации каждого элемента массива.

Аналогично, Array.Sort(T[]) использует CompareTo(T).

Сортирует элементы во всем массиве с использованием реализации универсального интерфейса IComparable (Of T) каждого элемента массива.

Давайте посмотрим:

LINQPad (4):

var ar = new double[] {double.NaN, 0, 1, double.NaN};
Array.Sort(ar);
ar.Dump();
// NaN, NaN, 0, 1

LINQPad (3.5):

var ar = new double[] {double.NaN, 0, 1, double.NaN};
Array.Sort(ar);
ar.Dump();
// NaN, 0, NaN, 1

LINQPad (3.5) - ПРИМЕЧАНИЕ Массив является объектом иповедение "ожидается" в соответствии с CompareTo контрактом.

var ar = new object[] {double.NaN, 0d, 1d, double.NaN};
Array.Sort(ar);
ar.Dump();
// NaN, NaN, 0, 1

Хмм.В самом деле.В заключение:

У меня нет ИДЕИ.

Удачного кодирования.

Answer 3

Концептуально NaN - это не число, поэтому сравнение с числом не имеет смысла, следовательно:

a < NaN = false for all a,
a > NaN = false for all a and
NaN != NaN (!)

Чтобы решить эту проблему, вам нужно написать собственный компаратор, который использует IsNaN, чтобы сделать номера NaN меньше (или больше) всех чисел, чтобы они все отображались на одном конце сортировки.

Редактировать: Вот пример версии сравнения:

class Program
{
    private static int NaNComparison(double first, double second)
    {
        if (double.IsNaN(first))
        {
            if (double.IsNaN(second)) // Throws an argument exception if we don't handle both being NaN
                return 0;
            else
                return -1;
        }
        if (double.IsNaN(second))
            return 1;

        if (first == second)
            return 0;
        return first < second ? -1 : 1;
    }

    static void Main(string[] args)
    {
        var doubles = new[] { double.NaN, 2.0, 3.0, 1.0, double.NaN };

        Array.Sort(doubles, NaNComparison);
    }
}

Answer 4

На самом деле странное поведение сортировки является результатом ошибки в .NET 3.5. Ошибка устранена в .NET 4.0.

Единственный способ решить эту проблему - использовать собственный настраиваемый компаратор или обновить его до .NET 4.0. См. Почему .NET 4.0 сортирует этот массив иначе, чем .NET 3.5?

Answer 5

, поскольку вы используете сортировку по умолчанию - алгоритм быстрой сортировки;реализация выполняет нестабильную сортировку;то есть, если два элемента равны, их порядок может не сохраниться