2017年3月2日星期四

Rx 的编程方式(一)

1. Observables & Reactive

先来一个简单直观的例子:

const { Observable } = require('rxjs');

const source$ = Observable.of([1, 2, 3]);
source$.subscribe(x => console.log(x));

过滤器节点:subscribe

2. Declarative Transformation( 声明式转换 )

如果我们想要平时开发的数据转换功能,可以使用一些类似管道的工具来做。

Observable.of(1, 2, 3)
    .map(n => n * 2)
    .subscribe(x => console.log(x));

过滤器节点:map、subscribe。我所理解的就像一条溪流流动的水,然后 map 这类 API 就像水桶,将水装入进行加工,当然,其他 map 的特性先不用细致了解。

3. Lazy Transformation( 懒执行透明特性 )

Observable 能够在流动的过程中进行选择,所谓的懒特性就是不会像 Promise 一样,给了一个数据承认,就一定会让你接受,你可以选择不接受或者现在不接受,先这样子理解。

Observable.range(1, 100)
    // 转换管道
    .map(n => n * 2)
    // 拦截节点
    .filter(n => n > 4)
    // 懒获取
    .take(2)
    .subscribe(x => {
       console.log(x);
    });

4. DOM Event

Rx 其实是可以独立与任何框架使用了,也可以按需加载想用的方法,对于 Rx,其实和 Zone 一样,有了自己的保护圈和玩法,如果你要玩它,就需要进入它的圈子,大多数的相关 API 就是 from 的特性,对于 Rx 5.0 模块化做的更好,以及渲染 Timeline 上更可控。

<button id="btn">加</button>
<h1 id="out">0</h1>
const btn = document.getElementById('btn');
const out = document.getElementById('out');

/* eslint-disable no-undef */
const { Observable } = Rx;
Observable.fromEvent(btn, 'click')
    // mapTo 能映射一个常量,map 需要一个函数
    .mapTo(1)
    .scan((acc, cur) => acc + cur, 0)
    .subscribe(count => {
        out.innerHTML = count;
    });

其中主要依赖了:

rxjs/Observable.js
rxjs/observable/fromEvent.js
rxjs/operator/mapTo.js
rxjs/operator/scan.js

如果是打包的方式可以按需加载,如果是 script 可以直接引入 rxjs/bundles/Rx.js,不过会比较大,所以最好是按需提取到公用的 external 文件中,也能使用 lite 的版本,是常用的精简版。

如果有两个事件怎么办呢?利用流的合并特性可以做:

// 加法流,然后转换成数据 1 流入给下一个输入
const { Observable } = Rx;
const inSource$ = Observable.fromEvent(inBtn, 'click').mapTo(1);
// 减法流,然后转换成数据 -1 流入给下一个输入
const outSource$ = Observable.fromEvent(outBtn, 'click').mapTo(-1);
// 合并成最后需要操作的流
const source$ = Observable.merge(inSource$, outSource$);
// 操作流并且订阅流的 next 函数
source$.scan((acc, cur) => {
    if(acc + cur < 0) {
     return 0;
    }
    return acc + cur;
}, 0).subscribe(count => {            
    print.innerHTML = count;
});

5. Async HTTP

前端主要除了这种简单的数据操作,更多的是要看异步场景下的复杂度,下面用 Promiseasync/awaitObserable 三者的写法来对比。

(1) Promise方案

const data = fetchOrders().then(res => {
    if(res.status === 200) {
        return res.data;
    }
});
   
data.then(orders => orders.filter(order => order.text === 'Bob'))
    .then(orders => orders.map(order => order.id))
    .then(ids => console.log(ids));

function fetchOrders() {
    return axios.post('orders.json');
}

(2) async/await

function fetchOrders() {
    return axios.post('orders.json');
}

renderOrders();
async function renderOrders() {
    const res = await fetchOrders();
    if(res.status === 200) {
        const data = res.data;
        data.filter(order => order.text === 'Bob')
            .map(order => order.id)
            .forEach(id => console.log(id));
    }
}

(3) Observable

const { Observable } = Rx;

function fetchOrders() {
    const promise = axios.post('orders.json');
    return Observable.fromPromise(promise);
}
   
const hook =
    fetchOrders()
        .switchMap(res => {
            let data = [];
            if(res.status === 200) {
                data = res.data;
            }
            
            return Observable.from(data);
        })
        .filter(order => order.text === 'Bob')
        .map(order => order.id)
        .filter(id => id !== void 0)
        .subscribe(id => {
            console.log(id);
        });

