实现一个run方法,使得run(fucArr)能顺序输出1、2、3
1 | const fucArr = [ |
题目简析
我们观察 fucArr 每一个子项都具有如下结构：
- 接收一个方法
next - 有一个计时器，计时器回调方法体内对应着相应的输出
- 输出结束调用
next方法。
他们的差异就是：计时器时间逐个减少。
直接循环调用 3 个方法肯定是不可取的。为了能按序输出，函数的执行过程应该是上一个函数 console 之后， 再执行下一个函数，而接收的这个 next参数就是执行下一个方法的关键。因为是头到尾依次调用，我们就把fucArr 称之为一个队列。
思路一:递归
我们假象自己是个编译器，然后把执行的过程进行单步拆解。
fucArr是做先执行等待队列第一个，等待中的函数队列为原函数队列的slice(1)；- 等待next执行后，然后又执行等待函数队列的第一个函数，等待中的函数队列为原函数队列的slice(1)；
听着是不是很像一个 递归 的过程，没错，那我们先用递归来实现一下1
2
3
4
5
6
7
8var 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
6var 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
10var 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
10var 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
12var 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
4store=>next=>action=>{
// dosomething...
next()
}
a结构在第一次调用时，会返回一个方法，第二次调用时返回第二个方法，我们先来看源码的一个操作过程。1
const chain = middlewares.map(middleware => middleware(middlewareAPI))
首先是一层循环调用，使得函数体变为b结构：1
2
3
4next=>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
27const 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
4action=>{
// dosomething...
next()
}
这些关键还是要如何构建每个函数接收的参数next。
我们做如下假设，当fucArr只有一个函数时 返回的就应该是：1
2
3
4
5
6
7
8fucArr[0](()=>{}) // 为了避免报错，next应为一个空函数// 即：
action => {
setTimeout(() => {
console.log(action++);
//(()=>{}) 这玩意儿就是接收的next
(()=>{})(action)
}, 300)
}
当fucArr有两个函数时返回：1
2
3
4
5
6
7
8fucArr[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 | var reduceResult = fucArr.reduce((pre,next)=> (...arg)=>pre(next(...arg))); |
所以最终形态是1
2
3
4
5
6var 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
5var 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
8async 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
8function go(){
fucArr.reduce((prev,next)=>{
return prev.then(()=>new Promise(resolve=>{
next(resolve);
}))
},Promise.resolve());
}
go();
map Promise.resolve()
和上的思路差不多，但是写法略有不同：1
2
3
4
5
6let 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
16function* 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
5fucArr.reduceRight((prev, next) => {
return() => {
next(prev)
}
}, () => {})()
让我们看看reduceRight执行的具体过程：
reduce
上面讲了如何用reduceRight去拼凑f1(f2(f3(()=>{})))这种形式，其实用reduce也可以拼凑的：1
2
3
4
5
6const run = arr => arr.reduce((prev, next) => {
return (...args) => {
prev(() => next(...args))
}
});
run(fucArr)(() => {});
它这种拼凑方式我认为是最复杂的，下面看看具体步骤：
虚线框表示在闭包内，剪头代表参数归谁.
总结
1 |
|
自定义事件 new CustomEvent & document.createEvent
new CustomEvent
最近一个项目中需要模拟发起事件，在mdn中发现了这个构造方法CustomEvent1
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
5function createEvent(params, eventName = 'mock-event') {
return new CustomEvent(eventName, { detail: params });
}
const event = createEvent({ id: '0010' });
发起事件调用dispatchEvent方法发起事件，传入你刚才创建的方法
1 | window.dispatchEvent(event); |
DEMO
1 | const ev = document.getElementById('main'); |
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
8document.dispatchEvent(event);
//当然我们需要定义监控test事件的处理程序
document.addEventListener("test", function(e){
var obj = e.detail;
alert(obj.a + " " + obj.b);
});
// "test success"
综合
1 | //1 |
数组拍平,扁平化
1 | let arr = [ |
递归
如果有对递归不太熟悉的同学，可以看看我的读书笔记 【算法图解】读书笔记：第3章 递归。
递归的核心就在于两步：找到基线条件和递归条件。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15function 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时候，遍历完成
但是广度优先搜索的结果是不保证顺序的。
- 参考书籍：《图解算法》
- 不推荐的笔记，没书可以看看【算法图解】读书笔记：第6章 广度优先搜索
1 | function flat(arr) { |
投机取巧的 toString
1 | // [1,2,3,[44,55,[66,77]]].toString().split(",") |
迭代 - 深度优先搜索
原理与广度优先搜索类似，通过模拟栈的行为去遍历数组。好处是能够保证有序输出。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20function 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 | function calc(arr) { |
打印出1 5 2 8 6 3 10 9 7 4
1 | 1 |
思路1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24function 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 | //i 代表行数 |
快速排序,三路快排
快速排序算法的优化思路总结
算法与面试之-如何准备算法面试
快速排序是什么?
快速排序是图灵奖得主C. A. R. Hoare（1934–）于1960时提出来的。
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
整个排序过程只需要三步：
- 在数据集之中，选择一个元素作为”基准”（pivot）。
- 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。
- 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
引自wikipedia 快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
步骤
- 找到该数组的基准点(中间数)，并创建两个空数组left和right；
- 遍历数组，拿出数组中的每个数和基准点进行比较，如果比基准点小就放到left数组中，如果比基准点大就放到right数组中；
- 对数组left和right进行递归调用。
方法一
1 | function quickSort(arr) { |
1 | function qSort(arr) { |
1 | function qSort(arr) { |
实现一个quickSort的封装，并且定义left和right，找到数组的基准点baseDot和对应的基数base，然后遍历数组的每一项和base进行对比，最后递归调用，给出一个跳出条件if (arr.length <= 1) {return arr;}
方法二
1 | function quickSort(array, left, right) { |
快速排序的基本思想就是分治法
引自wikipedia 在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
快速排序的改进方法：三路快排
定义: 三路快速排序是快速排序的的一个优化版本， 将数组分成三段， 即小于基准元素、 等于 基准元素和大于基准元素， 这样可以比较高效的处理数组中存在相同元素的情况,其它特征与快速排序基本相同。
我这里简单概括一下思路，有兴趣的同学可到上面的链接上阅读：快速排序及优化(Java实现)
- 随机选取基准值base(支点随机选取),参考快速排序算法的优化思路总结
- 配合着使用插入排序(当问题规模较小时，近乎有序时，插入排序表现的很好)
- 当大量数据，且重复数多时，用三路快排
1 |
|
可以看到对有重复数据的数据优化还是很可观的。
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 | new Vue({ |
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
10new Vue({
data: {
value: 'demo'
},
created () {
let dom = document.createElement('div');
dom.innerHTML = '{{ value }}';
this.$compile(dom);
}
})