else语句会拖慢运行时间?
发布于 7 年前 作者 fulvaz 3805 次预览 最后一次回复是 7 年前 来自 问答
在做leetcode的题目. 练习2sum的时候, 我的代码如下
var twoSum = function(nums, target) {
const set = {};
for (var i = 0; i < nums.length; i++) {
const val = nums[i];
const find = set[val];
if (find !== undefined) {
return [find, i,];
} else {
// 如果将来某个值满足target - nums[i], 则可以和这个位置匹配
set[target - val] = i;
}
}
};
80 ms, 排在60%
然后看了排在80%的代码, 就比我少了一个else, 我自己测试一下代码
var twoSum = function(nums, target) {
const set = {};
for (var i = 0; i < nums.length; i++) {
const val = nums[i];
const find = set[val];
if (find !== undefined) {
return [find, i,];
}
// 就这里去除了else
// 如果将来某个值满足target - nums[i], 则可以和这个位置匹配
set[target - val] = i;
}
};
56 ms, 排88%
一个else语句能有这么大影响? 什么原理?
11 回复
看起来像是常数时间的差距，有没有多提交几次看看结果。。。
搞acm的时候要是被卡常数时间，会很想杀了出题人。。
不必太抠细节，后面还有 三数之和，四数之和 等你。有你扣细节的时候。 这个东西还是经过基准测试再说吧，不过一般来说else在代码解析上是要走代码块跳转，最终编译成汇编也是走了地址跳转，这样CPU还要进行分支预测，100%走else，何必再搞个else。
使用 v8 7.1.302.4 生成的字节码，两者一模一样：
可能是偶然，和数据有关
偶然吧
@justjavac 本来还想V8的优化器应该没这么强，但大佬验证过了，应该是妥了。 这种靠参数判断的都能进行优化，强。 —这句话不准确容易产生误导，请看我8楼回答
@justjavac thanks~
@justjavac @fulvaz 如果我只定义twoSum方法，打印出的汇编代码如下，else代表有else，noelse代表无else。
根本没有执行，也就是说明jsutjavac的汇编是twoSum传入参数后执行后的优化结果。
所以V8也是根据参数传入后再进行优化的。 但由于twoSum的在if内被return了，所以这个函数是不可能被采取分支的，也就是说要么是被return，要么else一定执行。如果我对这个函数稍作修改，并传入不通参数会怎么样呢？即if内的把return去除，同时传入不同参数,会是怎么样呢？即else.js:
elseno.js:
结果是不同的，如下：
细心的人就会发现，else.js的汇编码，多出了地址跳转！我的一般理解，看来是没错的。而上文的汇编码正好一致，也恰好是这个方法的return造成。但这个并不代表V8的优化器的成本下降，即使是优化后是相同汇编码，但else可能造成走更多步的优化策略。
备注：汇编是使用目前v8的master分支的d8打印的，node打印出的无效信息过多了。
我忽略这个了，谢谢 @zy445566
@justjavac 并没有，你上文只是说了一个事实，我觉得可能太简单了，容易让人有错误的遐想。所以做了下补充
@zy445566 代码里是判断 undefined，我的测试代码居然没有使用 undefined，失误失误