一道赋值面试题引发的思考4

实现一个run方法,使得run(fucArr)能顺序输出1、2、3

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
const fucArr = [
next => {
setTimeout(() => {
console.log(1);
next()
}, 300)
},
next => {
setTimeout(() => {
console.log(2);
next()
}, 200)
},
next => {
setTimeout(() => {
console.log(3);
next()
}, 100)
}
]

var run = arr=>{



}

题目简析

我们观察 fucArr 每一个子项都具有如下结构:

  1. 接收一个方法 next
  2. 有一个计时器,计时器回调方法体内对应着相应的输出
  3. 输出结束调用 next 方法。

他们的差异就是:计时器时间逐个减少。

直接循环调用 3 个方法肯定是不可取的。为了能按序输出,函数的执行过程应该是上一个函数 console 之后, 再执行下一个函数,而接收的这个 next参数就是执行下一个方法的关键。因为是头到尾依次调用,我们就把fucArr 称之为一个队列。

思路一:递归

我们假象自己是个编译器,然后把执行的过程进行单步拆解。

  1. fucArr 是做先执行等待队列第一个,等待中的函数队列为原函数队列的slice(1);
  2. 等待next执行后,然后又执行等待函数队列的第一个函数,等待中的函数队列为原函数队列的slice(1);

听着是不是很像一个 递归 的过程,没错,那我们先用递归来实现一下

1
2
3
4
5
6
7
8
var run = arr => {
// 递归语句千万条,找到出口第一条,那咱们判断递归出口的条件就是等待队列为空if (arr.length === 0) return;
// 好的,一句话执行过程写完了
arr[0](() => run(arr.slice(1)));
}
run(fucArr)

// 1 2 3;

思路二

现在我们从递归的思路中跳脱出来,换种思路继续思考…..

上一个函数执行到某个时机触发了下一个函数的执行。

也就是说上一个函数 trigger,下一个函数才开始执行。

根据描述 trigger 实际上做的就是触发等待队列的第一个函数的执行,因此我们可以如下定义。

1
2
3
4
5
6
var run = arr => {
const trigger = () => {
if (arr.length === 0) return;
arr.shift()();
}
}

那么 trigger 何时进行调用呢?很显然, 上一个函数式通过next 去触发下一个函数调用,因此 trigger 应该就是函数接收的next,我们为了方便参数绑定需要重构一下咱们的等待队列函数。当然不要忘了,首次执行要手动trigger一下喔。

1
2
3
4
5
6
7
8
9
10
var run = arr => {
const trigger = () => {
if (arr.length === 0) return;
arr.shift()();
}
arr = arr.map(val => {
return() => val(trigger);
})
trigger();
}

其实做参数绑定还有一种更优雅一点的方式,bind,所以大家注意咯,bind不单单能绑定this喔。

我们可以稍微改动一下:

1
2
3
4
5
6
7
8
9
10
var run = arr => {
const trigger = () => {
if (arr.length === 0) return;
arr.shift()();
}
arr = arr.map(val => {
return val.bind(null, trigger);
})
trigger();
}

都9102年了,既然是前端面试那肯定少不了Promise 的对吧,那我们可不可以掺入一些Promise的元素在里面呢?答案是必然的。

根据Promise的特性,当本身状态改变,去触发then里的方法(这里不要深究这句话,意思了解就好)。是resolve 作为本身状态改动的方法。那状态改变是去做什么事呢?好的,没错trigger。那何时状态改变呢?上一个函数next调用的时候。

1
2
3
4
5
6
7
8
9
10
11
12
var run = arr => {
const trigger = () => {
if (arr.length === 0) return;
arr.shift()();
}
arr = arr.map(val => {
return() =>new Promise(resolve => {
val(resolve)
}).then(trigger);
})
trigger();
}

redux的思路

现在继续清空上面的思路,不要被干扰。

