c++ - 如何从有序集中返回最近的元素？

Question

我有一个 vector ，其中包含一些浮点值，这些值彼此合理分开，并根据某些函数进行排序。例如，

double foo(double x)
{
   return 199.1*x;
}
double x = 3000000.3157;
double y = x + DBL_EPSILON;

std::vector<double> s { y,y+10};
std::sort(s.begin(),s.end(),[](double x,double y) { return foo(x) < foo(y) ;} );

现在有人拥有一把接近我在 s 中的 key ，例如 x .在lambda时代, 都有自己的小搜索功能，比如

std::cout<<std::distance(s.begin(),std::lower_bound(s.begin(),s.end(),x,
[] (double x,double y) { return foo(x) < foo(y);}))<<std::endl;
    std::cout<<std::distance(s.begin(),std::lower_bound(s.begin(),s.end(),x,
[] (double x,double y) { double f1 = foo(x);
                         double f2 = foo(y);
                         return f1 < f2;}))<<std::endl;

得到不同的位置(对应的值也大不相同)。

在查看用法时，似乎它们与查找 key k有关。

• 一组有序浮点值中最接近的元素。
• 比率，r ，它(理想情况下应该是 [0,1] )附加到连续值 x1 & x2这样函数的返回值 f(x1,x2,r)约等于 k .

它们看起来都相关，并且与插值相关。我如何实现它们？

注意:

在下面的简短代码中

double f1 = foo(x);
double f2 = foo(y);
bool l = foo(x) < foo(y);
std::cout<<std::boolalpha<<(f1<f2)<< " "<<l<<" "<<(f1 == f2) << std::endl;
std::cout << std::boolalpha << (foo(x) < foo(y)) << " "<< (foo(y) < foo(x))
          << " "<<(foo(x) == foo(y) )<<std::endl;
std::cout << std::boolalpha << std::isless(foo(x) , foo(y))
          << " "<< std::isless(foo(y) , foo(x)) <<std::endl;

我用 GCC 得到输出在 X86 机器上作为

false true true
true true false
false false

虽然我的猜测是 GCC 会在运行时执行更高的精度(80 位)，除非我强制它存储结果，从而导致 l 的不同结果。 & (f1<f2) (这导致了上述问题)。我也有兴趣知道为什么 foo(x) < foo(y)和 foo(y) < foo(x)都说true !

Answer 1

这两个语句没有完成任何事情，因为对于这些数字，DBL_EPSILON 小于 1ulp:

double x = 3000000.3157;
double y = x + DBL_EPSILON;

可以肯定的是，我打印了 x 和 y 的十六进制表示并得到以下内容:

4146E3602868DB8C
4146E3602868DB8C

当我通过几个不同版本的 G++(4.4.5 和 4.8.0)运行问题底部的示例并同时优化(-O3)和关闭(无标志)时，我得到以下输出:

false false true
false false true
0 0

我怀疑您所看到的行为正是您假设的原因:您的编译器对中间结果的精度更高，并且正在渗透到这些比较中。

您使用的是什么版本的编译器，应用程序中的其他代码是否调整任何舍入模式？您使用的是什么编译标志？

---

编辑 1

通过在优化关闭 和 32 位模式下重新编译，我能够重现您的行为。在那种模式下，我看到编译器将 foo 的结果留在浮点堆栈上:

_Z3food:
.LFB1053:
    .cfi_startproc
    pushl   %ebp    #
    .cfi_def_cfa_offset 8
    .cfi_offset 5, -8
    movl    %esp, %ebp  #,
    .cfi_def_cfa_register 5
    subl    $8, %esp    #,
    movl    8(%ebp), %eax   # x, tmp61
    movl    %eax, -8(%ebp)  # tmp61, x
    movl    12(%ebp), %eax  # x, tmp62
    movl    %eax, -4(%ebp)  # tmp62, x
    fldl    -8(%ebp)    # x
    fldl    .LC0    #
    fmulp   %st, %st(1) #,
    leave

这表明这是 i386 ABI 的一个怪癖。为了检验这个理论，我更仔细地研究了 i386 ABI。在 page 38 of this PDF (也就是内部页码的“第 3-12 页”)，我发现可能是确凿的证据:

%st(0) Floating-point return values appear on the top of the floating- point register stack; there is no difference in the representation of single- or double-precision values in floating-point registers. If the function does not return a floating-point value, then this register must be empty. This register must be empty before G entry to a function.

后面几段接着说:

A floating-point return value appears on the top of the Intel387 register stack. The caller then must remove the value from the Intel387 stack, even if it doesn’t use the value. Failure of either side to meet its obligations leads to undefined program behavior. The standard calling sequence does not include any method to detect such failures nor to detect return value type mismatches. Therefore the user must declare all functions properly. There is no difference in the representation of single-, double- or extended-precision values in floating-point registers.

进一步向下搜索到第 3-27 页(PDF 第 53 页)和第 3-28 页(PDF 第 54 页)会出现以下令人困惑的曲折。图3-30中的表格表明初始舍入模式是“53位( double )”，这是进程初始化时的模式。

它继续在下一页给出以下警告:

The initial floating-point state should be changed with care. In particular, many floating-point routines may produce undefined behavior if the precision control is set to less than 53 bits. The _fpstart routine (see Chapter 6) changes the precision control to 64 bits and sets all exceptions to be asked. This is the default state required for conformance to the ANSI C standard and to the IEEE 754 Floating-point standard.

A couple reference网络上的 s 表明 Linux 确实将 x87 设置为扩展精度(至少在 32 位 ABI 中)。

---

编辑 2

看来扩展精度确实是罪魁祸首。我在测试用例中添加了以下代码，as suggested by this page :

void set_fpu (unsigned int mode)
{
      asm ("fldcw %0" : : "m" (*&mode));
}

// ...

set_fpu(0x27F);

添加这些行后，测试用例返回我在 64 位 ABI 中看到的相同值。

因此，假设您在 Linux 下编译 32 位程序，这似乎是您看到奇怪的比较和排序结果的原因。

您能否像我上面那样在 FPU 设置为 53 位精度的情况下重新运行您的排序和搜索代码，看看这是否解决了您在两个 lambda 表达式之间看到的差异？