Aaaaaaaty

Aaaaaaaty 查看完整档案

杭州编辑中国传媒大学  |  电子信息工程 编辑阿里巴巴  |  前端工程师 编辑 github.com/Aaaaaaaty/blog 编辑
编辑

天猫营销平台持续招人中,服务端、客户端、前端、算法;base 杭州;有需要请发送简历到tianyu.aty@alibaba-inc.com;注明来自[sf]

个人动态

Aaaaaaaty 发布了文章 · 2018-02-26

结合kmp算法的匹配动画浅析其基本思想

写在最前

本次分享一下通过实现kmp算法的动画效果来试图展示kmp的基本思路。

欢迎关注我的博客,不定期更新中——

前置概念

字符串匹配

字符串匹配是计算机科学中最古老、研究最广泛的问题之一。一个字符串是一个定义在有限字母表∑上的字符序列。例如,ATCTAGAGA是字母表∑ = {A,C,G,T}上的一个字符串。字符串匹配问题就是在一个大的字符串T中搜索某个字符串P的所有出现位置。

kmp算法

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

在js中字符串匹配我们通常使用的是原生api,indexOf;其本身是c++实现的不在这次的讨论范围中。本次主要通过动画演示的方式展现朴素算法与kmp算法对比过程的异同从而试图理解kmp的基本思路。

PS:在之后的叙述中BBC ABCDAB ABCDABCDABDE为主串;ABCDABD为模式串

效果预览

2018-02-23 18_56_50

上方为朴素算法即按位比较,下方为kmp算法实现的字符串比较方式。kmp可以通过较少的比较次数完成匹配。

基本思路

从上图的效果预览中可以看出使用朴素算法依次比较模式串需要移位13次,而使用kmp需要8次,故可以说kmp的思路是通过避免无效的移位,来快速移动到指定的地点。接下来我们关注一下kmp是如何“跳着”移动的:

wechatimg167

与朴素算法一致,在之前对于主串“BBC ”的匹配中模式串ABCBABD的第一个字符均与之不同故向后移位到现在上图所示的位置。主串通过依次与模式串中的字符比较我们可以看出,模式串的前6个字符与主串相同即ABCDAB;而这也就是kmp算法的关键。

根据已知信息计算下一次移位位置

我们先从下图来看朴素算法与kmp中下一次移位的过程:
wechatimg165

朴素算法雨打不动得向后移了一位。而kmp跳过了主串的BCD三个字符。从而进行了一次避免无意义的移位比较。那么它是怎么知道我这次要跳过三个而不是两个或者不跳呢?关键在于上一次已经匹配的部分ABCDAB

从已匹配部分发掘信息

我们已知此时主串与模式串均有此相同的部分ABCDAB。那么如何从这共同部分中获得有用的信息?或者换个角度想一下:我们能跳过部分位置的依据是什么?

第一次匹配失败时的情形如下:

    BBC ABCDAB ABCDABCDABDE
        ABCDABD
              D != 空格 故失败

为了从已匹配部分提取信息。现在将主串做一下变形:

    ABCDABXXXXXX...  X可能是任何字符

我们现在只知道已匹配的部分,因为匹配已经失败了不会再去读取后面的字符,故用X代替。

那么我们能跳过多少位置的问题就可以由下面的解得知答案:

    //ABCDAB向后移动几位可能能匹配上?
    ABCDABXXXXXX...
    ABCDABD

答案自然是如下移动:

    ABCDABXXXXXX...
        ABCDABD

因为我们不知道X代表什么,只能从已匹配的串来分析。

故我们能跳过部分位置的依据是什么?

答:已匹配的模式串的前n位能否等于匹配部分的主串的后n位。并且n尽可能大。

举个例子:

//第一次匹配失败时匹配到ABCDDDABC为共同部分
    XXXABCDDDABCFXXX
       ABCDDDABCE
//寻找模式串的最大前几位与主串匹配到的部分后几位相同,
//可以发现最多是ABC部分相同,故可以略过DDD的匹配因为肯定对不上
    XXXABCDDDABCFXXX
             ABCDDDABCE     

现在kmp的基本思路已经很明显了,其就是通过经失败后得知的已匹配字段,来寻找主串尾部与模式串头部的相同最大匹配,如果有则可以跨过中间的部分,因为所谓“中间”的部分,也是有可能进入主串尾与模式串头的,没进去的原因即是相对位置字符不同,故最终在模式串移位时可以跳过。

部分匹配值

上面是用通俗的话来述说我们如何根据已匹配的部分来决定下一次模式串移位的位置,大家应该已经大体知道kmp的思路了。现在来引出官方的说法。

之前叙述的在已匹配部分中查找主串头部与模式串尾部相同的部分的结果我们可以用部分匹配值的说法来形容:

  • 其中定义"前缀"和"后缀"。"前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。
  • "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。

例如ABCDAB

  • 前缀分别为A、AB、ABC、ABCD、ABCDA
  • 后缀分别为B、AB、DAB、CDAB、BCDAB

很容易发现部分匹配值为2即AB的长度。从而结合之前的思路可以知道将模式串直接移位到主串AB对应的地方即可,中间的部分一定是不匹配的。移动几位呢?

答:匹配串长度 - 部分匹配值;本次例子中为6-2=4,模式串向右移动四位

代码实现

计算部分匹配表

function pmtArr(target) {
    var pmtArr = []
    target = target.split('')
    for(var j = 0; j < target.length; j++) {
    //获取模式串不同长度下的部分匹配值
        var pmt = target
        var pmtNum = 0
        for (var k = 0; k < j; k++) {
            var head = pmt.slice(0, k + 1) //前缀
            var foot = pmt.slice(j - k, j + 1) //后缀
            if (head.join('') === foot.join('')) {
                var num = head.length
                if (num > pmtNum) pmtNum = num
            }
        }
        pmtArr.push(j + 1 - pmtNum) 
    }
    return pmtArr
}

kmp算法

