功能开销可以使程序减慢50倍？

Question

我有一个代码,我正在为一个项目运行.它是O(N ^ 2),其中N对于我的情况是200.有一种算法可以将此O(N ^ 2)转换为O(N logN).这意味着,使用这种新算法,它应该快〜100倍.然而,我只是增加了2倍(也快了2倍).

我试图缩小范围,看看我是否搞砸了什么,或者它是否是我编写这个程序的方式所固有的.首先,我在嵌套类中有很多函数开销.例如,我有很多这个(在很多循环中):

energy = globals->pair_style->LJ->energy();

自从我得到正确的结果,当涉及到实际的数据,只是错误的速度增加,我想知道,如果功能开销实际上造成的是多速度降低,多达50倍.

谢谢!

Answer 1

首先,你的解释,即O(N logN)是比〜100倍的速度O(N^2)进行N=200不正确.大哦符号处理限制中的上限和行为,并不考虑复杂性中的任何乘法常数.

其次,是的,在现代硬件功能上,由于管道中断,调用往往相对昂贵.要了解在您的情况下这有多大的因素,您必须提出一些微基准测试.