如何使用qsort比较长双精度浮点数并处理NaN？

Question

如何使用qsort()比较长双精度浮点数，并考虑非数字？

当对可能包含非数字的数组进行排序时，我想将所有这些NAN放在排序后数组的一端。

---

qsort()对比较函数有一些限制。

如果第一个参数被认为小于、等于或大于第二个参数，则函数应返回小于、等于或大于零的整数。
C11dr §7.22.5.2 3

当将相同的对象多次传递给比较函数时，结果应相互一致。也就是说，对于 qsort，它们应在数组上定义一个完全排序，...相同的对象始终以相同的方式与关键字进行比较。
§7.22.5 4

a > b 当且仅当 a <= b 或者 a 不是数字或者 b 不是数字时为假。因此，a > b 不等于 !(a <= b)，因为如果其中一个是 NaN，则它们具有相反的结果。

如果比较函数使用return (a > b) - (a < b);，则当一个或两个a或b为NaN时，代码将返回0。数组将无法按所需排序，失去了完全排序的要求。

在使用类别函数（例如int isnan(real-floating x)或int isfinite(real-floating x)）时，这种排序中long double方面非常重要。我知道isfinite(finite_long_double_more_than_DBL_MAX)可能会返回false。因此，我担心isnan(some_long_double)可能会做某些意外的事情。

---

我尝试了下面的方法。显然，它按照所需的方式进行排序。

子问题：下面的“compare（）”是否足以按所需的方式进行排序？有什么推荐的简化方法吗？如果不行——如何修复？ （对于此任务，像0.0L和-0.0L这样的值以任何方式进行排序都可以）

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <float.h>

int compare(const void *a, const void *b) {
  const long double *fa = (const long double *) a;
  const long double *fb = (const long double *) b;
  if (*fa > *fb) return 1;
  if (*fa < *fb) return -1;

  if (*fa == *fb) {
    //return -memcmp(fa, fb, sizeof *fa); if -0.0, 0.0 order important.
    return 0;
  }
  // At least one of *fa or *fb is NaN
  // is *fa a non-NaN?
  if (!isnan(*fa)) return -1;
  if (!isnan(*fb)) return 1;

  // both NaN
  return 0;
  // return -memcmp(fa, fb, tbd size); if NaN order important.
}

int main(void) {
  long double x[] = { 0.0L / 0.0, 0.0L / 0.0, 0.0, 1.0L / 0.0, -0.0, LDBL_MIN,
      LDBL_MAX, 42.0, -1.0L / 0.0, 867-5309, -0.0 };
  x[0] = -x[0];
  printf("unsorted: ");
  size_t n = sizeof x / sizeof x[0];
  for (size_t i = 0; i < n; i++) {
    printf("%.3Le,", x[i]);
  }
  printf("\nsorted: ");
  qsort(x, n, sizeof x[0], compare);
  for (size_t i = 0; i < n; i++) {
    printf("%.3Le,", x[i]);
  }
  puts("");
}

输出

unsorted: nan,-nan,0.000e+00,inf,-0.000e+00,3.362e-4932,1.190e+4932,4.200e+01,-inf,-4.442e+03,-0.000e+00,
sorted: -inf,-4.442e+03,-0.000e+00,0.000e+00,-0.000e+00,3.362e-4932,4.200e+01,1.190e+4932,inf,nan,-nan,

如果我确定比较函数是正确的，我会在代码审查上发表改进意见。但是我不太自信代码能够正确处理那些讨厌的NaN值。

- chux - Reinstate Monica

---

检查数字是否为NaN；如果其中一个是NaN而另一个不是，则报告NaN较小（或较大，取决于排序方向和NaN出现的位置）。假设它们都是NaN，则返回0。否则，它们都不是NaN，您可以使用适当的比较进行处理。如果您认为NaN中有不同的值，则必须对NaN进行表征并根据所选规则生成有效的比较。请注意，检查NaN应该放在最前面，而不是最后。 - Jonathan Leffler

如果你认为两个“被认为相等”的数字“不能以相同方式表示”，那么我认为你要么是错了，要么是错误陈述了事实。 - R.. GitHub STOP HELPING ICE

@EOF 为了这段代码的目的，两个不同的NaN可以相等比较 - 它们将只是以某种顺序出现在排序列表中。返回0不违反§7.22.5 4。 - chux - Reinstate Monica

@chux：我会使用 isnan()，但我的要求并不苛刻，不需要识别不同类型的 NaN。我知道有信号和非信号 NaN；我相信有许多位模式表示 NaN。但我从未需要详细研究它们以了解在 isnan() 表面下发生了什么。一个关键点是，如果数组中有两个元素——比如 x[10] 和 x[30]——那么比较 x[10] 和 x[30] 应该产生与比较 x[30] 和 x[10] 一致的结果。如果一个是负数，另一个必须是正数或者两个都是零。 - Jonathan Leffler

为什么不在排序之前从数组中删除 NaN 值？即使您可以在存在 NaN 的情况下进行排序，任何后续代码都需要以某种方式处理它们的存在 - 选项几乎只有忽略、丢弃或报告。删除 NaN 可以让后续代码假定它们不存在，即较少需要检查。 - Peter