function mapKMPStr(base, target) {
    var isMatch = []
    var pmt = pmtArr(target)
    console.time('kmp')
    var times = 0
    for(var i = 0; i < base.length; i++) {
        times++
        var tempIndex = 0
        for(var j = 0; j < target.length; j++) {
            if(i + target.length <= base.length) {
                if (target.charAt(j) === base.charAt(i + j)) {
                    isMatch.push(target.charAt(j))
                } else {
                    if(!j) break //第一个就不匹配直接跳到下一个
                    var skip = pmt[j - 1]
                    tempIndex = i + skip - 1
                    break 
                }
            }
        }
        var data = {
            index: i,
            matchArr: isMatch
        }
        callerKmp.push(data)
        if(tempIndex) i = tempIndex
        if(isMatch.length === target.length) {
            console.timeEnd('kmp')
            console.log('移位次数:', times)
            return i
        }
        isMatch = []
    }
    console.timeEnd('kmp')
    return -1

有了思路后整体实现并不复杂,只需要先通过模式串计算各长度的部分匹配值,在之后的与主串的匹配过程中,每失败一次后如果有部分匹配值存在,我们就可以通过部分匹配值查找到下一次应该移位的位置,省去不必要的步骤。

所以在某些极端情况下,比如需要搜索的词如果内部完全没有重复,算法就会退化成遍历,性能可能还不如传统算法,里面还涉及了比较的开销。

参考文章

最后

惯例po作者的博客,不定时更新中——

有问题欢迎在issues下交流。

查看原文

赞 7 收藏 5 评论 0

Aaaaaaaty 发布了文章 · 2018-02-12

由一个“bug”到鲜为人知的jQuery.cssHooks

写在最前

本次分享一下在一次jQuery赋值样式失效的结果中来分析背后原因的过程。在翻jQuery源码的过程中,感觉真是还不能说自己只是会用jQuery,我好像连会用都达不到(逃

欢迎关注我的博客,不定期更新中——

一个很简单的赋值问题

$('#' + id).css({"left": "200"})

image

我只是单纯的想控制一个left值,大家都懂,但是竟然失败了,打印出的元素属性中可以看到left为"";我其实一开始没想到可能是jQuery本身的原因导致的,我先考虑的是我这个元素是不是当前要赋值的?js的问题?等等。。干想了半天,认为可能还是本身的写法问题。所以进行了如下实验:

$('#' + id).css({"left": 200})

image

看起来是字符串和数字的区别!omg,从来没想过字符串和数字的效果竟然会不一致。。你以为事情已经结束了?no,看下面这个:

$('#' + id).css({"width": "200"})

image

好的为什么,width设定字符串就可以被添加px后缀,left就不可以??

现在我们可以总结一下通过jQuery.fn.css方法来设定元素属性的时候会有一些不一致的情况,以width和left为例子(因为属性很多,不一致的情况很多,了解原理即可):

  • left通过number类型可以补全px完成样式设定,string类型无法设定属性
  • width均可以通过number或string类型完成设定属性

从而可以抛出由一开始的奇怪现象的底层问题:为什么通过jQuery.fn.css方法设定样式时,string类型的值在某些属性上无法生效?

从源码中找线索

jQuery的源码相比react、vue相比应该是很直接的了,就是一个js。(不过我仍然看不懂?

首先引入一个没有压缩过的jQuery,里面保留了所有的注释和代码结构,很方便大家阅读

https://cdn.bootcss.com/jquery/3.3.1/jquery.js

先找到我们本次设定样式的方法jQuery.fn.css:

jQuery.fn.extend( {
        css: function( name, value ) {
            return access( this, function( elem, name, value ) {
                var styles, len,
                    map = {},
                    i = 0;
                if ( Array.isArray( name ) ) {
                    styles = getStyles( elem );
                    len = name.length;
    
                    for ( ; i < len; i++ ) {
                        map[ name[ i ] ] = jQuery.css( elem, name[ i ], false, styles );
                    }
    
                    return map;
                }
    
                return value !== undefined ?
                    jQuery.style( elem, name, value ) :
                    jQuery.css( elem, name );
            }, name, value, arguments.length > 1 );
        }
    } );

如何通过浏览器来调试源码呢?(因为直接看源码太繁琐了,通过debug的形式可以看到每次的调用栈)我们可以通过console.log的形式,在这段源码中将console写入,之后在控制台中就可以看到对应源码的调用:

wechatimg152

进入jQuery.style之后就会来到最终产生区别的地方:

style: function( elem, name, value, extra ) {
    
            ...
            hooks = jQuery.cssHooks[ name ] || jQuery.cssHooks[ origName ];
            if ( value !== undefined ) {
                type = typeof value;
                if ( type === "string" && ( ret = rcssNum.exec( value ) ) && ret[ 1 ] ) {
                    value = adjustCSS( elem, name, ret );
                    type = "number";
                }
                ...
                if ( type === "number" ) {
                    value += ret && ret[ 3 ] || ( jQuery.cssNumber[ origName ] ? "" : "px" );
                }
                ...
                if ( !hooks || !( "set" in hooks ) ||( value = hooks.set( elem, value, extra ) ) !== undefined ) {
                    //此时的value到底是200还是200px;只有添加了后缀才能赋值成功
                    if ( isCustomProp ) {
                        style.setProperty( name, value );
                    } else {
                        style[ name ] = value;
                    }
                }
    
            } 
            ...
        },

源码中可以看到在传入的value中确实对string和number做了区分;而不是我之前所认为的,string应该和number差不多:)如果传入number类型,便会为其添加px后缀;但是这仍然没有解释为什么left和width均传入string而结果不同的问题。重点在于这句话:

hooks = jQuery.cssHooks[ name ] || jQuery.cssHooks[ origName ];
...
if ( !hooks || !( "set" in hooks ) ||
    ( value = hooks.set( elem, value, extra ) ) !== undefined ) {
    ...
}

在value是string类型,到最终赋值之前,还会经过value = hooks.set( elem, value, extra ) ) !== undefined的判断,也就是说如果hooks.set方法存在,我们还有一次通过这个方法来将string类型的value进行后缀补全的机会。而这个hooks是由jQuery.cssHooks得到的,那么jQuery.cssHooks是什么:

wechatimg153

从源码中可以看出,cssHooks中包含了属性的一些方法,其中left只有get;width有get和set。再结合上面的判断条件就可以推断出,由于width存在了set方法,在其方法中对string类型的value完成了后缀的补齐,而left则不行从而形成了文中一开始的“神奇”现象。

cssHooks

直接向 jQuery 中添加钩子,用于覆盖设置或获取特定 CSS 属性时的方法,目的是为了标准化 CSS 属性名或创建自定义属性。
$.cssHooks 对象提供了一种通过定义函数来获取或设置特定 CSS 值的方法。可以用它来创建新的 cssHooks 用于标准化 CSS3 功能,例如,盒子阴影(box shadows)及渐变(gradients)。

例如,某些基于 Webkit 的浏览器会使用 -webkit-border-radius 来设置对象的 border-radius,然而,早先版本的 Firefox 则使用 -moz-border-radius。cssHook 就可以将这些不同的写法进行标准化,从而让 .css() 可以使用统一的标准化属性名(border-radius 或对应的 DOM 属性写法 borderRadius)。

该方法除了提供了对特定样式的处理可以采用更加细致的控制外,$.cssHooks 同时还扩展了 .animate() 方法上的属性集。

简单来说,jQuery给我们暴露了一个钩子,我们可以自己定义方法比如set,来实现针对某个属性的特定行为。所以出现left和width的问题就是有没有set这个钩子方法。so。。我们还剩最后一个问题:

为什么width要对其设定钩子函数?

答案可以从其set方法来窥探一下:

set: function( elem, value, extra ) {
    var matches,
        styles = getStyles( elem ),
        isBorderBox = jQuery.css( elem, "boxSizing", false, styles ) === "border-box",
        subtract = extra && boxModelAdjustment(
            elem,
            dimension,
            extra,
            isBorderBox,
            styles
        );

    // Account for unreliable border-box dimensions by comparing offset* to computed and
    // faking a content-box to get border and padding (gh-3699)
    if ( isBorderBox && support.scrollboxSize() === styles.position ) {
        subtract -= Math.ceil(
            elem[ "offset" + dimension[ 0 ].toUpperCase() + dimension.slice( 1 ) ] -
            parseFloat( styles[ dimension ] ) -
            boxModelAdjustment( elem, dimension, "border", false, styles ) -
            0.5
        );
    }

    // Convert to pixels if value adjustment is needed
    if ( subtract && ( matches = rcssNum.exec( value ) ) &&
        ( matches[ 3 ] || "px" ) !== "px" ) {

        elem.style[ dimension ] = value;
        value = jQuery.css( elem, dimension );
    }

    return setPositiveNumber( elem, value, subtract );
}

从这个钩子函数中我们可以看出,要对width做特殊处理是因为css的盒模型有好几种,content-box|border-box|inherit分别代表“不包括padding、border、margin” | “包含border和padding” | “继承”;故为了统一外界的调用,隐藏这些背后的判断,从而增加了这个set方法。顺带着在其中把px补全了。同时left这种没什么需要兼容的故没有设定set方法。

小结

虽然cssHooks不常用(我反正从来没用过,现在对于标准化格式有很多其他的方法来做,cssHooks的钩子感觉还是有些复杂了),但这次通过页面上一个很小的问题从而引发思考并且试图深挖一些的过程还是值得总结下来的。虽然我们不是造轮子的人,但理解别人的轮子也是比“会用”好一些的;更何况看了cssHooks我感觉我都不会用jQuery:)

参考文章

最后

惯例po作者的博客,不定时更新中——

有问题欢迎在issues下交流。

查看原文

赞 8 收藏 10 评论 0

Aaaaaaaty 发布了文章 · 2018-02-04

记一次“失利后”经过半年准备通过阿里社招的经历与感悟

写在最前

本次分享一下在作者上一次“失利”即拿到毕业证第二天突然“收到”阿里社招面试通知失败之后,通过分析自己的定位与实际情况,做出的未来一到两年的规划。以及本次社招的面试经历(但这部分不是重点,每个人的面试经历都是不一样的。千人千面嘛)

PS:当然了计划赶不上变化,半年后一次内推的机会“稀里糊涂”得就通过了。。

欢迎关注我的博客,不定期更新中——

基于个人定位与实际情况的发展方向

上一次面试挂了后,我便对自己的情况进行了总结:

  • 17届普通211,非cs科班。数据结构与算法、计算机基础等方面相对薄弱。
  • 在面试挂掉的时间点是17年6月,实习半年,尚未毕业,缺少硬性工作经验条件。
  • 公司内部尚无主力产品,工作基本为零散项目,缺少业务驱动的可深挖性。例如有主力产品为react,那么你可以借着业务深入了解其源码与原理等一切以react栈为出发点的知识与实践经验
  • 前端基本功技术栈:css相对弱(因为我真的懒得写样式),对js的基础知识兴趣浓厚,同时向往服务端,尝试基于node搭建服务。

于此同时我个人认为通过面试的最重要关键点:一定要有一个亮点打动你的面试官!

什么是亮点?

亮点就是在某个层面的深入研究成果:)

PS: 只是针对刚工作的伙伴,高p请放过我

