发表于 | 阅读次数:

之前因为工作需要，在一个域名A的页面中，使用iframe包含另一个域名B的页面。在chrome，firefox测试一切正常。
当测试到IE7时，发现域名B中的页面session失效，不能写入session。

网上搜索后了解， 因为IE有安全策略，限制页面不保存第三方cookie(当前访问域名A下的页面为第一方cookie，而域名B下的页面为第三方cookie)。
虽然有安全策略限制，但我们可以引入P3P声明允许第三方收集个人信息，使第三方cookie不被拒绝。

P3P：Platform for Privacy Preferences（隐私偏好平台）是W3C公布的一项隐私保护推荐标准，能够保护在线隐私权。使用Internet者可以选择在浏览网页时，是否被第三方收集并利用自己的个人信息。如果一个站点不遵守P3P标准，它的Cookies将被自动拒绝。

在iframe的页面头加入以下语句即可解决session失效问题。

1
header('P3P: CP="CURa ADMa DEVa PSAo PSDo OUR BUS UNI PUR INT DEM STA PRE COM NAV OTC NOI DSP COR"');

IE iframe 跨域访问session问题解决了，但测试后发现，即使加入了P3P，safari浏览器依然不能保存iframe页面中的session。

原来safari的安全策略是，当cookie并未以第一方cookie保存过的（非iframe），将判断为不安全而直接拒绝。因此与IE的P3P有些不同

首先在iframe的页面中判断某个session值是否存在。如果不存在，使用js修改window.top.location跳到一个本域的setSession.PHP页面。
因为是用window.top.location打开，因此并非iframe去访问，且能以第一方cookie保存.
然后在setSession.php页面执行完set session后，会跳回A域名的页面。之后就能使用session而不失效了。

a.com/index.php
1
2
3
4
5
6
7
8
9
10
11
12
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">  
<html>  
 <head>  
  <meta http-equiv="content-type" content="text/html;charset=utf-8">  
  <title> domain A page </title>  
 </head>  
  
 <body>  
  <p>A Page</p>  
  <iframe src="http://b.com/index.php"></iframe>  
 </body>  
</html>
b.com/index.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
<?php  
header('P3P: CP="CURa ADMa DEVa PSAo PSDo OUR BUS UNI PUR INT DEM STA PRE COM NAV OTC NOI DSP COR"');  
session_start();  
  
$ua = $_SERVER['HTTP_USER_AGENT'];  
// 如果是safari  
if(strstr($ua, 'Safari')!='' && strstr($ua, 'Chrome')==''){  
    // 如果未设置第一方cookie  
    if(!isset($_SESSION['safari'])){  
        echo '<script type="text/javascript"> window.top.location="http://b.com/setSession.php"; </script>';  
        exit();  
    }  
}  
  
$_SESSION['code'] = md5(microtime(true));  
?>  
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">  
<html>  
 <head>  
  <meta http-equiv="content-type" content="text/html;charset=utf-8">  
  <title> domain B page </title>  
 </head>  
  
 <body>  
  <p>B Page</p>  
  <?php  
  if(isset($_SESSION['code'])){  
    echo 'code:'.$_SESSION['code'];  
  }  
  ?>  
 </body>  
</html>
b.com/setSession.php
1
2
3
4
5
6
<?php  
header('P3P: CP="CURa ADMa DEVa PSAo PSDo OUR BUS UNI PUR INT DEM STA PRE COM NAV OTC NOI DSP COR"');  
session_start();  
$_SESSION['safari'] = 1;  
header('location:http://a.com/index.php');  
?>

发表于 | 分类于 | 阅读次数:

