C++,二分查找法与斐波那切查找法效率对比


  • ACG

    总有人说斐波那切查找法在极大数据量情况下比二分查找法快,因为斐波那切查找法只有加减法,没有除法,然而二分查找法取中值完全可以右移1位center = (lo + hi)>>1来实现,位移操作是比加减法还要快的操作,因此我决定实践出真实

    PS:有个老哥已经做过实验了,在极大数据量情况下斐波那切查找法确实快一点,但是他的二分查找法是用除法实现的
    原贴:https://blog.csdn.net/fovwin/article/details/9077017
    本贴基于原贴代码,将除法改为位移,将C的callac操作改为C++的new,重新试验

    测试环境:

    CPU: R7 1700 @3.80GHz
    RAM: 32G
    OS: Windows Pro for Workstation 1909
    Compiler: MSVC 2019
    C++ standard: ISO C++17

    输入数据:长度为400,000,000的有序数组,array[i]=i
    对比方式:生成release版程序,从array中寻找数据4613841,用VS自带的性能探测器统计所需时间

    image.png
    二分查找法用时:521ms
    image.png
    534ms

    二分查找法险胜,二者差距几乎可以忽略不计,而数据输入的长度已经远超原贴实验中的长度了,且继续增加长度会引起数组上溢

    结论:两种算法在海量数据查找中性能差距可以忽略不计


Log in to reply