06月14, 2018

谁说前端不关心算法

遥想2016年初,在我刚刚从一个ACMer转成一个FEer的时候,基本上js的api是记不住几个的。

当时看着培训的同学可以写出Array.prototype.slice.call(……)这样一长串不知道要干什么用的代码的时候,我只能暗暗感叹

这就是大佬吧

当时乖巧又单纯的我,连api都记不住,自然也不知道它的时间复杂度。

直到!!!

时间线回到2018年。

那天,师兄兴高采烈的指着一本书上的代码对我说,“你看它时间复杂度可以从 O(m * n) 优化成 O(m + n) !”

然后我看了一下他所谓的 O(m + n),呃嗯嗯嗯,这不是大暴力么???

alt

虽然工作中没啥用,但作为一只算法汪,决定和师兄一起学习一些真正有趣的算法。

思考了一下,HDU什么的不支持js来做题,扔给师兄多少有点残忍(说的像你自己还会用C++做题似的……)

所以就打开了LeetCode,秉承着从简单的开始的原则,然后选择了通过率最高的一道题

…咳…从简单开始……

题目文艺的说法是——你有一份珠宝图鉴,你对着图鉴看看手里这堆石头有多少个是珠宝。不文艺的说法呢,不文艺的自己读题去……

这么高的通过率,显然题目也是没有坑的,我用老母亲的眼神看着自己行云流水写出的一串代码自然的AC了。

let numJewelsInStones = function(J, S) {
    return S.split("").filter(item => J.includes(item)).length;
};

师兄也AC了之后,我们互相看代码

(根本没什么好看的好么!)

原以为实现方式差不多,没想到师兄说我,你这不是用js的思维作弊么。

看了一下师兄的代码,他认认真真的自己实现了一个map,然后再遍历去查找了一遍。

认真的思考了一下我之前写C++时候的思维

然后,啥也没想起来。

又看了看自己的代码,split的时间复杂度是多少??includes应该是 O (n) 的吧?忐忑的心情中,我去看了一下runtime的榜,60ms,打败96%,看起来不慢诶……

alt

本来这道简简单单的题可能就这么的翻页了,但是这个榜它冥冥之中带领着我,就这么峰回路转的,走上了另一条路……

这个排名第一的人,他是这么写的

alt

那么问题来了,这他喵的indexOf怎么就比includes快出了8ms???

此时,麻烦剪辑老师切成16年和18年的对比,两年后的我依旧不能确切的说出这个api的时间复杂度。

好的吧,我不知道肯定是有大佬知道的。

我就随意的在某度上搜了一下,emmm,没有??好吧,垃圾,换Google肯定就能搜到了呢。

emmm?为啥还是没有?

……

……

……

遥想起当年在实验室中,学长们口口相传的告诉我们经典的api的时间复杂度的场景,我决定,去看底层的实现来把这个搞清楚!

在我下这个决定的时候,我甚至觉得苦苦寻觅不到的分享主题有了!

alt

好好好,好吧。

所以就去看实现吧!大概是一种初生牛犊不怕虎的精神,当时的我决定去看V8的实现。

在github上找了V8的源码,随意的翻了一下,就看到了这里 ↓↓↓

(function(global, utils, extrasUtils) {
    "use strict";
    %CheckIsBootstrapping();
    // -------------------------------------------------------------------
    // Imports
    var GlobalArray = global.Array;
    ……
    ……
    var ArrayIndexOf = GlobalArray.prototype.indexOf;
    var ArrayJoin = GlobalArray.prototype.join;
    var ArrayPop = GlobalArray.prototype.pop;
    ……
    utils.SetUpLockedPrototype(InternalArray, GlobalArray(), [
      "indexOf", ArrayIndexOf,
      "join", ArrayJoin,
      ……
]);

欣喜之余,问题来了,global在哪里传过来的?

看着一个凌乱的C++项目,我思考了两分钟之后,决定把代码clone下来! (内心os:到时候全局搜一下就好了嘛)

半天之后,终于下载好了项目 我搜~

alt

再搜~

alt

就这样,经过了一波搜索加查看后,我选择打开了ECMA-262的文档。

看着有些熟悉的文档……

为什么熟悉呢?因为之前大佬组织了一波翻译ECMA-262文档的活动,还在实习我的开开心心的报名了,然后泪流满面的翻译完了ECMA-262的第七章,请为乖巧的我点赞,靴靴

文章当时发在众成翻译上,说到这里不得不说,众成翻译真的好用,特别适合一些没经验还想锻炼英文翻译能力的萌新。

我,喵喵,实名为众成翻译安利,安利给我公众号仅有的6个粉丝……

好的,回到正题,文档中有句话是这么说的

The includes method intentionally differs from the similar indexOf method in two ways. First, it uses the SameValueZero algorithm, instead of Strict Equality Comparison, allowing it to detect NaN array elements. Second, it does not skip missing array elements, instead treating them as undefined.

仔细的看了看 SameValueZero 方法和 Strict Equality Comparison 之后,貌似没什么影响?

这时候福至心灵的我,回到了LeetCode,复制了第一的代码,粘贴,提交。

alt

好的,拜拜。【摔!】

本文链接:http://crystalmiao.com/post/algorithm-in-fe.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。