Charon

Charon 查看完整档案

北京编辑邢台学院  |  计算机基础与应用 编辑望海康信  |  高级工程师 编辑 segmentfault.com/u/charon_5f4765a39cea7 编辑
编辑

世界核平

个人动态

Charon 发布了文章 · 10月18日

javaScript之异步发展史二(generator,async)

接着来说,generator生成器函数:看似同步的异步流程控制风格。

基础部分可以看一下阮一峰老师的 生成器函数的概念了解一下。

ECMAScript 6 入门 生成器

这里只做一些 生成器函数配合promise的高级使用。

在生成器函数中可以 同步的使用try catch来捕获错误。

生成器中可以使用yield 来等待 异步promise的返回,这样我们配合使用就可以 同步的来监听 异步任务里的错误。

支持Promsie的Generator Runner

如何自动从执行到结束一个生成器函数,asynquence 这个库里的runner()做了实现,现在我们来实现一个自己简易版本,run(...)

function run(gen){
    var args = [].slice.call(arguments,1);//不包含第一个之后的参数
    var it = gen.apply(this,args);//用当前上下文 还有args参数初始化生成器
    return Prommise.resolve().then(function handleNext(value){
        var next = it.next(value);//对下一个yield出的值运行
        return (function handleResult(next){
            if(next.done){//如果迭代到最后,生成器函数运行完毕
                return next.value;
            }else{//未运行完毕
                //next.value的值不一定是promsie,有可能是个立即值,所以通过promise.resolve()统一转成异步操作
                return Promise.resolve(next.value).then(
                        handleNext,//成功就回复异步循环,把决议的值发回生成器
                        function handleErr(err){
                            //如果value是 被拒绝的promise,就把错误传回生成器进行出错处理
                            //[https://www.axihe.com/api/js-es/ob-generator/throw.html](https://www.axihe.com/api/js-es/ob-generator/throw.html)
                            //it.throw(err)类似it.next  也会继续往下走,处理错误,返回 next对象包含done和value
                            return Promise.resolve(it.throw(err)).then(handleResult)    
                        }
                )
            }
        })(next)
    })
    
}

//测试调用
        function foo(b) {
            return request(b);
        }
        function request(b) {
            return new Promise(function (resolve, reject) {
                setTimeout(function () {
                    if (b) {
                        resolve('100')
                    } else {
                        reject('200')
                    }
                }, 2000)
            })
        }
        function *main() {
            try {
                var texts = yield foo();
                console.log(texts)
                var text = yield foo(true);
                console.log(text)

            } catch (err) {
                console.error(err);
            }
            var text = yield foo(true);
            console.log(text)
            return 40;
        }
console.log(run(main).then(function (v) { console.log(v) }))

这种自动运行run的方式,它会自动异步运行你传给它的生成器。

这种模式看起来是不是很眼熟,这就是async与await的前身
ES7的 async和await如下

function foo(x,y){
    return request('http://...')
}
async function main(){
    try{
        var text = await foo(1,51);
        console.log(text)
    }catch(err){
        console.error(err)
    }
}
main()

使用async关键词修饰。

生成器中promise的并发。

使用生成器实现异步的方法全部要点在于创建简单,顺序,看似同步的代码,将异步的细节尽可能的隐藏起来。

function bar(url1,url2){
    return Promise.all([
        request(url1),
        request(url2)
    ])
}
function *foo(){
    var results = yield bar('http://...1','http://...2');
    const [r1,r2] = results;
    var r3 = request('http://...3'+r1+r2)
    console.log(r3)
}

//更高级的用法,组合promise 的api
function bar(){
    Promise.all([baz(...).then(...),Promise.race([...])]).then(...)
}

像bar方法里这种逻辑,如果直接放在生成器内部的话,那就失去了一开始使用生成器的理由,应该有意把这样的细节从生成器中抽象出来,以避免它把高层次的任务表达变得杂乱。

查看原文

赞 0 收藏 0 评论 0

Charon 发布了文章 · 10月17日

如何实现一个mini-react的大概思路

准备工作

git地址 mini-react
如果不能使用请联系我。
这里不做太多 工具的介绍,所以打包工具选用相对简单的parcel

npm install -g parcel-bundler

接下来新建index.jsindex.html,在index.html中引入index.js
然后就是babel的配置
.babelrc

{
    "presets": ["env"],
    "plugins": [
        ["transform-react-jsx", {
            "pragma": "React.createElement"
        }]
    ]
}

这个transform-react-jsx就是将jsx转换成js的babel插件,它有一个pragma项,可以定义jsx转换方法的名称,你也可以将它改成h(这是很多类React框架使用的名称)或别的。

准备完成以后我们就可以用命令parcel index.html将它跑起来了。

jsx

在开始之前要先了解一个概念,在react中render或者函数组件中返回的代码,如下:

const title = <h1 className="title">Hello, world!</h1>;

这段代码并不是合法的js代码,它是一种被称为jsx的语法扩展,通过它我们就可以很方便的在js代码中书写html片段。

本质上,jsx是语法糖,上面这段代码会被babel转换成如下代码

const title = React.createElement(
    'h1',
    { className: 'title' },
    'Hello, world!'
);

有兴趣,可以用babel做个测试 babel测试

React.createElement和虚拟DOM

我们知道所有的jsx代码,都会被转换成React.createElement这种形式
从jsx解析结果来看,createElement方法参数应该是:

createElement(tag,attrs,child1,child2,child3,child4)

第一个参数是DOM元素的标签名,比如说:div,span,h1,main
第二个参数是一个对象,里面包含了所有属性,可能包含className,id等等
第三个参数开始,就是它的子节点。
那我们只要自己一个React全局对象,给它挂载这个React.createElement方法就可以进行接下来的处理:

const React = {};
React.createElement = function(tag, attrs, ...children) {
  return {
    tag,
    attrs,
    children
  };
};
export default React;

我们的createElement方法返回的对象记录了这个DOM节点所有信息,换句话说,通过它我们就可以生成真正的DOM,这个记录信息的对象我们称之为虚拟DOM。
接下来来测试下:

image

输出:
image

打开调试工具,我们可以看到输出的对象和我们预想的一致

处理好了jsx,现在我们来开始处理入口

ReactDOM.render方法是我们的入口
先定义ReactDOM对象,然后看它的render方法~
先看看默认解析是什么样

const ReactDOM={};
ReactDOM.render(
    <h1>Hello, world!</h1>,
    document.getElementById('root')
);

//经过转换
ReactDOM.render(
    React.createElement( 'h1', null, 'Hello, world!' ),
    document.getElementById('root')
);

可以看到ReactDom.render的解析,所以render第一个参数是createElement返回的对象,也就是虚拟DOM,,第二个参数也就是要挂载目标的DOM。
也就是说render方法就把虚拟dom对象-js对象变成真实dom对象,然后插入到根标签内。
然后开始定义:

const ReactDom = {};
const render = function(vnode, container) {
  return container.appendChild(_render(vnode));
};
ReactDom.render = render;
思路: 先把虚拟dom对象-js对象变成真实dom对象,然后插入到根标签内。

_render方法,接受虚拟dom对象,返回真实dom对象:
如果传入的是null,字符串或者数字 那么直接转换成真实dom然后返回就可以了~,如果是其他类型要做一些特殊处理,看代码把。

import handleAttrs from './handleAttrs';
import {createComponent,setComponentProps} from '../components/utills';
const ReactDom = {};
//传入虚拟dom节点和真实包裹节点,把虚拟dom节点通过_render方法转换成真实dom节点,然后插入到包裹节点中,这个就是react的初次渲染
const render = function (vnode, container) {
    return container.appendChild(_render(vnode));
};
ReactDom.render = render;
export function _render(vnode) {
    console.log('reactDom render', vnode);
    if (vnode === undefined || vnode === null || typeof vnode === 'boolean') {//做个防错
        vnode = '';
    }
    if (typeof vnode === 'number') {
        vnode = String(vnode);
    }
    if (typeof vnode === 'string') {//如果是最里面一层或者就是个字符串的话,转化成Node类型,遵从appendChild要求
        let textNode = document.createTextNode(vnode);
        return textNode;
    }
    if (typeof vnode.tag === 'function') {//是一个组件<app></app>这种  babel会给我们做转换 vnode.tag得类型
        //hooks
        const component = createComponent(vnode.tag, vnode.attrs);//组件类型的话,创建组件
        setComponentProps(component, vnode.attrs);//设置组件属性,并且转换为真实dom,component.base里存着真实dom
        return component.base;
    }
    // vnode= {tag,props,children}
    // {tag:"li",attrs:{xxx:},children:1}   这几种情况都排除之后,那就是html元素了
    const dom = document.createElement(vnode.tag);
    if (vnode.attrs) {//但是有可能传入的是个div标签,而且它有属性。那么需要处理属性,由于这个处理属性的函数需要大量复用,我们单独定义成一个函数:   
        Object.keys(vnode.attrs).forEach(key => {
            const value = vnode.attrs[key];
            handleAttrs(dom, key, value);//如果有属性,例如style标签、onClick事件等,都会通过这个函数,挂在到dom上
        });
    }
    vnode.children && vnode.children.forEach(child => render(child, dom)); // 有子集的话,递归渲染子节点
    return dom;
}

export default ReactDom;

但是可能有子节点(babel转的结构,可以下代码输出看下,完事会把git链接放上来)的嵌套,于是要用到递归(就在上面代码得结尾):

 vnode.children && vnode.children.forEach(child => render(child, dom));

如果要是html元素标签,而且它有属性。那么需要处理属性,由于这个处理属性的函数需要大量复用,我们单独定义成一个函数(上面handleAttrs就是这个setAttribute得导出):

export default function setAttribute(dom, name, value) {
    if (name === 'className') name = 'class';
    if (/on\w+/.test(name)) {
      name = name.toLowerCase();
      dom[name] = value || '';
    } else if (name === 'style') {
      if (!value || typeof value === 'string') {
        dom.style.cssText = value || '';
      } else if (value && typeof value === 'object') {
        for (let name in value) {
          dom.style[name] =
            typeof value[name] === 'number' ? value[name] + 'px' : value[name];
        }
      }
    } else {
      if (name in dom) {
        dom[name] = value || '';
      }
      if (value) {
        dom.setAttribute(name, value);
      } else {
        dom.removeAttribute(name);
      }
    }
  }
  

然后处理上面说的组件类型了,加入新一个新的处理方式:

我们先定义好Component这个类,并且挂载到全局React的对象上

import { enqueueSetState } from './setState';
export class Component {
    constructor(props = {}) {
        this.state = {};
        this.props = props;
    }
    setState(stateChange){
        console.log('state')
      
        enqueueSetState(newState, this);//异步合并state,并更新组件得方法
    }
}

image

组件类型 babel也会通过React.crateElement()来给我们做转换,下面就是实现_render里所用到得createComponent创建和setComponentProps设置属性以及相关得renderComponent根据虚拟DOM生成真实DOM加载等方法。