Answer 1

这只是对你的测试进行简单的重新排序，但如果需要，它可以使NaN的状态更加清晰易懂。

int compare(const void *a, const void *b)
{
    const long double fa = *(const long double *) a;
    const long double fb = *(const long double *) b;

    if (isnan(fa))
    {
        if (isnan(fb))
        {
            return 0;
        }
        return 1;
    }
    if (isnan(fb))
    {
        return -1;
    }
    if (fa > fb) return 1;
    if (fa < fb) return -1;

    /* no more comparisons needed */
    return 0;
}

由于对 NaN 的测试在顶部，且不应通过任何 NaN，因此底部三行可以安全地替换为您的

return (a > b) - (a < b);

除了讨论不同的NaN类型（听起来有点像有多少天使可以在CPU核心上跳舞），这应该足够稳定以满足您的需求，我无法看到此代码可能存在任何问题。

使用Clang编译器，无论是-ffast-math还是-fdenormal-fp-math=[ieee|preserve-sign|positive-zero]都不会产生其他结果。使用gcc进行测试时，即使使用-ffast-math、-funsafe-math-optimizations甚至-ffinite-math-only（后者最有可能是因为除了与NaN直接比较之外没有其他操作），也没有产生其他结果。

为了完整起见，我还测试了std::numeric_limits::signaling_NaN();和std::numeric_limits::quiet_NaN();（来自C++标头）-同样，在排序方面没有任何区别。

- Jongware

---

这可能会使NaN的状态更清晰，但您是否看到与原始compare()相比的功能差异-如果有的话？在NaN很少的典型数据集中，首先测试NaN似乎更慢。那么唯一的优点是代码清晰度吗？ - chux - Reinstate Monica

@chux：你在质疑你的程序是否正确排序。这段代码使用了另一种测试顺序，这可能导致不同的结果。但实际上并没有，它似乎回答了你的问题“我的compare()是否足够……”（是的）。所以，没有什么需要修复的地方，也很少有简化的余地。（我认为这样重新排列测试更易读，但没有副作用，我假设没有或只有微小的计算优势。） - Jongware

关于首先进行 isNaN 测试：这是为了消除任何关于可能未定义行为的疑虑。这样，要么首先剔除 NaN。一个小提示：每个测试都编译成单个 fucomi 指令。不知道是否会导致显著的减速（由于流水线等原因 - 真的不知道）。 - Jongware

这是一个好答案，并且是由于评论的强度，才导致接受该答案。 - chux - Reinstate Monica

@chux：嗨，伙计！我对回答你的高度技术问题有些疑虑，尤其是在阅读了那些值得保存的评论之后。同时，感谢你对我的回答进行追问，这真是一种愉悦！ - Jongware

Answer 2

The NaN test

int isnan(real-floating x);

isnan 宏用于确定其参数值是否为 NaN。首先，以比其语义类型更宽的格式表示的参数会被转换为其语义类型。然后根据参数的类型进行确定。^235
235 对于 isnan 宏，除非实现支持在评估类型中但不支持在语义类型中使用 NaN，否则确定的类型不重要。

isnan(some_long_double) 在大多数平台上都能正常工作，但在某些罕见的平台上可能不行。

int isunordered(real-floating x, real-floating y) 的作用类似于 isnan()，但它考虑了两个参数。

在许多平台上，代码可以使用 (a == a) 作为候选的 NaN 测试，因为当 a 是 NaN 时，它的值为 0，否则为 1。不幸的是，除非实现定义了 __STDC_IEC_559__，否则不能保证这种方法有效。

---

比较运算符
>=, >, <, <= 和 C11 7.12.14 比较宏

当至少有一个操作数是 NaN 时，使用 >=, >, <, <= 可能会导致 "无效" 的浮点异常。因此，在进行比较之前先测试是否为 NaN 是明智的，正如 @usr2564301 所回答的那样。

C 提供了宏 isgreaterequal()、isgreaterequal()、isless()、islessthna()，用于进行比较并且不会引发 "无效" 的浮点异常。对于 double 来说，这是一个很好的替代方案，但是这些宏使用了一个 real-floating，该类型可能与 long double 不同。例如，isgreater(long_double_a, long_double_a) 可能会被评估为 double 并且不能提供所需的比较结果。

分类宏的挑战在于 语义类型 可能比 long double 更窄。

---

以下代码结合了上述思路，并且据我所读的 C 规范是定义良好且功能正确的，除了一种罕见的情况：当 long double 具有 NaN 但 real-floating（通常为 double）没有时。

#include <math.h>

// compare 2 long double.  All NaN are greater than numbers.
int compare(const void *a, const void *b) {
  const long double *fa = (const long double *) a;
  const long double *fb = (const long double *) b;

  if (!isunordered(*fa, *fb)) {
    return (*fa > *fb) - (*fa < *fb);
  }

  if (!isnan(*fa)) {
    return -1;
  }
  return isnan(*fb);  // return 0 or 1
}

注意：阅读了许多好的评论并学到了很多知识，我将发布这个自我回答，如我可以回答自己的问题吗？中所述，除了接受其他答案。

- chux - Reinstate Monica