6. Cancellation( 可取消的特性 )

其实这个特性很好用,可以随时取消你订阅的流,这是 Promise 做不到的,一旦发起承认就无法取消。

hook.unsubscribe();

7. Create HTTP Request

上面的 ajax 使用的是 axios 封装的,然后返回的是 Promise 的对象,如果要用 Observable 的生态,那么就需要利用 fromPromise 进行转化,这看上去不是特别好,所以能够直接利用 Observable 生态下的 ajax 进行操作。

与之前方案需要修改的地方有 2 个:
1. fetchOrders 函数请求 ajax 的方式
2. ajax 响应返回的对象不一样,毕竟之前使用的 axios

// 1. 使用 Observable.ajax
function fetchOrders() {
    return Observable.ajax.post('orders.json');
}

// 2. 修改一下 ajax 响应基础数据的处理
if(res.status === 200) {
    // res.data => res.response, ng2 如果不是 json 需要调用 json() 方法
    data = res.response;
}

8. Observable.create 的一些细节

(1) Obserable 的组成
我之前仿造过一个简单 Obserable 的实现:Obserable
这里用简单的结构来说一下:

class Observable {
    constructor (fn) {
        this.fn = fn;
    }
    
    static create(fn) {
        return new Observable(fn);
    }

    subscribe(next, error, complete) {
        if (typeof next !== 'function') {
            return this.fn(next);
        }
        
        return this.fn({
            next,
            error: error || () => {},
            complete: complete || () => {}
        });
    }
}

从上面代码可以看出来,构造器主要接收一个函数,然后 create 方法主要返回的是一个 Obserable 实例。然后 subscribe 方法接收的是三个参数,如果我们传入的是一个 function 那么就会调用 this.fn 传入一个对象,这个对象有三个属性值:next、error、complete,默认情况下 next 是必须传入的,其余的是可选,为了安全,自己手动创建的最好调用一下 complete

这样看上来其实也挺简单的。下来回到 rxjs 本身来看一下 create 的用法:

function fetchSomeone() {
    return Observable.create(observer => {
        observer.next('ok');
        observer.complete();
    });
}

fetchSomeone().subscribe(x => console.log(x));
// 或者如下写法
fetchSomeone().subscribe({
    next: (x) => console.log(x),
    complete: () => {}
});

这里用法比较简单,就是传入一个常量字符串 ok,然后在这个 Observable 被订阅的时候传给订阅者。

剩下的一些内容单独来看:
(1) Error Handle( 错误的处理机制 )
(2) Hot and Cold 数据流以及它们之间的转换关系
(3) 流节点之间的转换
(4) 流节点的并发问题

后面可能会比较细节,如果有兴趣可以直接看下面的 PPT,我主要也是按 PPT 的例子和思路来写。

参考的PPT: https://speakerdeck.com/jfairbank/devnexus-2017-the-rise-of-async-javascript

2017年2月16日星期四

编程

Everybody in this country should learn how to program a computer, because it teaches you how to think. - Steve Jobs

作为乔帮主的粉,很认同他对于自己产品热爱的那份情感。对于编程也一样,如果没有兴趣是肯定不行的,但是兴趣又是培养的,在编程过程中体验乐趣是很重要的。

读书的时候老师会教你程序设计的课程,我们这里把它叫做编程。比如可以抽象是:
Programs = Algorithms + Data Structures

I. 对于数据结构,可以用一个简单的例子来理解一下。

一堆书有两种简单放的方式:
1. 重叠放
2. 摊开放
语言的表达太淡,来个简单的图:

那么对于这里的数据结构就是这三本书放的方式,每一种方式都有各自的好处。

II. 那么算法是什么呢?

算法就是解决处理问题的策略或者说对信息的处理过程。我理解的算法是逻辑相关过程式的。
接着上面取书的例子,我要拿第二本书,具体过程是什么呢?
第一种方式我们要取第二本书的话(严谨一点的是在不移动当前书的空间位置的情况下),必须要把第一本书拿开。
第二种方式的话,我们只需要拿中间那本书就行了。

// 第一种方式
books: ["第一本书", "第二本书", "第三本书"]
needTakeBook: 2
takeBook: 1

while(takeBook < needTakeBook)
    do books -> take // 不断地拿书

books: ["第二本书", "第三本书"]
books -> take // 拿到第二本书
// 第二种方式
books: ["第一本书", "第二本书", "第三本书"]
books -> takeTheSecond

