else语句会拖慢运行时间?

问答

Ffulvaz发布于8 年前最后回复8 年前|11 回复4009 浏览0 收藏

在做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语句能有这么大影响? 什么原理?

查看回复

AnzerWall#1·8 年前

看起来像是常数时间的差距，有没有多提交几次看看结果。。。

搞acm的时候要是被卡常数时间，会很想杀了出题人。。

zy445566#2·8 年前

不必太抠细节，后面还有三数之和，四数之和等你。有你扣细节的时候。这个东西还是经过基准测试再说吧，不过一般来说else在代码解析上是要走代码块跳转，最终编译成汇编也是走了地址跳转，这样CPU还要进行分支预测，100%走else，何必再搞个else。

justjavac#3·8 年前

使用 v8 7.1.302.4 生成的字节码，两者一模一样：

[generated bytecode for function: twoSum]
Parameter count 3
Frame size 48
   22 E> 000001BA957CE3BA @    0 : a5                StackCheck 
   55 S> 000001BA957CE3BB @    1 : 7e                CreateEmptyObjectLiteral 
         000001BA957CE3BC @    2 : 26 f9             Star r2
   76 S> 000001BA957CE3BE @    4 : 0b                LdaZero 
         000001BA957CE3BF @    5 : 26 f8             Star r3
   88 S> 000001BA957CE3C1 @    7 : 28 03 00 00       LdaNamedProperty a0, [0], [0]
   81 E> 000001BA957CE3C5 @   11 : 69 f8 02          TestLessThan r3, [2]
         000001BA957CE3C8 @   14 : 99 45             JumpIfFalse [69] (000001BA957CE40D @ 83)
   63 E> 000001BA957CE3CA @   16 : a5                StackCheck 
  123 S> 000001BA957CE3CB @   17 : 25 f8             Ldar r3
  127 E> 000001BA957CE3CD @   19 : 2a 03 03          LdaKeyedProperty a0, [3]
         000001BA957CE3D0 @   22 : 26 fb             Star r0
  153 S> 000001BA957CE3D2 @   24 : 25 fb             Ldar r0
  156 E> 000001BA957CE3D4 @   26 : 2a f9 05          LdaKeyedProperty r2, [5]
         000001BA957CE3D7 @   29 : 26 fa             Star r1
  171 S> 000001BA957CE3D9 @   31 : 9c 1e             JumpIfUndefined [30] (000001BA957CE3F7 @ 61)
  209 S> 000001BA957CE3DB @   33 : 7a 01 07 25       CreateArrayLiteral [1], [7], #37
         000001BA957CE3DF @   37 : 26 f6             Star r5
         000001BA957CE3E1 @   39 : 0b                LdaZero 
         000001BA957CE3E2 @   40 : 26 f7             Star r4
         000001BA957CE3E4 @   42 : 25 fa             Ldar r1
  217 E> 000001BA957CE3E6 @   44 : 31 f6 f7 08       StaInArrayLiteral r5, r4, [8]
         000001BA957CE3EA @   48 : 0c 01             LdaSmi [1]
         000001BA957CE3EC @   50 : 26 f7             Star r4
         000001BA957CE3EE @   52 : 25 f8             Ldar r3
  223 E> 000001BA957CE3F0 @   54 : 31 f6 f7 08       StaInArrayLiteral r5, r4, [8]
         000001BA957CE3F4 @   58 : 25 f6             Ldar r5
  226 S> 000001BA957CE3F6 @   60 : a9                Return 
  316 S> 000001BA957CE3F7 @   61 : 25 fb             Ldar r0
  327 E> 000001BA957CE3F9 @   63 : 35 02 0a          Sub a1, [10]
         000001BA957CE3FC @   66 : 26 f6             Star r5
         000001BA957CE3FE @   68 : 25 f8             Ldar r3
  334 E> 000001BA957CE400 @   70 : 30 f9 f6 0b       StaKeyedProperty r2, r5, [11]
   97 S> 000001BA957CE404 @   74 : 25 f8             Ldar r3
         000001BA957CE406 @   76 : 4c 0d             Inc [13]
         000001BA957CE408 @   78 : 26 f8             Star r3
         000001BA957CE40A @   80 : 8a 49 00          JumpLoop [73], [0] (000001BA957CE3C1 @ 7)
         000001BA957CE40D @   83 : 0d                LdaUndefined 
  345 S> 000001BA957CE40E @   84 : a9                Return 
Constant pool (size = 2)
Handler Table (size = 0)

justjavac#4·8 年前

可能是偶然，和数据有关

分支预测：为什么有序数组比无序数组快?

captainblue2013#5·8 年前

偶然吧

zy445566#6·8 年前

引用 justjavac使用 v8 7.1.302.4 生成的字节码，两者一模一样：

@justjavac 本来还想V8的优化器应该没这么强，但大佬验证过了，应该是妥了。这种靠参数判断的都能进行优化，强。 ---这句话不准确容易产生误导，请看我8楼回答

fulvaz#7·8 年前

引用 justjavac可能是偶然，和数据有关分支预测：为什么有序数组比无序数组快?

@justjavac thanks~

zy445566#8·8 年前

引用 justjavac可能是偶然，和数据有关分支预测：为什么有序数组比无序数组快?

@justjavac @fulvaz 如果我只定义twoSum方法，打印出的汇编代码如下，else代表有else，noelse代表无else。根本没有执行，也就是说明jsutjavac的汇编是twoSum传入参数后执行后的优化结果。所以V8也是根据参数传入后再进行优化的。但由于twoSum的在if内被return了，所以这个函数是不可能被采取分支的，也就是说要么是被return，要么else一定执行。如果我对这个函数稍作修改，并传入不通参数会怎么样呢？即if内的把return去除，同时传入不同参数,会是怎么样呢？即

else.js:

// else.js
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) {
            [find, i,];
        } else {
            // 如果将来某个值满足target - nums[i], 则可以和这个位置匹配
            set[target - val] = i;
        }
    }
};

twoSum([1,2,3],4)

elseno.js:

// elseno.js
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) {
            [find, i,];
        } 
		// 就这里去除了else
		// 如果将来某个值满足target - nums[i], 则可以和这个位置匹配
		set[target - val] = i;
    }
};

twoSum([1,2,undefined],4)

结果是不同的，如下：

细心的人就会发现，else.js的汇编码，多出了地址跳转！我的一般理解，看来是没错的。而上文的汇编码正好一致，也恰好是这个方法的return造成。但这个并不代表V8的优化器的成本下降，即使是优化后是相同汇编码，但else可能造成走更多步的优化策略。

备注：汇编是使用目前v8的master分支的d8打印的，node打印出的无效信息过多了。

justjavac#9·8 年前

我忽略这个了，谢谢 @zy445566

zy445566#10·8 年前

引用 justjavac我忽略这个了，谢谢 @zy445566

@justjavac 并没有，你上文只是说了一个事实，我觉得可能太简单了，容易让人有错误的遐想。所以做了下补充

justjavac#11·8 年前

引用 zy445566@justjavac 并没有，你上文只是说了一个事实，我觉得可能太简单了，容易让人有错误的遐想。所以做了下补充

@zy445566 代码里是判断 undefined，我的测试代码居然没有使用 undefined，失误失误

参与回复

登录后即可参与回复。登录

else语句会拖慢运行时间?

回复 (11)