个人理解亮点可以是两方面:

  1. 在公司的项目中中,源于业务并高于业务的沉淀。正如同之前我总结个人情况中提到。如果你的简历里面主要介绍了react的项目。那么这其中会存在两个互补的研究即项目与react(同理还有vue与项目等等,为啥不是单独的react、vue;因为这只是个框架,结合框架解决实际问题才是最重要的,框架真的太多了,但业务都是相似的):

    (1)业务的难点,如何解决,更好的思路?针对业务的优化?等等业务层面的深挖。

    (2)针对react你都了解多少?如果你对其了解只停留在api的阶段,那应该是凉凉了。。源码?设计思想?至少给知道diff怎么回事,setState到底是同步的还是异步的,以及为什么要这么处理?等等很多。

    核心思路就是通过你的业务与对技术相结合的深度挖掘来打动你的面试官

  2. 第二点我是针对自己做的,因为结合我之前的分析可以发现我其实不具备1的条件,即没有主力业务。在你的业务量极小的时候,你是没有业务驱动的需求去让你挖掘那些背后的优化与更好的解决方案的。也许你会说那你也可以读react源码啊。但是,我读了源码不能反哺到业务中又有什么用呢?不知道如何解决实际的问题,仍然没有做到1的要求即项目与某框架的技术的结合沉淀。故针对我个人情况我选择了如下方式:

    (1)由于自己其实没有别人那么忙,我就强制自己每周周末坚持沉淀自己,并产出技术文章,不论是哪个方面的(因为我真的做不到1中的事情,我只好多学习多产出)。通过撰写博客引起更多人的关注,同时也可以让面试官侧面了解我,毕竟一次面试能决定的东西太少了

    (2)在这个过程中我找到适合自己的路,选择一个较脱离主要业务(react之类的)的技术方向来进行一定程度的研究(我选的是canvas与node)。核心思路还是你要自己有自己的沉淀并以此试图打动面试官(逃

这是我半年来关于canvas与node的一些学习与记录:

半年来技术沉淀的成果与自我感觉的“亮点”

  • 半年中总结了34篇包括但不限于css、js、node、canvas等技术博客托管在github中,获得了400个star,同时发布了bezierMaker.js——N阶贝塞尔曲线生成器
  • 在博客有一定曝光度的积累中,陆续收到了一些面试邀请,基本上是阿里的;但是我知道我菜。。就没去,可能有的是群发,不过都提到了我的博客可能还是编辑了一下的吧:)
  • 读了node源码并提了第一个pr,但由于“口齿不清”的英语,和node项目维护者叙说很久无果就不了了之了,也算一次实践吧
  • 个人最得意的一个小作品即自我感觉的“亮点”canvas进阶——实现静态图像的变形并合成动态效果,在之后的面试中的项目经验中主要介绍了这个。与此同时这篇文章中收到w3cplus大漠老师的邀请,希望将canvas系列文章发布在其网站中

突如其来的面试

2017.12月末,师哥突然跟我说现在部门有机会要不要试试,我本来是想拒绝的,因为距离上次被拒只差了半年,加上我现在工作经验满打满算也就一年,其中还有半年实习。。好的一面就来了:),由于这篇文章不是纯粹的面经也不是纯粹的技术文章,同时很多面试题都是有答案的,故大家有兴趣自行百度下面面试题,作者不过多说明。

一面

一面其实就是我的师哥。。所以严格来说就是一次交流,没有技术上的问题;因为我的朋友圈其实已经发了很多我自己的玩具代码了估计师哥心里也是有数的:)

主要介绍了目前团队所做的业务、相关的理念等等。更多的就是互相了解情况,我大概说了一下我这边做的事基本也就结束了。

二面

二面是师哥的老大,也是未来我如果入职的上司。其实这才算是一面。他更多的是来对我了解一些基础情况与一些技术思想(他本身是java)聊得很快也就20分钟:

  • 自我介绍
  • react、vue原理,这个虽然源码没看过但是两者的区别还有基本的思想还是能说几句的
  • react怎么优化?关于优化其实react的diff算法是怎么计算的你了解清楚了就知道什么操作会让diff算的慢也就知道怎么优化了:)
  • 为什么选择阿里?因为是阿里
  • 好像没问什么了结束的很快,同时告诉我下次是前端组leader来面试

三面

面试官好像和豆瓣有些渊源,上来就问我你是不是克军团队的,我说我不是。。

  • 自我介绍
  • 先从简历的项目了解一遍,时长大约20分钟,其实很多就是很久前做的都忘记了就是大概说说。。
  • react的思想是什么?数据驱动balabala,举了一个之前封装轮播图的例子
  • 对redux怎么看?这个强力推荐这篇文章,拯救了我这个问题从时间旅行的乌托邦,看状态管理的设计误区,这位文章的作者虽然喜欢怼人但是技术还是很强的
  • 碰到问题你是如何解决的?百度、谷歌、别人的文章;但是!我其实并不相信别人的文章,很多东西的底层应该是规范而不是别人的总结,比如我总结的从HTML5与PromiseA+规范来看事件循环,在代码的世界里,其实不需要太多别人的理解,规范就是规范,真的想知道为什么,就去看看底层的定义。这可比你读了谁谁的文章来的靠谱,毕竟人都会犯错?
  • 0.1 + 0.2 ? 我脱口而出不等于0.3,然后面试官好像有点吃惊,“你是在网上看到这个题?”,“我其实很喜欢这种js的边边角角”,自己总结过一些比如类型转换之类的:)
  • 函数与构造函数的区别?我觉得没啥区别,区别都是new调用做的,改了this的指向而已
  • 那么延伸一下,数值怎么存储?64位浮点型;“小数怎么存储?”嗯其实关于小数二进制存储有点懵,就没说上来。。
  • 关于css,说一下并列布局的方式;核心思路是怎么让block不自适应平铺为整行。触发bfc就可以了;比如绝对布局,float,inline-block等等
  • 有没有一些有意思的项目?终于等来了可以介绍我的“亮点”作品了,关于作品是啥往上找。。主要就是将静态图通过绘制自定义贝塞尔曲线变为扭曲效果同时生成过程动画。对这个项目的原理我和面试官讨论了给有20分钟,看得出来他对这个项目很感兴趣或者说这么做的思路也是平时少见的。
  • 你在同事眼里是个怎样的人?怎么感觉像是hr在跟我说话。。我觉得还算nice吧嘻嘻
  • 你现在在北京,打算来杭州么?去!必须去!不去肯定挂了。。

笔试

穿插了一个笔试,就一道题:写一个js的通用事件绑定函数

交叉面

交叉面充分说明了,没有主力业务的可怕=。=,因为你不能光写你的作品吧?你总给写公司的业务,但是这个业务吧你又没有需求把它优化到别人的标准,或者说根本没有优化:)

  • 一开始介绍了自己的项目也就是上面提及的。面试官接下来一句我就凉了,在webgl中也可以实现? 好的我没用过webgl。“哦没用过,好的”
  • 移动端做过什么优化么?我心想我这边的业务,都是活动页做啥优化。。但是我还是说了我看到别人的优化方案,例如直出、域名收敛
  • “域名收敛?为什么要收敛?”“因为dns解析慢啊?”“那和pc端有什么区别,pc端域名不是发散来提高并发数么?” 我心里一想是啊,其实浏览器pc和m没啥区别那为啥一个发散一个收敛,或者说发散我们都知道克服pc浏览器的并发限制。那m端?我当时有点迷没说上来就过了,回来又百度了一下感觉上其实就是m端网速慢dns太耗时。。我没反应过来还有网速的事情
  • js与native怎么交互?内心独白:我*,我真没做过。。“嗯虽然我没做过,但是我了解过应该是native定义一套协议,js使用该协议发请求,native拦截解析并返回js的所需balabala”
  • 缓存策略都有哪些,包括native;我??我没做过native啊。。缓存策略对浏览器的我研究过一些基本就是基于我这篇文章来说的基于node的微小服务——细说缓存与304
  • 看你的简历里写了rn项目,对rn有做过优化么,全量么?有没有自己改过内核?这就是我之前说的我所面临的业务问题,我这个rn项目撑死了是两个人写的,很快就结束了不维护了都,哪里来的优化。。哎所以身在一个好项目中很关键;“嗯没做过优化,只是使用层面(微笑脸”
  • 除了react对什么框架熟悉?“毕设用的vue,仅限使用”
  • vue与react有什么区别?“于我来说最直观的是写法的区别,jsx与模板;同时debug中也存在差异。再有就是框架实现思想上的区别了,数据绑定与diff”
  • 看你写的截图插件,碰到动态图怎么办?“当时使用的是html2canvas,其中确实会存在动态图截取失败的问题,嗯确实没有好的解决方案”
  • 看你的博客,对canvas使用的很多,有过一些沉淀么比如引擎?我*,引擎??“没有没有,不过我封装过一个贝塞尔曲线生成器”
  • m端与pc在html5的新特性上有哪些是不一样的?有做过什么么?表示我真的忘了有很多新接口,比如电池陀螺仪之类的;一时间想成了pwa的特性。。“我用过新的音频api接口,虽然pc与m都有,但是这个做了一些效果,实现了读取从设备收取的外界声音,转化为可视化波形”
  • 参与过开源项目么?给node提pr被拒了很惭愧,但是也有收获
  • 自己觉得积累最多的沉淀是什么?可能是对js语言本身上的一些探索吧

终面&hr

来到了北京的一个工作点,准备视频面,我之后才反应过来我其实已经被hr面过了。。因为跟在老板身边是个男的。。

  • 自我介绍
  • 项目介绍,主要介绍了canvas。
  • hr:为什么毕业半年就准备换工作?因为再待在舒适区我就废了
  • hr:当时实习半年你就已经了解了情况为什么不考虑当时就走?因为三方。。
  • hr:单身来杭州?有女票,不过是浙江人
  • 没什么问题了,你有问题么?没
  • 很快就结束了也就20分钟不到吧

小计

至此完成了对自己这边年来的准备的一个回顾与面试经验的分享。面经不是重点每个人都是不一样的,更重要的应该是如何在当前的工作中找到自己应该努力的方向,并且持续地发光发热,让别人认可你,打动他们。

PS:目前是待发offer状态,之后如果hc没有问题,背调没有问题,体检没有问题,我就可以奔赴2000公里外的杭州了。当然了结果很重要,但过程更令人回味更多。

PPS: 这一切都是个人感悟,说的不对的,不严谨的,欢迎一起分享你的想法,在码梦的路上,一去不归。

PPPS:由于只毕业半年,我估计可能是p5(但是社招p5基本无hc),p6就太赚了,不过这都是后话,静候佳音

最后

惯例po作者的博客,不定时更新中——

有问题欢迎在issues下交流。

查看原文

赞 31 收藏 76 评论 14

Aaaaaaaty 发布了文章 · 2018-01-29

基于JavaScript求解八数码最短路径并生成动画效果

写在最前

本次分享一下通过广度优先搜索解决八数码问题并展示其最短路径的动画效果。

欢迎关注我的博客,不定期更新中——

效果预览

该效果为从[[2, 6, 3],[4, 8, 0],[7, 1, 5]] ==> [[[1, 2, 3],[4, 5, 6],[7, 8, 0]]]的效果展示

2018-01-28 20_50_42

源码地址

配置方式如下:

var option = {
    startNode: [
        [2, 6, 3],
        [4, 8, 0],
        [7, 1, 5]
    ],
    endNode: [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 0]
    ],
    animateTime: '300' //每次交换数字所需要的动画时间
}
var eightPuzzles = new EightPuzzles(option)