其实上面拿书的方式的代码就是实现了算法,算法本质上就是思考这个场景下的策略。
编程本身是抽象的,学会了抽象就学会了编程。

那么要一个好看能看的东西我们就需要换一些描述来显示出来。

生病了,随便写点吧~休息了。

2017年1月16日星期一

为什么需要 KeyMirror

前言

今天有朋友问了 “KeyMirror” 这个库有什么用的问题,其实这个问题并不难,这里扫一下盲区。

会按照下面这个逻辑来展开,彻底理解一下:

  1. KeyMirror 有什么用?
  2. Google Closure Compiler 是什么?
  3. KeyMirror 解决了什么问题,好处是什么?
  4. KeyMirror 的源码是什么样子?
  5. 用 Gulp 配置一个压缩任务,测试一下 Google Closure Compiler.

一、KeyMirror 有什么用

直观的来看一下,测试代码如下:

var kv = {
    GET_USER: null,
    SET_USER: null,
    REMOVE_USER: null
};

// keyMirror 是对应的测试方法
var kv_new = keyMirror(kv);
console.log(kv);
console.log(kv_new);

最后输出的结果如下:

kv_test1

然后就是相当于重新生成了一个 key == value 的结构。但是肯定就会想,为毛要多此一举呢?其实这个跟 Google Closure CompilerAdvanced 模式有关。接下来我们来看一下它是什么。

二、Google Closure Compiler 是什么

如果有兴趣的朋友可以直接跳到文章后面,使用 Gulp 把环境搭起来测试,因为下面的地址都要翻墙!

有官方文档,需要翻墙:文档

大致的意思就是说,Closure Compiler 是一个工具,这个工具能够编译 JavaScript 代码,编译后的代码能下载更快并且执行也更快。它能够解析你的 JS 代码,并且去分析它,能移除没有使用到的代码,重写、压缩得到最终的生产环境下的 JS 代码。它拥有检测语法、变量声明、类型定义以及对 JS 语言缺陷做一些检查。

总之,这就是做 JS 编译并且做一些常用检测的一款工具。

具体能够在线体验,也需要翻墙,在线体验地址

这个工具有三种模式:
1. 只去空格( Whitespace only )
2. 简单处理( Simple )
3. 最优处理( Advanced )

用 KeyMirror 的原因就是因为第三种(Advanced,最优处理)模式下,会将 Map<K, V> 格式的 K 进行压缩,比如:

// 源代码
var kv = {
    GET_USER: null,
    SET_USER: null,
    REMOVE_USER: null
};

// 编译后( 整理了一下格式,实际情况下会再添加压缩 )
var a = {
    a: null,
    c: null,
    b: null
};

在引用的时候就变成:

// 源代码
var kv_new = keyMirror(kv);
console.log(kv_new.GET_USER);

// 编译后
var a = keyMirror({ a: null, c: null, b: null });
console.log(a.a);

这样如果在没有进行 KeyMirror 处理的时候,引用就会错误了,这种编译模式破坏了我们的代码,要避免这个编译导致的 Key 改变,可以给 Key 添加引号(单、双均可),其实能够分析的就是静态的属性,动态基本上是不好做好的,可以这样理解。

// 源代码
var kv = {
    'STOP_USER': null
};

// 编译后
var a = {
    STOP_USER: null
};

然而我们这样做了之后,代码就得不到更有效的压缩,这样 Closure Compiler 的功能就被削弱了,所以引入 KeyMirror 既能保证代码前后的功能一致,也能享受压缩带来的性能提升。

三、KeyMirror 的源码是什么样子

既然知道了上面的背景和原因,我们来看下如何实现一个这玩意,其实特别简单的功能,就是让 K,V 相等。

var keyMirror = function(obj) {
    var ret = {};
    var key;
    
    // 对参数的控制,必须是对象
    if (!(obj instanceof Object && !Array.isArray(obj))) {
        throw new Error('keyMirror(...): Argument must be an object.');
    }
    
    // 简单的遍历,将对应 K 赋值给 Map[K]
    for (key in obj) {
        // 只拷贝自己的属性
        if (!obj.hasOwnProperty(key)) {
            continue;
        }
        ret[key] = key;
    }
    
    return ret;
};

四、Gulp 配置测试 Closure Compiler

这里需要用到两个东西:gulp、google-closure-compiler-js

直接上代码:

