C_I*_*ner 6 c algorithm performance primes sieve-of-eratosthenes
我试图比较两种算法的运行时速度:一个强力C程序打印素数(10,000个数字)和一个Sieve of Eratosthenes C程序(也是10,000个素数).
我测得的筛选算法的运行时间为:0.744秒
我测得的蛮力算法的运行时间为:0.262秒
然而,有人告诉我,Eratosthenes算法的筛子比蛮力方法更有效,所以我认为它运行得更快.所以要么我错了,要么我的程序有缺陷(我怀疑).
因此,我的问题是:由于我得到了与我预期相反的结果,这是否证明了与试验师相比,Eratosthenes的Sieve 在速度方面确实是效率较低的算法？
我不确定它是否有任何意义,但我使用的是Dev C++编译器和Windows 7.
TL; DR:比较一个输入大小的代码变量的速度是没有意义的; 比较经验增长顺序真正反映了代码的算法性质,并且对于相同的输入大小测试范围,在不同的测试平台上将保持一致.比较绝对速度值仅对具有相同渐近或至少局部生长行为的代码变体有意义.
仅在一个输入尺寸下测量两个实现的速度是不够的.通常需要几个数据点来评估代码增长的运行时间经验顺序(因为代码可以使用不同的输入大小运行).它被发现作为运行时间比率的对数,以输入尺寸比率为基础.
因此,即使在某些输入code_1运行10比快倍code_2,但它的运行时间加倍与输入大小每增加一倍,而对于code_2只增长为1.1倍,很快code_2将成为远远快很多code_1.
因此,算法效率的真正衡量标准是其运行时复杂度(以及其空间的复杂性,即内存要求).当我们凭经验测量时,我们只测量手头的特定代码(在特定输入大小范围内),而不是算法本身,即它的理想实现.
特别是,试验划分的理论复杂性O(n^1.5 / (log n)^0.5)在产生的n个素数中通常被视为~ n^1.40..1.45经验增长的顺序(但~n^1.3最初可以是较小的输入规模).对于Eratosthenes的筛子,它O(n log n log (log n))通常被视为~ n^1.1..1.2.但是,试验部门和Eratosthenes的筛子肯定存在次优实施方式~n^2.0.
所以不,这没有任何证据.一个数据点是没有意义的,至少需要三个才能获得"全局",即能够确定地预测更大输入大小所需的运行时间/空间.
具有已知确定性的预测是科学方法的全部内容.
顺便说一句,你的运行时间很长.10,000个素数的计算应该几乎是瞬时的,远远低于在快速盒子上运行的C程序的1/100秒.也许你也在测量打印时间.别.:)
不,经过的运行时间不是测量效率的标准,因为它在不同平台之间变化 - 说"我的算法在10秒内运行"几乎没有提供关于算法本身的信息.除此之外,您还需要列出整个环境规范和同时运行的其他进程,这将是一个巨大的混乱.因此,订单符号的发展(Big Oh,Little Oh,Omega等).
效率通常分为两个小节:
...其中一种算法可能具有极高的时间效率,但在空间方面效率非常低.反之亦然.在缩放他们需要为给定输入执行的指令量时,基于它们的渐近行为来分析算法n.这是对博士计算机科学家精心研究的领域的一个非常高级的解释 - 我建议你在这里阅读更多关于它的最佳低级解释.
请注意,我附加了Big Oh表示法的链接 - 姐妹符号都可以在Wikipedia页面上找到,它通常是一个很好的起点.它也会影响空间和时间效率的差异.
使用Big Oh实现时间效率的小应用:
考虑一下Racket中的以下递归函数(如果我知道它将在Python中 - 我可以做的最好的伪代码):
(define (fn_a input_a)
(cond
[(empty? input_a) empty]
[(empty? (rest input_a)) input_a]
[(> (first input_a) (fn_a (rest input_a))) (cons (first input_a) empty)]
[else (fn_a (rest input_a))]))
......我们看到:empty?,rest,>和first都是O(1).我们还注意到,在最坏的情况下,呼叫来取得fn_a在对第三个条件和第四个条件rest的input_a.然后我们可以将递归关系写为T(n)= O(1)+ 2T(n - 1).在递归关系图表中查看,我们看到它fn_a的顺序为O(2 ^ n),因为在最坏的情况下,会进行两次递归调用.
同样重要的是要注意,通过Big Oh的正式定义,说明fn_aO(3 ^ n)也是正确的(无论多么无用).分析时使用Big Oh表示很多算法,但是使用Big Theta来收紧边界更合适,本质上意味着:相对于给定算法,最低,最准确的顺序.
小心,阅读正式的定义!