最近刷 leetcode 遇到了一道题目，没有什么头绪，看了答案说是需要用到动态规划，
刚好对动态规划也没有学习过，就去查阅了一些相关的文章，这里记录一下心得和体会。
分享一下我看的这篇文章，感觉整体上讲的还是挺不错的，由浅入深(http://www.hawstein.com/posts/dp-novice-to-advanced.html)[http://www.hawstein.com/posts/dp-novice-to-advanced.html]。

这里我还是用三段式来学习一个新的知识。

是什么

动态规划是一种思想，并没有一种具体的实现方式，它在我们求解一些问题的时候可以给我们提供一个思路。动态规划需要我们学会如何拆分问题。
通常这些问题会具有以下特征：每一个阶段的决策会影响到后面的决策，

为什么

为什么要用动态规划结果就很显而易见了，因为我们需要一种较为高效的方式来寻找到最优解。

怎么用

要用好这一种思想，最重要的就是要学会如何拆分问题，当我们把问题拆分出来了，整个解决思路就自然而然的寻找到了。

动态规划最终要做的就是找到状态定义和状态转移方程。

这里拿一个简答的动态规划的题目做例子。有三种硬币，1，3，5 元，最少需要多少硬币能够达到总数n元

1、状态定义

计算机的本质是一个状态机，内存里存储的所有数据构成了当前的状态，CPU只能利用当前的状态计算出下一个状态。

我们可以设n元需要的最少硬币数为d(n),这就可以看做是一个状态, 显然 d(0) = 0, d(1) = 1,

d(2) 可以被转化成 d(1) + 1 = 2

d(3) 可以被转化成 d(3 - 1) + 1 = d(2) + 1 = 3 和 d(3 - 3) + 1 = d(0) + 1 = 1, 显然后者更小

d(4) 可以使被转化成 d(4 - 1) + 1 = d(3) + 1 = 2 和 d(4 - 3) + 1 = d(1) + 1 = 2, 两者一样大

d(5) 可以被转化成 d(5 - 5) + 1 = d(0) + 1 = 1、d(5 - 3) + 1 = d(2) + 1 = 3、d(5 - 1) + 1 = d(5) + 1 = 3,显然1最小

2、状态转移方程

我们可以把 d(n) 看做是 d(n) = min(d(n - Vi) + 1); n - Vi >= 0; Vi = [1, 3, 5];

n d(n)
0 0
1 1
2 2
3 1
4 2

总的来说，动态规划需要我们找到问题的子问题，再从子问题找到状态转移方程，最后找到解决的方法

发表于 | 分类于 | 阅读次数:

call, apply, bind 算是比较面试中比较常问到的几个问题，再我们实际开发中也算是常用到的几个方法，了解清楚他们背后的运行机制和原理对一个前端开发者来说也就十分的必要了。

用法

先来看看他们各自的用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

var petter = {
    name:'petter',
};

function say(text, color) {
    console.log(this.name + ':' + text + ',' + color);
}

// call 的用法
say.call(petter, 'call', 'red');

// apply 的用法
say.apply(petter, ['call', 'red']);

// bind 的用法
var petter_say = say.bind(petter, 'call');
petter_say('red');

call 和 apply的区别只是在第二参数，他们第一个参数都是用于改变函数this的指向，call 后面需要按顺序传入函数所需的多个参数， apply 则需要将函数所需的参数放入数组中传给apply的第二参数。

bind 和他们又很不一样，bind会返回一个改变了this的新的函数，后面和call一样，你可以把所有参数提前传入，也可以后面再把参数传入。

原生实现

了解他们各自的用法之后，我们也可以自己通过原生的代码去实现上面的方法

call 的实现

1
2
3
4
5
6
7
8
9
10
11
12

Function.prototype.my_call = function(new_this, ...params) {
    // 用来做唯一索引用的，也可以不用symbol，为了安全用symbol能够保证外面绝对无法访问
    // 整个原理是需要把方法挂载到传入的对象上去，然后通过这个对象去调用用这个函数
    const fn_symbol = Symbol('fn');
    if (new_this === null || new_this === undefined) {
        new_this = window; // 传入null或者undefined的时候需要让this指向window
    }
    new_this[fn_symbol] = this; // 这里的this指向的是这个方法
    new_this[fn_symbol](...params); 
    delete new_this[fn_symbol];
}

apply 的实现

实现了call之后，apply 的实现也是类似的

1
2
3
4
5
6
7
8
9
10
// 唯一的区别就是这里的params不需要展开运算符
Function.prototype.my_apply = function(new_this, params) {
    const fn_symbol = Symbol('fn');
    if (new_this === null || new_this === undefined) {
        new_this = window;
    }
    new_this[fn_symbol] = this;
    new_this[fn_symbol](...params); 
    delete new_this[fn_symbol];
}

bind 的实现

bind 和 call 有点类似，但又不太一样，bind 会返回一个新的函数，所以我们得保存传入的this然后返回一个新的函数出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Function.prototype.my_bind = function(new_this, ...params) {
    const fn_symbol = Symbol('fn');
    if (new_this === null || new_this === undefined) {
        new_this = window;
    }
    new_this[fn_symbol] = this;
    return function(...new_params) {
        new_this[fn_symbol](...[...params, ...new_params]);
    };
}

// 或者可以借助call来实现
Function.prototype.my_bind_c = function(new_this, ...params) {
    const fn = this;
    return function (...new_params) {
        fn.call(new_this, ...params, ...new_params);
    };
}

现在我们可以更好的去理解为什么bind之后的方法无法再去改变他的this了，因为闭包的关系，传入的new_this我们是无法再去改变他的指向的.

发表于 | 阅读次数:

在使用ts中我们经常会需定义函数的接口，例如

1
2
3
4
5
6
7
8
9
10
11
12

interface GetParam {
(key:string):string;
}

const getParam:GetParam = function(key) {
    const config = {
        config1:'config1',
        config2:'config2',
    };
    return config[key];
}

但有时候我们需要我们的方法，根据我们传入的参数，来返回不同的类型,例如我们可以这样子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

interface GetParam {
  (key:string|string[]):string|string[];
}

const getParam:GetParam = function(key) {
  const config = {
    config1:'config1',
    config2:'config2',
  };
  if (typeof key === 'string') {
    return config[key];
  } else {
    const result:string[] = [];
    key.forEach((item) => {
      result.push(config[item]);
    });
    return result;
  }
}

这样写会存在一个问题，就是我们在使用这个方法的时候，我们是明确知道传入字符串的时候返回的是字符串，传入数组的时候返回的是数组。
但是这样写接口我们调用的时候ide并不能准确的帮我们识别类型。我们可能需要这样去调用方法才能让ide做类型推断。

1
2

const config1 = getParam('config1') as string;

为了应对这种情况，我们可以使用ts 的函数重载，虽然这不是正真意义上的重载，但是能够帮助ide更好的去做类型推断。

我们只需要把接口改成这样就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
interface GetParam {
  (key:string):string;
  (keys:string[]):string[];
}

const getParam:GetParam = function(key:string|string[]) {
  const config = {
    config1:'config1',
    config2:'config2',
  };
  if (typeof key === 'string') {
    return config[key];
  } else {
    const result:string[] = [];
    key.forEach((item) => {
      result.push(config[item]);
    });
    return result;
  }
}


const config1 = getParam('config1');

这样当我们传入参数为字符串的时候，ide就能自动的帮我们推断出返回的值是字符串。

发表于 | 阅读次数:

最近准备开发一个 react-native 的组件，需要通过 yarn link 的方式进行开发，但是在编译的时候就会要么识别不到这个包，要么识别包里面的依赖

查了很久资料才发现这个问题的所在 https://github.com/facebook/metro/issues/1 ,symlinks 在 react-native 是无法正常运行的

后来终于找到了解决方案 https://www.bram.us/2018/03/10/working-with-symlinked-packages-in-react-native/

首先我们先安装

1
yarn global add wml

然后用 wml 将我们的组件库链过来

1
wml add ~/my-package ~/main-project/node_modules/my-package

在在我们的 main-project 下执行

1
2

wml start

发表于 | 分类于 | 阅读次数:

根据功能划分，操作符可以分为以下几类

  • 创建类
  • 转化类
  • 过滤类
  • 合并类
  • 多播类
  • 错误处理类
  • 辅助工具类
  • 条件分支类
  • 数学和合计类

创建类

操作符 功能
create 直接创建观察者
of 产生同步的数据流
range 产生一个数值范围内的数据流
generate 以循环方式产生数据
repeat和repeatWhen 重复的产生数据
empty 产生空数据
throw 产生直接出错的数据
nerver 永不完结的数据
interval 和 timer 间隔给定时间持续产生数据
from 从数组等枚举类型产生数据
fromPromise 从promise对象产生数据
fromEvent 和 fromEventPattern 从外部事件产生数据
ajax 从ajax 产生数据
defer 延迟产生数据

合并类

注意：名字中含有all的都是处理高阶数据流的

操作符 功能
concat 和 concatAll 把多个数据流以首尾方式合并
merge 和 mergeAll 把多个数据流以先到先得的方式合并
zip 和 zipAll 把多个数据流以一一对应方式合并
combineLatest、combineAll 和 withLatestFrom 持续合并多个数据流最新的数据
race 从多个数据流中选取第一个产生的数据流
startWith 在数据流前面添加一个指定数据
forkJoin 只获取多个数据流最后产生的那个数据
switch 和 exhaust 从高阶数据流中切换数据

辅助类

操作符 功能
count 统计数据流中产生的所有数据的个数
max 和 min 统计数据流中最大的和最小的数据
reduce 和数据中的reduce操作类似
every 判断是否所有数据满足某个条件
isEmpty 判断一个数据流是否为空
defaultEmpty 如果一个数据流为空就默认产生一个指定数据

过滤类

操作符 功能
filter 过滤掉不满足条件的数据
first 获取满足判定的第一个数据
last 获取满足判定的最后一个数据
take 从数据源中选取最先出现的若干数据
takeLast 从数据源中选取最后出现的若干数据
takeWhile 和 takeUntil 从数据源中选取若干数据直到某种情况发生
skip 忽略最先出现的若干数据
skipWhile 和 skipUntil 从数据流中忽略数据直到满足某种条件
throttleTime、debounceTime 和 auditTIme 基于时间的数据流量筛选
throttle、debounce 和 audit 基于数据内容的筛选
distnct 删除重复数据
distnctUntilChanged 和 distnctUntilKeyChanged 删除重复的连续数据
ignoreElements 忽略数据流中所有数据
elementAt 获取指定位置出现的数据
single 判断是否只有一个数据满足条件

转化类

操作符 功能
map 映射每个数据，和数组的map类似
mapTo 将所有数据映射为同一个数据
pluck 提取数据流中每个数据的某个字段
windowTime、windowCount、windowWhen、windowToggle和window 产生高阶Observable对象
bufferTime，bufferCount、bufferWhen、bufferToggle和buffer 产生数组构成的数据流
concatMap、mergeMap、switchMap、exhaustMap 映射产生高阶Observable对象然后合并
scan 和 scanMerge 产生规约运算结果的数据流

异常处理

操作符 功能
catch 捕获上游产生的error
retry 和 retryWhen 当上游产生错误时，尝试重试
finally 无论是否出错都要进行的一些操作

多播

操作符 功能
multicast 灵活选取subject对象进行多播
publishLast 只多播数据流中最后一个数据
publishReplay 对数据流中给定的数量进行多播
publishBehavior 拥有默认数据的多播

发表于 | 分类于 | 阅读次数:

xss 和 csrf 可以说是最常见的攻击手段，面试也很大概率会问到这两个东西，下面我们可以了解一下他们是什么。

xss

xss 也叫跨站脚本攻击。是一种非常常见的攻击手段，我们可以把它看做是一个html注入攻击。和我们长听到的sql注入非常的类似。

常见的 xss 攻击方式。

通过 url 注入

比方说A网站有个内容是通过url中的参数来显示的，并且没有对其做任何的xss防范，那么攻击者就可以通过url将攻击脚本注入到网页中，然后将带有攻击脚本的url进行特殊处理，然后将处理后的url发给第三者完成攻击

通过一些表单输入做注入

最常见得就是富文本评论，因为需要保持html的原样，所以就很容易被人注入攻击脚本，当其他用户访问了被注入攻击脚本的页面的时候就会被攻击。

防御方式

对xss的防御思路，主要有两种，可以看我们具体的需求来决定使用哪一种。

http-only

这个东西主要针对的是cookie，在 xss 注入的时候可能会有js盗取cookie，我们可以将 cookie 设置为http-only,这样 js 就会无法操作cookie，不过这也仅仅防范了这一种可能性，还是无法防御其他手段的 xss 攻击

设置黑名单

通过设置黑名单，将一些特殊的字段进行删除或者转译来达到防御的手段，比方说 <script>，黑名单的实现比较简单，但是 xss 攻击的花样非常的多，我们很难知道所有的攻击手段，很有可能会造成攻击漏洞。

设置白名单

白名单的思路也很简单，我们根据我们的需求设置允许使用的标签和属性，然后把不在白名单中的标签或者属性都去掉，在实现上会比黑名单复杂一点，需要把进行防御的内容转为树状结构进行遍历然后处理掉白名单以为的标签和属性。

CSP (Content Security Policy)

内容安全策略，用于指定哪些内容可以被执行。通过设置 Content-Security-Policy 响应头我们可以设置哪些内容是可以执行的。

csp 本质上也是一个白名单，我们通过配置告诉浏览器哪些内容是可以安全执行的。

具体的配置我们可以去 MDN 上查看 https://developer.mozilla.org/zh-CN/docs/Web/HTTP/Headers/Content-Security-Policy__by_cnvoid/default-src

相关知识可以看看阮老师的这篇文章 http://www.ruanyifeng.com/blog/2016/09/csp.html

CSRF

csrf 也叫跨站请求伪造。攻击方式就是第三方的网站可以在用户不知情的情况下发送请求到被攻击的网站上。比方说网站A，我们有一个网站B会偷偷帮用户发请求到A，发送的时候浏览器会自动的挟带上A的cookie，而A又是对cookie做验证，这就导致了 csrf 攻击

防御方式

sameSite 可以禁止来自第三方网站的请求携带 cookie，他有两个值

  • Strict 禁止一切请求携带 cookie
  • Lax 允许一部分请求携带 cookie，比方说链接

不过目前这还是一个试验箱的属性，只有部分浏览器支持这个值。

增加验证

验证的方式有很多，可以有如下几种

  • 验证码，不过验证码可能会带来比较不好的用户体验
  • token，在表单或者请求头中增加一个token做验证
  • referer验证，referer需要在后端进行，这个单词其实拼写错误的，原本应该是referrer，我们可以通过referer来判断请求是否来源于当前网站，如果不是则判定为非法请求

发表于 | 分类于 | 阅读次数:

如今模块化的编程方式，已经成为了每个前端程序员必须掌握的一门技术，es6 也带了 import 和 export 两个新语法，搞清楚他们的作用和用法也是我们所必须要学习的。

需要注意的一些概念

  • 首先，es6 的模块是基于文件的模块，在浏览器端还不支持 import 和 export 语法，我们开发过程使用，也是需要通过打包工具将其编译为 es5 的语法才能使用。
  • es6 的模块是单利的，也就是说，模块只有一个实例，每次我们 import 的时候，其实都是同一个对象。如果需要有多个模块实例的话，则需要通过 export 一个工厂方法来实现

语法

es6 模块主要就是两个新的关键字 import 和 export

named export (命名导出)

1
2
3
4
5
6
7
8
9
10
11
function test() {
}

var awesome = 'awesome';

var name = 'test'

export {
  test,
  awesome
};

在模块内作用域都是局部的，只要没有 export 出去，外面就无法访问到。

我们也可以在导出的时候给成员重命名 export { test as try }。

模块是单例的

1
2
3
4
5
6
7
8
9
10
11
// test.js
let name = 'test';
export {name};

// index.js
import { name } from './test';
name = 'index change it';

// getname.js
import { name } from './test';
console.log(name); // index change it

当我们在 index.js 修改了从 test.js import 进来的 name，之后我们再在 getname.js 中 import 它，这时候我们就会发现这个值就被修改了。

这是因为在 import 的时候，我们本质上可以看做是引了一个对变量的指针。虽然有这个特性，但是我们应该避免使用这个特性，
因为这会增大我们程序的复杂度，会使得程序变得难以维护，追踪变量在哪里被修改是非常麻烦的。

export default (默认导出)

1
2
3
// test.js
const name = 'test';
export default name;

当文件中有默认导出的时候我们可以通过下面几种方式得到这个值

  • import name from './test' 这个 name 也可以叫其他名字比方说import test from './test' 这里 name 和 test 其实指的是同一个东西

  • import { default as name } from './test 这里的 default 不能省略

namespace import (命名空间引入)

1
2
import * as test from './test'
console.log(test.name);

es6 的设计理念是让我们按需引用，不过还是看具体的需要，如果引入的模块比较小的话，
我们还是可以通过使用命名空间引入的方式来进行引用。

import 立执行的函数

1
import 'rxjs/operators/add';

有时候我们会看到一些类似于上面的用法，这些一般加载的是一些立执行的函数，一般我们也要避免使用这种，因为他会导致你的代码变得难以理解，后来的 rxjs6 也修改了这种用法

发表于 | 分类于 | 阅读次数:

最近准备学习一下算法的一些知识，这里做一下笔记。

我们经常耳熟能详的一些算法，例如快排，归并，堆排序等，都是用比较的操作来进行排序的，这几种排序方法都可以达到上界 O(n log n)。

现在我们来了解一些不常用的线性排序算法，这些算法时间复杂度可以达到 O(log n)，不过都是在牺牲空间换取时间，一般来说我们基本不会用到这几种算法，只是给我们开阔一下思维方式。

计数排序

基础思想

计数排序的基本思想就是，对数组中每一个元素 x，确定出小于 x 的个数，然后我们就可以根据这一信息得到每一个元素在数组排列的位置。

时间复杂度：O(n); 空间复杂度：O(n+k)

步骤

例如给定数组

1
2

var arr = [6,4,5,6,3,7,4]

第一步：

通过一次循环得到数组中最大的数为 7，然后初始化一个用于记录的数组，他的数组长度和 arr 的最大的数一样大，
最后得到的数组将会是

1
2

var record_arr = [0,0,0,0,0,0,0]; // 数组大小为7

第二步：

遍历 arr，用record_arr记录每个数字出现的次数

1
2
3
4

for (var i = 0 ; i < arr.length; i ++;) {
    record_arr[arr[i]] ++;
}

第三步：

按顺序遍历出 record_arr ，这里有两种做法，我们先来看一下比较简单粗暴的方法。

1
2
3
4
5
6
7
8
9
10

var result = [];

for (var i = 0 ; i < record_arr.length; i ++;) {
    if (record_arr[i] > 0) {
        for (var j = 0; j < record_arr[i]; j++) {
            result.push(i);
        }
    }
}

网上给的基本都是这种方法，思维方式可能会比较绕一点

1
2
3
4
5
6
7
8
9

for (var i = 1 ; i < record_arr.length; i++;) {
    record_arr[i] += record_arr[i-1]; // 这样我们就可以知道每个位置的元素，前面有多少个元素了，然后就可以通过前面元素的数量推断出挡墙这个元素所处的位置
}
var result = [];
for (var i = arr.length - 1; i >=0; i-- ) {
    result[record_arr[arr[i]] - 1] = arr[i]; // 通过元素前的数量将元素插入到指定的位置
    record_arr[arr[i]]--;
}

两个方法效率都一样，只是思维的方式不同，可以都尝试理解一下。

最后整合代码之后是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

function count_sort(arr) {
    var max_value;
    var result = [];

    max_value = arr.reduce((accumulator, current) => { return accumulator > current ? accumulator : current; })

    var record_arr = (new Array(max_value + 1)).fill(0);

    arr.forEach((value) => {
        record_arr[value] ++;
    })

    for (var i = 1 ; i < record_arr.length; i++) {
        record_arr[i] += record_arr[i-1];
    }


    var result = [];
    for (var i = arr.length - 1; i >=0; i-- ) {
        result[record_arr[arr[i]] - 1] = arr[i];
        record_arr[arr[i]]--;
    }
    return result;
}

此算法的缺陷也非常明显，根据待排数组中最大值，可能会导致大量无用的内存占用，而且无法对负数和小数进行排序，所以基本上根本看不到会有使用这个算法的地方，但是算法思想还是可以借鉴的。

基数排序

基础思想

从个位到十分位，再到百分位，依次进行排序，每次排序必须采用时间稳定的算法，可以采用上面的计数排序。

时间复杂度：O(n); 空间复杂度：O(n+k)

步骤

第一步：

给定一个数组

1
2

var arr = [23,40,12,145];

先将个位排序

1
arr = [40,12,23,145];

再排十位

1
arr = [12,23,40,145];

最后排百位

1
arr = [12,23,40,145];

桶排序

基础思想

将区间[0,1)分成n个相同大小的子区间，或称为桶。然后将n个输入元素分布到各个桶中去。每个桶中的元素用一个链表来存储。先对每个桶中的数据进行排序，然后遍历每个桶，按照次序把各个桶中的元素列出来即可。

桶排序假设输入数据服从均匀分布，因此每个桶中的数据量相差不多，平均情况下它的时间代价为O(n)。

时间复杂度是O(n)。空间复杂度是O(n)。需要一个辅助数组来存放桶（链表）。

发表于 | 分类于 | 阅读次数:

RxJs

最近在研究一下 RxJs ，这是一个非常强大的用于响应式编程的库，学习难度也比较高，想要学习的人最好要对发布订阅模式和函数式编程比较熟悉，这样学习起来就会更加的快捷顺畅。

函数式编程的教程网上有很多，推荐大家可以看这个 https://github.com/llh911001/mostly-adequate-guide-chinese, 英语能力比较强的人可以去看一下英文原版的教程。

在有了对函数式编程和发布订阅模式的了解之后，学习 RxJs 才会比较的容易。因为这里面充斥着大量的概念。

用途

要学习一个东西的时候，我最好带着目的去学习，所以首先我得明白我们为什么要花这么大的功夫去学习和使用这个库。

  • 处理比较复杂的异步逻辑的时候，它的一套规范，能让你很容易的写出高可维护，高拓展性的代码
  • 函数式编程，这是一个非常棒的编程思想，在开发大型应用到的时候能够加强代码的可维护性。
  • 处理多并发异步操作的时候，能够更加简单明了

基本概念

学习 RxJS 我们先要了解清楚其中的几个基本概念。

Observable （被观察者)