var gulp = require('gulp');
var compiler = require('google-closure-compiler-js').gulp();

gulp.task('go', function () {
    return gulp.src('./index.js')
        .pipe(compiler({
            // 编译等级,不区分大小写哈
            compilation_level: 'advanced',
            warning_level: 'VERBOSE',
            output_wrapper: '(function(){\n%output%\n}).call(this)',
            js_output_file: 'index.advanced.min.js',
            create_source_map: true
        }))
        .pipe(gulp.dest('.'));
});
// 测试代码
var kv = {
    GET_USER: null,
    SET_USER: null,
    REMOVE_USER: null
};
// 必须要和 keyMirror 代码一起,不然会被提示 error。
// Error: Compilation error, 1 errors
var kv_new = keyMirror(kv);
console.log(kv);
console.log(kv_new);

亲测非常的慢,不知道是不是我姿势不对,advanced 模式都是花费 12s 左右,simple 模式也花费 8s 左右,第一次测试我还卡挂了,所以基本上代码量上去了感觉是不适用的。

参考地址:

[1] https://developers.google.com/closure/compiler/

[2] https://github.com/facebook/react/issues/1639

[3] https://gist.github.com/zpao/d25251b139647a79cddf

[4] https://www.npmjs.com/package/keymirror

2016年12月8日星期四

Angular 组件交流方式

以下的测试例子都可以在 github 找到,但是最近好像不太稳定。
其实 ng2 在这方面做得挺好的,用起来也很简单,所以看完基本就可以动手写一写。强大并不止是这一方面,在写这些的过程中,通过一些配置,让开发很纯粹,有时间再录一个新手入门的开发教程。

(1) 父组件向子组件流入数据

这种方式是最简单的,在 ng2 中处理得非常完美,通过在子组件中标记 @Input() 输入接口的方式进行接收父组件的值,我下面的 demo 主要分了几种场景,尽可能的多覆盖不同情况吧。

基本上例子中覆盖了常见的情况:

  • 直接传入一个字符串的情况,不需要绑定父组件的一个变量
  • 绑定父组件变量的情况,然后可以在父组件中不断修改
  • 输入别名的情况,可以在子组件中对输入的变量名进行重新设置
  • ngOnChanges() 在子组件中监听属性的修改
  • 特殊情况下,我们需要对父组件传入的数据进行过滤
  • @ViewChild() 注解的跨多层子组件的观察方式

说了这么多,来看一下实际的代码吧。


// Parent component
import { Component, OnInit } from '@angular/core';
    
@Component({
    selector: 'app-parent',
    templateUrl: './parent.component.html',
    styleUrls: ['./parent.component.css']
})
export class ParentComponent implements OnInit {
    
    baby: string = '你的名字';
    
    constructor() { }
    
    ngOnInit() {
    }
    
}


// Parent html
<h3>请输入 Baby 的名字:</h3>
<input [(ngModel)]="baby" type="text"> 
<app-child babyName="hello" [inputBabyName]="baby" aliasBabyName="我是别名"></app-child>
    

// Child component
import { Component, OnInit, Input, SimpleChange } from '@angular/core';

@Component({
    selector: 'app-child',
    templateUrl: './child.component.html',
    styleUrls: ['./child.component.css']
})
export class ChildComponent implements OnInit {
    
    @Input() babyName: string;
    @Input() inputBabyName: string;
    @Input('aliasBabyName') aliasName: string;
    
    changes: string;
    
    constructor() { }
    
    ngOnInit() {
    }
    
    ngOnChanges(changes: SimpleChange) {
        this.changes = JSON.stringify(changes);
    }
}


// Child html
<h3>我是子组件的属性(babyName) => {{babyName}}</h3>
<h3 style="color:red;">我是跟父组件来:{{inputBabyName}}</h3>
<h3>我是 aliasBabyName => aliasName:{{aliasName}}</h3>

那么我需要过滤一下值要怎么弄呢?

这样我们就可以用到 setter 和 getter 的特性来做,具体如下:


// Child component
_filterName: string = '';
    
@Input()
set filterName(n: string) {
    this._filterName = n + 'wowo~~~';
}
    
get filterName() {
    return this._filterName;
}


// Parent html
<app-child [filterName]="babyName"></app-child>

这个其实也是用 @Input() 这个注解来做的,有点类似 computed 的概念吧,但是这样做对于习惯 Java 的小伙伴是很友好的,其实通过一些权限的设置,还能够更加的强大。

