为什么我的 TArray<TPair<Integer, Double>> 在某些值为 NaN 时无法使用自定义比较器进行排序？

Question

我有一个 TPair 记录的通用数组，其中包含一个整数索引和一个双精度值。我通过构造一个 TComparer<TPair<Integer, Double>> 来按每个 TPair 的值对这个数组进行排序，该 TComparer<TPair<Integer, Double>> 只调用每个 TPair 的值的默认值 TComparer<Double>。但是，调用排序时出现访问冲突。这个问题似乎与我的某些值是 NaN 的事实有关。我无法控制某些值为 NaN 的事实，因此我需要解决这个问题。

在为双打调用默认 TComparer 之前，我尝试检查 NaN，并将 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.

Remy LeBeau 指出我在 Comparer2 中的检查不完整。用以下内容替换 Comparer2 会使排序调用 return 成为预期的输出。所以很明显问题出在默认双比较器尝试比较 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
             );

Answer 1

排序完成后要将 NaN 定位到哪里 - 数组的前面还是后面？当您检测到 NaN 时，根本不要调用默认的 TComparer，只需调用 return < 0 或 > 0，具体取决于您想要 [=11] 的位置=] 相对于另一个值定位（如果两者都是 NaN，return 则为 0）。当您确实为两个非 NaN 值调用默认 TComparer 时，您在 Compare1 和 Compare2 中都有 Left.Value 和 Right.Value .

试试这样的方法：

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

为什么我的 TArray<TPair<Integer, Double>> 在某些值为 NaN 时无法使用自定义比较器进行排序？

Why is my TArray<TPair<Integer, Double>> failing to sort using a custom comparer when some values are NaN?

delphi

delphi-10.3-rio