这是 RxJS 最核心的部分，一个可被订阅的对象。

Observer （观察者）

这个单词和 Observable 非常的相似，用于订阅Observable，RxJs 也提供了他的实现接口

1
2
3
4
5
6
7

interface Observer<T> {
  closed?: boolean;
  next: (value: T) => void;
  error: (err: any) => void;
  complete: () => void;
}
  • closed：会在Observer 取消订阅的时候调用
  • next：是用来接收Observable发出来的消息
  • error：用来接收Observable发出的error
  • complete：当 Observable 执行complete的时候会调用

Subscription （订阅）

当 Observable 添加订阅的时候会返回一个 Subscription，主要用来取消订阅的

Operators （操作符）

操作符，使用函数式编程风格的纯函数，我们可以放心大胆的使用它而不用去担心对外部环境的影响

Subject （主体）

可以看做是一个特殊的 Observable，能够同时将信息推送给多个Observer，而Observable一个subscribe只会发送给一个Observer。

Schedulers （调度器）

调度器控制着何时启动 subscription 和何时发送通知，可以用来实现异步的通知。

一些用法

简单用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 创建Observables
var observable = Rx.Observable.create(function subscribe(observer) {
    observer.next(‘any value’)
});

// 创建Observer
vat observer = {
    next:(val) => {
        console.log(val);
    },
};

