我正在InterviewBit上尝试关于数组的问题.在这个问题中,我创建了一个内联函数,返回整数的绝对值.但有人告诉我,我的算法在提交时效率不高.但当我改为使用abs()C++库时,它给出了正确的答案判决.
这是我的功能得到了一个低效的判决 -
inline int abs(int x){return x>0 ? x : -x;}
int Solution::coverPoints(vector<int> &X, vector<int> &Y) {
int l = X.size();
int i = 0;
int ans = 0;
while (i<l-1){
ans = ans + max(abs(X[i]-X[i+1]), abs(Y[i]-Y[i+1]));
i++;
}
return ans;
}
这是得到正确答案的那个-
int Solution::coverPoints(vector<int> &X, vector<int> &Y) {
int l = X.size();
int i = 0;
int ans = 0;
while (i<l-1){
ans = ans + max(abs(X[i]-X[i+1]), abs(Y[i]-Y[i+1]));
i++;
}
return ans;
}
为什么会发生这种情况,因为我认为内联函数最快,因为没有调用？或者该网站有错误？如果网站是正确的,那么C++ abs()使用什么比这更快inline abs()？
gez*_*eza 26
我不同意他们的判决.他们显然是错的.
在当前的优化编译器上,两种解决方案都能产生完全相同的输出.甚至,如果他们不产生完全相同的,他们会产生高效代码库中的一个(也可能是有点令人惊讶,一切都匹配:算法,使用的寄存器或许是因为实际的库实现是一样的.作为OP的一个？).
没有理智的优化编译器会在你的abs()代码中创建分支(如果它可以在没有分支的情况下完成),正如其他答案所暗示的那样.如果编译器没有优化,那么它可能不是内联库abs(),因此它也不会很快.
优化abs()是编译器最简单的事情之一(只需在窥孔优化器中为它添加一个条目,并完成).
此外,我已经看到过去的库实现,其中abs()实现为非内联库函数(虽然很久以前).
证明两种实现都是相同的:
GCC:
myabs:
mov edx, edi ; argument passed in EDI by System V AMD64 calling convention
mov eax, edi
sar edx, 31
xor eax, edx
sub eax, edx
ret
libabs:
mov edx, edi ; argument passed in EDI by System V AMD64 calling convention
mov eax, edi
sar edx, 31
xor eax, edx
sub eax, edx
ret
铛:
myabs:
mov eax, edi ; argument passed in EDI by System V AMD64 calling convention
neg eax
cmovl eax, edi
ret
libabs:
mov eax, edi ; argument passed in EDI by System V AMD64 calling convention
neg eax
cmovl eax, edi
ret
Visual Studio(MSVC):
libabs:
mov eax, ecx ; argument passed in ECX by Windows 64-bit calling convention
cdq
xor eax, edx
sub eax, edx
ret 0
myabs:
mov eax, ecx ; argument passed in ECX by Windows 64-bit calling convention
cdq
xor eax, edx
sub eax, edx
ret 0
ICC:
myabs:
mov eax, edi ; argument passed in EDI by System V AMD64 calling convention
cdq
xor edi, edx
sub edi, edx
mov eax, edi
ret
libabs:
mov eax, edi ; argument passed in EDI by System V AMD64 calling convention
cdq
xor edi, edx
sub edi, edx
mov eax, edi
ret
在Godbolt Compiler Explorer上亲自查看,您可以在其中检查各种编译器生成的机器代码.(链接由Peter Cordes亲切提供.)
use*_*670 19
您abs根据条件执行分支.虽然内置变体只是从整数中删除了符号位,但很可能只使用了几条指令.可能的装配示例(取自此处):
cdq
xor eax, edx
sub eax, edx
cdq复制寄存器eax的符号以注册edx.例如,如果它是正数,则edx将为零,否则,edx将为0xFFFFFF,表示-1.如果是正数,则带有原点编号的xor操作将不会改变任何数字(任何数字x或0都不会改变).但是,当eax为负时,eax xor 0xFFFFFF会产生(不是eax).最后一步是从eax中减去edx.同样,如果eax为正,则edx为零,并且最终值仍然相同.对于负值,(~eax) - (-1)= -eax这是所需的值.
正如您所看到的,这种方法只使用三个简单的算术指令而根本没有条件分支.
编辑:经过一些研究后发现,abs的许多内置实现使用相同的方法return __x >= 0 ? __x : -__x;,并且这样的模式是编译器优化的明显目标,以避免不必要的分支.
但是,这并不能证明使用自定义abs实现是合理的,因为它违反了DRY原则,没有人能够保证您的实现对于更复杂的场景和/或不寻常的平台同样有用.通常,只有在存在明确的性能问题或在现有实现中检测到某些其他缺陷时,才应考虑重写某些库函数.
Edit2:只需从int切换到float,就会显着降低性能:
float libfoo(float x)
{
return ::std::fabs(x);
}
andps xmm0, xmmword ptr [rip + .LCPI0_0]
和自定义版本:
inline float my_fabs(float x)
{
return x>0.0f?x:-x;
}
float myfoo(float x)
{
return my_fabs(x);
}
movaps xmm1, xmmword ptr [rip + .LCPI1_0] # xmm1 = [-0.000000e+00,-0.000000e+00,-0.000000e+00,-0.000000e+00]
xorps xmm1, xmm0
xorps xmm2, xmm2
cmpltss xmm2, xmm0
andps xmm0, xmm2
andnps xmm2, xmm1
orps xmm0, xmm2
如果您使用标准库版本,您的解决方案可能会被教科书"更清晰",但我认为评估是错误的.您的代码被拒绝的确没有正当理由.
这是某些人正式正确(通过教科书)的情况之一,但坚持以纯粹的愚蠢方式知道唯一正确的解决方案,而不是接受替代解决方案并说"......但这是最好的做法,你知道吗.
从技术上讲,这是一种正确,实用的方法,可以说"使用标准库,就是它的用途,它可能会尽可能地优化".即使"尽可能优化"部分可以在某些情况下由于标准对某些算法和/或容器的某些限制而非常错误.
现在,除了意见,最佳实践和宗教.事实上,如果你比较两种方法......
int main(int argc, char**)
{
40f360: 53 push %rbx
40f361: 48 83 ec 20 sub $0x20,%rsp
40f365: 89 cb mov %ecx,%ebx
40f367: e8 a4 be ff ff callq 40b210 <__main>
return std::abs(argc);
40f36c: 89 da mov %ebx,%edx
40f36e: 89 d8 mov %ebx,%eax
40f370: c1 fa 1f sar $0x1f,%edx
40f373: 31 d0 xor %edx,%eax
40f375: 29 d0 sub %edx,%eax
//}
int main(int argc, char**)
{
40f360: 53 push %rbx
40f361: 48 83 ec 20 sub $0x20,%rsp
40f365: 89 cb mov %ecx,%ebx
40f367: e8 a4 be ff ff callq 40b210 <__main>
return (argc > 0) ? argc : -argc;
40f36c: 89 da mov %ebx,%edx
40f36e: 89 d8 mov %ebx,%eax
40f370: c1 fa 1f sar $0x1f,%edx
40f373: 31 d0 xor %edx,%eax
40f375: 29 d0 sub %edx,%eax
//}
......它们会产生完全相同的相同指令.
但即使编译器都使用比较后跟一个条件移动(它可能做的更复杂的"分支任务",并且将例如在的情况下做min/ max),这也许一个CPU周期左右,比较慢有点黑客,所以除非你这样做几百万次,否则"无效率"的说法有点令人怀疑.
一次缓存未命中,并且您有条件移动的罚款的百倍.
对于这两种方法都有正确的论据,我不会详细讨论.我的观点是,将OP的解决方案视为"完全错误",因为这种小而不重要的细节是相当狭隘的.
编辑:
(有趣的琐事)
我只是试着在我的Linux Mint盒子上试图获得乐趣而且没有任何利润,它使用的是较旧版本的GCC(5.4与上面的7.1相比).
由于我包括<cmath>没有太多的想法(嘿,一个abs 非常明显属于数学的功能,不是它!)而不是<cstdlib>哪个主机整数重载,结果是,好...... 令人惊讶.调用库函数远不如单表达式包装器.
现在,为了保护标准库,如果包含<cstdlib>,那么,在任何一种情况下,生成的输出都是完全相同的.
作为参考,测试代码如下:
#ifdef DRY
#include <cmath>
int main(int argc, char**)
{
return std::abs(argc);
}
#else
int abs(int v) noexcept { return (v >= 0) ? v : -v; }
int main(int argc, char**)
{
return abs(argc);
}
#endif
...导致
4004f0: 89 fa mov %edi,%edx
4004f2: 89 f8 mov %edi,%eax
4004f4: c1 fa 1f sar $0x1f,%edx
4004f7: 31 d0 xor %edx,%eax
4004f9: 29 d0 sub %edx,%eax
4004fb: c3 retq
现在,显然很容易陷入无意中使用错误的标准库函数的陷阱(我演示了我自己多么容易!).所有这些都没有来自编译器的任何警告,例如"嘿,你知道,你在double整数值上使用了一个重载(好吧,显然没有警告,这是一个有效的转换).
考虑到这一点,可能还有另一个"理由",为什么OP提供他自己的单线程并不是那么糟糕和错误.毕竟,他本可以犯同样的错误.
| 归档时间： |
|
| 查看次数： |
1701 次 |
| 最近记录： |