@ViewChild() 的方式

这种方式我觉得更多的是,我的沟通逻辑存在于 TS 中的时候就很实用。并且是描述性的定义方式,所以逻辑也是清晰的。


// Parent component
// 方式1,定义了 `#` 的钩子也是可以引用的
@ViewChild('child') cc: ChildComponent;
    
// 直接观察某一个子组件
@ViewChild(ChildComponent)
cc_other: ChildComponent;
    
// 调用的时候
this.cc.name = '变身啦!超级赛亚人';
this.cc_other.name = '变身啦!超级赛亚人 4';

可以思考一下,是否任何形式的父组件流入子组件的方式,都可以触发 ngOnChanges() 方法。

(2) 子组件向父组件通信

从软件的结构上来讲,是上层抽象对底层的具体实现是隐藏的,所以具体层的东西最好尽可能少的知道抽象层的事情,也许表达方式不一样,但是这样的话封闭性会好很多,更多的暴露是以某一个权限开放的接口形式。但是通信是很复杂的东西,就好像人与人之间的联系是一样的。好吧,我们来具体说一下子组件怎么访问父组件。主要通过的方式是:

  • 在子组件定义一个 @Output()EventEmitter<T> 对象,这个对象可以是 Subject 的形式存在,也就是可以使用 RxJS 的思想来做,其中 T 范型表示定义需要传入的数据具体类型。
  • 父组件中定义一个自己的函数来修改自身的信息,或者再传入其他子组件使用。

// Parent component
import { Component, OnInit } from '@angular/core';
    
@Component({
    selector: 'app-parent',
    templateUrl: './parent.component.html',
    styleUrls: ['./parent.component.css']
})
export class ParentComponent implements OnInit {
    
    babyName: string;
    
    constructor() { }
    
    ngOnInit() {
    this.babyName = '小撸一号';
    }
    
    changeBabyName(newBabyName) {
        this.babyName = newBabyName;
    }
 
}


// Parent html
<h3>BabyName:{{babyName}}</h3>
<app-child (changeBabyName)="changeBabyName($event)"></app-child>


import { Component, OnInit, Output, EventEmitter } from '@angular/core';
    
@Component({
    selector: 'app-child',
    templateUrl: './child.component.html',
    styleUrls: ['./child.component.css']
})
export class ChildComponent implements OnInit {
    
    @Output()
    changeBabyName: EventEmitter<string> = new EventEmitter<string>();
    
    rhashcode = /\d\.\d{4}/;
    
    constructor() { }
    
    ngOnInit() {
    }
    
    getNewBabyName(e) {
        let newName = this.makeHashCode('小撸新号');
        this.changeBabyName.next(newName);
    }
    
    /* UUID http://stackoverflow.com/questions/105034/how-to-create-a-guid-uuid-in-javascript */
    makeHashCode(prefix) {
        prefix = prefix || '60sky';
        return String(Math.random() + Math.random()).replace(this.rhashcode, prefix);
    }
}


<button (click)="getNewBabyName($event)">我要改我自己的名字</button>

其中需要注意的是父组件中方法注入的 $event 对象,这个对象在这里注入的是子组件传入的值,所以在父组件中就可以直接使用了,我这里定义了 string 类型的数据,所以传入后定义接口的参数类型也是相对应的。

(3) 无关组件的通信

ng2 在无关组件的处理上,真的处理得很干脆,给你一个钩子,你用吧!就是这种简单的思路。这里我只介绍部分,因为官方文档有更加详细的介绍,不然我这篇文章就写得太长了~因为方式有很多种,发挥小聪明就能发现很多。

  • 事件回调传来传去的方式
  • Service 的注入
  • # 钩子的方式

这里介绍的是一个 # 钩子的方式来做,直接来代码吧,很方便的。
其中,需要注意的是作用域的隔离,子组件可以很好的隔离作用域。


// Parent component
import { Component, OnInit } from '@angular/core';
    
@Component({
    selector: 'app-parent',
    templateUrl: './parent.component.html',
    styleUrls: ['./parent.component.css']
})
export class ParentComponent implements OnInit {
    
    babyName: string = '小撸一号';
    
    constructor() { }
    
    ngOnInit() {
    }
    
}


// Parent html
<input [(ngModel)]="babyName" type="text">
    
<app-child #child [childName]="babyName"></app-child>
<app-otherChild helloBaby="child.childName"></app-otherChild>