import { Component } from './component';
export function createComponent(component, props) {
    let inst;
    //如果是类定义组件component是function,直接返回实例。
    if (component.prototype && component.prototype.render) {
        inst = new component(props);//实例化
    } else {//如果是函数组件
        inst = new Component(props);
        inst.constructor = component; //把函数组件储存下,方便统一render调用
        inst.render = function () {
            this.constructor(props);//调用函数
        }
    }
    return inst;//返回组件实例
}
export function setComponentProps(component, props) {//设置属性,并执行部分生命周期
    if (!component.base) {//首次加载
        if (component.componentWillMount) component.componentWillMount();//执行将要装载生命周期
    } else if (component.base && component.componentWillReceiveProps) {//props变化
        component.componentWillReceiveProps(props);
    }

    component.props = props;//props变化了,重新赋值
    renderComponent(component);//生成真实dom  
}
export function renderComponent(component) {
    console.log('renderComponent');
    let base;
    //调用render方法,返回jsx,通过createElement返回虚拟dom对象 这里会用到state 此时的state已经通过上面的setState时队列合并 更新了
    const renderer = component.render();
    if (component.base && component.shouldComponentUpdate) {//优化用得生命周期,根据返回值确定是否继续要渲染
        let result = true;
        result = component.shouldComponentUpdate({}, component.newState);//props得处理有点问题,后续要改进下
        if (!result) {
            return;
        }
    }

    if (component.base && component.componentWillUpdate) {//组件即将更新得时候触发生命周期函数,首次加载不触发
        component.componentWillUpdate();
    }

    //根据diff算法,得到真实dom对象
    base = diffNode(component.base, renderer);

    if (component.base) {
        if (component.componentDidUpdate) component.componentDidUpdate();//更新完毕生命周期,首次不加载
    } else {
        component.base = base;//base是真实DOM,将本次得真实DOM挂载到组件上,方便判断是否首次挂载。
        base_component = component;//互相引用,方便后续队列处理
        component.componentDidMount && component.componentDidMount();//首次挂载完后,真实dom生成后得生命周期
        return;
    }

    //不是首次加载,挂载真实的dom对象到对应的 组件上 方便后期对比
    component.base = base;

    //不是首次加载,挂载对应到组件到真实dom上 方便后期对比~
    base._component = component;
}

然后就是根据虚拟DOM得到真实DOM得 diff算法

总而言之,我们的diff算法有两个原则:

  • 对比当前真实的DOM和虚拟DOM,在对比过程中直接更新真实DOM
  • 只对比同一层级的变化
import handleAttrs from '../reactDom/handleAttrs';
import {setComponentProps,createComponent} from '../components/utills';
/**
 * @param {HTMLElement} dom 真实DOM
 * @param {vnode} vnode 虚拟DOM
 * @param {HTMLElement} container 容器
 * @returns {HTMLElement} 更新后的DOM
 */
export function diffNode(dom, vnode) {//当前得dom 真实DOM,当前得vnode 虚拟DOM
    let out = dom;
    if (vnode === undefined || vnode === null || typeof vnode === 'boolean') {
        vnode = '';
    }
    if (typeof vnode === 'number') {
        vnode = String(vnode);
    }

    if (typeof vnode === 'string') {//diff  text node  文本节点
        if (dom && dom.nodeType === 3) {//当前dom就是文本节点
            if (dom.textContent !== vnode) {//如果内容和虚拟dom不一样,更改
                dom.textContent = vnode;
            }
        } else {//如果当前dom不是文本节点,创建一个新的文本节点,并更新;
            out = document.createTextNode(vnode);
            if (dom && dom.parentNode) {
                //https://www.w3school.com.cn/jsref/met_node_replacechild.asp
                dom.parentNode.replaceChild(out, dom);
            }
        }
        return out;//更新完,返回
    }

    if (typeof vnode.tag === 'function') {//因为会递归调用,如果某一次调用传入得是组件类型,也就是说调用过程中有一层得节点是组件,就对比组件更新
        return diffComponent(dom, vnode);
    }
    console.log(dom, vnode)
    if (!dom || !isSameNodeType(dom, vnode)) {//如果真实DOM要是不存在,或者当前元素标签层级有变化得话
        out = document.createElement(vnode.tag);

        if (dom) {
            [...dom.childNodes].map(item => out.appendChild(item)); // 将原来的子节点移到新节点下
            console.log(out, 'out', dom.childNodes)
            if (dom.parentNode) {
                dom.parentNode.replaceChild(out, dom); // 移除掉原来的DOM对象
            }
        }
    }

    if (
        (vnode.children && vnode.children.length > 0) ||
        (out.childNodes && out.childNodes.length > 0)
    ) {//如果 有子集的话,对比子集更新, 两个都要判断一种虚拟dom有子集,一种是虚拟DOM没子集,但是真实dom有子集
        diffChildren(out, vnode.children);
    }

    diffAttributes(out, vnode);//更新属性
    return out;

}
export function diffAttributes(dom, vnode) {
    const old = {}; // 当前DOM的属性
    const attrs = vnode.attrs; // 虚拟DOM的属性

    for (let i = 0; i < dom.attributes.length; i++) {
        const attr = dom.attributes[i];
        old[attr.name] = attr.value;
    }

    // 如果原来的属性不在新的属性当中,则将其移除掉(属性值设为undefined)
    for (let name in old) {
        if (!(name in attrs)) {
            handleAttrs(dom, name, undefined);
        }
    }

    // 更新新的属性值
    for (let name in attrs) {
        if (old[name] !== attrs[name]) {
            handleAttrs(dom, name, attrs[name]);
        }
    }
}
function diffChildren(dom, vchildren) {//父级真实dom,和虚拟DOM子集
    const domChildren = dom.childNodes;//真实DOM子集  和vchildren对应 同层次对比
    //没有key得真实DOM集合
    const children = [];
    //有key得集合
    const keyed = {};
    if (domChildren.length > 0) {//真实DOM有子集
        for (let i = 0; i < domChildren.length; i++) {
            const child = domChildren[i];
            const key = child.key;
            if (key) {//根据有没有key,把子集分一下
                keyed[key] = child;
            } else {
                children.push(child);
            }
        }
    }
    if (vchildren && vchildren.length > 0) {//虚拟dom子集有
        let min = 0;
        let childrenLen = children.length;//无key得长度
        for (let i = 0; i < vchildren.length; i++) {//循环虚拟dom
            const vchild = vchildren[i];
            const key = vchild.key;
            let child;
            if (key) {//有key
                if (keyed[key]) {//从真实dom里找一下,看有没有
                    child = keyed[key];//储存下
                    keyed[key] = undefined;//清空
                }
            } else if (min < childrenLen) {//否则没有key,从没key里找,并且开始childrenLen不是0
                for (let j = min; j < childrenLen; j++) {
                    let c = children[j];

                    if (c && isSameNodeType(c, vchild)) {//用真实DOM和虚拟DOM比对一下看是不是同一个节点类型和值相等,包括组件得比对
                        child = c;//是同一个找到了,存一下
                        children[j] = undefined;//清空下
                        if (j === childrenLen - 1) childrenLen--;//做下标记,这个元素找过了,下次略过这个元素min也一样
                        if (j === min) min++;
                        break;
                    }
                }
            }

            child = diffNode(child, vchild);//当前这项真实DOM和虚拟DOM做一个比对,更新如果里面还有子集又会调用diffChildren,返回真实Dom
            const f = domChildren[i];//获取原来真实dom集合中得当前项
            console.log(child, f)
            if (child && child !== f) {//如果比对完得child和当前这个f不一样
                if (!f) {//如果不存在,reacrDom第一次render时,直接添加到父级里
                    dom.appendChild(child);
                } else {//child 已经从真实dom找过一轮,并且和虚拟DOM对比生成过的了。
                    // dom.insertBefore(child, f);
                    // dom.removeChild(f);
                    dom.replaceChild(child, f);//替换掉
                }
            }

        }
        if (dom) {
            if (childrenLen > vchildren.length) {//删除多余节点
                for (let i = vchildren.length; i < childrenLen; i++) {
                    dom.removeChild(children[i]);
                }
            }
        }
    }
}

function isSameNodeType(dom, vnode) {//这个方法很多地方用到
    if (typeof vnode === 'string' || typeof vnode === 'number') {
        return dom.nodeType === 3 && dom === String(vnode); //查看是否是文本节点
    }
    if (typeof vnode.tag === 'string') {
        return dom.nodeName.toLowerCase() === vnode.tag.toLowerCase(); //查看当前层级是否标签换了
    }
    return dom && dom._component && dom._component.constructor === vnode.tag;//在renderComponent做过互相引用,
    //通过createComponent方法里实例化处理根据constructor判断是否是vbode.tag得实例,如果不是当前层级 组件更换了,
    //diffChildren里找对应组件时会用到这里
}
function diffComponent(dom, vnode) {
    let c = dom && dom._component;
    let oldDom = dom;
    // 如果组件类型没有变化,则重新set props
    if (c && c.constructor === vnode.tag) {
        setComponentProps(c, vnode.attrs);
        dom = c.base;
        // 如果组件类型变化,则移除掉原来组件,并渲染新的组件
    } else {
        if (c) {
            unmountComponent(c);
            oldDom = null;
        }

        c = createComponent(vnode.tag, vnode.attrs);

        setComponentProps(c, vnode.attrs);
        dom = c.base;

        if (oldDom && dom !== oldDom) {
            oldDom._component = null;
            removeNode(oldDom);
        }
    }
    return dom;
}

function removeNode(dom) {
    if (dom && dom.parentNode) {
        dom.parentNode.removeChild(dom);
    }
}

这上面里的是整套得diff算法,包含了对各种类型得处理以及子集得处理,可以跟着代码仓库例子跑一跑,自己手写一下,diffChildren会稍微复杂一点。
shouldComponentUpdate中得props第一个参数有点问题。有兴趣得同学可以看看看着在代码里做一下优化
剩下就是优化setState得合成
优化使用requestAnimationFrame实现。
window.requestAnimationFrame() 告诉浏览器——你希望执行一个动画,并且要求浏览器在下次重绘之前调用指定的回调函数更新动画。该方法需要传入一个回调函数作为参数,该回调函数会在浏览器下一次重绘之前执行


import { renderComponent } from './utills';

/**
 * 队列   先进先出 后进后出 ~
 * @param {Array:Object} setStateQueue  抽象队列 每个元素都是一个key-value对象 key:对应的stateChange value:对应的组件
 * @param {Array:Component} renderQueue  抽象需要更新的组件队列 每个元素都是Component
 */
const setStateQueue = [];
const renderQueue = [];
function defer(fn) {
    //requestIdleCallback的兼容性不好,对于用户交互频繁多次合并更新来说,requestAnimation更有及时性高优先级,requestIdleCallback则适合处理可以延迟渲染的任务~
    //   if (window.requestIdleCallback) {
    //     console.log('requestIdleCallback');
    //     return requestIdleCallback(fn);
    //   }
    //高优先级任务 异步的 先挂起  
    //告诉浏览器——你希望执行一个动画,并且要求浏览器在下次重绘之前调用指定的回调函数更新动画。该方法需要传入一个回调函数作为参数,该回调函数会在浏览器下一次重绘之前执行
    return requestAnimationFrame(fn);
}
export function enqueueSetState(stateChange, component) {
    //第一次进来肯定会先调用defer函数
    if (setStateQueue.length === 0) {
        //清空队列的办法是异步执行,下面都是同步执行的一些计算
        defer(flush);
    }
    // setStateQueue:[{state:{a:1},component:app},{state:{a:2},component:test},{state:{a:3},component:app}]

    //向队列中添加对象 key:stateChange value:component
    setStateQueue.push({
        stateChange,
        component
    });
    //如果渲染队列中没有这个组件 那么添加进去
    if (!renderQueue.some(item => item === component)) {
        renderQueue.push(component);
    }
}