首先给 applymiddleware(以下简称amw)一个简单的定义,amw是接收若干个函数作为参数,最终会返回一个函数,这个函数调用,会按照顺序,依次执行前面作为参数传入的函数。为了不把问题复杂化,请接收我的误导引导,不要怀疑。

以下是作为参数传入的函数要求的结构以下称a结构:

1
2
3
4
store=>next=>action=>{
// dosomething...
next()
}

a结构在第一次调用时,会返回一个方法,第二次调用时返回第二个方法,我们先来看源码的一个操作过程。

1
const chain = middlewares.map(middleware => middleware(middlewareAPI))

首先是一层循环调用,使得函数体变为b结构:

1
2
3
4
next=>action=>{
// dosomething...
next()
}

这样做是为了以闭包的形式在 dosomething 中能够使用到 middlewareApi

根据b结构我们可以稍稍改变下原题 :

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
const fucArr = [
next => action => {
setTimeout(() => {
console.log(action++);
next(action)
}, 300)
},
next => action => {
setTimeout(() => {
console.log(action++);
next(action)
}, 200)
},
next => action => {
setTimeout(() => {
console.log(action++);
next(action)
}, 100)
}
]

var run = arr=>{



}
// 实现一个run方法,run方法接收fucArr为参数;返回一个函数,这个函数接收一个参数1,最终,依次输出1、2、3// run(fucArr)(1) => 1 2 3

变题相对于多了一个参数传递的过程,实际上我们需要顺序执行的其实是结构c:

1
2
3
4
action=>{
// dosomething...
next()
}

这些关键还是要如何构建每个函数接收的参数next

我们做如下假设,当fucArr只有一个函数时 返回的就应该是:

1
2
3
4
5
6
7
8
fucArr[0](()=>{}) // 为了避免报错,next应为一个空函数// 即:
action => {
setTimeout(() => {
console.log(action++);
//(()=>{}) 这玩意儿就是接收的next
(()=>{})(action)
}, 300)
}

fucArr有两个函数时返回:

1
2
3
4
5
6
7
8
fucArr[0](fucArr[1](()=>{}))
// 即:
action => {
setTimeout(() => {
console.log(action++);
fucArr[1](()=>{})(action)
}, 300)
}

当有三个函数的时返回:

