小埋社区

    • Register
    • Login
    • Search
    • Categories
    • Recent
    • Tags
    • Popular
    • Users
    • Groups

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

    编程
    1
    1
    149
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • Bruce
      Bruce ACG last edited by

      总有人说斐波那切查找法在极大数据量情况下比二分查找法快,因为斐波那切查找法只有加减法,没有除法,然而二分查找法取中值完全可以右移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

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

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

      1 Reply Last reply Reply Quote 0
      • First post
        Last post
      © 2017-2022 小埋社区 All Rights Reserved | 皖ICP备17016228号-2