function flush() {//下次重绘之前调用,合并state
    let item, component;
    //依次取出对象,执行 
    while ((item = setStateQueue.shift())) {
        const { stateChange, component } = item;

        // 如果没有prevState,则将当前的state作为初始的prevState
        if (!component.prevState) {
            component.prevState = Object.assign({}, component.state);
        }
        let newState;
        // 如果stateChange是一个方法,也就是setState的第二种形式
        if (typeof stateChange === 'function') {
            newState = Object.assign(
                component.state,
                stateChange(component.prevState, component.props)
            );
        } else {
            // 如果stateChange是一个对象,则直接合并到setState中
            newState = Object.assign(component.state, stateChange);
        }
        component.newState = newState;
        component.prevState = component.state;
    }
    //先做一个处理合并state的队列,然后把state挂载到component下面 这样下面的队列,遍历时候,能也拿到state属性
    //依次取出组件,执行更新逻辑,渲染
    while ((component = renderQueue.shift())) {
        renderComponent(component);
    }
}

有兴趣的同学,可以拉下来代码自己改改看看呦。
window.requestAnimationFrame

文章参考
从零自己编写一个React框架 【中高级前端杀手锏级别技能】
hujiulong的博客

未完待续

查看原文

赞 0 收藏 0 评论 0

Charon 发布了文章 · 10月13日

javaScript之异步发展史一(回调,promise )

jsvascript现在运行的部分和将来运行的部分之间的关系就是异步编程的核心

事件循环(仅浏览器描述不包含node事件循环)

如果javascrip程序发出一个ajax请求,从服务器获取一些数据,那你就在一个函数(通常称为回调函数)中设置好响应代码,然后javascrip引擎会通知宿主环境:这个回调函数暂停执行,你一旦完成网络请求,拿到数据就请调用这个回调函数。
然后浏览器就会设置侦听来自网络的响应,拿到数据之后,就会把回调函数插入到事件循环,以此实现对这个回调的调度执行。(将来执行)(定时器回调函数也是类似)

用一段伪代码来描述 一下事件循环的概念

//eventLoop 是一个用作队列的数组
//先进,先出
var eventLoop = [];
var event;
while(true){//永远执行
    //一次tick
    if(eventLoop.length>0){
        event = eventLoop.shift();//拿到队列中的下一个事件
        //现在开始执行下一个事件
        try{
            event();
        }catch(err){
            reportError(err);//捕获异常函数
        }
    }
}

循环的每一轮称一个tick,对每个tick而言,如果在队列有等待事件,就会从队列中摘下一个事件并执行,这些事件就是回调函数。

setTimeout(...)并没有立刻把你的回调函数挂到事件循环中,它所做的是设定一个定时器,当定时器到时后,环境会把你的回调函数放到事件循环中,这样在未来的某个时刻的tick会摘下并执行这个回调。

如果这时候事件循环中有20个项目了,你的回调就会等待,它得排在其他项目后面——通常没有抢占得方式支持直接将其排到队首(后面会讲建立在事件循环上新概念任务队列,Promise异步特性来解决精细控制),这也解释了为什么定时器得精度可能不太高,大体来说,只能确保你的回调函数不会在指定时间间隔之前运行,但可能在那个时刻运行,也可能在那之后运行,要根据事件队列得状态所决定。

所以换句话说,程序分成了很多小块,在事件循环中一个一个执行,严格来说和你程序不直接相关得其他事件也可能插入到队列中。

考虑异步出现得问题

var a=1;
var b=2;
function foo(){
    a++;
    b=b*a;
    a=b+3;
}
function bar(){
    b--;
    a=8+b;
    b=a*2;
}
//ajax某个库提供请求
ajax('http://some.url.1',foo);
ajax('http://some.url.2',bar);

同一段代码有两个可能输出意味着还是存在不确定性。
在JavaScript得特性中,这种函数顺序得不确定性就是通常所说得竞态条件(race condition),foo()和bar()相互竞争,看谁先运行,具体来说就是,因为无法可靠预测a和b得最终结果,所以才是竞态条件。

通过异步事件循环可以解决以下问题,考虑

var res=[];
//从ajax取得记录结果
function response(data){
    res = res.concat(data.map(function(val){
        return val*2;
    }))
}
//ajax某个库提供请求
ajax('http://some.url.1',response);
ajax('http://some.url.2',response);

如果返回数据记录几千条或更少,这不算什么,但是假如有1000万条,就可能需要运行相当一段时间了(移动设备需要时间更长,等等)。
这样代码运行时,会阻塞其他操作,界面上所有其他代码都不能运行调用或者ui刷新(类似卡死)。
这里有个比较简单解决方案

var res=[];
function response(data){
    var chunk = data.splice(0,1000);
    res = res.concat(chunk.map((val)=>{
        return val*2;
    }));
    if(data.length>0){
        setTimeout(function(){
            response(data);
        },0)
    }
}

这样进行拆分多个异步任务形式,不阻塞JavaScript引擎来提高站点响应性能。
当然,我们没有协调这些'进程'的顺序,所以结果的顺序是不可预测的。

任务

在es6中,有一个新的概念建立在事件循环队列之上,叫做任务队列(job queue),这个概念给大家带来最大影响可能是Promise的异步特性。

从概念上描述应该是: 它是挂在事件循环队列的每个tick之后的一个队列,在事件循环的每个tick中,可能出现的异步动作(例如Promise)不会导致一个完整的新事件添加到事件循环队列中,而会在当前tick的任务队列末尾添加一个项目(一个任务)。
这就像是在说:这里还有一件事将来要做,但要确保在其他任何事情发生之前就完成它(类似插队,插入到了当前tick 的任务队列)。

一个任务可能引起更多的任务被添加到同一个队列末尾。所以理论上来说,任务循环(job loop)可能无限循环(一个任务总是添加另一个任务,以此类推),进而导致程序没有足够资源,无法转移到下一个事件循环tick。

设想一个调度任务(不要hack)的api,称为schedule(...)

(//当前的tick
    console.log('a');
    setTimeout(function(){console.log('b')},0);//回调 添加到事件循环tick
    schedule(function(){//添加到当前tick的任务队列
        console.log('c');
        schedule(function(){//上面任务导致这个添加到当前tick的任务队列,也就是说一个任务总时添加另一个任务
            console.log('d');
        })
    })
)

实际打印结果 a c d b,因为任务处理是在当前事件循环tick结尾处,且定时器触发是为了是为了调度下一个事件循环tick(如果可用的话!)

Promise的异步特性就是基于任务的。

小结:一旦有事件需要运行,事件循环就会运行,知道队列清空,事件循环每一轮称为一个tick,用户交互,io和定时器会向事件队列添加事件。
任意时刻,一次只能从队列处理一个事件,执行事件的时候,可能直接间接引发一个或多个后续事件。

多个事件交替执行,要确保执行顺序防止竞态出现。

1.回调

考虑

listen('click',function(){
    setTimeout(function request(){
        ajax('http://some.url.1',function request(text){
            if(text === 'hello'){
                handler();
            }else if(text === 'world'){
                request();
            }
        })
    },500)
})

这里三个异步操作形成的链,这种代码通常被称为回调地狱,在线性顺序追踪这段代码时,不得不从一个函数跳到下一个,再跳到下一个,在整个代码中跳来跳去以查看流程。而且这还是简化的形式,真实的异步javascript程序代码要混乱的多,这使得这种追踪的难度会成倍的增加。

信任问题

例如使用一个第三方库,传入回调函数

analytics.trackPurchase(purchaseData,function(){
    chargeCreditCard();
})

我们把程序一部分执行权交给某个第三方,这被称为控制反转

例如上面代码:假如这个库的维护者误传了代码,导致回调执行多次,这就是极严重的bug。

这种 把执行权交给第三方库会产生种种有可能发生的问题:

1.调用回调过早。
2.调用回调过晚(或没有调用)。
3.调用次数过多或过少。
4.没有把所需环境/或参数成功传给你
5.吞掉可能出现的错误或者异常
...
这感觉就像是一个麻烦列表,所以我们可以逐渐意识到,对于被传给我们无法信任工具库的每个回调,我们都将不得不创建大量的混乱逻辑来兼容。

我们可以发明一些特定逻辑来解决这些信任问题,比如:
1.分离回调,一个成功,一个错误。
2.node风格,回调第一个参数保留错误对象(如果有的话),成功的话,这个参数就会被置空。
但是其难度高于应有的水平,可能会产生更笨重,更难维护的代码,并且缺少足够的保护,其中的损害直到收到bug的影响才会发现。

我们需要一个通用解决方案,不管我们创造多少回调,这一方案都可以复用,且没有重复代码的开销。

Promise

回调是把控制权交给第三方,接着期待其能够调用回调,实现正确功能(控制反转)。
但是假如我们能够把控制反转再反转回来,是不是就可以解决这个问题了,如果我们不把回调提供给第三方,而是希望第三方给我们提供了解其任务何时结束的能力,然后由我们自己代码来决定下一步做什么,那会怎么呢,这种范式就被称为Promise

未来值

假如我们向第三方发送一个请求,通常我不能立刻拿到结果而是第三方给返回了一个 标识(promise),保证最终我会得到我的结果。
这是一个未来值,换句话说一旦我需要的结果准备好了,我就用我的标识换取这个结果。
但是还有另一种结果,执行失败了。
这也可以看到未来值一个重要特性:可能成功,可能失败。

现在值和将来值
同步异步行为(Zalgo)

var x,y=2;
ajax('...',function(res){
    x=res;
})
console.log(x+y)//NaN

y是现在值 x是将来值,通过回调方式代码会异常丑陋,Promise中为了统一处理现在和将来,我们把他都变成了将来,即所有操作都是异步的了。

Promise.all([Promise.resolve(y),fetch('...')]).then(function(values){
    console.log(values[0]+value[1]);
})

向我们之前说的可能会有拒绝,完成值总时编程给出的,而拒绝值,通常被称为拒绝原因(reject),可能是程序逻辑设置的,也可能是从运行异常隐式得出的值。

//new时传入函数是立即执行得
new Promise(function(resolve,reject){...}).then(function(res){//完成处理函数

},function(err){//拒绝处理函数

})

从外部看,由于promise封装了依赖时间的状态——等待底层值得完成或拒绝,所以promise本身和时间是无关得。因此promise可与i按照可预测得方式组合,而不用关心时序。
另外,一旦promise决议,他就永远保持这个状态,此时它就成了不变值(immutable value),可以根据需求多次查看。
promise决议后就是外部不可变得值,我们可以安全得把这个值传递给第三方,并确信它不会被有意无意修改,特别是对于多方查看同一个promise决议得情况,这是promise设计最基础和最重要得因素,我们不应该随意忽略这一点。

调用过早

这个问题主要就是担心代码是否会引入类似Zalgo这样副作用,在这类问题中,一个任务有时同步完成,有时异步完成,这可能会导致竞态条件。
根据定义,Promise不必担心这种问题,因为即使是立刻完成得promise(类似new Promise(function(resolve){resolve(42)}))也无法被同步观察到。
也就是说,对于一个promise调用then时,即使这个promise已经决议,提供给then得回调也总是会被异步调用。
不需要插入自己得setTimeout,promise会自动防止Zalgo出现。

调用过晚

promise创建对象调用resolve()或reject()时,这个promise得then注册得观察回调就会被自动调度,可以确信,这些被调度得回调再下一个异步事件点上一定会被触发。
同步查看时不可能得,所以一个同步任务链无法以这种方式运行来实现按照预期有效延迟另一个回调得发生。也就是说,一个promise决议后,这个promise上有所通过then注册得回到都会再下一异步时机点上依次被调用,这些回调中任意一个都无法延迟或延误对其他回调得调用。
例如