// Child component
import { Component, OnInit, Input } from '@angular/core';
    
@Component({
    selector: 'app-child',
    templateUrl: './child.component.html',
    styleUrls: ['./child.component.css']
})
export class ChildComponent implements OnInit {
    
    @Input() childName: string;
    
    constructor() { }
    
    ngOnInit() {
    }
    
}


<h3 style="color:red;">Child:{{childName}}</h3>


// OtherChild component
import { Component, OnInit, Input } from '@angular/core';
    
@Component({
    selector: 'app-otherChild',
    templateUrl: './otherChild.component.html',
    styleUrls: ['./otherChild.component.css']
})
export class OtherChildComponent implements OnInit {
    
    @Input() helloBaby: string;
    
    constructor() { }
    
    ngOnInit() {
    }
    
    changeChildName(e) {
        this.helloBaby = '小撸新号';
    }
}


// OtherChild html
<h3 style="color:blue;">otherChild:{{helloBaby}}</h3>
<button (click)="changeChildName($event)">我来统一修改一下</button>

其实还有一些方式和特殊场景下的处理,所以总体来说,ng2 在这方面是不错的~

2016年11月30日星期三

二叉树简单两三下

前言

树和图一样,是常用的数据结构模型,但是我的理解树是图的一个用于更具体的数据结构。今天温习的是树中比较简单、常用的二叉树。因为一个简单固定的结构更有利于查询,所以有了二叉查找树的概念。

简单介绍下

研究依然以点-线模型的分析理解,不过树是从一个方向顺势的分支结构。这里可以是自上向下,也可以自下向上。

树的常见术语有几个:

  • 根节点
  • 子节点
  • 叶子节点
  • 子树
  • 路径
  • 键(这里是抽象主要的数据)

二叉树:

  • 子节点不超过两个
  • 左节点
  • 右节点

如果具备查找特性:

较小值在左,较大值在右

这里准备一组值来构建树:

[ 23, 45, 16, 37, 3, 99, 22 ]

然后我需要构建的树的成品是:

树

具体实现

  1. 首先需要构造一个节点对象,来表示节点这一个描述元素
class Node {
    constructor (data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    getData () {
        return this.data;
    }

    output() {
        console.log(this.data);
    }
}

主要包含:

  • data: 节点的键
  • left: 左节点
  • right: 右节点
  • getData: 获取键
  • output: 辅助输出函数

  1. 树的对象以及树的操作
class Tree {
    constructor () {
        // 根节点默认是 null
        this.root = null;
    }

    // 插入节点
    insert (data) {
        const node = new Node(data, null, null);

        if(this.root === null) {
            this.root = node;
        } else {
            let current = this.root;
            let parent = null;

            while(1) {
                parent = current;
                if(data < current.data) {

                    current = current.left;
                    if(current === null) {
                        parent.left = node;
                        break;
                    }
                } else {

                    current = current.right;
                    if(current === null) {
                        parent.right = node;
                        break;
                    }
                }
            }
        }

        return this;
    }

    // 中序遍历
    ascOrder (node) {
        if(node !== null) {
            this.ascOrder(node.left);
            node.output();
            this.ascOrder(node.right);
        }
    }

    // 先序遍历
    rootOrder (node) {
        if(node !== null) {
            node.output();
            this.rootOrder(node.left);
            this.rootOrder(node.right);
        }
    }

    // 后序遍历
    leafOrder (node) {
        if(node !== null) {
            this.leafOrder(node.left);
            this.leafOrder(node.right);
            node.output();
        }
    }

    // 执行路径的 action: left or right
    action (path) {
        let node = this.root;

        while(node[path] !== null) {
            node = node[path];
        }

        return node;
    }

    // 最小值
    min () {
        return this.action('left');
    }

    // 最大值
    max () {
        return this.action('right');
    }