// 添加订阅
var subscription = observable.subscribe(observer); // 输出any value

// 取消订阅
subscription.unsubscribe();

Subject 订阅

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 新建主体
var subject = new Rx.Subjecgt();

var observerA = {
    next:(val) => {
        console.log('this is ObserverA', val);
    }
};

var ObserverB = {
    next:(val) => {
        console.log('this is ObserverB', val);
    }
};

subject.subscribe(ObserverA);
subject.subscribe(ObserverB);

subject.next(1);
// 输出
// this is ObserverA 1
// this is ObserverB 1

多播的 Observables

Observable 只能给一个 Observer 发送消息，而多播的 Observables 可以给多个 Observer发送消息

Observables 底层本质上是用 Subject 让多个 Observer 观察到同一个 Observable 执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

var source = Rx.observable.from([1,2]);
var subject = new Rx.Subject();
var multicasted = source.multicast(subject);

// 本质上是在 subject.subscribe();
multicasted.subscribe((val) => {
    console.log('Observer A', val);
});
multicasted.subscribe((val) => {
    console.log('Observer B', val);
});

// 本质上是 source.subscribe(subject);
multicasted.connect();

refCount 引用计数

有时候我们想要当第一个订阅者添加的时候自动的去 connect，在最后一个订阅者取消订阅的时候，取消连接。

