2 china123w china123w 于 2015.05.28 16:58 提问

讨论下这两个函数fact1和fact2的效率

int fact1(int limit)
{
for (i=1;i<limit;i++) fact *= i;
}
int fact2(int limit)
{
for (i=limit; i!=0; i--) fact *= i;
}
这个是当时上学老师出的一道题,我也觉得应该效率一样,不知道各位有什么不同看法

根据10楼兄弟的回答,我用objdump的反汇编结果如下:

 00000000004004c2 <fact1>:
  4004c2:   55                      push   %rbp
  4004c3:   48 89 e5                mov    %rsp,%rbp
  4004c6:   89 7d ec                mov    %edi,-0x14(%rbp)
  4004c9:   c7 45 f8 00 00 00 00    movl   $0x0,-0x8(%rbp)
  4004d0:   c7 45 fc 00 00 00 00    movl   $0x0,-0x4(%rbp)
  4004d7:   c7 45 f8 01 00 00 00    movl   $0x1,-0x8(%rbp)
  4004de:   eb 0e                   jmp    4004ee <fact1+0x2c>
  4004e0:   8b 45 fc                mov    -0x4(%rbp),%eax
  4004e3:   0f af 45 f8             imul   -0x8(%rbp),%eax
  4004e7:   89 45 fc                mov    %eax,-0x4(%rbp)
  4004ea:   83 45 f8 01             addl   $0x1,-0x8(%rbp)
  4004ee:   8b 45 f8                mov    -0x8(%rbp),%eax
  4004f1:   3b 45 ec                cmp    -0x14(%rbp),%eax
  4004f4:   7c ea                   jl     4004e0 <fact1+0x1e>
  4004f6:   5d                      pop    %rbp
  4004f7:   c3                      retq   

00000000004004f8 <fact2>:
  4004f8:   55                      push   %rbp
  4004f9:   48 89 e5                mov    %rsp,%rbp
  4004fc:   89 7d ec                mov    %edi,-0x14(%rbp)
  4004ff:   c7 45 f8 00 00 00 00    movl   $0x0,-0x8(%rbp)
  400506:   c7 45 fc 00 00 00 00    movl   $0x0,-0x4(%rbp)
  40050d:   8b 45 ec                mov    -0x14(%rbp),%eax
  400510:   89 45 f8                mov    %eax,-0x8(%rbp)
  400513:   eb 0e                   jmp    400523 <fact2+0x2b>
  400515:   8b 45 fc                mov    -0x4(%rbp),%eax
  400518:   0f af 45 f8             imul   -0x8(%rbp),%eax
  40051c:   89 45 fc                mov    %eax,-0x4(%rbp)
  40051f:   83 6d f8 01             subl   $0x1,-0x8(%rbp)
  400523:   83 7d f8 00             cmpl   $0x0,-0x8(%rbp)
  400527:   75 ec                   jne    400515 <fact2+0x1d>
  400529:   8b 45 fc                mov    -0x4(%rbp),%eax
  40052c:   5d                      pop    %rbp
  40052d:   c3                      retq   

应该和你的觉过一样,减法可以直接判断,加法多了一个mov,但是我这边怎么这么繁琐,没你的简易

13个回答

nswcfd
nswcfd   2015.05.29 18:47
已采纳

反汇编一下就知道区别了。

循环条件的判断,一个是迭代量跟某个固定值的比较(cmp %eax, XXX),一个是迭代量是否为0的比较(test %eax, %eax)。
cmp和test的效率有区别吗?

-O3之后,就会发现,循环体是4条指令跟3条指令的区别。
也就是说,可以直接利用减法的结果来进行判断调整,加法则不行,还需要额外的比较。

.L4:
imull %eax, %edx
addl $1, %eax
cmpl %edi, %eax
jne .L4

.L14:
imull %eax, %edx
subl $1, %eax
jne .L14