1
fucArr[0](fucArr[1](fucArr[2](()=>{}))

仔细观察返回函数的结构发现,所有的函数都是接受上一个函数调用后的返回值(以下称模式1),最后一个函数接收的是一个空函数。我们尝试构建模式1:

1
2
3
4
5
6
// 首先初始想法模型是这样的
// 但是由于咱们是程序执行,不能像上面咱们描述问题的时候,继续往next里塞函数。
// 而在遍历到 next 的下一个函数的时当前是无法明确next应该是什么,因此我们需要将模式改变一下。
pre(next());
// 当遍历到next下一个节点时,把当前函数作为arg传入进来
arg=>pre(next(arg))

pre + next + 遍历,这三个关键词没错,就是reduce。因此:

1
2
3
var reduceResult = fucArr.reduce((pre,next)=> (...arg)=>pre(next(...arg)));
// 我们发现这个返回的还是一个 arg=>pre(next(arg)) 这样模式的函数,接收的参数任然是一个函数。
// 于是乎真的需要返回的函数其实是 return reduceResult(()=>{});

所以最终形态是

1
2
3
4
5
6
var run = arr=>{
var reduceResult = arr.reduce((pre,next)=> (...arg)=>pre(next(...arg)));
return reduceResult(()=>{});
}
run(fucArr)(1);
// 1 2 3

一个关于连续回调的面试题

递归

我们每次只执行数组中的第一个方法,同时,我们向next里面塞一个方法,这个方法会剔除掉数组中的第一个元素然后继续执行数组中“第一个方法”。(注意,这个方法是数组中的第二个方法)

1
2
3
4
5
var run = arr => {
if(arr.length === 0) return;
arr[0](() => run(arr.slice(1)));
}
run(fucArr)

async await

上面的问题其实就是异步串行,async中利用for配合await可以比较简单的写出异步串行:

1
2
3
4
5
6
7
8
async function go(){
for(let i=0;i<fucArr.length;i++){
await new Promise(resolve=>{
fucArr[i](resolve);
})
}
}
go();

reduce Promise.resolve()

在我的另外一篇文章中,有介绍reduce和Promise.resolve()的妙用, reduce使用Promise.resolve()构造连续Promise回调,它们也是解决异步串行的一个方法:

1
2
3
4
5
6
7
8
function go(){
fucArr.reduce((prev,next)=>{
return prev.then(()=>new Promise(resolve=>{
next(resolve);
}))
},Promise.resolve());
}
go();

map Promise.resolve()

和上的思路差不多,但是写法略有不同:

1
2
3
4
5
6
let resolve=Promise.resolve();
fucArr.map(item=>{
resolve=resolve.then(()=>{
return new Promise(item);
})
})

Generator

利用Generator方法也是很容易解决这种异步串行问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function* go(){
for(let i=0;i<fucArr.length;i++){
yield new Promise(resolve=>{
fucArr[i](resolve);
});
}
}
let g=go();
let run=(p)=>{
if(!p.done){
p.value.then(()=>{
run(g.next())
})
}
}
run(g.next());

reduceRight

我们假设fucArr中的三个方法分别为f1,f2,f3,那么f1(f2(f3(()=>{})))肯定是可以满足要求的,reduceRight就是把这写方法拼凑成f1(f2(f3(()=>{})))这种形式。

1
2
3
4
5
fucArr.reduceRight((prev, next) => {
return() => {
next(prev)
}
}, () => {})()

让我们看看reduceRight执行的具体过程:

reduce

上面讲了如何用reduceRight去拼凑f1(f2(f3(()=>{})))这种形式,其实用reduce也可以拼凑的:

1
2
3
4
5
6
const run = arr => arr.reduce((prev, next) => {
return (...args) => {
prev(() => next(...args))
}
});
run(fucArr)(() => {});

它这种拼凑方式我认为是最复杂的,下面看看具体步骤:

虚线框表示在闭包内,剪头代表参数归谁.

总结

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
<!DOCTYPE html>
<html>

<head>
<meta charset="UTF-8">
<title></title>
</head>

<body>
<script type="text/javascript">
const fucArr = [
next => {
setTimeout(() => {
console.log(1);
next()
}, 900)
},
next => {
setTimeout(() => {
console.log(2);
next()
}, 500)
},
next => {
setTimeout(() => {
console.log(3);
next()
}, 100)
}
]

var run1 = arr => {
(async function(arr) {
for(let i = 0; i < arr.length; i++) {
await new Promise(resolve => {
arr[i](resolve);
});
}
})(arr);
};

//run1(fucArr);

var run2 = arr =>
arr.reduce(
(next, v) =>
next.then(() => new Promise(res => {
v(res);
})),
Promise.resolve()
);

//run2(fucArr);

function run3(fucArr) {
if(!fucArr.length) return;
fucArr.shift()(function() {
run3(fucArr);
})
}

//run3(fucArr)

var run4 = (arr) => arr.reduceRight((p, v) => v.bind(this, p), () => {})();
//run4(fucArr)

async function run5(arr) {
for(var item of arr) {
await new Promise((res) => {
item(res);
})
}
}

//run5(fucArr);

const run6 = arr =>
arr.reduce((prev, next) =>
(...args) => prev(() => next(...args))
)(() => {});
run6(fucArr); // redux思想

var run7 = arr=> arr.length && arr.shift()(() => run(arr))
</script>
</body>

</html>

自定义事件 new CustomEvent & document.createEvent

new CustomEvent

最近一个项目中需要模拟发起事件,在mdn中发现了这个构造方法CustomEvent

1
2
//构造方法 CustomerEvent() 创建一个新的 CustomEvent 对象。
event = = new CustomEvent(typeArg ,customEventInit)

参数说明:

  • typeArg是DOMString代表事件的名称。一个表示 event 名字的字符串
  • customEventInit(可选):一个字典类型参数,有如下字段
    • detail, 可选的默认值是 null 的任意类型数据,是一个与 event 相关的值
    • bubbles 一个布尔值,表示该事件能否冒泡。 来自 EventInit。注意:测试chrome默认为不冒泡。
    • cancelable 一个布尔值,表示该事件是否可以取消。 来自 EventInit

发起事件用法

1
new CustomEvent(eventName, params);

创建一个自定义事件

1
const event=new CustomEvent('mock-event');

传递参数

这里值得注意,需要把想要传递的参数包裹在一个包含detail属性的对象,否则传递的参数不会被挂载?(这里不太确定,我试过传id和params都不会生效)

1
2
3
4
5
function createEvent(params, eventName = 'mock-event') {
return new CustomEvent(eventName, { detail: params });
}

const event = createEvent({ id: '0010' });

发起事件调用dispatchEvent方法发起事件,传入你刚才创建的方法

1
2
3
4
5
6
window.dispatchEvent(event);

//监听事件
window.addEventListener('mock-event', ({ detail: { id } }) => {
console.log('id',id) // 会在控制台打印0010
});

DEMO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const ev = document.getElementById('main');    
const event = new CustomEvent('eventName', {         
detail: {               
message: 'Hello World',
 time: new Date()         
},
bubbles: true,
cancelable: true,
    
});    
ev.addEventListener('eventName', function(e) {      
console.log(e);    
}, );    
setTimeout(function() {      
ev.dispatchEvent(event); //给节点分派一个合成事件
}, 1000);

document.createEvent

首先创建自定义事件对象

1
var event = document.createEvent("CustomEvent");

然后初始化事件对象

1
event.initCustomEvent(in DOMString type, in boolean canBubble, in boolean cancelable, in any detail);

其中,第一个参数为要处理的事件名
第二个参数为表明事件是否冒泡
第三个参数为表明是否可以取消事件的默认行为
第四个参数为细节参数

例如:

1
event.initCustomEvent("test", true, true, {a:1, b:2})

表明要处理的事件名为test,事件冒泡,可以取消事件的默认行为,细节参数为一个对象{a:”test”, b:”success”}

最后触发事件对象

1
2
3
4
5
6
7
8
document.dispatchEvent(event);

//当然我们需要定义监控test事件的处理程序
document.addEventListener("test", function(e){
var obj = e.detail;
alert(obj.a + " " + obj.b);
});
// "test success"

综合

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//1
function dispatchEvent(element, type, data) {
var event; // Event and CustomEvent on IE9-11 are global objects, not constructors

if(isFunction(Event) && isFunction(CustomEvent)) {
event = new CustomEvent(type, {
detail: data,
bubbles: true,
cancelable: true
});
} else {
event = document.createEvent('CustomEvent');
event.initCustomEvent(type, true, true, data);
}

return element.dispatchEvent(event);
}

//2
(function() {
if (typeof window.CustomEvent === 'undefined') {
function CustomEvent(event, params) {
params = params || {
bubbles: false,
cancelable: false,
detail: undefined
};
var evt = document.createEvent('Events');
var bubbles = true;
for (var name in params) {
(name === 'bubbles') ? (bubbles = !!params[name]) : (evt[name] = params[name]);
}
evt.initEvent(event, bubbles, true);
return evt;
};
CustomEvent.prototype = window.Event.prototype;
window.CustomEvent = CustomEvent;
}
})();
//触发如下:
document.dispatchEvent(event);

//3
if (!window.CustomEvent) {
window.CustomEvent = function(type, config) {
config = config || { bubbles: false, cancelable: false, detail: undefined};
var e = document.createEvent('CustomEvent');
e.initCustomEvent(type, config.bubbles, config.cancelable, config.detail);
return e;
};
window.CustomEvent.prototype = window.Event.prototype;
}
//触发的时候
var dispatch = function(event) {
var e = new CustomEvent(event, {
bubbles: true,
cancelable: true
});
//noinspection JSUnresolvedFunction
window.dispatchEvent(e);
};

数组拍平,扁平化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
let arr = [
[
['1-7', '2-6'],
'4-6',
[
['2-0', '1-4'],
['3-9'],
'4-5',
],
]
]

// Q1: 完成数组 flat 函数
// const flat= arr => [].concat(...arr.map(v => Array.isArray(v) ? flat(v) : v));

function flat(arr) {
// code

return arr
}

arr = flat(arr);
console.log(arr);

递归

如果有对递归不太熟悉的同学,可以看看我的读书笔记 【算法图解】读书笔记:第3章 递归

递归的核心就在于两步:找到基线条件和递归条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function flat(arr) {
const result = []; // 利用闭包缓存我们的结果
function _flat(arr) {
arr.forEach(element => {
if(Array.isArray(element)) { // 递归条件
_flat(element);
} else { // 基准条件
result.push(element); // 将符合结果的值推入我们的结果数组中
}
})
}
_flat(arr);
arr = result;
return arr;
}

迭代 - 广度优先搜索

这个思路是我借鉴《图解算法》中广度优先搜索算法章节写的。

1.创建一个数组,保存结果
2.创建一个队列
3.初始化
4.使用 while 循环去遍历 list 里面的每一项
5.将第一项推出队列

  • 如果是数组,将子项依次推入队列
  • 如果是字符串,将子项推入结果

6.当 list 长度为0时候,遍历完成

但是广度优先搜索的结果是不保证顺序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function flat(arr) {
const result = []; // 利用闭包缓存我们的结果
function _flat(arr) {
arr.forEach(element => {
if(Array.isArray(element)) { // 递归条件
_flat(element);
} else { // 基准条件
result.push(element); // 将符合结果的值推入我们的结果数组中
}
})
}
_flat(arr);
arr = result;
return arr;
}

投机取巧的 toString

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// [1,2,3,[44,55,[66,77]]].toString().split(",")
// [1,2,3,[44,55,[66,77]]].join().split(",")

// [1,2,3,[44,55,[66,77]]].flat(2)
// ["1", "2", "3", "44", "55", "66", "77"]

// 首页你得确定你的数据里面没有字符串 ',' 哦
function flat(arr) {
arr.toString().split(',')
return arr;
}

// or
// 异曲同工
function flat(arr) {
arr.join(',').split(',')
return arr;
}

迭代 - 深度优先搜索

原理与广度优先搜索类似,通过模拟栈的行为去遍历数组。好处是能够保证有序输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function flat(arr) {
let ret = [];
let s = []; // 模拟栈的行为
if (arr.length > 0) {
for (let i = arr.length - 1; i >= 0; i--) { // 先进后出
s.push(arr[i]);
}
}
while (s.length > 0) { // 当栈空了,遍历完成
let cur = s.pop();
if (Array.isArray(cur)) {
for (let i = cur.length - 1; i >= 0; i--) {
s.push(cur[i]);
}
} else {
ret.push(cur);
}
}
return ret;
}

数组计算 ‘1-7’ => 1 * 7 = 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function calc(arr) {
// 随手骚一下,不建议 eval
arr = arr.map(el => eval(el.replace('-', '*')));
return arr;
}

// or

function calc(arr) {
arr = arr.map(el => {
const list = el.split('-');
return +list[0] * +list[1];
});
return arr;
}

打印出1 5 2 8 6 3 10 9 7 4

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

思路1:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function printArr(n) {   //n 代表行数
var a = [],
k = 1, //起始值
p = 0;
for(var i = 0; i < n; i++) {
p = i;
for(var j = 0; j < n - i; j++) {

if(a[j]) {
a[p][j] = k;
} else {
a[j] = [];
a[j][j] = k;
}
k++;
p++;
}
}

return a;
}
console.log(printArr(4));
console.log(printArr(5));
console.log(printArr(6));

思路2:从最后一位往前push,if当前push个数=行数,行数+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//i 代表行数
function printArr(n) {
var a = [],
k = 1; //起始值
for(var i = 0; i < n; i++) {
for(var j = i; j < n; j++) {
if(a[j]) {
a[j].unshift(k++)
} else {
a[j] = [];
a[j].unshift(k++)
}
}
}
return a;
}
console.log(printArr(4));
console.log(printArr(5));
console.log(printArr(6));

快速排序,三路快排

快速排序算法的优化思路总结

算法与面试之-如何准备算法面试

快速排序是什么?

快速排序是图灵奖得主C. A. R. Hoare(1934–)于1960时提出来的。
快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

整个排序过程只需要三步:

  • 在数据集之中,选择一个元素作为”基准”(pivot)。
  • 所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。
  • 对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

引自wikipedia 快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n)算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