    // 查找固定值
    find (data) {
        let node = this.root;

        while(node !== null) {
            if(data === node.data) {
                return node;
            } else if(data < node.data) {
                node = node.left;
            } else {
                node = node.right;
            }
        }

        return node;
    }
}

最后我在 Node 环境下测试,所以导出一下 Tree 类:

module.exports = Tree;

对于每一种排序后的结果是不一样的,可以用图形来表示一下:

中序遍历的过程:

中

先序遍历的过程:

14805224572732

后序遍历的过程:

14805226761054

其实看图是最直观的,其实算法这玩意最好的就是能够体会思想,然后根据实际的场景进行映射建立数据结构模型,以最优或更平衡的去解决问题。

测试代码如下:

const Tree = require('./binTree');

const log = s => console.log(s);

const tree = new Tree();
[23, 45, 16, 37, 3, 99, 22].forEach(n => tree.insert(n));

log('中-排序:');
tree.ascOrder(tree.root);

log('先-排序:');
tree.rootOrder(tree.root);

log('后-排序:');
tree.leafOrder(tree.root);

console.log('=====================');

log('最小值:');
log( tree.min() );

log('最大值:');
log( tree.max() );

log('查找 3:');
log( tree.find(3) );

log('查找 11:');
log( tree.find(11) );

终端跑的结果如下:

测试结果

无厘头 Graph

前言

今天晚上无意翻到一个图的文章,查了一下感觉网上实现和其他都好复杂,所以自己按理解搞了一下,不知道是我实现是不是错了...感觉还好~进入正题,先还是来点理论知识,不过大多是自己的想法,不一定都对,可以纠正。

图是一种数学模型,和数学挂勾一般都会比较复杂,所以形象的理解成最简单的模型,点-线 模型。其实最简单的是 1 个点的模型,涉及 2 个点还好,3 个点过后模型就会作出相应的改变。

这里用简单的语言来说图中的二元关系,不过还是先假设一点数学符号:

G => 表示所有的顶点集合

V => 表示顶点

E => 表示边,抽象意义上是无向边

那么用数学来表示就是:G=<V, E>

其实根本不用理解数学的模型,我这里理解是只需要知道这是一个点-线模型就可以了。

如何表示图呢?

这里有两种表示方法:表和矩阵,其间都是邻接关系

这里我有一个测试图,在网上弄的,虽然是无向图,其实在我们代码中,肯定是有向的,是入口的问题:

图

图的结构确定过后,就可以做出表的结构了,这里我没有用方向,因为我理解的图是一个不能简单表示的,理解成坐标系更好理解一点。分为:x, y 轴的方式。其中,x0 表示开始,后面表示相邻的点,按顺时针排列(不一定按这个顺序)。

表

代码中的图

在代码中表示,没有图形那么直观,所以需要映射成代码模型,这里简单实现一下,但是不具备很多功能。

假设:

class G => 一个图的类,包括图的定义和常用遍历方法

this.V => 表示点集合的个数,但是这里我舍弃了 0 的位置

this.T => 我按数据库表的方式理解命名的,关系的集合

this.E => 边的个数

this.visited => 访问过的 bool 集合,其实就是标记

this.defined => 工具小函数,是否定义过,与图无关

所以最后有关的符号有:

G、V、T、E

是不是感觉一下子变简单了,不过程序的抽象有一个上层,那就是类。
然后我这里按计算机的方式,定义了输入、输出函数:input、output

class G {
    constructor(V) {
        this.V = V;
        this.T = [];
        this.E = 0;
        this.visited = [];

        for (let v = 0; v < this.V; ++v) {
            this.T[v] = [];
            this.T[v].push(-1);
        }

        this.defined = s => s !== void 0;
    }
    input(v, w) {
        this.T[v].push(w);
        this.T[w].push(v);

        this.E++;

        return this;
    }
    output() {
        console.table(this.T);
    }
}

然后能够看出,其实边是由点的连接组成的,刚好符合数学的定义,并且与相邻有相关性。

那么,实现了结构,还应该有其他作用,那么接下来看一下遍历算法:深度遍历(DFS) 和 广度遍历(BFS)。准确来说应该是优先采用什么策略的遍历方式。其实我这里的实现感觉...不好,和树关系大了点,不过树的大集合就能够上升到图。

dfs(v) {
    this.visited[v] = true;

    if (this.defined( this.T[v] )) {
        console.log('老孙到此一游:' + v);
    }

    this.T[v].forEach(t => {
        if (t !== -1 && !this.visited[t]) {
            this.dfs(t);
        }
    });
}

对于深度遍历,是将图按一个固定方向,纵向的结果,所以是一个递归的结构。

bfs(node) {
    this.visited[node] = true;

    var queue = [];
    queue.push(node);
    while(queue.length > 0) {
        var v = queue.shift();
        if(this.defined( this.T[v] )) {
            console.log('老孙到此一游:' + v);
        }

        this.T[v].forEach(t => {
            if(t !== -1 && !this.visited[t]) {
                this.visited[t] = true;
                queue.push(t);
            }
        });
    }
}

对于广度遍历,是将图按一个固定方向,横向的结果,所以是一个链式进出的关系,这里是用队列,在 JS 中做队列这种先进先出比较简单。

// 测试代码
var v = [1, 2, 3, 4, 5];
let g = new G( v.length + 1 );
g.input(1, 2).input(1, 5)
    .input(2, 4).input(2, 5).input(2, 3)
    .input(3, 4)
    .input(4, 5)
    .output();
g.dfs(1);
console.log('------------');
// 让它失忆一下
g.visited = [];
g.bfs(1);

执行结果

……-_-# 简单玩一下,睡觉了 zZZ

2016年11月3日星期四

JavaScript - EventEmitter 背后的秘密

什么是 Event Emitter?

Event emitter 听起来只是触发一个事件,这个事件任何东西都能监听。

想象一下这样的场景,在你的异步代码中,去“呼叫”一些事件的发生,以及让你其他部分都要听到你的“呼叫”并且注册他们的想法。

为了不同的目的,对于 Event Emitter 模式有大量不同的实现,但是基本的想法是为了给一个框架提供事件的管理以及能够去订阅他们。

在这里,我们的目标创建属于我们自己的 Event Emitter 去理解背后的秘密。所以,让我们看一下下面的代码是怎么工作的。

let input = document.querySelector('input[type="text"]');
let button = document.querySelector('button');
let h1 = document.querySelector('h1');

button.addEventListener('click', () => {
    emitter.emit('event:name-changed', { name: input.value });
});

let emitter = new EventEmitter();
emitter.subscribe('event:name-changed', data => {
    h1.innerHTML = `Your name is: ${data.name}`;
});

让我们开始。

class EventEmitter {
    constructor() {
        this.events = {};
    }
}

我们先创建一个 EventEmiiter 类以及初始化 events 空对象属性。这个 events 属性的目的是为了存储我们的事件集合,这个 events 对象使用事件名当做 key,用订阅者集合当做 value。(可以把每个订阅者看作是一个函数)。

订阅函数

subscribe(eventName, fn) {
    if (!this.events[eventName]) {
        this.events[eventName] = [];
    }

    this.events[eventName].push(fn);
}

这个订阅函数获取事件名称,在我们之前的例子中,它是 "event:name-changed" 以及传入一个回调,当有人调用 emit(或尖叫)事件的时候调用回调。

在 JavaScript 函数的优点之一是函数是第一对象,所以我们能像之前我们的订阅方法一样,通过函数作为另一个函数的参数。

如果未注册这个事件,我们需要在第一次为它设置一个初始值,事件名称作为 key 以及初始化一个空数组赋值给它,然后我们将函数放入这个数组,以便我们想通过 emit 去调用这个事件。

调用函数

emit(eventName, data) {
    const event = this.events[eventName];
    if (event) {
        event.forEach(fn => {
            fn.call(null, data);
        });
    }
}

这个调用函数接受事件名,这个事件名是我们想“呼叫”的名称,以及我们想传递给这个事件的数据。如果在我们的 events 中存在这个事件,我们将带上数据循环调用所有订阅的方法。

使用上面的代码能做我们所说的全部的事情。但我们仍然有一个问题。当我们不再需要它们的时候,我们需要一种方法来取消注册这些订阅,因为如果你不这样做,将造成内存泄漏。

让我们来解决这个问题,通过在订阅函数中返回一个取消注册的方法。

subscribe(eventName, fn) {
    if (!this.events[eventName]) {
        this.events[eventName] = [];
    }

    this.events[eventName].push(fn);

    return () => {
        this.events[eventName] = this.events[eventName].filter(eventFn => fn !== eventFn);
    }
}

因为 JavaScript 函数是第一对象,你能在一个函数中返回一个函数。因此现在我们能调用这个取消注册函数,如下:

let unsubscribe = emitter.subscribe('event:name-changed', data => console.log(data));

unsubscribe();

当我们调用取消注册函数的时候,我们删除的功能依赖于对订阅函数集合的筛选方法(Array filter)。

和内存泄露说再见!👋👋

你能运行这份代码,所有代码都在这里。

注:这份代码可能需要翻墙或者特别慢,所以我放到了 github 上,大家可以下载。(⊙o⊙)…暂时放我的账号下,如果有合适的地方请联系我。

原文出自:https://medium.com/@NetanelBasal/javascript-the-magic-behind-event-emitter-cce3abcbcef9#.nzgbagnxe