八数码问题

百度一下可以百度出来很多介绍,在此简单说明一下八数码问题所要解决的东西是什么,即将一幅图分成3*3的格子其中八个是图一个空白,俗称拼图游戏=。=,我们需要求解的就是从一个散乱的状态到恢复原状最少需要多少步,以及每步怎么走。

我们可以抽象为现有数字0-8在九宫格中,0可以和其他数字交换。同时有一个开始状态和结束状态,现在需要求解出从初始到结束所需要的步数与过程。

解决思路

网上有很多算法可以解决八数码问题,本次我们采用最容易理解也是最简单的广度优先搜索(BFS),虽然是无序搜索并且浪费效率,不过我们还是先解决问题要紧,优化的方式大家可以接着百(谷)度(歌)一下。比如A*之类的,因为作者也不太会(逃。

广度优先搜索

原图来自JS 中的广度与深度优先遍历
<center>原图来自JS 中的广度与深度优先遍历</center >
这张图很好的展示了最基本的广度优先搜索的概念,即一层一层来遍历节点。在代码实现中我们需要按照上面图中1-12的顺序来遍历节点。实现方式可以为维护一个先入先出的队列Queue,按顺序将一层的节点从队尾推入,之后从从队头取出。当某个节点存在子节点,则将子节点推入队列的队尾,这样就可以保证子节点均会排在上层节点的后面。

结合八数码与广度优先搜索

现在我们已知广搜的相关概念,那么如何结合到八数码问题中呢?

  1. 首先我们需要将八数码中即0-8这九个数的每一种组合当做一种状态,那么按照排列组合定理我们可以求出八数码可能存在的状态数:9!即362880种排列组合。
  2. 对八数码的每种状态转换为代码中的表达方式,在此作者使用的是通过二维数组的形式,在文章的开头的配置方式中就可以看到初始与最终状态的二维数组表示。
  3. 为什么选择二维数组?因为对于0的移动限定是有一定空间边界的,比如0如果在第二行的最右边,那么0只能进行左上下三种移动方式。通过二维数组的两种下标可以很方便的来判断下一个状态的可选方向。
  4. 将每种状态转化为二维数组后,就可以配合广搜来进行遍历。初始状态可以设定为广搜中图的第一层,由初始状态通过判断0的移动方向可以得到不大于4中状态的子节点,同时需要维护一个对象来记录每个子节点的父节点是谁以此来反推出动画的运动轨迹及一个对象来负责判断当前子节点先前是否已出现过,出现过则无需再压入队。至此反复求出节点的子节点并无重复的压入队。
  5. 在遍历状态的过程中,可以将二维数组转化为数字或字符串,如123456780。在变为一维数组后便可以直接判断该状态是否等于最终状态,因为从数组变为了字符串或数字的基本类型就可以直接比较是否相等。如果相等那么从该节点一步步反推父节点至起始节点,得到动画路径。
  6. 在页面中通过动画路径生成动画。

当你明白了思想之后,我们将其转化为代码思路既可以表示为如下步骤:

  1. 初始节点压入队。
  2. 初始节点状态计入哈希表中。
  3. 出队,访问节点。
  4. 创建节点的子结点,检查是否与结束状态相同。若是,搜索结束,若否,检查哈希表是否存在此状态。若已有此状态,跳过,若无,把此结点压入队。
  5. 重复3,4步骤,即可得解。
  6. 根据目标状态结点回溯其父节点,可以得到完整的路径。
  7. 通过路径生成动画

看起来一切都很美好是不是?但是我们仍然忽略了一个问题,很关键。

八数码的可解性问题

如果真的像拼图一样,从一个已知状态打散到另一个状态,那么肯定是可以复原的。但是我们现在的配置策略是任意的,从而我们需要判断起始状态是否可以达到结束状态。判断方式是通过起始状态和结束状态的逆序数是否同奇偶来判断

逆序数:在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。一个排列中所有逆序总数叫做这个排列的逆序数。

如果起始状态与结束状态的逆序数的奇偶性相同,则说明状态可达,反之亦然。至于为什么,作者尝试通过简单的例子来试图说明并推广到整个结论:

//起始状态为[[1,2,3],[4,5,6],[7,8,0]]
//可以看做字符串123456780
//结束状态为[[1,2,3],[4,5,6],[7,0,8]]
//可以看做字符串123456708

这个变换只需要一步,即0向左与8进行交换。那么对于逆序数而言,0所在的位置是无关紧要的,因为它比谁都小,不会导致位置变化逆序数改变。所以0的横向移动不会改变逆序数的奇偶性。

//起始状态为[[1,2,3],[4,5,6],[7,8,0]]
//可以看做字符串123456780
//结束状态为[[1,2,3],[4,5,0],[7,8,6]]
//可以看做字符串123450786

这个变换同样只需要一步,即0向上与6进行交换。我们已知0的位置不会影响逆序数的值。那么现在我们只需要关注6的变化。6从第6位置变为第9位置,导致7与8所在位置之前的逆序数量出现了变化。7、8都比6大,则整体逆序数量会减少2,但是逆序数-2仍然保持了奇偶性。与此同时我们可以知道,当0纵向移动的时候,中间的两个数(当前例子7、8的位置)只会有三种情况。要不都比被交换数大(比如7、8比6大)要不一个大一个小,要不都小。如果一大一小,则逆序数仍会保持不变,因为总量上会是+1-1;都小的话则逆序数会+2,奇偶性同样不受到影响。故我们可以认为,0的横向与纵向移动并不会改变逆序数的奇偶性。从而我们可以在一开始通过两个状态的逆序数的奇偶性来判断是否可达。

核心代码

判断可解性

EightPuzzles.prototype.isCanMoveToEnd = function(startNode, endNode) {
    startNode = startNode.toString().split(',')
    endNode = endNode.toString().split(',')
    if(this.calParity(startNode) === this.calParity(endNode)) {
        return true 
    } else {
        return false
    }
}
EightPuzzles.prototype.calParity = function(node) {
    var num = 0
    console.log(node)
    node.forEach(function(item, index) {
        for(var i = 0; i < index; i++) {
            if(node[i] != 0) {
                if (node[i] < item) {
                    num++
                } 
            }
        }
    })
    if(num % 2) {
        return 1
    } else {
        return 0
    }
}

广度优先搜索

EightPuzzles.prototype.solveEightPuzzles = function() {
    if(this.isCanMoveToEnd(this.startNode, this.endNode)) {
        var _ = this
        this.queue.push(this.startNode)
        this.hash[this.startNodeStr] = this.startNode
        while(!this.isFind) { 
            var currentNode = this.queue.shift(),
                currentNodeStr = currentNode.toString().split(',').join('') //二维数组变为字符串
            if(_.endNodeStr === currentNodeStr) { //找到结束状态
                var path = []; // 用于保存路径
                var pathLength = 0
                var resultPath = []
                for (var v = _.endNodeStr; v != _.startNodeStr; v = _.prevVertx[v]) {
                    path.push(_.hash[v]) // 顶点添加进路径
                }
                path.push(_.hash[_.startNodeStr])
                pathLength = path.length
                for(var i = 0; i < pathLength; i++) {
                    resultPath.push(path.pop())
                }
                setTimeout(function(){
                    _.showDomMove(resultPath)
                }, 500)
                _.isFind = true
                return
            }
            result = this.getChildNodes(currentNode) //获得节点子节点
            result.forEach(function (item, i) {
                var itemStr = item.toString().split(',').join('')
                if (!_.hash[itemStr]) { //判断是否已存在该节点
                    _.queue.push(item)
                    _.hash[itemStr] = item
                    _.prevVertx[itemStr] = currentNodeStr //记录节点的父节点
                }
                
            })
        }
    } else {
        console.log('无法进行变换得到结果')
    }
    
}

生成动画

EightPuzzles.prototype.calDom = function(node) { //根据当前状态渲染各数字位置
    node.forEach(function(item, index) {
        item.forEach(function(obj, i) {
            $('#' + obj).css({left: i * (100+2), top: index* (100 + 2)})
        })
    })
}
EightPuzzles.prototype.showDomMove = function(path) {
    var _ = this
    path.forEach(function(item, index) { //每次状态改变调用一次渲染函数
        setTimeout(function(node) {
            this.calDom(node)
        }.bind(_, item), index * _.timer)
    })
}

参考文章

最后

惯例po作者的博客,不定时更新中——

有问题欢迎在issues下交流。

查看原文

赞 1 收藏 3 评论 0

Aaaaaaaty 关注了专栏 · 2018-01-25

前端杂货铺

前端各种干(杂)货

关注 21

Aaaaaaaty 发布了文章 · 2018-01-19

canvas进阶——实现静态图像的变形并合成动态效果

写在最前

在之前的这篇bezierMaker.js——N阶贝塞尔曲线生成器的文章中我们提到了对于高阶贝塞尔公式的绘制与生成。不过更多的童鞋看到后可能会不知道其使用场景是什么。故作者本次分享一下基于bezierMaker.js实现的将静态图片按照自定义曲线轨迹扭曲图片并合称为动态效果。

欢迎关注我的博客,不定期更新中——

效果预览

之前的描述可能不是很清楚我们直接看下效果图:

首先加载一张图:
image

然后通过bezierMaker.js提供的试验场功能来绘制一段曲线,进行图片扭曲:
image

最后拟合为动态图:

2018-01-19 12_40_32

再来一个竖直方向的扭动:

anmate

demo地址

源码地址

图像变形实现思路

  1. 绘制一条由bezierMaker.js生成的贝塞尔曲线,以此来掌握曲线各点的准确坐标值
  2. 确定扭曲方向为横向或纵向
  3. 根据该方向的基准线(图中的灰色线)来计算本次绘制的曲线与基准对比的偏移量,按照该方向每隔1px记录一个值
  4. 将图像数据按照选定方向进行切分,将一个一维数组imgData.data变为一段一段有方向的二维数组
  5. 将每段数组按照之前记录的偏移值进行移位后再拼接为一维数组
  6. 将新拼接好的数组重新赋值到imgData中

其中较为核心的实现即横向与纵向对一维图像数据的切分。其中横向相对简单,细节如下:

image

如上图所示,在原始图像的数据中的数据形式为一维数组的形式,而对其进行拆分则是一个从中不断截取与提取数据的过程。横向拆分较为简单,只需要确定每一行开始的位置即可,截取的数量就是一行的元素数。同时纵向拆分则需要多加一步,我们需要计算每一层数组中的每一个数,像上图一般拆分第每列数组时首先要遍历图的宽得到每一列的索引,再遍历图的高,通过高✖️宽✖️4 + 宽 ✖️ 4算出当前值在原数据中的位置。当拆分成功数组后,将数组依次移位,移位数为之前曲线与基准线的偏移量决定。

//pg.js
//按行拆分
bezierArr.forEach(function (obj, index) {
    if (_.imgStartY < obj.y && _.imgStartY + _.imgHeight > obj.y && type === 'row') {
    
        var diffX = parseInt(obj.x - _.baseX, 10) //计算偏移量
        var dissY = parseInt(obj.y - _.imgStartY, 10)
        var rowNum = dissY
        imgDataSlice = _.imgData.data.slice((rowNum) * _.imgWidth * 4, rowNum * _.imgWidth * 4 + _.imgWidth * 4) //按层切片
        ...
    }
})

//按列拆分
for (var i = 0; i < _.imgWidth; i++) {
    imgDataSlice = []
    for (var j = 0; j < _.imgHeight; j++) {
        var index = j * _.imgWidth * 4 + i * 4
        var sliceArr = _.imgData.data.slice(index, index + 4)
        imgDataSlice = imgDataSlice.concat(Array.from(sliceArr))
    }
    if(_.imgChangeObj[i]) {
        for (var k = 0; k < Math.abs(_.imgChangeObj[i].diffY * 4); k++) {
            imgDataSlice = _.arraymove(_.imgChangeObj[i].diffY, imgDataSlice)
        }
        for (var p = 0; p < imgDataSlice.length / 4; p++) {
            arr[p * _.imgWidth * 4 + i * 4] = imgDataSlice[p * 4]
            arr[p * _.imgWidth * 4 + i * 4 + 1] = imgDataSlice[p * 4 + 1]
            arr[p * _.imgWidth * 4 + i * 4 + 2] = imgDataSlice[p * 4 + 2]
            arr[p * _.imgWidth * 4 + i * 4 + 3] = imgDataSlice[p * 4 + 3]
        }
    }
}

核心的数组拆分移位再合并的逻辑相对分散,知道思路即可有兴趣的同学欢迎戳源码~

合并成动态效果

核心思想为从我们的原始形态到最终态的两张静态图我们已经得到了。现在我们需要做的是添加几张过渡态。在这里面有两种方式:

  • 将计算的各点偏移量进行按比例偏移,比如一共四张图合成则需要三次改变状态,那么每次将数组移位的量设定为总量的1/3,每次移位后拼出一维数组更新到一张离屏canvas中将其保存为base64,作为后续合并时的替换url
  • 计算贝塞尔曲线控制点的偏移量且进行按比例偏移。如一开始的垂直或水平的初始图控制点形成了一条直线。同时最终形态的控制点位置我们已经知道了,借此我们可以将控制点由直线到两边的过程按比例切分,依次计算各中间态控制点所形成曲线导致的偏移图像数据,导出base64,作为后续合并替换的url

作者一开始使用了第一种方式,但是有一个明显的缺陷及通过按比例直接偏移会导致拆分出来的每层的偏移每次都是相同的,那么就会出现锯齿现象。因为图像扭曲可能上一层在这一次移位的时候偏移5合适可是你仍然偏移了总量的1/3导致与下一层的图像不匹配从而出现锯齿。故重新选择了第二种方式,由重新计算各中间态图像的控制点再来移位图像数据,图像的呈现情况就改善了很多。

小结

由于操作图像数据量比较大,故在尝试demo的时候如果遇到ui卡顿那是正在计算中,并没有引入webworker之类的所以请稍等一会就会出现结果=。=
PS:demo使用步骤

  • 加载图像
  • 画曲线,竖向切分请点击checkbox,同时曲线宽要大于图像的宽。横向切分数据则曲线高要大于图像,保证起终点在基准线外。描点后点击绘制
  • 计算结束后点击合成

其他canvas相关文章

最后

demo地址

源码地址

惯例po作者的博客,不定时更新中——

有问题欢迎在issues下交流。

查看原文

赞 4 收藏 15 评论 1

Aaaaaaaty 发布了文章 · 2018-01-09

canvas进阶——贝塞尔公式推导与物体跟随复杂曲线的轨迹运动

写在最前

在之前的这篇文章中我们提到了对于贝塞尔公式的运用。本次分享一下如何推导贝塞尔公式以及附一个简单的?即小球跟随曲线轨迹运动。

欢迎关注我的博客,不定期更新中——

效果预览

2017-12-26 14_18_42

demo地址

对于如何绘制连续的贝塞尔曲线可以参照这篇文章:基于canvas使用贝塞尔曲线平滑拟合折线段

在本例中生成的曲线由以上文章中的源码提供。

贝塞尔曲线公式推导

7460499-2603066c32c19ba9

上面这张图是贝塞尔曲线的完整公式,看起来一脸懵逼=。=,因为这是N阶的推导公式,本次我们以一二阶贝塞尔公式的推导来理解一下这个推导公式的由来。先来看下网上流传已久的几张贝塞尔动图:

1012380-20170218214830535-1198588161

1012380-20170218214945519-1357139579

1012380-20170218215045082-1043570102

在这三张图中最重要的部分是我们需要理解变量t。t的取值范围是0-1。从上面的gif中也可以看出来似乎曲线的绘制过程就是t从0到1的过程。嗯其实就是这样的。t的真实含义是什么呢?

在p0p1、p1p2、p2p3等等的起点到控制点再到终点的连线中,每段连线都被分割成了两部分(仔细看动图中的黑色、绿色、蓝色圆点),各段连线中两部分的比值都是相同的,比值范围是0到1,而这个比值就是t

来看下面的一阶贝塞尔曲线示意图:

image

pt是p0p1上的任意一点,p0pt / ptp1 = t。从而我们可以引出下面的推导

image

此时t为时间,v为速度。我们可以看做从p0到p1的距离等于固定速度乘以固定时间

image

故到p上某一点的时间为固定的速度乘以某个时间值。同时固定的速度已经已经可以表示为上面的推导公式。此时等式右边就形成了t(0,1) / t;即相当于某个时间值 / 固定时间值,即产生了我们一开始所强调的变量t,其取值范围为[0,1]。从而下面的等式也就比较好理解了。

image

至此一阶贝塞尔曲线我们已经推到了出来,其中变量为起点、终点与比值t。

那么二阶公式如何从一阶过渡过去呢?

来看下面这张图:

image

其中Pp(t)的经过路径就是我们所求的二阶贝塞尔曲线,那么其实我们也可以将其从一阶进行演变:

image

我们先将pa、pb两个点所连线段当做一阶曲线,之后再由两端一阶曲线分别表示pa、pb,最后就得到了我们的二阶曲线公式。仔细观察就能发现这和我们最初的完整公式是相同的:

7460499-2603066c32c19ba9

其中n选择不同数值时就可以得出不同阶的曲线公式。同时从上面的推导过程也可以知道,不论是几阶曲线,我们都可以完全由一阶来表示,而这个“表示”的过程就是我们在上面看到的形成动画中那些辅助线。故可以感受下作者自己写的曲线形成动画中的效果,每段辅助线均由一阶曲线形成:

2017-12-28 17_21_52

相关地址

物体跟随复杂曲线轨迹运动

当我们知道曲线的公式有何而来之后,如何让小球沿着曲线运动就很好理解了。我们生成的每段曲线都是可以用公式表示出来的,也正因如此我们就可以得到每个t值时的曲线坐标点。从而知道物体的绘制坐标。

//核心逻辑
LinearGradient.prototype.drawBall = function() {
    var self = this
    var item = ctrlNodesArr[ctrlDrawIndex] 
    //存储了各段曲线的控制点
    //各段曲线均为三阶贝塞尔,故下面计算x,y值代入到了三阶公式中
    var ctrlAx = item.cAx,//各个控制点
        ctrlAy = item.cAy,
        ctrlBx = item.cBx,
        ctrlBy = item.cBy,
    ...
    if(item.t > 1) {
        ctrlDrawIndex++ //当一段曲线的t>1说明曲线已经走到头
    }else {
        self.ctx.clearRect(0, 0, self.width, self.height)
        item.t += 0.05
        var ballX = ox * Math.pow((1 - item.t), 3) + 3 * ctrlAx * item.t * Math.pow((1 - item.t), 2) + 3 * ctrlBx * Math.pow(item.t, 2) * (1 - item.t) + x * Math.pow(item.t, 3)
        var ballY = oy * Math.pow((1 - item.t), 3) + 3 * ctrlAy * item.t * Math.pow((1 - item.t), 2) + 3 * ctrlBy * Math.pow(item.t, 2) * (1 - item.t) + y * Math.pow(item.t, 3)
        //代入三阶贝塞尔曲线公式算出小球的坐标值
        self.ctx.beginPath()
        self.ctx.arc(ballX, ballY, 5, 0, Math.PI * 2, false)
        self.ctx.fill()
    }
    if(ctrlDrawIndex !== ctrlNodesArr.length) {
        window.requestAnimationFrame(newMap.drawBall.bind(self))
    }
}

其他canvas相关文章

最后

demo地址:这里✨✨

源码地址:欢迎star

惯例po作者的博客,不定时更新中——

有问题欢迎在issues下交流。

查看原文

赞 9 收藏 11 评论 5

Aaaaaaaty 发布了文章 · 2018-01-09

基于casperjs、resemble.js实现一个像素对比服务

写在最前

本次分享一个提供设计稿与前端页面进行像素对比的node服务,旨在为测试或者前端人员自己完成一个辅助性测试。相信我,在像素级别的对比下,网页对设计稿的还原程度一下子就会凸显出来。
欢迎关注我的博客,不定期更新中——

效果预览

1

前置知识

本次用到了以下两个库作为辅助工具:

  • casperjs:基于PhantomJS的编写。其内部提供了一个无界面浏览器,简单来说用它你可以以代码的形式来完成模拟人来操作浏览器的操作,其中涉及鼠标各种事件,等等非常多的功能,本次主要使用其附带的截图功能。
  • resemble.js:图片像素对比工具。调用方法简单理解为,传入两张图,返回一张合成图并附带对比参数如差别度等等。基本实现思路可以理解为通过将图片转为canvas后,获取其图像像素点,之后对每个像素点进行一次比对。

所以整个服务我们应该已经有了大题的思路即通过casperjs来进入某个网站截取某个页面,再将其与设计图进行比对得出结果。

整体思路

image
通过上图我们应该能整理出一个大概的流程:

  1. 从前端页面接收设计稿图片及需要截取的网站地址与节点信息
  2. 将设计稿保存到images文件夹
  3. 开启子进程,启动casperjs,完成对目标网站的截取
  4. 截取后请求form.html将图片地址信息填入并重新传回服务器
  5. 服务端获取图片信息通过resemblejs将截取图与设计稿进行比对
  6. 结果传回前端页面

这其中有一个问题可能会有人注意到就是:为什么在casperjs中对目标网站截图了不能直接把信息传回服务器中,而是选择了再去打开一个表单页面通过表单的形式来提交信息?

答:首先我对casperjs和node了解都不那么深入,我理解的是首先casperjs不是一个node模块,它是跑在操作系统中的,我尚且没有发现怎么在casperjs中建立与node服务的通信,如果有方法一定要告诉我,因为我真的不太了解casper!其次由于无法建立通信,我只能退而求其次,通过casper快速打开一个我写好的表单页面并且填写好图片信息传回服务器,这么做是可以完成最初的诉求。所以就有了上面from.html那段的操作。

实现细节

实现一个简易静态服务器

因为涉及到index.html与form.html页面的返回,故需要实现一个超级简易的静态服务器。代码如下:

const MIME_TYPE = {
    "css": "text/css",
    "gif": "image/gif",
    "html": "text/html",
    "ico": "image/x-icon",
    "jpeg": "image/jpeg",
    "jpg": "image/jpg",
    "js": "text/javascript",
    "json": "application/json",
    "pdf": "application/pdf",
    "png": "image/png",
    "svg": "image/svg+xml",
    "swf": "application/x-shockwave-flash",
    "tiff": "image/tiff",
    "txt": "text/plain",
    "wav": "audio/x-wav",
    "wma": "audio/x-ms-wma",
    "wmv": "video/x-ms-wmv",
    "xml": "text/xml"
}
function sendFile(filePath, res) {
    fs.open(filePath, 'r+', function(err){ //根据路径打开文件
        if(err){
            send404(res)
        }else{
            let ext = path.extname(filePath)
            ext = ext ? ext.slice(1) : 'unknown'
            let contentType = MIME_TYPE[ext] || "text/plain" //匹配文件类型
            fs.readFile(filePath,function(err,data){
                if(err){
                    send500(res)
                }else{
                 res.writeHead(200,{'content-type':contentType})
                    res.end(data)
                }
            })
        }
    })
}

解析表单并将图片存储到images文件夹

const multiparty = require('multiparty') //解析表单
let form = new multiparty.Form()
    form.parse(req, function (err, fields, files) {
        let filename = files['file'][0].originalFilename,
            targetPath = __dirname + '/images/' + filename,
        if(filename){
            fs.createReadStream(files['file'][0].path).pipe(fs.createWriteStream(targetPath))
            ...
        } 
    })

通过创建可读流读出文件内容,再通过pipe写入到制定路径下即可保存上传来的图片。

运行casperjs

const { spawn } = require('child_process')
spawn('casperjs', ['casper.js', filename, captureUrl, selector, id])
casperjs.stdout.on('data', (data) => {
    ...
}) 

通过spawn可以创建子进程来启动casperjs,同样也可以使用exec等。

截图并提交数据到form.html

const system = require('system')
const host  = 'http://10.2.45.110:3033'
const casper = require('casper').create({
    // 浏览器窗口大小
    viewportSize: {
        width: 1920,
        height: 4080
    }
})
const fileName = decodeURIComponent(system.args[4])
const url = decodeURIComponent(system.args[5])
const selector = decodeURIComponent(system.args[6])
const id = decodeURIComponent(system.args[7])
const time = new Date().getTime()
casper.start(url)
casper.then(function() {
        console.log('正在截图请稍后')
        this.captureSelector('./images/casper'+ id + time +'.png', selector)
})
casper.then(function() {
    casper.start(host + '/form.html', function() {
        this.fill('form#contact-form', {
            'diff': './images/casper'+ id + time +'.png',
            'point': './images/' + fileName,
            'id': id
        }, true)
    })
})
casper.run()

代码还是比较简单的,主要过程就是打开一个页面,然后在then中传入你的操作,最后执行run。在这个过程里我不太知道如何与node服务通信,故选择了再开一个页面。。想深入研究的可以去看casperjs的官网非常详尽!

通过resemble.js进行像素比对并返回数据

function complete(data) {
        let imgName = 'diff'+ new Date().getTime() +'.png',
            imgUrl,
            analysisTime = data.analysisTime,
            misMatchPercentage = data.misMatchPercentage,
            resultUrl = './images/' + imgName
        fs.writeFileSync(resultUrl, data.getBuffer())
        imgObj = {
            ...
        }
        let resEnd = resObj[id] // 找回最开始的res返回给页面数据
        resEnd.writeHead(200, {'Content-type':'application/json'})
        resEnd.end(JSON.stringify(imgObj))
    }
let result = resemble(diff).compareTo(point).ignoreColors().onComplete(complete)

这其中涉及到了一个点,即我现在所得到的结果要返回给最初的请求里,而从一开始的请求到现在我已经中转了多次,导致我现在找不到我最初的返回体res了。想了很久只能暂时采用了设定全局对象,在接收最初的请求后将请求者的ip和时间戳设定为唯一id存为该对象的key,value为当前的res。同时整个中转流程中时刻传递id,最后通过调用resObj[id]来得到一开始的返回体,返回数据。这个方法我不认为是最优解,但是鉴于我现在想不出来好方法为了跑通整个服务不得已。。如果有新的思路请务必告知!!

部署

安装PhantomJS(osx)

官网下载: phantomjs-2.1.1-macosx.zip

解压路径:/User/xxx/phantomjs-2.1.1-macosx

添加环境变量:~/.bash_profile 文件中添加

export PATH="$PATH:/Users/xxx/phantomjs-2.1.1-macosx/bin"

terminal输入:phantomjs --version

能看到版本号即安装成功

安装casperjs

brew update && brew install casperjs

安装resemble.js

cnpm i resemblejs //已写进packjson可不用安装
brew install pkg-config cairo libpng jpeg giflib
cnpm i canvas //node内运行canvas

node服务

git clone https://github.com/Aaaaaaaty/gui-auto-test.git

cd gui-auto-test

cnpm i

cd pxdiff

nodemon server.js

打开http://localhost:3033/index.html

参考文献

最后

惯例po作者的博客,不定时更新中——
有问题欢迎在issues下交流。

查看原文

赞 2 收藏 2 评论 4

Aaaaaaaty 发布了文章 · 2018-01-05

从零实现一个自定义html5播放器

写在最前

本次的分享是一个基于HTML5<vedio>标签实现的一个自定义视频播放器。其中实现了播放暂停、进度拖拽、音量控制及全屏等功能。
欢迎关注我的博客,不定期更新中——

效果预览


画面卡顿请看这个地址
https://user-gold-cdn.xitu.io...
点我查看源码仓库

核心思路

我相信一定会有些没有接触过制作自定义播放器的童鞋对于<vedio>标签的认识会停留在此。

<video controls="controls" autoplay="autoplay">
  <source data-original="movie.ogg" type="video/ogg" />
</video>

其中controls属性经过设定,会在界面中显示一个浏览器自带的控制条。如果对于UI没有要求的需求,其内置控制器已经可以满足大部分的需求。当然了如果是这样你们也不会看到这篇分享了=。=

隐藏控制条并模拟

那么实现一个自定义功能的播放器关键就在于,我们不使用原生的控制器,将其隐藏掉之后,在下方同样的位置通过html、css来模拟所需样式,同时通过js来调用vedio标签所暴露给我们的接口函数及属性,以及检测用户的操作行为来同步的模拟UI与视频播放数据的相应变化。

几个核心函数及属性的用法

myVid=document.getElementById("video1");
//控制视频开关
myVid.play() //播放
myVid.pause() //暂停
//模拟视频进度条
myVid.currentTime=5; //返回或设定当前视频播放位置
myVid.duration // 返回视频总长度
//模拟视频音量
myVid.volume //音量
//获取视频当前状态后判断何时从loading切换为播放
myVid.readyState
//0 = HAVE_NOTHING - 没有关于音频/视频是否就绪的信息
//1 = HAVE_METADATA - 关于音频/视频就绪的元数据
//2 = HAVE_CURRENT_DATA - 关于当前播放位置的数据是可用的,但没有足够的数据来播放下一帧/毫秒
//3 = HAVE_FUTURE_DATA - 当前及至少下一帧的数据是可用的
//4 = HAVE_ENOUGH_DATA - 可用数据足以开始播放

在所有实现中的关键点,较为繁琐的是对于进度条的模拟。其中使用了video标签中的currentTime以及duration属性,通过当前播放时间与总播放时间的比值,就可以计算出进度条相对于总长的位置。同时用户通过拖拽进度条所最后设置的长度也可以用来反向推算出此时视频应该播放的位置。

拖拽代码思路

//核心代码示例
var dragDis = 0
var processWidth = xxx //拖拽条总长
$('body').mousedown(function(e) {
    startX = e.clientX
    dragDis = startX - leftInit //leftInit为拖拽条起始点距屏幕左侧的距离
    dragTarget.css({ //拖拽按钮
        left: dragDis
    })
    dragProcess.css({ //进度条(蓝色进度条)
        width: dragDis
    }) // 令进度条和拖拽按钮渲染在同一位置
    videoSource.pause()
}).mousemove(function(e) {
    moveX = e.clientX
    disX = moveX - startX
    var left = dragDis + disX
    if(left > processWidth) {
        left = processWidth
    } else if(left < 0) {
        left = 0
    }
    dragTarget.css({
        left: left
    })
    dragProcess.css({
        width: left
    })
}).mouseup(function(e) {
    videoSource.play()
    videoSource.currentTime = $('蓝色拖拽条').width() / processWidth * duration //拖拽后计算视频的正确播放位置
})

同理音量的控制与其上行为基本一致,故在源码中作者将音量与进度部分通过不同元素进行判断是进行进度还是音量的拖拽控制。

通过查询视频流状态控制播放前的加载动画

function ifState() {
    var state = videoSource.readyState
    if(state === 4) { //状态为4即可播放
        videoPlayer()
    } else {
        $('.play-sym-wrapper').remove()
        $('body').append('<div class="play-sym-wrapper"><img class="play-sym" data-original="./images/loading.gif"></div>')
        //添加loading动画
        setTimeout(ifState, 10)
    }
}
setTimeout(ifState, 10)

核心的控制部分已经说完了,有兴趣的同学可以去源码的html中点击播放,其中被迫有很多零碎的需求,比如点击暂停,保存音量等等。整个视频播放器的基础功能实现的还算完善。

最后

惯例po作者的博客,不定时更新中——
有问题欢迎在issues下交流。

查看原文

赞 3 收藏 4 评论 0

Aaaaaaaty 发布了文章 · 2018-01-05

Javascript之bind

写在最前

最近开始重新学习一波js,框架用久了有些时候觉得这样子应该可以实现发现就真的实现了,但是为什么这么写好像又说不太清楚,之前读了LucasHC以及冴羽的两篇关于bind的文章感觉自己好像基础知识都还给体育老师了哈哈哈,所以危机感爆棚,赶紧重头复习一遍。本次主要围绕bind是什么;做了什么;自己怎么实现一个bind,这三个部分。其中会包含一些细节代码的探究,往下看就知道。

所以bind是什么

bind()方法创建一个新的函数, 当被调用时,将其this关键字设置为提供的值,在调用新函数时,在任何提供之前提供一个给定的参数序列。
var result = fun.bind(thisArg[, arg1[, arg2[, ...]]]) 
result(newArg1, newArg2...)

没看懂没事接着往下看。

bind到底做了什么

从上面的介绍中可以看出三点。首先调用bind方法会返回一个新的函数(这个新的函数的函数体应该和fun是一样的)。同时bind中传递两个参数,第一个是this指向,即传入了什么this就等于什么。如下代码所示:

this.value = 2
var foo = {
    value: 1
}
var bar = function() {
  console.log(this.value)
}
var result = bar.bind(foo)
bar() // 2
result() // 1,即this === foo

第二个参数为一个序列,你可以传递任意数量的参数到其中。并且会预置到新函数参数之前。

this.value = 2
var foo = {
    value: 1
};
var bar = function(name, age, school) {
  console.log(name) // 'An'
  console.log(age) // 22
  console.log(school) // '家里蹲大学'
}
var result = bar.bind(foo, 'An') //预置了部分参数'An'
result(22, '家里蹲大学') //这个参数会和预置的参数合并到一起放入bar中

我们可以看出在最后调用 result(22, '家里蹲大学') 的时候,其内部已经包含了在调用bind的时候传入的 'An'

一句话总结:调用bind,就会返回一个新的函数。这个函数里面的this就指向bind的第一个参数,同时this后面的参数会提前传给这个新的函数。调用该新的函数时,再传递的参数会放到预置的参数后一起传递进新函数。

自己实现一个bind

实现一个bind需要实现以下两个功能

  • 返回一个函数,绑定this,传递预置参数
  • bind返回的函数可以作为构造函数使用。故作为构造函数时应使得this失效,但是传入的参数依然有效

1、返回一个函数,绑定this,传递预置参数

this.value = 2
var foo = {
    value: 1
};
var bar = function(name, age, school) {
    console.log(name) // 'An'
    console.log(age) // 22
    console.log(school) // '家里蹲大学'
    console.log(this.value) // 1
}
Function.prototype.bind = function(newThis) {
    var aArgs   = Array.prototype.slice.call(arguments, 1) //拿到除了newThis之外的预置参数序列
    var that = this
    return function() {
        return that.apply(newThis, aArgs.concat(Array.prototype.slice.call(arguments)))
        //绑定this同时将调用时传递的序列和预置序列进行合并
    }
}
var result = bar.bind(foo, 'An')
result(22, '家里蹲大学')

这里面有一个细节就是Array.prototype.slice.call(arguments, 1) 这句话,我们知道arguments这个变量可以拿到函数调用时传递的参数,但不是一个数组,但是其具有一个length属性。为什么如此调用就可以将其变为纯数组了呢。那么我们就需要回到V8的源码来进行分析。#这个版本的源码为早期版本,内容相对少一些。


function ArraySlice(start, end) {
  var len = ToUint32(this.length); 
  //需要传递this指向对象,那么call(arguments),
  //便可将this绑定到arguments,拿到其length属性。
  var start_i = TO_INTEGER(start);
  var end_i = len;
  
  if (end !== void 0) end_i = TO_INTEGER(end);
  
  if (start_i < 0) {
    start_i += len;
    if (start_i < 0) start_i = 0;
  } else {
    if (start_i > len) start_i = len;
  }
  
  if (end_i < 0) {
    end_i += len;
    if (end_i < 0) end_i = 0;
  } else {
    if (end_i > len) end_i = len;
  }
  
  var result = [];
  
  if (end_i < start_i)
    return result;
  
  if (IS_ARRAY(this))
    SmartSlice(this, start_i, end_i - start_i, len, result);
  else 
    SimpleSlice(this, start_i, end_i - start_i, len, result);
  
  result.length = end_i - start_i;
  
  return result;
};

从源码中可以看到通过call将arguments下的length属性赋给slice后,便可通过 start_i & end_i来获得最后的数组,所以不需要传递进slice时就是一个纯数组最后也可以得到一个数组变量。

2、bind返回的函数可以作为构造函数使用

被用作构造函数时,this应指向new出来的实例,同时有prototype属性,其指向实例的原型。

this.value = 2
var foo = {
  value: 1
};
var bar = function(name, age, school) {
  ...
  console.log('this.value', this.value)
}
Function.prototype.bind = function(newThis) {
  var aArgs   = Array.prototype.slice.call(arguments, 1)
  var that = this  //that始终指向bar
  var NoFunc = function() {}
  var resultFunc = function() {
    return that.apply(this instanceof that ? this : newThis, aArgs.concat(Array.prototype.slice.call(arguments)))
  } 
  NoFunc.prototype = that.prototype //that指向bar
  resultFunc.prototype = new NoFunc()
  return resultFunc
  
}
var result = bar.bind(foo, 'An')
result.prototype.name = 'Lsc' // 有prototype属性
var person = new result(22, '家里蹲大学')
console.log('person', person.name) //'Lsc'

上面这段模拟代码做了两件重要的事。

1.给返回的函数模拟一个prototype属性。,因为通过构造函数new出来的实例可以查询到原型上定义的属性和方法

var NoFunc = function() {}
...
NoFunc.prototype = that.prototype //that指向bar
resultFunc.prototype = new NoFunc()
return resultFunc

通过上面代码可以看出,that始终指向bar。同时返回的函数已经继承了that.prototype即bar.prototype。为什么不直接让返回的函数的prototype属性resultFunc.prototype 等于为bar(that).prototype呢,这是因为任何new出来的实例都可以访问原型链。如果直接赋值那么new出来的对象可以直接修改bar函数的原型链,这也就是是原型链污染。所以我们采用继承的方式(将构造函数的原型链赋值为父级构造函数的实例),让new出来的对象的原型链与bar脱离关系。

2.判断当前被调用时,this是用于普通的bind还是用于构造函数从而更改this指向。

如何判断当前this指向了哪里呢,通过第一点我们已经知道,通过bind方法返回的新函数已经有了原型链,剩下需要我们做的就是改变this的指向就可以模拟完成了。通过什么来判断当前被调用是以何种姿势呢。答案是instanceof

instanceof 运算符用来测试一个对象在其原型链中是否存在一个构造函数的 prototype 属性。
// 定义构造函数
function C(){} 
function D(){} 
var o = new C();
// true,因为 Object.getPrototypeOf(o) === C.prototype
o instanceof C; 
// false,因为 D.prototype不在o的原型链上
o instanceof D; 

从上面可以看出,instanceof可以判断出一个对象是否是由这个函数new出来的,如果是new出来的,那么这个对象的原型链应为该函数的prototype.
所以我们来看这段关键的返回的函数结构:

var resultFunc = function() {
    return that.apply(this instanceof that ? 
        this : 
        newThis, 
        aArgs.concat(Array.prototype.slice.call(arguments)))
  } 

在这其中我们要先认清this instanceof that 中的this是bind函数被调用后,返回的新函数中的this。所以这个this可能执行在普通的作用域环境,同时也可能被new一下从而改变自己的指向。再看that,that始终指向了bar,同时其原型链that.prototype是一直存在的。所以如果现在这个新函数要做new操作,那么this指向了新函数,那么 this instanceof that === true, 所以在apply中传入this为指向,即指向新函数。如果是普通调用,那么this不是被new出来的,即新函数不是作为构造函数,this instanceof that === false就很显而易见了。这个时候是正常的bind调用。将调用的第一个参数作为this的指向即可。

完整代码(MDN下的实现)

if (!Function.prototype.bind) {
  Function.prototype.bind = function(oThis) {
    if (typeof this !== 'function') {
      // closest thing possible to the ECMAScript 5
      // internal IsCallable function
      throw new TypeError('Function.prototype.bind - what is trying to be bound is not callable');
    }

    var aArgs   = Array.prototype.slice.call(arguments, 1),
        fToBind = this,
        fNOP    = function() {},
        fBound  = function() {
          return fToBind.apply(this instanceof fNOP
                 ? this
                 : oThis,
                 aArgs.concat(Array.prototype.slice.call(arguments)));
        };

    if (this.prototype) {
      // Function.prototype doesn't have a prototype property
      fNOP.prototype = this.prototype; 
    }
    fBound.prototype = new fNOP();
    return fBound;
  };
}

可以看到,其首先做了当前是否支持bind的判定,不支持再实行兼容。同时判断调用这个方法的对象是否是个函数,如果不是则报错。

同时这个模拟的方法也有一些缺陷,可关注MDN上的Polyfill部分

小结

模拟bind实现最大的一个缺陷是,模拟出来的函数中会一直存在prototype属性,但是原生的bind作为构造函数是没有prototype的,这点打印一下即可知。不过这样子new出来的实例没有原型链,那么它的意义是什么呢。如果哪天作者知道了意义会更新在这里的=。= 如果说错的地方欢迎指正,一起交流哈哈。

查看原文

赞 1 收藏 1 评论 0

认证与成就

  • 获得 94 次点赞
  • 获得 3 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 3 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

  • bezierMaker.js

    原生HTML5的canvas中所支持的贝塞尔曲线最多只到3阶 bezierMaker.js可以理论支持N阶贝塞尔曲线的生成,同时提供了试验场来自行添加拖拽控制点并形成绘制动画

注册于 2017-12-29
个人主页被 1.4k 人浏览