p.then(function(){
    p.then(function(){
        console.log('c')
    })
    console.log('a')
})
p.then(function(){
    console.log('b')
})
//abc

这里,c无法打断或抢占b,这是因为promise得运作方式。(所有都是异步)

promise调度技巧
有的时候不同调用方式,会有很多调度得细微差别。

var p3=new Promise(function(resolve,reject){
    resolve('b')
})
var p1=new Promise(function(resolve,reject){
    resolve(p3)
})
var p2 =new Promise(function(resolve,reject){
    resolve('a')
})
p1.then(function(v){
    console.log(v)
})
p2.then(function(v){
    console.log(v)
})
//ab

p1不是用立即值而是用另一个promise p3决议,后者本身决议值是b,规定得行为是把p3展开到p1,但是是异步的展开,所以,在异步任务中,p1得回调排在p2得回调之后。

回调未调用

首先,没有任何东西(包括javascript错误)能阻止promise向你通知它的决议(如果它决议了),如果你对promise注册一个完成回调,一个拒绝回调,那么promise决议时总会调用其中一个。
但是如果promise本身永远不会决议呢》即使这样,promise也提供了解决方案,其使用了竞态的高级抽象机制:

function timeoutPromise(delay){
    return new Promise(function(resolve,reject){
        setTimeout(function(){
            reject('超时了')
        },delay)
    })
}
//foo(),一个promise ,监听它超时
Promise.race([foo(),timeoutPromise(5000)]).then(function(){
    //及时完成
},function(err){
    //foo被拒绝,或者没事按时完成,通过err来查看
})
//顾名思义,Promse.race就是赛跑的意思,意思就是说,Promise.race([p1, p2, p3])里面哪个结果获得的快,就返回那个结果,不管结果本身是成功状态还是失败状态。

调用过多或者过少

根据定义,回调被调用正确次数应该是1,过少是0,和未被调用是一种情况。
过多很容易解释,promise的定义方式使得它只能被决议一次,如果出于某种原因,promise创建代码试图调用resolve或reject多次,或者试图两者都调用,那么这个promise将会只接受第一次决议,并默默忽略任何后续调用。

由于promise只能被决议一次,所以任何通过then注册的(每个)回调就只会被调用一次。
当然如果你把回调注册了不止一次(比如p.then(f);p.then(f)),那么它被调用次数就会和注册次数相同。

未能传递参数/环境值

promise至多只能有一个决议值(完成或拒绝)

如果没有用任何显式值决议(resolve(),reject()),那么这个值就是undefined,但不管这个值是什么,无论当前或者未来,它都会传给所有注册的(完成或拒绝)回调。

还有就是使用多个参数决议(resolve(),reject()),第一个参数之后的所有参数都会默默忽略。这样是对promise机制的无效使用。
如果要传递多个值,就必须把他们封装在单个值中传递,比如通过一个对象或者数组。

是可信任的promise吗

promise并没有完全摆脱回调,它只是改变了传递回调的位置,我们并不是把回调传给第三方库,而是从第三方得到某个东西(外观上看是一个真正的promise(有可能是promise也有可能是鸭子类型thenable )),然后把回调传给这个东西。

thenable可以自行百度了解下

但是这怎么就能确定比回调更加值得信任呢,如果确定返回的这个东西就是一个promise呢,这难道不是一个(脆弱的)纸牌屋,在里面只能信任我们已经信任的?

关于promise的很重要但是常常被忽略的一个细节是,promise对这个问题已经有一个解决方案,包含在原生es6 promise实现中解决方案就是Promise.resolve(...)。

如果向Promise.resolve(...)传递一个非promise,非thenable的立即值,就会得到一个用这个值填充的promsie。

如果向Promise.resolve(...)传递一个真正的promise,就只会返回一个promise。

如果向Promise.resolve(...)传递了一个非promise的thenable值,前者就会试图展开这个值,而且展开过程会持续到提取出一个具体的非类promise的最终值。

从Promsie.resolve(...)得到的是一个真正的promise,是一个可以信任的值(返回的总是一个promise),如果传入的已经是真正的promise,那么你得到就是它本身,所以通过Promsie.resolve(...)过滤来获取可信任性完全没有坏处。

假设我们要调用一个工具foo(),且不确定得到的返回值是否是一个可信任的行为良好的promise,但我们可以知道它至少是一个thenable,那么:

//不要只是这么做
foo(42).then(function(v){
    console.log(v)
})

//而是如下
Promoise.resolve(foo(42)).then(function(v){
    console.log(v)
})

对于用Promise.resolve(...)为所有函数的返回值(不管是不是thenable)都封装一层,另一个好处是,这样很容易把函数调用规范为定义良好的异步任务,如果foo(42)有时返回是一个立即值(不是异步调用),有时返回promise,那么Promise.resolve(foo(42))就能保证总会返回一个promise结果,而且可以避免的Zalgo就能得到更好的代码。

链式流

每次对Promose调用then(...),它都会返回一个新的promise,我们可以将其链接起来;
不管从then(...)调用的完成回调(第一个参数)返回的值是什么,他都会自动设置为被链接promise的完成。

例如

var p = Promise.resolve(21);
var p2 = p.then(function(v){
    return v*2;
})
p2.then(function(v){
    console.log(v)//42
})

使用return会立即完成链接的promise,如果不想立刻完成链接可以返回promise对象。

术语:决议,完成以及拒绝

决议(resolve) 完成(fulfill) 拒绝(reject)
new Prmose(function(resolve,reject){}) 使用到了resolve,reject
命名从技术来说,这无关紧要,但是从团体开发来说,不要使用有可能产生歧义的命名。
拒绝 很容易决定,几乎所有文献都命名为reject;
第一个参数为什么叫决议(resolve)不叫fulfill,因为resolve有可能返回一个错误reject出来,例如:resolve(Promise.reject('错误'))

reject不会像resolve一样进行展开,如果向reject传入一个promsie值,它会把这个值原封不动设置为拒绝理由,往后传递,而不是底层的立即值。

错误处理

错误处理最自然的方式自然是try catch,但是它只能是同步的,无法用于异步。(后期讲如何使用try catch 变相监听异步)

为了避免丢失和抛弃的promise错误,有一部分开发同学认为promise链的最后总以一个catch结束,例如:

var p = Promsie.resolve(42);
p.then(function(v){
    //会报错
    console.log(v.toLowerCase)
}).catch(handleErrors)

但是会有一个问题,假如handleErrors内部也有错误,那谁来捕获它。
所以说:Promise 对象的回调链,不管以then方法或catch方法结尾,要是最后一个方法抛出错误,都有可能无法捕捉到(因为 Promise内部的错误不会冒泡到全局)。因此,我们可以提供一个done方法,总是处于回调链的尾端,保证抛出任何可能出现的错误。

 Promise.prototype.done = function (onFulfilled, onRejected) {
    this
      .then(onFulfilled, onRejected)
      .catch(function (reason) {
        // 抛出一个全局错误
        setTimeout(() => {
          throw reason
        }, 0) 
      })
  }

promise常用api

Promise.all([..]):需要一个数组参数,由promise实例组成,等待数组里的promise、全部决议才会then,一旦有一个拒绝主promise.all会立即拒绝,并丢弃其他所有promise结果,then回调参数是一个数组,对应all数组里决议的消息列表。

Promise.race([..]):竞态,Promse.race就是赛跑的意思,意思就是说,Promise.race([p1, p2, p3])里面哪个结果获得的快,就返回那个结果,不管结果本身是成功状态还是失败状态。(永远不要传递空数组,不然永远不会决议),和all一样一旦有一个拒绝,race就会拒绝。

none([..]):类似all。不过完成和拒绝的情况互换了。

any([..]):类似all。但是会忽略拒绝,所以只需完成一个而不是全部。

first([..]) last([..])

如何把需要回调的函数封装为支持promise的函数:

if(!Promise.wrap){
    Promise.wrap=function(fn){
        return function(){
            var args = [].slice.call(arguments);
            return new Promsie(function(resolve,reject){
                fn.apply(null,args.concat(function(err,v){//回调
                    if(err){
                        reject(err)
                    }else{
                        resolve(v)
                    }             
                }))
            })
        }
    }
}

var request = Promise.wrap(ajax);
request('http://....').then(..)

wrap 一个promise的工厂

无法取消的promise,只能设置超时,但是很简陋,推荐查看promise抽象库,例如asynquence abort();
单独的promise不应该被取消,但是取消一个序列是合理的(promsie链),因为不会像对待promise那样把序列作为一个单独的不变值来传送。

javaScript之异步发展史二(generator,async)

查看原文

赞 0 收藏 0 评论 0

Charon 发布了文章 · 9月29日

javascript之排序及搜索和去重算法

排序算法

记录一些常见的简单的算法

  1. 冒泡排序,最简单的算法,从运行时间角度看,性能最差一个,比较相邻项,交换位置O(n2)
 function swap(array, i, j) {
      [array[j], array[i]] = [array[i], array[j]]
 }

 const Compare = {
       LESS_THAN: -1,
       BIGGER_THAN: 1,
       EQUAL_THAN: 0
 }
