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，但是我这边怎么这么繁琐，没你的简易
反汇编一下就知道区别了。
循环条件的判断，一个是迭代量跟某个固定值的比较（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
效率一样，没有任何区别。
没区别。
你又没有把n变成log(n)，这样的效率比较有什么意义？
我知道++i的效率是高于i++的，
你这两个函数，从遍历角度来看，都是o(n)的
如果真的要讨论效率的话，我只能说，我觉得前面那个要快一点，因为，一开始乘的数字会小一点，大概也许会快一点吧
除非你的fact是一个非常奇怪的数据类型，它和不同大小的i相乘所耗费的时间还不同。
你分别大括号里的for之前一个记录时间,for之后一个记录时间,然后相减，分别看一下它们执行的时间毫秒差就可以看出来了。
这应该效率一样的把， 不觉得会有什么区别
我当时也觉得应该效率一样，不过现在的看法是：
i=1中，只要读i的地址，然后把1传递即可
i=limit中，既要读i的地址，也要读limit的地址，然后再传值，所以我感觉是第二个效率高，大家觉得呢
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的取值范围,上面下面进入循环里面的情况不一样
感觉一样都是O(n)。
一样！ 编译器都应该会优化循环limit次
我怎么感觉会报未定义的i、fact错误呢
[XXXXX ~]$ cat x.c
int fact1(int limit)
{
int i, n = 1;
for (i = 0; i < limit; i++)
n *= i;
return n;
}
int fact2(int limit)
{
int i, n = 1;
for (i = limit; i != 0; i--)
n *= i;
return n;
}
[XXXXX ~]$ gcc -S x.c -o -
.file "x.c"
.text
.globl fact1
.type fact1, @function
fact1:
.LFB0:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
movl %edi, -20(%rbp)
movl $1, -4(%rbp)
movl $0, -8(%rbp)
jmp .L2
.L3:
movl -4(%rbp), %eax
imull -8(%rbp), %eax
movl %eax, -4(%rbp)
addl $1, -8(%rbp)
.L2:
movl -8(%rbp), %eax
cmpl -20(%rbp), %eax
jl .L3
movl -4(%rbp), %eax
leave
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE0:
.size fact1, .-fact1
.globl fact2
.type fact2, @function
fact2:
.LFB1:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
movl %edi, -20(%rbp)
movl $1, -4(%rbp)
movl -20(%rbp), %eax
movl %eax, -8(%rbp)
jmp .L6
.L7:
movl -4(%rbp), %eax
imull -8(%rbp), %eax
movl %eax, -4(%rbp)
subl $1, -8(%rbp)
.L6:
cmpl $0, -8(%rbp)
jne .L7
movl -4(%rbp), %eax
leave
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE1:
.size fact2, .-fact2
.ident "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-4)"
.section .note.GNU-stack,"",@progbits
[XXXXX ~]$ gcc -S x.c -o - -O3
.file "x.c"
.text
.p2align 4,,15
.globl fact1
.type fact1, @function
fact1:
.LFB0:
.cfi_startproc
xorl %edx, %edx
testl %edi, %edi
movl $1, %eax
jle .L3
.p2align 4,,10
.p2align 3
.L6:
imull %edx, %eax
addl $1, %edx
cmpl %edi, %edx
jne .L6
.L3:
rep
ret
.cfi_endproc
.LFE0:
.size fact1, .-fact1
.p2align 4,,15
.globl fact2
.type fact2, @function
fact2:
.LFB1:
.cfi_startproc
testl %edi, %edi
movl $1, %eax
je .L11
.p2align 4,,10
.p2align 3
.L14:
imull %edi, %eax
subl $1, %edi
jne .L14
.L11:
rep
ret
.cfi_endproc
.LFE1:
.size fact2, .-fact2
.ident "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-4)"
.section .note.GNU-stack,"",@progbits
我的汇编如下
ubuntu:~/data$ gcc -S x.c -o - -O3
.file "x.c"
.text
.p2align 4,,15
.globl fact1
.type fact1, @function
fact1:
.LFB24:
.cfi_startproc
rep
ret
.cfi_endproc
.LFE24:
.size fact1, .-fact1
.p2align 4,,15
.globl fact2
.type fact2, @function
fact2:
.LFB25:
.cfi_startproc
rep
ret
.cfi_endproc
.LFE25:
.size fact2, .-fact2
.globl fact
.bss
.align 4
.type fact, @object
.size fact, 4
fact:
.zero 4
.comm limit,4,4
.comm i,4,4
.ident "GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3"
.section .note.GNU-stack,"",@progbits
ubuntu:~/data$ gcc -S x.c -o - -O1
.file "x.c"
.text
.globl fact1
.type fact1, @function
fact1:
.LFB24:
.cfi_startproc
cmpl $1, %edi
jle .L4
movl $1, %eax
.L3:
addl $1, %eax
cmpl %edi, %eax
jne .L3
.L4:
rep
ret
.cfi_endproc
.LFE24:
.size fact1, .-fact1
.globl fact2
.type fact2, @function
fact2:
.LFB25:
.cfi_startproc
testl %edi, %edi
je .L9
.L8:
subl $1, %edi
jne .L8
.L9:
rep
ret
.cfi_endproc
.LFE25:
.size fact2, .-fact2
.globl fact
.bss
.align 4
.type fact, @object
.size fact, 4
fact:
.zero 4
.comm limit,4,4
.comm i,4,4
.ident "GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3"
.section .note.GNU-stack,"",@progbits