我们可以使用 ConnectableObservable 的 refCount() 方法来生成Observable，这个Observable 在有第一个订阅者的时候自动的进行connect，然后在最后一个订阅者取消订阅的时候停止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

var source = Rx.Observable.interval(500); // 此方法会在给定的时间间隔发出连续的数字
var subject = new Rx.Subject();
var refCounted = source.multicast(subject).refCount();

var subscriptionA = refCounted.subscribe({
    next:(val) => {
        console.log('OberverA:',val);
    },
});
var subscriptionB = refCounted.subscribe({
    next:(val) => {
        console.log('OberverB:',val);
    },
});
setTimeout(() => {
    subscriptionA.unsubscribe();
}, 600);

setTimeout(() => {
    // 此时 共享的Observable 将会停止，因此refCounted后面不会再有订阅者
    subscriptionB.unsubscribe();
}, 1200);

BehaviourSubject

BehaviourSubject 是 Subject 的一个变体，他会将当前值传给新新订阅的订阅者。

1
2
3
4
5
6
7
8
9
10

var subject = new Rx.BehaviourSubject(0); // 给与一个初始值

var observer = {
    next:(val) => {
        console.log(val)
    }
};

subject.subscribe(observer);// 输出 0

ReplySubject

ReplySubject 可以缓存值，你可以指定缓存多少个值发送给新的订阅者，也可以缓存多少时间内的值发送给新的订阅者