function defaultCompareFn(a, b) {
       if (a === b) {
            return Compare.EQUAL_THAN;
       }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
function modifiedBuddleSort(array,compareFn = defaultCompareFn){
    const {length} =array;
    for(let i=0;i<length;i++){
        for(let j =0;j<length-1-i;j++){
            if(compareFn(array[j],array[j+1])===Compare.BIGGER_THAN){
                swap(array,j,j+1)
            }
        }
    }
    return array;
}

2.选择排序,原址排序,找到最小值放第一位,第二小放第二位,以此类推O(n2)

function selectionSort(array,compareFn = defaultCompareFn){
    const {length} =array;
    let indexMin;
    for(let i=0;i<length-1;i++){
        indexMin =i;
        for(let j=i;j<length;j++){
            if(compareFn(array[indexMin],array[j])===Compare.BIGGER_THAN){
                indexMin = j;
            }
        }
        if(i!==indexMin){
            swap(array,i,indexMin);
        }
    }
    return array;
}

3.插入排序,每次排一个数组项,以此构建最后排序数组,假定第一项已经排序过,接着和第二项进行比较-,看第二项是否要插入第一项之前,接着和第三项比较,看需要查到哪,以此类推/排序小型数组,这个比选择和冒泡性能好。

function insertionSort(array, compareFn = defaultCompareFn){
    const {length}=array;
    let temp;
    for(let i=1;i<length;i++){
        let j =i;
        temp = array[i];
        while(j>0&&compareFn(array[j-1],temp)=== Compare.BIGGER_THAN){
            array[j] = array[j-1];
            j--;
        }
        array[j] = temp;
    }
    return array;
}

4.计数排序,(整数排序算法),一个数组计算,数字出现过的次数

 function countingSort(array) {

     if (array.length < 2) {

        return array;

     }

     const maxValue = findMaxValue(array);

     const counts = new Array(maxValue + 1);

     array.forEach(element => {

         console.log(element)

         if (!counts[element]) {

         counts[element] = 0;

         }

         counts[element]++;

     });

    console.log(counts)

    let sortedIndex = 0;

     counts.forEach((count, i) => {

         while (count > 0) {

             array[sortedIndex++] = i;

             count--;

         }

     })

    return array;

 }

 function findMaxValue(array) {

     let max = array[0];

     for (let i = 1; i < array.length; i++) {

         if (max < array[i]) {

            max = array[i];

         }

     }
     return max;
 }

5.归并排序加去重,O(nlog(n)),分而治之算法,将原始数组切分成较小的数组,直到每个小数组只有一个位置,然后再将小的合并成较大数组,直到最后一个排序完毕的大数组。
分治法,递归实现。

function mergeSort(array,compareFn = defaultCompareFn){
    if(array.length>1){
        const {length} = array;
        const middle = Math.floor(length/2);
        const left = mergeSort(array.slice(0,middle),compareFn);//划分
        const right = mergeSort(array.slice(middle),compareFn);//划分
        array = merge(left,right,compareFn)//合并 治
    }
    return array;
}

function merge(left,right,compareFn){
    const res = [];
    while(left.length>0&&right.length>0){
        if(compareFn(left[0],right[0])===Compare.LESS_THAN){
            res.push(left.shift())
        }else if(compareFn(left[0], right[0]) === Compare.EQUAL_THAN){
            left.shift();
        }else{
            res.push(right.shift())
        }
    }
    return res.concat(left).concat(right);
}

6.快排也许是最常用得排序算法,O(nlog(n)),性能通常比其他复杂度为O(nlog(n))算法要好,和归并一样,也是分而治之得算法思想。

  1. 首先选出一个值作为主元(pivot),默认就用数组中间那个值。
  2. 创建两个指针引用,左边指向数组第一个,右边指向数组最后一个,移动左指针,直到找到比主元大得值,然后移动右指针找到比主元小得值,然后交换它们位置,重复这个过程,直到左指针超过了右指针,这个过程会把比主元小的值都放在左边(主元之前),比主元大的值放在右边(主元之后),这一步叫做划分操作。
  3. 接着,算法对划分得小数组(较主元小得值组成的子数组,以及较主元大得值组成得子数组)重复之前得两个步骤,直至数组已完全排序。

原址快排如下

function quickSort(array,compareFn = defaultCompareFn){
    return quick(array, 0, array.length, compareFn);//左 右起点
}
function quick(array, left, right, compareFn){
    let index;
    if(array.length>1){
        index = partition(array, left, right, compareFn);//排序,交换位置   划分过程
        if(left<index-1){//找出相对主元较小得 组项
            quick(array, left, index - 1, compareFn);//对较小组继续划分,交换位置 继续分而治之得过程
        }
        if(index<right){//找出相对主元较大 得组项
             quick(array, index, right, compareFn);//同上  对较大组划分
        }
    }
    return array;
}
function partition(array, left, right, compareFn){
    let pivot = array[Math.floor((left+right)/2)];//取中间当作主元
    let i =left;
    let j =right;
    while(i<=j){
        while (compareFn(array[i], pivot) === Compare.LESS_THAN) {//找到比主元大或相等得
            i++;
        }
         while (compareFn(array[j], pivot) === Compare.BIGGER_THAN) {//找到比主小或相等得
            j--;
        }
        if(i<=j){
             swap(array, i, j);
             i++;//交换完位置之后,都对应加一减一,继续走查找
             j--;
        }
    }
    return i;
}

补充一个去重算法

 function mapClearArr(arr) {

     let map = new Map();

     let newArr = [];

     const { length } = arr;

     for (let i = 0; i < length; i++) {

         let current = arr[i];

         if (map.get(current) == null) {

            map.set(arr[i], 1);

            newArr.push(current);

         }

     }

     return newArr;

 }

下面介绍几种搜索算法
1.顺序搜索,顺序或线性是最基本得算法,机制是,将每一个数据结构中得元素和我蛮要找得元素作比较,顺序搜索是最低效得一种算法。

const DOES_NOT_EXIST=-1;
function sequentialSearch(array,value,equalsFn=defaultEquals){
    for(let i=0;i<array.length;i++){
        if(equalsFn(value,array[i])){
            return i;
        }
    }
    return DOES_NOT_EXIST;
}

2.二分搜索,类似数字游戏,想一个数字,我们每回应一个数,那个人都会回应我们是高了还是低了,对了。
这个算法要求数组已排序。


function lesserOrEquals(a,b,compareFn){
    const comp = compareFn(a,b);
    return comp===Compare.LESS_THAN||comp===Compare,EQUALS;
}
function binarySearch(array,value,compareFn=defaultCompare){
    const scrtedArray = quickSort(array);
    let low =0;
    let high = arr.length-1;
    while(lesserOrEquals(low,high,compareFn)){
    //左右未重叠
        const mid = Math.floor((low+high)/2);
        const element = scrtedArray[mid];
        if(compareFn(element,value)===Compare.LESS_THAN){
            low = mid+1;
        }else if(compareFn(element,value)===Compare.BIGGER_THAN){
            high = mid-1;
        }else{
            return mid;
        }
    }
    return DOES_NOT_EXIST;
}

分而治之得版本

function binarySerchRecursive(array,value,low,high,compareFn=defaultCanpare){
    if(low<high){
        const mid = Math.floor((low+high)/2);
        const element = array[mid];
        if(compareFn(element,value)===Compare.LESS_THAN){
            return binarySerchRecursive(array,value,mid+1,high,compareFn)
        }else if(compareFn(elemetn,value)===Compare.BIGGER_THAN){
            return binarySerchRecursive(array,value,low,mid-1,compareFn);
        }else{
            return mid;
        }
    }
    return DOES_NOT_EXIST;
}
function binarySeach(array,value,compareFn=defaultCompare){
    const sortedArrar=quickSort(array);
    const low = 0;
    const high = arr.length-1;
    return binarySerchRecursive(array,value,low,high,compareFn)
}

https://ruphi.cn/archives/154/
内插算法和二分算法区别

查看原文

赞 0 收藏 0 评论 0

Charon 赞了文章 · 9月15日

immer.js 实战讲解文档

文章在 github 开源, 欢迎 Fork 、Star

前言

Immer 是 mobx 的作者写的一个 immutable 库,核心实现是利用 ES6 的 proxy,几乎以最小的成本实现了 js 的不可变数据结构,简单易用、体量小巧、设计巧妙,满足了我们对JS不可变数据结构的需求。
无奈网络上完善的文档实在太少,所以自己写了一份,本篇文章以贴近实战的思路和流程,对 Immer 进行了全面的讲解。

数据处理存在的问题

先定义一个初始对象,供后面例子使用:
首先定义一个currentState对象,后面的例子使用到变量currentState时,如无特殊声明,都是指这个currentState对象

let currentState = {
  p: {
    x: [2],
  },
}

哪些情况会一不小心修改原始对象?

// Q1
let o1 = currentState;
o1.p = 1; // currentState 被修改了
o1.p.x = 1; // currentState 被修改了

// Q2
fn(currentState); // currentState 被修改了
function fn(o) {
  o.p1 = 1;
  return o;
};

// Q3
let o3 = {
  ...currentState
};
o3.p.x = 1; // currentState 被修改了

// Q4
let o4 = currentState;
o4.p.x.push(1); // currentState 被修改了

解决引用类型对象被修改的办法

  1. 深度拷贝,但是深拷贝的成本较高,会影响性能;
  2. ImmutableJS,非常棒的一个不可变数据结构的库,可以解决上面的问题,But,跟 Immer 比起来,ImmutableJS 有两个较大的不足:

    • 需要使用者学习它的数据结构操作方式,没有 Immer 提供的使用原生对象的操作方式简单、易用;
    • 它的操作结果需要通过toJS方法才能得到原生对象,这使得在操作一个对象的时候,时刻要注意操作的是原生对象还是 ImmutableJS 的返回结果,稍不注意,就会产生意想不到的 bug。

看来目前已知的解决方案,我们都不甚满意,那么 Immer 又有什么高明之处呢?

immer功能介绍

安装immer

欲善其事必先利其器,安装 Immer 是当前第一要务

npm i --save immer

immer如何fix掉那些不爽的问题

Fix Q1、Q3

import produce from 'immer';
let o1 = produce(currentState, draft => {
  draft.p.x = 1;
})

Fix Q2

import produce from 'immer';
fn(currentState);
function fn(o) {
  return produce(o, draft => {
    draft.p1 = 1;
  })
};

Fix Q4

import produce from 'immer';
let o4 = produce(currentState, draft => {
  draft.p.x.push(1);
})

是不是使用非常简单,通过小试牛刀,我们简单的了解了 Immer ,下面将对 Immer 的常用 api 分别进行介绍。

概念说明

Immer 涉及概念不多,在此将涉及到的概念先行罗列出来,阅读本文章过程中遇到不明白的概念,可以随时来此处查阅。

  • currentState
    被操作对象的最初状态
  • draftState
    根据 currentState 生成的草稿状态,它是 currentState 的代理,对 draftState 所做的任何修改都将被记录并用于生成 nextState 。在此过程中,currentState 将不受影响
  • nextState
    根据 draftState 生成的最终状态
  • produce 生产
    用来生成 nextState 或 producer 的函数
  • producer 生产者
    通过 produce 生成,用来生产 nextState ,每次执行相同的操作
  • recipe 生产机器
    用来操作 draftState 的函数

常用api介绍

使用 Immer 前,请确认将immer包引入到模块中

import produce from 'immer'

or

import { produce } from 'immer'

这两种引用方式,produce 是完全相同的

produce

备注:出现PatchListener先行跳过,后面章节会做介绍

第1种使用方式:

语法:
produce(currentState, recipe: (draftState) => void | draftState, ?PatchListener): nextState

例子1:

let nextState = produce(currentState, (draft) => {

})

currentState === nextState; // true

例子2:

let currentState = {
  a: [],
  p: {
    x: 1
  }
}

let nextState = produce(currentState, (draft) => {
  draft.a.push(2);
})

currentState.a === nextState.a; // false
currentState.p === nextState.p; // true

由此可见,对 draftState 的修改都会反应到 nextState 上,而 Immer 使用的结构是共享的,nextState 在结构上又与 currentState 共享未修改的部分,共享效果如图(借用的一篇 Immutable 文章中的动图,侵删):

图片描述

自动冻结功能

Immer 还在内部做了一件很巧妙的事情,那就是通过 produce 生成的 nextState 是被冻结(freeze)的,(Immer 内部使用Object.freeze方法,只冻结 nextState 跟 currentState 相比修改的部分),这样,当直接修改 nextState 时,将会报错。
这使得 nextState 成为了真正的不可变数据。

例子:

let nextState = produce(currentState, (draft) => {
  draft.p.x.push(2);
})

currentState === nextState; // true
第2种使用方式

利用高阶函数的特点,提前生成一个生产者 producer

语法:
produce(recipe: (draftState) => void | draftState, ?PatchListener)(currentState): nextState

例子:

let producer = produce((draft) => {
  draft.x = 2
});
let nextState = producer(currentState);
recipe的返回值

recipe 是否有返回值,nextState 的生成过程是不同的:
recipe 没有返回值时:nextState 是根据 recipe 函数内的 draftState 生成的;
recipe 有返回值时:nextState 是根据 recipe 函数的返回值生成的;

let nextState = produce(
  currentState, 
  (draftState) => {
    return {
      x: 2
    }
  }
)

此时,nextState 不再是通过 draftState 生成的了,而是通过 recipe 的返回值生成的。

recipe中的this

recipe 函数内部的this指向 draftState ,也就是修改this与修改 recipe 的参数 draftState ,效果是一样的。
注意:此处的 recipe 函数不能是箭头函数,如果是箭头函数,this就无法指向 draftState 了

produce(currentState, function(draft){
  // 此处,this 指向 draftState
  draft === this; // true
})

patch补丁功能

通过此功能,可以方便进行详细的代码调试和跟踪,可以知道 recipe 内的做的每次修改,还可以实现时间旅行。

Immer 中,一个 patch 对象是这样的:

interface Patch {
  op: "replace" | "remove" | "add" // 一次更改的动作类型
  path: (string | number)[] // 此属性指从树根到被更改树杈的路径
  value?: any // op为 replace、add 时,才有此属性,表示新的赋值
}

语法:

produce(
  currentState, 
  recipe,
  // 通过 patchListener 函数,暴露正向和反向的补丁数组
  patchListener: (patches: Patch[], inversePatches: Patch[]) => void
)

applyPatches(currentState, changes: (patches | inversePatches)[]): nextState

例子:

import produce, { applyPatches } from "immer"

let state = {
  x: 1
}

let replaces = [];
let inverseReplaces = [];

state = produce(
  state,
  draft => {
    draft.x = 2;
    draft.y = 2;
  },
  (patches, inversePatches) => {
    replaces = patches.filter(patch => patch.op === 'replace');
    inverseReplaces = inversePatches.filter(patch => patch.op === 'replace');
  }
)

state = produce(state, draft => {
  draft.x = 3;
})
console.log('state1', state); // { x: 3, y: 2 }

state = applyPatches(state, replaces);
console.log('state2', state); // { x: 2, y: 2 }

state = produce(state, draft => {
  draft.x = 4;
})
console.log('state3', state); // { x: 4, y: 2 }

state = applyPatches(state, inverseReplaces);
console.log('state4', state); // { x: 1, y: 2 }

state.x的值4次打印结果分别是:3、2、4、1,实现了时间旅行,
可以分别打印patchesinversePatches看下,

patches数据如下:

[
  {
    op: "replace",
    path: ["x"],
    value: 2
  },
  {
    op: "add",
    path: ["y"],
    value: 2
  },
]

inversePatches数据如下:

[
  {
    op: "replace",
    path: ["x"],
    value: 1
  },
  {
    op: "remove",
    path: ["y"],
  },
]

可见,patchListener内部对数据操作做了记录,并分别存储为正向操作记录和反向操作记录,供我们使用。

至此,Immer 的常用功能和 api 我们就介绍完了。

接下来,我们看如何用 Immer ,提高 React 、Redux 项目的开发效率。

用immer优化react项目的探索

首先定义一个state对象,后面的例子使用到变量state或访问this.state时,如无特殊声明,都是指这个state对象

state = {
  members: [
    {
      name: 'ronffy',
      age: 30
    }
  ]
}

抛出需求

就上面定义的state,我们先抛一个需求出来,好让后面的讲解有的放矢:
members 成员中的第1个成员,年龄增加1岁

优化setState方法

错误示例

this.state.members[0].age++;

只所以有的新手同学会犯这样的错误,很大原因是这样操作实在是太方便了,以至于忘记了操作 State 的规则。

下面看下正确的实现方法

setState的第1种实现方法

const { members } = this.state;
this.setState({
  members: [
    {
      ...members[0],
      age: members[0].age + 1,
    },
    ...members.slice(1),
  ]
})

setState的第2种实现方法

this.setState(state => {
  const { members } = state;
  return {
    members: [
      {
        ...members[0],
        age: members[0].age + 1,
      },
      ...members.slice(1)
    ]
  }
})

以上2种实现方式,就是setState的两种使用方法,相比大家都不陌生了,所以就不过多说明了,接下来看下,如果用 Immer 解决,会有怎样的烟火?

用immer更新state

this.setState(produce(draft => {
  draft.members[0].age++;
}))

是不是瞬间代码量就少了很多,阅读起来舒服了很多,而且更易于阅读了。

优化reducer

immer的produce的拓展用法

在开始正式探索之前,我们先来看下 produce 第2种使用方式的拓展用法:

例子:

let obj = {};

let producer = produce((draft, arg) => {
  obj === arg; // true
});
let nextState = producer(currentState, obj);

相比 produce 第2种使用方式的例子,多定义了一个obj对象,并将其作为 producer 方法的第2个参数传了进去;可以看到, produce 内的 recipe 回调函数的第2个参数与obj对象是指向同一块内存。
ok,我们在知道了 produce 的这种拓展用法后,看看能够在 Redux 中发挥什么功效?

普通reducer怎样解决上面抛出的需求

const reducer = (state, action) => {
  switch (action.type) {
    case 'ADD_AGE':
      const { members } = state;
      return {
        ...state,
        members: [
          {
            ...members[0],
            age: members[0].age + 1,
          },
          ...members.slice(1),
        ]
      }
    default:
      return state
  }
}

集合immer,reducer可以怎样写

const reducer = (state, action) => produce(state, draft => {
  switch (action.type) {
    case 'ADD_AGE':
      draft.members[0].age++;
  }
})

可以看到,通过 produce ,我们的代码量已经精简了很多;
不过仔细观察不难发现,利用 produce 能够先制造出 producer 的特点,代码还能更优雅:

const reducer = produce((draft, action) => {
  switch (action.type) {
    case 'ADD_AGE':
      draft.members[0].age++;
  }
})

好了,至此,Immer 优化 reducer 的方法也讲解完毕。

Immer 的使用非常灵活,多多思考,相信你还可以发现 Immer 更多其他的妙用!

参考文档

查看原文

赞 36 收藏 21 评论 5

Charon 发布了文章 · 9月13日

javascript数据结构之树(二叉搜索树,平衡二叉树,红黑树)

一种非顺序数据结构--树。

树是一种分层数据的抽象模型,一个树结构包含一系列存在父子关系的节点,每个节点都有一个父节点(除了顶部第一个节点)以及零个或多个子节点,位于树顶部的节点叫根节点。

二叉树和二叉搜索树

二叉树中的节点最多只能有两个节点,一个左侧的节点,一个右侧节点。
二叉搜索树(BST)是二叉树的一种,但是只允许在左侧储存比父节点小的数据,在右侧储存比父节点大的数据。
image

和链表一样,通过引用来表示节点之间的关系,在双向链表里,每个节点有俩引用,一个指向上一个节点,一个指向下一个节点,对于二叉搜索树也使用同样方式,不同的地方是一个指向左侧节点,一个指向右侧节点(树中会称节点为键)。

  1. insert(key) 树里插入键
  2. search(key) 树里查找一个键
  3. inOrderTraverse() 中序遍历所有(上行顺序遍历,先左,自身,右)
  4. preOrderTraverse() 先序遍历所有(先自身,左,右)
  5. postOrderTraverse() 后序遍历所有(先左,右,自身)
  6. min() 获取树最小值
  7. max() 获取树最大值
  8. remove(key) 删除树里某个键

中序,先序,后序,都是递归实现,描述可能不太具体,具体还是看代码把。

const Compare = {
    LESS_THAN:-1,
    BIGGER_THAN:1
}
function defaultCompare(a,b){
    if(a===b){
        return 0;
    }
    return a<b?Compare.LESS_THAN:Compare.BIGGER_THAN;
}
class Node{
    constructor(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree{
    constructor(compareFn = defaultCompare){
        this.compareFn = compareFn;
        this.root = null;
    }
    insert(key){
        if(!this.root){
            this.root = new Node(key);
        }else{
            this.insertNode(this.root,key);
        }
    }
    insertNode(node,key){//查找对比键大小插入,最后生成结构如上图
        if(this.compareFn(key,node.key)===Compare.LESS_THAN){
            if(!node.left){
                node.left = new Node(key);
            }else{
                this.insertNode(node.left,key);
            }
        } else {
            if(!node.right){
                node.right = new Node(key);
            }else{
                this.insertNode(node.right,key);
            }
        }
    }
    search(key){
        return this.searachNode(this.root,key);
    }
    searachNode(node,key){
        if(!node){
            return false;
        }
        if(this.compareFn(key,node.key)===Compare.LESS_THAN){
            return this.searachNode(node.left,key);
        }else if(this.compareFn(key,node.key)===Compare.BIGGER_THAN){
            return this.searachNode(node.right,key);
        }else{
            return true;//可以根据自己需要返回
        }
    }
    min(){
        return this.minNode(this.root);
    }
    minNode(node){
       let current = node;
       while(current&&current.left){
            current = current.left;
       }
       return current;
    }
    max(){
        return this.maxNode(this.root);
    }
    maxNode(node){
       let current = node;
       while(current&&current.right){
            current = current.right;
       }
       return current;
    }
    remove(key){
        this.root = this.removeNode(this.root,key)
    }
    removeNode(node,key){
        if(!node){
            return null;
        }
        if(this.compareFn(key,node.key)===Compare.LESS_THAN){
        //向左查找
            node.left = this.removeNode(node.left,key);
            return node;
        }else if(this.compareFn(key,node.key)===Compare.BIGGER_THAN){
        //向右查找
            node.right = this.removeNode(node.right,key);
            return node;
        }else{//找到了
            if(!node.left&&!node.right){
                node = null;
                return node;
            }
            if(!node.left){
                node = node.right;
                return node;
            }else if(!node.right){
                node = node.left;
                return node;
            }
            //第三种情况,移除的节点有两个子节点,先找到要移除节点右边子树里最小的节点,然后移到当前删除位置,然后这会会有两个相同的键(当前删除位置===右侧子树最小节点),所以把右侧子树最小节点删掉。
            const aux = this.minNode(node.right);
            node.key = aux.key;
            node.right = this.removeNode(node.right,aux.key);
            return node;
        }
    }
    inOrderTraverse(cb){
        this.inOrderTraverseNode(this.root,cb);
    }
    inOrderTraverseNode(node,cb){
        if(node){
            this.inOrderTraverseNode(node.left,cb);
            cb(node.key);
            this.inOrderTraverseNode(node.right,cb);
        }
    }
    preOrderTraverse(cb){
        this.preOrderTraverseNode(this.root,cb)
    }
    preOrderTraverseNode(node,cb){
        if(node){
            cb(node.key);
            this.preOrderTraverseNode(node.left,cb);
            this.preOrderTraverseNode(node.right,cb);
        }
    }
    postOrderTraverse(cb){
        this.postOrderTraverseNode(this.root,cb);
    }
    postOrderTraverseNode(node,cb){
        if(node){
            this.postOrderTraverseNode(node.left,cb);
            this.postOrderTraverseNode(node.right,cb);
            cb(node.key);
        }
    }
}

const printNode = (value)=>console.log(value);//可以用此做回掉测试

image

image

image

二叉搜索树(BST)存在一个问题,在添加或删除后,可能会某一侧会很深,有的节点可能就几层,有的可能有很多层。

自平衡二叉树(AVL树)

AVL是一颗自平衡树,在添加或者移除节点的时候会尝试保证自平衡,任何一个节点(不论深度),左侧字树和右侧字数最多相差1。

AVL树需要根据节点高度来计算平衡因子,根据平衡因子来判断,是否需要旋转平衡。

计算一个节点高度的方法:getNodeHeight(node)
计算平衡因子方法:getBalanceFactor(node)
平衡因子的概念:对每个节点计算左子树和右子树的高度的差值,该值(left-right)应为0,1,-1,如果结果不是这三个值之一,则需要平衡AVL树。
LL:向右的单旋转
image
RR:向左的单旋转
image
LR:先左后右,先RR转再LL转,这种情况出现于不平衡节点的左侧节点高度大于右侧节点高度,并且左侧节点右侧较重,这种情况可以先对左侧节点进行左旋转修复,然后在对不平衡节点进行右旋转修复。
image
RL:先右后左,先LL转再RR转,这种情况出现于不平衡节点的右侧节点高度大于左侧节点高度,并且右侧节点左侧较重,这种情况可以先对右侧节点进行右旋转修复,然后对不平衡节点进行一个左旋转修修复。
image

const BalanceFactor = {//平衡因子的常量
    UNBALANCED_RIGHT:1,
    SLIGHTLY_UNBALANCED_RIGHT:2,
    BALANCED:3,
    SLTGHTLY_UNBALANCED_LEFT:4,
    UNBALANCED_LEFT:5
}
class AVLTree extends BinarySearchTree{
    constructor(compareFn=defaultCompare){
        super(compareFn);
        this.compareFn=compareFn;
        this.root = null;
    }
    getNodeHeight(node){
        if(!node){
            return -1
        }
        return Math.max(this.getNodeHeight(node.left),
        this.getNodeHeight(node.right))+1
    }
    getBalanceFactor(node){
        const heightDifference = this.getNodeHeight(node.left)-this.getNodeHeight(node.right);
        switch(heightDifference){
            case -2:
            return BalanceFactor.UNBALANCED_RIGHT;
            case -1:
            return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
            case 1:
            return BalanceFactor.SLTGHTLY_UNBALANCED_LEFT;
            case 2:
            return BalanceFactor.UNBALANCED_LEFT;
            default:
            return BalanceFactor.BALANCED;
        }
    }
    rotationLL(node){//右单旋转
       const tmp = node.left;
       node.left = tmp.right;
       tmp.right = node;
       return node;
    }
    rotationRR(node){//左单旋转
        const tmp = node.right;
        node.right = tmp.left;
        tmp.left = node;
        return tmp;
    }
    rotationLR(node){
        node.left = this.rotationRR(node.left);
        return this.rotationLL(node);
    }
    rotationRL(node){
        node.right = this.rotationLL(node.right);
        return this.rotationRR(node);
    }
    insert(key){
        this.root = this.insertNode(this.root,key)
    }
    insertNode(node,key){
        if(!node){
            return new Node(key);
        }else if(this.compareFn(key,node.key)===Compare.LESS_THAN){
        //向左继续
            node.left = this.insertNode(node.left,key);
        }elso if(this.compareFn(key,node.key)===Compare.BIGGER_THAN){
        //向右继续
            node.right = this.insertNode(node.right,key);
        }else{//不比当前key大也不比当前key小,等于当前重复
            return node;//重复的键
        }
        //递归插入完成后,根据函数依次弹栈,来计算当前的节点的平衡因子,查看是否失衡
        const balanceFactor = this.getBalanceFactor(node);
        if(balanceFactor === BalanceFactor.UNBALANCED_LEFT){//等于2,左侧子节点失衡
            if(this.compareFn(key,node.left.key)===Compare.LESS_THAN){//查看插入的节点是插到了当前节点左子节点的下左侧,符合LL,详细可以配上面图看
                node = this.rotationLL(node);
            }else {//右,符合LR
                return this.rotationLR(node);
            }
        }
        if(balanceFactor === BalanceFactor.UNBALANCED_RIGHT){//-2右侧失衡
            if(this.compareFn(key,node.right.key)===Compare.BIGGER_THAN){//查看插入的节点是插到了当前节点右子节点的下右侧,符合RR,详细可以配上面图看
                node = this.rotationRR(node);
            }else{//下左,符合RL
                return this.rotationRL(node);
            }
        }
        return node;
    }
    removeNode(node){
        node = super.removeNode(node,key);
        if(!node){
            return node;
        }
        const balanceFactor = this.getBalanceFactor(node);
        if(balanceFactor === BalanceFactor.UNBALANCED_LEFT){//左子节点失衡
            const balanceFactorLeft = this.getBalanceFactor(node.left);
            //判断左边是那种情况,是进行LL转还是LR转
            if(balanceFactorLeft===BalanceFactor.SLTGHTLY_UNBALANCED_LEFT||balanceFactorLeft.BALANCED){//差值为1或者其他情况的时候进行符合LL
                return this.rotationLL(node);
            }
            if(balanceFactorLeft===BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT){//左侧差值为-1,符合LR
                return this.rotationLR(node);
            }
        }
        if(balanceFactor === BalanceFactor.UNBALANCED_RIGHT){//差值为-2,右侧子节点不平衡
            const balanceFactorRight = this.getBalanceFactor(node.right);
            if(balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT||balanceFactorRight===BalanceFactor.BALANCED){//和左相反,差值-1或其他符合RR
                return return this.rotationRR(node);
            }
            if(balanceFactorRight === BalanceFactor.SLTGHTLY_UNBALANCED_LEFT){//差值为1符合RL
                return this.rotationRL(node);
            }
        }
        return node;
    }
}

红黑树

最先发明的平衡二叉查找树是AVL树(它严格符合平衡二叉查找树的定义,即任何节点的左右子树高度相差不超过 1,是一种高度平衡的二叉查找树。)但是在工程中,我们经常听到的通常是红黑树,而不是AVL树.那么为什么工程中都喜欢用红黑树,而不是其他平衡二叉查找树呢?
其实在这里,我们应该能有一些想法了.既然他严格按照规定执行,每次的插入,删除,都就会引发树的调整.调整的多了,自然会影响树的效率.那么红黑树又是怎样解决这个问题的呐?

其实,平衡二叉查找树中“平衡”的意思,其实就是让整棵树左右看起来比较“对称”、比较“平衡”,不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些,相应的插入、删除、查找等操作的效率高一些。
所以红黑树就是这种设计思路(近似平衡)了.

如果我们需要一个包含多次插入和删除的自平衡树,红黑树是比较好的,如果插入和删除频率较低,更多是进行搜索操作,那么AVL树比红黑树更好。

在红黑树中,每个节点遵循以下规则。

  1. 每个节点不是红的就是黑的。
  2. 树的根节点都是黑的。
  3. 所有叶节点都是黑的([注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!])
  4. 如果一个节点是红的,那么他的两个子节点都是黑的。
  5. 不能有两个相邻的红节点,一个红节点不能有红的父节点或子节点也就是说,红色节点是被黑色节点隔开的
  6. 从给定的节点到他的后代节点(null节点)的所有路径包含相同数量的黑色节点。

image
和AVL树一样,在进行节点的插入和删除时,就会破坏红黑树的一些规则.在红黑树中主要破坏的是以下两点:

  1. 任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;
  2. 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点;

插入

红黑树规定,插入的节点必须是红色的。而且,二叉查找树中新插入的节点都是放在叶子节点上。所以,关于插入操作的平衡调整,有这样两种特殊情况,但是也都非常好处理。
  1. 如果插入节点的父节点是黑色的,那我们什么都不用做,它仍然满足红黑树的定义。
  2. 如果插入的节点是根节点,那我们直接改变它的颜色,把它变成黑色就可以了。
  3. 其他:都会违背红黑树的定义,于是我们就需要进行调整,调整的过程包含两种基础的操作:左右旋转和改变颜色。
const Color = {
    RED:'red',
    BLACK:'black'
}
class RedBlackNode extends Node{
    constructor(key){
        this.key = key;
        this.color = Color.RED;
        this.parent = null;
    }
    isrRed(){
        return this.color === Color.RED;
    }
}
class RedBlackTree extends BinarySearchTree{
    constructor(compareFn = defaultCompare){
        super(compareFn);
        this.compareFn = compareFn;
        this.root = null;
    }
    insert(key){
        if(!this.root){
            this.root = new RedBlackNode(key);
            this.root.color = Colors.BLACK;
        }else{
            const newNode = this.insertNode(this.root,key);
            this.fixTreeProperties(newNode);
        }
    }
    insertNode(node,key){
       if(this.compareFn(key,node.key)===Compare.LESS_THAN){
            if(!node.left){
                node.left = new RedBlackNode(key);
                node.left.parent = node;
                return node.left;
            }else{
                return this.insertNode(node.left,key);
            }
       }else if(this.compareFn(key,node.key)===Compare.BIGGER_THAN){
            if(!node.right){
                node.right = new RedBlackNode(key);
                node.right.parent = node;
                return node.right;
            }else{
                return this.insertNode(node.right,key);
            }
       }else{//相同
            node.key = key; //key万一是复杂对象。
            return node;
       }
       
    }
    fixTreeProperties(node){
        while(node&&node.parent&&node.parent.isRed()&&node.color===!==Color.BLACK){
            let parent = node.parent;
            const grandParent = parent.parent;
            if(grandParent&&grandParent.left===parent){
            //父节点是左侧子节点
                const uncle = grandParent.right;
                if(uncle&&uncle.color === Color.RED){
                //左侧叔父节点是红色,重新填色,隔开颜色
                    grandParent.color = Color.RED;
                    uncle.color = Color.BALCK;
                    parent.color= Color.BALCK;
                    node = grandParent;
                }else{
                    //节点是右侧子节点-左旋转
                    if(node === parent.right){
                        this.rotationRR(parent);
                        node = parent;
                        parent = node.parent;
                    }
                    //节点是左侧子节点-右旋转
                    this.rotationLL(grandParent);
                    parent.color = Color.BLACK;
                    grandParent.color = Color.RED;
                    node = parent;
                }
            
            }else{//父节点是右侧节点
                const uncle = grandParent.left;
                //左侧叔父节点是红色,重新填色,隔开颜色
                if(uncle&&uncle.color === Color.RED){
                    grandParent.color = Color.RED;
                    uncle.color = Color.BALCK;
                    parent.color= Color.BALCK;
                    node = grandParent;
                }else{
                    if(node === parent.left){
                        //节点是左侧子节点-右旋转
                        this.rotationLLarent);
                        node = parent;
                        parent = node.parent;
                    }
                     //节点是右侧子节点旋转
                    this.rotationRRrandParent);
                    parent.color = Color.BLACK;
                    grandParent.color = Color.RED;
                    node = parent;
                    
                }
            }
        }
        this.root.color = Color.Black;
    }
    rotationLL(node){//多了一步设置对应父级
        const tmp = node.left;
        node.left = tmp.right;
        if(tmp.right&&tmp.right.key){
            tmp.right.parent = node;
        }
        tmp.parent = node.parent;
        if(!node.parent){//顶级了
            this.root =tmp;
        }else{
            if(node === node.parent.left){
                node.parent.left = tmp;
            }else{
                 node.parent.right = tmp;
            }
        }
        tmp.right = node;
        node.parent = tmp;
        
    }
    rotationRR(node){//左旋转
        const tmp = node.right;
        node.right = tmp.left;
        if(tmp.left&&tmp.left.key){
            tmp.left.parent = node;
        }
        tmp.parent = node.parent;
        if(!node.parent){
            this.root = node;
        }else{
            if(node === node.parent.left){
                node.parent.left=tmp;
            }else{
                node.parent.right = tmp;
            }
        }
        tmp.left = node;
        node.parent = tmp;
    }
}

做个笔记,欢迎指出错误,该内容借鉴与学习javascript数据结构与算法

查看原文

赞 0 收藏 0 评论 0

Charon 发布了文章 · 9月9日

javascript数据结构之链表

链表数据结构

要储存多个元素,js中数组可能是最常用的数据结构,但是从数组的起点或中间插入或者移除项的成本很高,因为需要移动元素。
链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置,而是每个元素由一个存储元素本身的节点和指向下一个元素的引用组成,这是正常的链表,双向链表比正常的多了一个指向前一个的元素引用,循环链表可以是单向引用,也可以是双向引用,循环链表的最后一个元素指向下一个元素的指针不是undefined而是第一个元素head.
image
画的图有点渣,这是一个双向的循环链表。
创建一个最简单的链表

function defaultEquals(a,b){
    return a===b;
}
class Node{
    constructor(el){
        this.el = el;
        this.next = undefined;
    }
}
class LinkedList{//单向链表
    constructor(equals = defaultEquals){
        this.count = 0;
        this.head = undefined;
        this.equalsFn = equals;
    }
    push(el){
        const tail = this.getElAt(this.count-1);
        if(tail.next){
            throw '循环链表不支持此方法!';
            return;
        }
        const node = new Node(el);
        let current;
        if(!this.head){
            this.head = node;
        }else{
            current = this.head;
            while(current.next){
               current = current.next;
            }
            current.next = node;
        }
        this.count++;
    }
    getElAt(index){//根据位置获取元素
         if(index>=0 && index<this.count){
            let current = this.head;
            for(let i=0;i<index && current;i++){
                current = current.next;
            }
            return current;
         }
         return undefined;
    }
    removeAt(index){//根据位置移除
        if(index>=0 && index<this.count){
            let current = this.head;
            if(index===0){
                this.head = current.next;
            }else{
                let previous=this.getElAt(index-1);//获取前一个
                current = previous.next;         
                previous.next = current.next;
            }
            this.count--;
            return current.el;
        }
        return undefined;
    }
    insert(el,index){//任意位置插入
        if(index>=0 && index<=this.count){
            const node = new Node(el);
            if(index===0){
                const current = this.head;
                node.next = current;
                this.head = node;
            }else{
                const previous = this.getElAt(index-1);
                const current = previous.next;
                node.next = current;
                previous.next = node;
            }
            this.count++;
            return true;
        }
        return false;
    }
    indexOf(el){
        let current = this.head;
        for(let i=0;i<this.count;i++){
            if(this.equalsFn(current.el,el)){
                return i;
            }
            current = current.next;
        }
        return -1;
    }
    remove(el){
        let index = this.indexOf(el);
        return this.removeAt(index);
    }
    size(){
        return this.count;
    }
    isEmpty(){
        return this.size() === 0;
    }
    getHead(){
        return this.head;
    }
    toString(){
        if(!this.head){
            return '';
        }
        let str = `${this.head.el}`;
        let current = this.head.next;
        for(let i=0;i<this.size() && current;i++){
            str=`${str}${current.el}`;
            current = current.next;
        }
        return str;
    }
}

双向链表,增加一个指向前一个元素的引用

class DoublyNode extends Node{
    constructor(el,next,prev){
        super(el);
        this.prev = prev;
    }
}
class DoublyLinkedList extends LinkedList{
    constructor(equals = defaultEquals){
       super(equals);
       this.tail = undefined;
    }
     push(el){
        const node = new DoublyNode(el);
        let current;
        if(!this.head){
            this.head = node;
            
        }else{
            current = this.head;
            while(current.next){
               current = current.next;
            }
            current.next = node;
            node.prev = current;
        }
        this.tail = node;
        this.count++;
    }
    insert(el,index){
        if(index>=0 && index<=this.count){
            const node = new DoublyNode(el);
            let current = this.head;
            if(index===0){
                if(!this.head){
                    this.head = node;
                    this.tail = node;
                }else{
                    node.next = current;
                    current.prev = node;
                    this.head = node;
                }
            }else if(index === this.count){
                current = this.tail;
                node.prev = current;
                current.next = node;
                this.tail = node;
            }else{
                const previous = this.getElAt(index-1);
                current = previous.next;
                previous.next = node;
                node.prev = previous;
                node.next = current;
                current.prev = node;
            }
            this.count++;
            return true;
        }
        return false;
    }
    removeAt(index){
        if(index>=0 && index<this.count){
            let current = this.head;
            if(index===0){
                this.head = current.next;
                if(this.count===1){
                    this.tail=undefined;
                }else{
                    this.head.prev = undefined;
                }
            }else if(index===this.count-1){
                current = this.tail;
                this.tail = current.prev;
                this.tail.next = undefined;
            }else{
                current = this.getElAt(index);
                const previous = current.prev;
                previous.next = current.next;
                current.next.prev = previous;
            }
            this.count--;
            return curren.el;
        }
        return undefined;
    }
}

循环链表,单向 最后一个元素指向下一个元素指针tail.next不是undefined而是第一个元素head,双向,是第一个元素上一个引用head.prev不是undefined而是指向最后tail.

class CircularLinkedList extends LinkedList{
    constructor(equalsFn=defaultEquals){
        super(equalsFn)
    }
   
    insert(el,index){
        if(index>=0 && index<=this.count){
            const node = new Node(el);
            const current = this.head;
            if(index==0){
                if(!this.head){
                    this.head = node;
                    node.next = this.head;
                }else{
                    node.next = current;
                    current = this.getElAt(this.size()-1);
                    this.head = node;
                    current.next = this.head;
                }
            } else {
                const previous = this.getElAt(index-1);
                node.next = previous.next;
                previous.next = node;
            }
            this.count++;
            return true;
        }
        return false;
    }
    removeAt(index){
        if(index>=0 && index<this.count){
            let current = this.head;
            if(index===0){
                if(this.size()==1){
                    this.head = undefined;
                }else{
                    const removed = this.head;
                    current = this.getElAt(this.size()-1);
                    this.head = this.head.next;
                    current.next = this.head;
                    current = removed;
                }
            }else{
                const previous = this.getElAt(index-1);
                current = previous.next;
                previous.next = current.next;
            }
            this.count--;
            return current.el;
        }
        return undefined;
    }
}

有序链表,根据自己规则生成比较函数,来将元素插入正确的位置保证链表的有序性。

const Compare = {
    LESS_THAN:-1,
    BIGGER_THAN:1
}
function defultCompare(a,b){
    if(a===b){
        return 0;
    }
    return a<b?Compare.LESS_THAN:Compare.BIGGER_THAN;
}
class SortedLinkedList extends LinkedList{
    constructor(equalsFn=defaultEquals,compareFn=defultCompare) {
        super(equalsFn)
        this.compareFn = compareFn;
    }
    insert(el){
        if(this.isEmpty()){
            return super.insert(el,0);
        }else{
            const pop = this.getIndexNextSortedEl(el);
            return super.insert(el,pop);
        }
    }
    getIndexNextSortedEl(el){
        let current = this.head;
        let i = 0;
        for(;i<this.size() && current;i++){
            const comp = this.compareFn(el,current.el);
            if(comp === Compare.LESS_THAN){
                return i;
            }
            current = current.next;
        }
        return i;
    }
}

有序链表不能使用push方法,不然无法保证有序性了。
可以使用链表来创建其他数据结构,比如栈,队列,双向队列。
链表相对数组最重要优点,就是无需移动链表中的元素就可以轻松添加删除元素,所以当需要频繁添加和删除很多元素时,最好的选择是链表而非数组。
该内容借鉴与学习javascript数据结构与算法

查看原文

赞 0 收藏 0 评论 0

Charon 发布了文章 · 9月8日

JavaScript数据结构杂谈(双端队列)

双端队列是与队列类似的项的有序集合,其实本质就是队列,只不过是前端与后端都支持插入和删除操作的队列,更实用,所以也就不存在先进先出这种说法了。

我们可以通过数组来实现,但是为了写出一个更高效得数据结构,使用对象来实现。

class Deque{
    constructor(){
        this.count= 0;
        this.lowestCount = 0;
        this.items = {};
    }
    isEmptry(){
        return this.size() === 0;
    }
    size(){
        return this.count - this.lowestCount;
    }
    clear(){
        this.count= 0;
        this.lowestCount = 0;
        this.items = {};
    }
    toString(){
        if(this.isEmptry()){
            return '';
        }
        let objString = `${this.items[this.lowestCount]}`;
        for (let i=this.lowestCount+1;i<this.count;i++) {
            objString = `${objString},${this.items[i]}`;
        }
        return objString;
    }
    addBack(el){
        this.item[this.count]=el;
        this.count++;
    }
    addFront(el){
        if(this.isEmptry()){
            this.addBack(el);
        }else if(this.lowestCount>0){
            this.lowestCount--;
            this.item[this.lowestCount]=el;
        }else{
            for(let i=this.count;i>0;i--){
                this.item[i]=this.item[i-1];
            }
            this.count++;
            this.lowestCount=0;
            this.item[0]=el;
        }
    }
    removeFront(){
        if(this.isEmptry()){
            return undefined;
        }
        let c = this.items[this.lowestCount];
        delete this.items[this.lowestCount];
        this.lowestCount++;
        return c;
    }
    removeBack(){
         if (this.isEmpty()) {
            return undefined;
         }
         this.count--;
         let c = this.items[this.count];
         delete this.items[this.count];
         return c;
    }
    peekFront() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.lowestCount];
    }
    peekBack() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.count - 1];
    }
 }