步骤

  1. 找到该数组的基准点(中间数),并创建两个空数组left和right;
  2. 遍历数组,拿出数组中的每个数和基准点进行比较,如果比基准点小就放到left数组中,如果比基准点大就放到right数组中;
  3. 对数组left和right进行递归调用。

方法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function quickSort(arr) {
if (arr.length<=1) {return arr;}
var left = [],
right = [],
baseDot =Math.round(arr.length/2),
base =arr.splice(baseDot, 1)[0];

for (var i =0; i <arr.length; i++) {
if (arr[i] < base) {
left.push(arr[i])
}else {
right.push(arr[i])
}
}

return quickSort(left).concat([base], quickSort(right));
}

var arr=[5,6,2,1,3,8,7,1,2,3,4,7];
console.log(quick_sort(arr));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function qSort(arr) {
if (arr.length==0) {
return [];
}
var left = [];
var right = [];
var pivot = arr[0];
for (var i =1; i <arr.length; i++) { // 注意这里的起始值,因为有一个作为flag了
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return qSort(left).concat(pivot, qSort(right));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function qSort(arr) {
if (arr.length==0) {
return [];
}
var left = [];
var right = [];
var pivot = arr[0];
for (var i =1; i <arr.length; i++) { // 注意这里的起始值,因为有一个作为flag了
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...qSort(left),pivot,...qSort(right)]
}

实现一个quickSort的封装,并且定义left和right,找到数组的基准点baseDot和对应的基数base,然后遍历数组的每一项和base进行对比,最后递归调用,给出一个跳出条件if (arr.length <= 1) {return arr;}

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function quickSort(array, left, right) {
var length =array.length;
left =typeof left ==='number'? left :0,
right =typeof right ==='number'? right : length-1;

if (left < right) {
var index = left -1;
for (var i = left; i <= right; i++) {
if (array[i] <= array[right]) {
index++;
var temp = array[index];
array[index] = array[i];
array[i] = temp;
}
}
quickSort(array, left, index -1);
quickSort(array, index +1, right);
}
return array;
}

快速排序的基本思想就是分治法

引自wikipedia 在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

快速排序的改进方法:三路快排

定义: 三路快速排序是快速排序的的一个优化版本, 将数组分成三段, 即小于基准元素、 等于 基准元素和大于基准元素, 这样可以比较高效的处理数组中存在相同元素的情况,其它特征与快速排序基本相同。

我这里简单概括一下思路,有兴趣的同学可到上面的链接上阅读:快速排序及优化(Java实现)

  • 随机选取基准值base(支点随机选取),参考快速排序算法的优化思路总结
  • 配合着使用插入排序(当问题规模较小时,近乎有序时,插入排序表现的很好)
  • 当大量数据,且重复数多时,用三路快排
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
<!DOCTYPE html>
<html>

<head>
<meta charset="UTF-8">
<title></title>
<script type="text/javascript">
console.time("test0")
function qSort(arr) {
if(arr.length == 0) {
return [];
}
var left = [];
var right = [];
var pivot = arr[0];
for(var i = 1; i < arr.length; i++) { // 注意这里的起始值,因为有一个作为flag了
if(arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...qSort(left), pivot, ...qSort(right)];
}
console.log(qSort([9, 4, 10, 3, 1, 1, 0, 10, 8, 3, 9, 9, 4, 10, 10, 9, 9, 9, 1, 0]));
console.timeEnd("test0")
</script>
<script type="text/javascript">
console.time("test1")
function qSort3(arr) { //三路快排
if(arr.length == 0) {
return [];
}
var left = [];
var center = [];
var right = [];
var pivot = arr[0]; //偷懒,直接取第一个,实际取值情况 参考[快速排序算法的优化思路总结]
for(var i = 0; i < arr.length; i++) {
if(arr[i] < pivot) {
left.push(arr[i]);
} else if(arr[i] == pivot) {
center.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...qSort3(left), ...center, ...qSort3(right)];
}
console.log(qSort3([9, 4, 10, 3, 1, 1, 0, 10, 8, 3, 9, 9, 4, 10, 10, 9, 9, 9, 1, 0]))
console.timeEnd("test1")
</script>
</head>

<body>
</body>

</html>




可以看到对有重复数据的数据优化还是很可观的。

Vue利用Object.freeze()提升性能

Object.freeze()是ES5新增的特性,可以冻结一个对象,防止对象被修改。
Object.freeze() 可以冻结一个对象,冻结之后不能向这个对象添加新的属性,不能修改其已有属性的值,不能删除已有属性,以及不能修改该对象已有属性的可枚举性、可配置性、可写性。该方法返回被冻结的对象。
当你把一个普通的 JavaScript 对象传给 Vue 实例的 data 选项,Vue 将遍历此对象所有的属性,并使用 Object.defineProperty 把这些属性全部转为 getter/setter,这些 getter/setter 对用户来说是不可见的,但是在内部它们让 Vue 追踪依赖,在属性被访问和修改时通知变化。
但 Vue 在遇到像 Object.freeze() 这样被设置为不可配置之后的对象属性时,不会为对象加上 setter getter 等数据劫持的方法。

vue 1.0.18+对其提供了支持,对于data或vuex里使用freeze冻结了的对象,vue不会做getter和setter的转换。

如果你有一个巨大的数组或Object,并且确信数据不会修改,使用Object.freeze()可以让性能大幅提升。在我的实际开发中,这种提升大约有5~10倍,倍数随着数据量递增。

并且,Object.freeze()冻结的是值,你仍然可以将变量的引用替换掉。举个例子:

1
<p v-for="item in list">{{ item.value }}</p>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
new Vue({
data: {
// vue不会对list里的object做getter、setter绑定
list: Object.freeze([
{ value: 1 },
{ value: 2 }
])
},
created () {
// 界面不会有响应
this.list[0].value = 100;

// 下面两种做法,界面都会响应
this.list = [
{ value: 100 },
{ value: 200 }
];
this.list = Object.freeze([
{ value: 100 },
{ value: 200 }
]);
}
})

vue的文档没有写上这个特性,但这是个非常实用的做法,对于纯展示的大数据,都可以使用Object.freeze提升性能。
由于 Object.freeze() 会把对象冻结,所以比较适合展示类的场景,如果你的数据属性需要改变,可以重新替换成一个新的 Object.freeze()的对象。

使用 vm.$compile 编译dom

$compile函数可以用来手动调用vue的方式来编译dom。在你需要处理某个jQuery插件生成的html或者服务端返回的html的时候,这个函数可以派上用场。但注意这是个私有api,随时都有可能变动,并且这种做法有违vue的理念。仅在不得已的时候使用。

1
2
3
4
5
6
7
8
9
10
new Vue({
data: {
value: 'demo'
},
created () {
let dom = document.createElement('div');
dom.innerHTML = '{{ value }}';
this.$compile(dom);
}
})