china123w
china123w 明白了,多谢,我ubuntu的编译器和你不一样,"GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3“
2 年多之前 回复
nswcfd
nswcfd 就是gcc v4.4.7 gcc -S -O3,只贴了一部分的汇编吗(循环相关的)
2 年多之前 回复
nswcfd
nswcfd 就是gcc v4.4.7 gcc -S -O3,只贴了一部分的汇编吗(循环相关的)
2 年多之前 回复
china123w
china123w 使用O1可以看到,如果使用O3全部被优化掉了,什么都看不到,gcc -S efficient.c -o 1231.s -O1,最后是多了一个cmpl
2 年多之前 回复
china123w
china123w 我这个汇编之多了一个mov,你可以看我的提问上面贴的反汇编结果
2 年多之前 回复
china123w
china123w 兄弟,你这个是什么编译器?你用的反汇编是objdump吗?
2 年多之前 回复
china123w
china123w 兄弟,你这个是什么编译器?你用的反汇编是objdump吗?
2 年多之前 回复
china123w
china123w 兄弟,你这个是什么编译器?你用的反汇编是objdump吗?
2 年多之前 回复
caozhy
caozhy   Ds   Rxr 2015.05.28 17:03

效率一样,没有任何区别。

Tiger_Zhao
Tiger_Zhao   Rxr 2015.05.28 17:04

没区别。
你又没有把n变成log(n),这样的效率比较有什么意义?

qq_17246605
qq_17246605   2015.05.28 17:05

我知道++i的效率是高于i++的,
你这两个函数,从遍历角度来看,都是o(n)的
如果真的要讨论效率的话,我只能说,我觉得前面那个要快一点,因为,一开始乘的数字会小一点,大概也许会快一点吧

china123w
china123w nswcfd大神给的时正解,你可以看下
2 年多之前 回复
qq_17246605
qq_17246605 回复china123w: 是的,毕竟只是猜测,科学总是有很多出乎人意料的结果
2 年多之前 回复
china123w
china123w 大概也许?呵呵……++i比i++块的原理应该是:这里中间使用了一个局部变量。
2 年多之前 回复
caozhy
caozhy   Ds   Rxr 2015.05.28 17:06

除非你的fact是一个非常奇怪的数据类型,它和不同大小的i相乘所耗费的时间还不同。

u012216727
u012216727   Ds   Rxr 2015.05.28 17:09

你分别大括号里的for之前一个记录时间,for之后一个记录时间,然后相减,分别看一下它们执行的时间毫秒差就可以看出来了。

china123w
china123w 回复wolf094014: 这个有啥好写论文的,我用了记录时间的方式,发现时间是一样的,ms为单位
2 年多之前 回复
u012216727
u012216727 为什么要理论上的,眼见为实,没经过测试,你在这里再怎么猜测都是没用的;你不会要写论文吧??????
2 年多之前 回复
china123w
china123w 这个是实际上的,理论上呢?
2 年多之前 回复
edouardzyc
edouardzyc   2015.05.28 17:14

这应该效率一样的把, 不觉得会有什么区别

china123w
china123w   2015.05.28 17:15

我当时也觉得应该效率一样,不过现在的看法是:

i=1中,只要读i的地址,然后把1传递即可
i=limit中,既要读i的地址,也要读limit的地址,然后再传值,所以我感觉是第二个效率高,大家觉得呢

u010209218
u010209218   2015.05.28 20:20

int fact1(int limit)
{
for (i=1;i<limit;i++) fact *= i;
}
int fact2(int limit)
{
for (i=limit; i!=0; i--) fact *= i;
}
你老师当时没给你答案吗,哎,看limit的取值范围,上面下面进入循环里面的情况不一样

a1193561652
a1193561652   Rxr 2015.05.29 13:18

感觉一样都是O(n)。

共13条数据 1 尾页
Csdn user default icon
上传中...
上传图片
插入图片