也可以使用链表来实现这种结构
链表的实现
该内容借鉴于学习javascript数据结构与算法。

查看原文

赞 0 收藏 0 评论 0

Charon 发布了文章 · 9月8日

JavaScript数据结构杂谈(栈)

有两种类似数组得结构在添加和删除时更为方便控制,就是栈和队列。

栈是一种后进先出原则得有序集合,新添加或者即将删除得一端叫栈顶,另一侧叫栈底,新元素在栈顶,旧元素在栈底,ECS执行环境就是典型得栈结构。

使用weakMap保证属性私有,weakMap必须用键才能取出值,它没有entries,keys,values等迭代器方法,所以除非知道键,否则没法取出值。

const item = new WeakMap();
class Stack{
    contructor(){
        item.set(this,[]);
    }
    push(el){
        const arr = item.get(this);
        arr.push(el);
    }
    pop(){
        const arr = item.get(this);
        return arr.pop();
    }
    peek(){
        const arr = item.get(this);
        return arr[arr.length-1];
    }
    isEmpry(){
        return item.get(this).length === 0;
    }
    clear(){
        item.set(this,[]);
    }
    toString(){
        if(this.isEmpry()){
            return '';
        }
        const arr = item.get(this);
        let str = `${arr[0]}`;
        for(let i=1;i<arr.length;i++){
            str=`${str}${arr[i]}`;
        }
        return str;
    }
}
//进制转换
const baseConverter = function(dec,base){
    const stack = new Stack();
    const digits = `0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ`;
    let num = dec;
    let rem;
    let string = '';
    if((base>=2||base<=36)){
        return '';
    }
    while(num>0){
        rem = Math.floor(num%base);
        stack.push(rem);
        num = Math.floor(num/base);
    }
    while(!stack.isEmpry()){
        string+=digits[stack.pop()];
    }
    return string;
}
console.log(baseConverter(100,10));

也可以用链表实现
链表实现
做个笔记,内容借鉴于学习javascript数据结构与算法。

查看原文

赞 0 收藏 0 评论 0

Charon 关注了用户 · 8月27日

Peter谭金杰 @jerrytanjinjie

前端架构师

微信公众号:前端巅峰

欢迎技术探讨~

个人微信:CALASFxiaotan

关注 4231

认证与成就

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

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 8月27日
个人主页被 217 人浏览