Почему мой TArray> не удается отсортировать с помощью пользовательского компаратора, когда некоторые значения NaN? - PullRequest
Новая
       27

Почему мой TArray> не удается отсортировать с помощью пользовательского компаратора, когда некоторые значения NaN?

0 голосов
/ 31 октября 2019

У меня есть общий массив TPair записей, которые содержат целочисленный индекс и двойное значение. Я сортирую этот массив по значению каждого TPair, создав TComparer<TPair<Integer, Double>>, который просто вызывает значение по умолчанию TComparer<Double> для каждого значения TPair. Тем не менее, я получаю нарушение прав доступа при вызове сортировки. Кажется, проблема связана с тем, что некоторые из моих значений NaN. Я не контролирую тот факт, что некоторые значения будут NaN, поэтому мне нужно обойти это.

Я пытался проверить NaN перед вызовом значения по умолчанию TComparer для двойных чисел и вместо замены NaN на Low(Integer), но это не помогло. На данный момент я сделал тестовое приложение, которое воспроизводит проблему, и я вижу, что функция TArray.QuickSort выполняет тысячи сравнений для массива из 3 элементов ... не знаю, что происходит.

Распечатка двух пар, сравниваемых в каждом вызове с любым из пользовательских компараторов, дает такой результат: 

[0] Left = (0, 1.00); Right = (1, NAN)
[1] Left = (1, NAN); Right = (1, NAN)
[2] Left = (2, 3.00); Right = (1, NAN)
[3] Left = (0, 0.00); Right = (1, NAN)
[4] Left = (0, 0.00); Right = (1, NAN)
...
[7328] Left = (0, 0.00); Right = (1, NAN)
[7329] Left = (58976, 0.00); Right = (1, NAN)

Нарушение прав доступа происходит при последующем вызове моего компаратора после записи этой последней строки.

Вот полное тестовое приложение: 

program Project51;

{$APPTYPE CONSOLE}

{$R *.res}

uses
   System.SysUtils, Generics.Collections, Generics.Defaults, Math;

type
   TIntDblPair = TPair<Integer, Double>;

var
   Comparer1, Comparer2 : IComparer<TIntDblPair>;
   ResultSet : TArray<TIntDblPair>;
   nCompares : Integer;

procedure Test(AComparer : IComparer<TIntDblPair>);
var
   I : Integer;
begin
   TArray.Sort<TIntDblPair>(ResultSet, AComparer);
   for I := 0 to Length(ResultSet) - 1 do
      WriteLn(Format('%d: %f', [ResultSet[I].Key, ResultSet[I].Value]));
   WriteLn;
end;

begin
   try
      SetLength(ResultSet, 3);
      ResultSet[0] := TIntDblPair.Create(0, 1);
      ResultSet[1] := TIntDblPair.Create(1, NaN);
      ResultSet[2] := TIntDblPair.Create(2, 3);

      nCompares := 0;
      Comparer1 := TComparer<TIntDblPair>.Construct(
                     function(const Left, Right: TIntDblPair): Integer
                     begin
                        WriteLn(Format('[%d] Left = (%d, %f); Right = (%d, %f)', [nCompares, Left.Key, Left.Value, Right.Key, Right.Value]));
                        Result := TComparer<Double>.Default.Compare(Right.Value, Left.Value);
                        Inc(nCompares);
                     end
                   );
//      Test(Comparer1);

      nCompares := 0;
      Comparer2 := TComparer<TIntDblPair>.Construct(
                     function(const Left, Right: TIntDblPair): Integer
                     begin
                        WriteLn(Format('[%d] Left = (%d, %f); Right = (%d, %f)', [nCompares, Left.Key, Left.Value, Right.Key, Right.Value]));
                        if IsNaN(Right.Value) then
                           Result := TComparer<Double>.Default.Compare(Low(Integer), Left.Value)
                        else if IsNaN(Left.Value) then
                           Result := TComparer<Double>.Default.Compare(Right.Value, Low(Integer))
                        else
                           Result := TComparer<Double>.Default.Compare(Right.Value, Left.Value);
                        Inc(nCompares);
                     end
                   );
      Test(Comparer2);

      Readln;
   except
      on E: Exception do
         Writeln(E.ClassName, ': ', E.Message);
   end;
end.

Реми Лебо указал, что мои проверки в Comparer2 не были завершены. Замена Comparer2 на следующее заставляет этот вызов сортировки возвращать ожидаемый результат. Таким образом, кажется очевидным, что проблема в том, что двойной компаратор по умолчанию пытается сравнить NaN. Это ошибка в реализации компаратора? 

Comparer2 := TComparer<TIntDblPair>.Construct(
               function(const Left, Right: TIntDblPair): Integer
               begin
                  if IsNaN(Right.Value) and IsNaN(Left.Value) then
                     Result := 0
                  else if IsNaN(Right.Value) then
                     Result := TComparer<Double>.Default.Compare(Low(Integer), Left.Value)
                  else if IsNaN(Left.Value) then
                     Result := TComparer<Double>.Default.Compare(Right.Value, Low(Integer))
                  else
                     Result := TComparer<Double>.Default.Compare(Right.Value, Left.Value);
               end
             );

1 Ответ

3 голосов
/ 31 октября 2019

Где нужно расположить NaN после сортировки - переднюю или заднюю часть массива? Когда вы обнаруживаете NaN, НЕ вызывайте значение по умолчанию TComparer, просто возвращайте < 0 или > 0 в зависимости от того, где вы хотите расположить NaN относительно другого значения (если ОБА - * 1007)*, верните 0 вместо). И когда вы ДЕЙСТВИТЕЛЬНО вызываете значение по умолчанию TComparer для двух не NaN значений, вы получаете Left.Value и Right.Value в обоих направлениях Compare1 и Compare2.

Вместо этого попробуйте что-то подобное: 

Comparer2 := TComparer<TIntDblPair>.Construct(
               function(const Left, Right: TIntDblPair): Integer
               begin
                 if IsNaN(Left.Value) then begin
                   if IsNaN(Right.Value) then begin
                     Result := 0;
                     // or maybe:
                     // Result := TComparer<Integer>.Default.Compare(Left.Key, Right.Key);
                   end else begin
                     // To move Nan's to the front of the array, return -1 here
                     // To move Nan's to the back of the array, return 1 here
                     Result := ...;
                   end;
                 end
                 else if IsNaN(Right.Value) then begin
                   // To move Nan's to the front of the array, return 1 here
                   // To move Nan's to the back of the array, return -1 here
                   Result := ...;
                 end else begin
                   Result := TComparer<Double>.Default.Compare(Left.Value, Right.Value);
                   // and maybe:
                   // if Result = 0 then
                   //   Result := TComparer<Integer>.Default.Compare(Left.Key, Right.Key);
                 end;
               end
             );
...