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

Question

我有一个向量,它包含一些相互分离的浮点值,并根据某些函数进行排序.例如,

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,例如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;

并获得不同的位置(相应的值非常不同).

在查看用法时,看起来,它们与寻找密钥有关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;

我在X86机器上用GCC输出

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.在这篇PDF的第38页(又名"内部页码"第3-12页)中,我发现吸烟枪很可能:

%st(0) 浮点返回值出现在浮点寄存器堆栈的顶部; 浮点寄存器中单精度值或双精度值的表示没有区别.如果函数未返回浮点值,则该寄存器必须为空.在G进入函数之前,该寄存器必须为空.

接着说几段后:

浮点返回值出现在Intel387寄存器堆栈的顶部.然后调用者必须从Intel387堆栈中删除该值,即使它不使用该值.任何一方未能履行其义务都会导致程序行为不明确.标准调用序列不包括检测此类故障的任何方法,也不包括检测返回值类型不匹配的方法.因此,用户必须正确声明所有功能.浮点寄存器中的单精度,双精度值或扩展精度值的表示没有区别.

进一步搜索第3-27页(PDF第53页)和第3-28页(PDF第54页)会产生以下令人困惑的曲折.图3-30中的表格表明初始舍入模式为"53位(双精度)",这就是进程初始化时的模式.

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

应小心更改初始浮点状态.特别是,如果精度控制设置为小于53位,许多浮点例程可能会产生未定义的行为._fpstart例程(参见第6章)将精度控制更改为64位,并设置要询问的所有异常.这是符合ANSI C标准和IEEE 754浮点标准所需的默认状态.

甲夫妇 参考的净额S指示的Linux确实设置的x87至扩展精度(至少在32位ABI).

编辑2

看来扩展精度确实是罪魁祸首.我按照此页面的建议将以下代码添加到测试用例中:

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

// ...

set_fpu(0x27F);

添加这些行后,测试用例将返回与64位ABI相同的值.

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

你可以重新运行你的排序和搜索代码,FPU设置为53位精度,如上所述,看看是否能解决你在两个lambda表达式之间看到的差异？