1
2
3
4
5
6
7
8
9
10
11
12
13

var subject = new Rx.ReplySubject(2);// 缓存2个值

subject.next(0);
subject.next(1);
subject.next(2);

subject.subscribe({
    next:(val) => {
        console.log(val)
    }
});
// 输出1，2

AsyncSubject

只有当 Observable 执行 complete 的时候，AsyncSubject 才会将最后一个值发送给订阅者

1
2
3
4
5
6
7
8
9
10
11
12
13
14

var subject = new Rx.AsyncSubject();

subject.subscribe({
    next:(val) => {
        console.log(val);
    },
});

subject.next(1);
subject.next(2);
subject.next(3);

subject.complete(); // 这时候才会输出3

Operators 操作符

RxJs 提供了很多的操作符，他们都是基于函数式编程的思想实现的。在使用操作符的时候，他们并不会修改原先的 Observable，而是返回一个新的 Observable，这是一个无副作用的操作，大大提高了我们程序的可维护性。

根据原理，我们也可以自己定义一个操作符函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

var myOperator = function (observable) {
   // 这里我们只是返回一个新的 Observable ，这个Observable 会让输入的值都加1
   return Rx.Observable.create(function subscribe(observer){
        observable.subscribe({
            next:(v) => observer.next(v + 1);
        });
   });
};

var source = Rx.Observable.from([1,2]);
var observable = myOperator(source);

observable.subscripe((val) => {
    console.log(val);
});
// 输出2，3