手写

Array篇

定义一个测试数组

const players = [
    { name: '科比', num: 24 },
    { name: '詹姆斯', num: 23 },
    { name: '保罗', num: 3 },
    { name: '威少', num: 0 },
    { name: '杜兰特', num: 35 }
]

forEach

参数代表含义

• item：遍历项
• index：遍历项的索引
• arr：数组本身

Array.prototype.sx_forEach = function (callback) {
    for (let i = 0; i < this.length; i++) {
        callback(this[i], i, this)
    }
}

players.sx_forEach((item, index, arr) => {
    console.log(item, index)
})
// { name: '科比', num: 24 } 0
// { name: '詹姆斯', num: 23 } 1
// { name: '保罗', num: 3 } 2
// { name: '威少', num: 0 } 3
// { name: '杜兰特', num: 35 } 4

map

参数代表含义

• item：遍历项
• index：遍历项的索引
• arr：数组本身

Array.prototype.sx_map = function (callback) {
    const res = []
    for (let i = 0; i < this.length; i++) {
        res.push(callback(this[i], i, this))
    }
    return res
}

console.log(players.sx_map((item, index) => `${item.name}--${item.num}--${index}`))
// [ '科比--24--0', '詹姆斯--23--1', '保罗--3--2', '威少--0--3', '杜兰特--35--4' ]

filter

参数代表含义

• item：遍历项
• index：遍历项的索引
• arr：数组本身

Array.prototype.sx_filter = function (callback) {
    const res = []
    for (let i = 0; i < this.length; i++) {
        callback(this[i], i, this) && res.push(this[i])
    }
    return res
}

console.log(players.sx_filter(item => item.num >= 23))
// [
//     { name: '科比', num: 24 },
//     { name: '詹姆斯', num: 23 },
//     { name: '杜兰特', num: 35 }
// ]

every

参数代表含义

• item：遍历项
• index：遍历项的索引
• arr：数组本身

Array.prototype.sx_every = function (callback) {
    let flag = true
    for (let i = 0; i < this.length; i++) {
        flag = callback(this[i], i, this)
        if (!flag) break
    }
    return flag
}

console.log(players.sx_every(item => item.num >= 23)) // false
console.log(players.sx_every(item => item.num >= 0)) // true

some

参数代表含义

• item：遍历项
• index：遍历项的索引
• arr：数组本身

Array.prototype.sx_some = function (callback) {
    let flag = false
    for (let i = 0; i < this.length; i++) {
        flag = callback(this[i], i, this)
        if (flag) break
    }
    return flag
}

console.log(players.sx_some(item => item.num >= 23)) // true
console.log(players.sx_some(item => item.num >= 50)) // false

reduce

参数代表含义

• pre：前一项
• next：下一项
• index：当前索引
• arr：数组本身

Array.prototype.sx_reduce = function (callback, initValue) {
    let start = 0, pre;
    //有初始化默认值情况下；
    if (initValue) {
        pre = initValue
    } else {
        //美亚初始化默认值情况下，取数组第一个数据
        pre = this[0]
        start = 1
    }
    for (let i = start; i < this.length; i++) {
        pre = callback(pre, this[i], i, this)
    }
    return pre
}

// 计算所有num相加
const sum = players.sx_reduce((pre, next) => {
    return pre + next.num
}, 0)
console.log(sum) // 85

findIndex

参数代表含义

• item：遍历项
• index：遍历项的索引
• arr：数组本身

Array.prototype.sx_findIndex = function (callback) {
    for (let i = 0; i < this.length; i++) {
        if (callback(this[i], i, this)) {
            return i
        }
    }
    return -1
}

console.log(players.sx_findIndex(item => item.name === '科比')) // 0
console.log(players.sx_findIndex(item => item.name === '安东尼')) // -1

find

参数代表含义

• item：遍历项
• index：遍历项的索引
• arr：数组本身

Array.prototype.sx_find = function (callback) {
    for (let i = 0; i < this.length; i++) {
        if (callback(this[i], i, this)) {
            return this[i]
        }
    }
    return undefined
}

console.log(players.sx_find(item => item.name === '科比')) // { name: '科比', num: 24 }
console.log(players.sx_find(item => item.name === '安东尼')) // undefined

fill

用处：填充数组

参数代表含义

• initValue：填充的值
• start：开始填充索引，默认0
• end：结束填充索引，默认length

Array.prototype.sx_fill = function (value, start = 0, end) {
  end = end || this.length
  for (let i = start; i < end; i++) {
      this[i] = value
  }
  return this
}

console.log(players.sx_fill('samy', 1, 3))
// [
//     { name: '科比', num: 24 },
//     'samy',
//     'samy',
//     'samy',
//     { name: '杜兰特', num: 35 }
// ]

includes

用处：查找元素，查到返回true，反之返回false，可查找NaN；

includes可以检测NaN，indexOf不能检测NaN，includes内部使用了Number.isNaN对NaN进行了匹配；

Array.prototype.sx_includes = function (value, start = 0) {
    if (start < 0) start = this.length + start
    const isNaN = Number.isNaN(value)
    for (let i = start; i < this.length; i++) {
        if (this[i] === value || Number.isNaN(this[i]) === isNaN) {
            return true
        }
    }
    return false
}

console.log([1, 2, 3].sx_includes(2)) // true
console.log([1, 2, 3, NaN].sx_includes(NaN)) // true
console.log([1, 2, 3].sx_includes(1, 1)) // false

join

用处：将数组用分隔符拼成字符串，分隔符默认为,

Array.prototype.sx_join = function (s = ',') {
    let str = ''
    for(let i = 0; i < this.length; i++) {
        str = i === 0 ? `${str}${this[i]}` : `${str}${s}${this[i]}`
    }
    return str
}

console.log([1, 2, 3].sx_join()) // 1,2,3
console.log([1, 2, 3].sx_join('*')) // 1*2*3

flat

Array.prototype.sx_flat = function () {
    let arr = this
    while (arr.some(item => Array.isArray(item))) {
        arr = [].concat(...arr)
    }
    return arr
}

const testArr = [1, [2, 3, [4, 5]], [8, 9]]

console.log(testArr.sx_flat())
// [1, 2, 3, 4, 5, 8, 9]

splice【难】

Array.prototype.splice

难点

• 截取长度和替换长度的比较，不同情况

Array.prototype.sx_splice = function (start, length, ...values) {
  if (length === 0) return []
  length = start + length > this.length - 1 ? this.length - start : length
  console.log(length)
  const res = [], tempArr = [...this]
  for (let i = start; i < start + values.length; i++) {
    this[i] = values[i - start]
  }
  this.length = start + values.length
  if (values.length < length) {
    const cha = length - values.length
    console.log(cha)
    for (let i = start + values.length; i < tempArr.length; i++) {
      this[i] = tempArr[i + cha]
    }
    this.length = this.length - cha 
  }
  if (values.length > length) {
    for (let i = start + length; i < tempArr.length; i++) {
      this.push(tempArr[i])
    }
  }
  for (let i = start; i < start + length; i++) {
    res.push(tempArr[i])
  }
  return res
}

Object篇

定义一个测试对象

const obj = {
    name: 'samy',
    age: 22,
    gender: '男'
}

entries

用处：将对象转成键值对数组

Object.prototype.sx_entries = function (obj) {
    const res = []
    for (let key in obj) {
        obj.hasOwnProperty(key) && res.push([key, obj[key]])
    }
    return res
}

console.log(Object.sx_entries(obj))
// [ [ 'name', 'samy' ], [ 'age', 22 ], [ 'gender', '男' ] ]

fromEntries

用处：跟entries相反，将键值对数组转成对象

Object.prototype.sx_fromEntries = function (arr) {
    const obj = {}
    for (let i = 0; i < arr.length; i++) {
        const [key, value] = arr[i]
        obj[key] = value
    }
    return obj
}

console.log(Object.sx_fromEntries([['name', 'samy'], ['age', 22], ['gender', '男']]))
// { name: 'samy', age: 22, gender: '男' }

keys

用处：将对象的key转成一个数组合集

Object.prototype.sx_keys = function (obj) {
    const keys = []
    for (let key in obj) {
        obj.hasOwnProperty(key) && res.push(key)
    }
    return keys
}

console.log(Object.keys(obj))
// [ 'name', 'age', 'gender' ]

values

用处：将对象的所有值转成数组合集

Object.prototype.sx_values = function (obj) {
    const values = []
    for (let key in obj) {
        obj.hasOwnProperty(key) && values.push(obj[key])
    }
    return values
}

console.log(Object.sx_values(obj))
// [ 'samy', 22, '男' ]

instanceOf

用处：A instanceOf B，判断A是否经过B的原型链;

instanceof 内部机制是通过判断对象的原型链中是不是能找到对应的的prototype； 基础类型没有 __proto__

function instanceOf(father, child) {
    const fp = father.prototype
    var cp = child.__proto__
    while (cp) {
        if (cp === fp) {
            return true
        }
        cp = cp.__proto__
    }
    return false
}

function Person(name) {
    this.name = name
}
const sx = new Person('samy')

console.log(instanceOf(Person, sx)) // true
console.log(instanceOf(Person, sx2)) // false

is

用处：Object.is(a, b)，判断a是否等于b；

Object.is():用来比较两个值是否严格相等，与严格比较运算符（===）的行为基本一致;不同之处只有两个：一是+0不等于-0，二是NaN等于自身。Object.is(v1, v2) 修复了 === 的一些BUG (-0和+0, NaN和NaN)：

+0 === -0 //true           NaN === NaN//false    
Object.is(+0, -0) //false  Object.is(NaN, NaN) //true

Object.prototype.sx_is = function (x, y) {
    if (x === y) {
        return x !== 0 || 1 / x === 1 / y// 防止 -0 和 +0
    }
    return x !== x && y !== y// 防止NaN
}

const a = { name: 'samy' }
const b = a
const c = { name: 'samy' }

console.log(Object.sx_is(a, b)) // true
console.log(Object.sx_is(a, c)) // false

assign【难】

Object.assign

难点

• assign接收多个对象，并将多个对象合成一个对象
• 这些对象如果有重名属性，以后来的对象属性值为准
• assign返回一个对象，这个对象 === 第一个对象

Object.prototype.sx_assign = function (target, ...args) {
    if (target === null || target === undefined) {
        throw new TypeError('Cannot convert undefined or null to object')
    }
    target = Object(target)

    for (let nextObj of args) {
        for (let key in nextObj) {
            nextObj.hasOwnProperty(key) && (target[key] = nextObj[key])
        }
    }
    return target
}

const testa = { name: 'samy' }
const testb = { name: 'samyzh', age: 22 }
const testc = { age: 18, gender: '男' }

const testd = Object.sx_assign(testa, testb, testc)
console.log(testd) // { name: 'samyzh', age: 18, gender: '男' }
console.log(testa === testd) // true

Function篇

call

Function.prototype.sx_call = function (obj, ...args) {//要点o：参数不一样，处理剩余参数；
    obj = obj || window
    const fn = Symbol()// Symbol是唯一的，防止重名key
    obj[fn] = this
    return obj[fn](...args)// 执行，返回执行值
}

const testobj = {
    name: 'samy',
    testFn(age) {
        console.log(`${this.name}${age}岁了`)
    }
}
const testobj2 = {
    name: 'samyzh'
}

testobj.testFn.sx_call(testobj2, 22) // samyzh22岁了

apply

Function.prototype.sx_apply = function (obj, args) {
    obj = obj || window
    const fn = Symbol()// Symbol是唯一的，防止重名key
    obj[fn] = this
    return obj[fn](...args)// 执行，返回执行值
}

const testobj = {
    name: 'samy',
    testFn(age) {
        console.log(`${this.name}${age}岁了`)
    }
}
const testobj2 = {
    name: 'samyzh'
}

testobj.testFn.sx_apply(testobj2, [22]) // samyzh22岁了

bind【难】

Function.prototype.bind

难点：

• bind是返回一个函数，而不是执行结果
• bind返回的函数，拿来当做构造函数，该怎么处理

Function.prototype.sx_bind = function (obj, ...args) {
    obj = obj || window
    const fn = Symbol() // Symbol是唯一的，防止重名key
    obj[fn] = this
    const _this = this

    const res = function (...innerArgs) {
       // console.log(this, _this)
        if (this instanceof _this) {
            this[fn] = _this
            this[fn](...[...args, ...innerArgs])
            delete this[fn]
        } else {
            obj[fn](...[...args, ...innerArgs])
            delete obj[fn]
        }
    }
    res.prototype = Object.create(this.prototype)
    return res
}

String篇

slice

参数代表含义

• start：开始截取的字符索引(包含此字符)
• end：结束截取的字符索引(不包含此字符)

注意点

• start > end：返回空字符串
• start < 0：start = 数组长度 + start

String.prototype.sx_slice = function (start = 0, end) {
    start = start < 0 ? this.length + start : start
    end = !end && end !== 0 ? this.length : end
    if (start >= end) return ''
    let str = ''
    for (let i = start; i < end; i++) {
        str += this[i]
    }
    return str
}

console.log(str.sx_slice(2)) // nshine_lin
console.log(str.sx_slice(-2)) // in
console.log(str.sx_slice(-9, 10)) // shine_l
console.log(str.sx_slice(5, 1)) // ''

substring

功能与slice大致相同

区别之处

• start > end：互换值

String.prototype.sx_sunstring = function (start = 0, end) {
    start = start < 0 ? this.length + start : start
    end = !end && end !== 0 ? this.length : end

    if (start >= end) [start, end] = [end, start]
    let str = ''
    for (let i = start; i < end; i++) {
        str += this[i]
    }

    return str
}

console.log(str.sx_sunstring(2)) // nshine_lin
console.log(str.sx_sunstring(-2)) // in
console.log(str.sx_sunstring(-9, 10)) // shine_l
console.log(str.sx_sunstring(5, 1)) // unsh

substr

参数代表含义

• start：开始截取的字符索引(包含此字符)
• length：截取的长度

注意点

• start < 0：start = 数组长度 + start
• length超出所能截取范围，需要做处理
• length < 0：返回空字符串

String.prototype.sx_substr = function (start = 0, length) {
    if (length < 0) return ''

    start = start < 0 ? this.length + start : start
    length = (!length && length !== 0) || length > this.length - start ? this.length : start + length

    let str = ''
    for (let i = start; i < length; i++) {
        str += this[i]
    }
    return str
}

console.log(str.sx_substr(3)) // shine_lin
console.log(str.sx_substr(3, 3)) // shi
console.log(str.sx_substr(5, 300)) // ine_lin

slice, substring 和 substr 的区别？

方法	参数	描述
slice	slice(start, end)	从start开始，截取到end - 1，如果没有end，则截取到左后一个元素；
substring	substring(start,end)	返回从start位置开始到end位置的子串**（不包含end）**
substr	substr(start,length)	返回从start位置开始length长度的子串

数组的slice 与 splice 的区别？

方法	参数	描述
slice	slice(start, end)	从start开始，截取到end - 1，如果没有end，则截取到左后一个元素，不影响原数组
splice	splice(start, num, item1,item2, ...)	从start索引开始，截取num个元素，并插入item1、item2到原数组里，影响原数组

Promise篇

all

• 接收一个Promise数组，数组中如有非Promise项，则此项当做成功
• 如果所有Promise都成功，则返回成功结果数组
• 如果有一个Promise失败，则返回这个失败结果

function all(promises) {
    const result = []
    let count = 0
    return new MyPromise((resolve, reject) => {
        const addData = (index, value) => {
            result[index] = value
            count++
            if (count === promises.length) resolve(result)
        }
        promises.forEach((promise, index) => {
            if (promise instanceof MyPromise) {
                promise.then(res => {
                    addData(index, res)
                }, err => reject(err))
            } else {
                addData(index, promise)
            }
        })
    })
}

race

• 接收一个Promise数组，数组中如有非Promise项，则此项当做成功
• 哪个Promise最快得到结果，就返回那个结果，无论成功失败

function race(promises) {
    return new MyPromise((resolve, reject) => {
        promises.forEach(promise => {
            if (promise instanceof MyPromise) {
                promise.then(res => {
                    resolve(res)
                }, err => {
                    reject(err)
                })
            } else {
                resolve(promise)
            }
        })
    })
}

allSettled

• 接收一个Promise数组，数组中如有非Promise项，则此项当做成功
• 把每一个Promise的结果，集合成数组，返回

function allSettled(promises) {
    return new Promise((resolve, reject) => {
        const res = []
        let count = 0
        const addData = (status, value, i) => {
            res[i] = {
                status,
                value
            }
            count++
            if (count === promises.length) {
                resolve(res)
            }
        }
        promises.forEach((promise, i) => {
            if (promise instanceof MyPromise) {
                promise.then(res => {
                    addData('fulfilled', res, i)
                }, err => {
                    addData('rejected', err, i)
                })
            } else {
                addData('fulfilled', promise, i)
            }
        })
    })
}

any

any与all相反

• 接收一个Promise数组，数组中如有非Promise项，则此项当做成功
• 如果有一个Promise成功，则返回这个成功结果
• 如果所有Promise都失败，则报错

function any(promises) {
    return new Promise((resolve, reject) => {
        let count = 0
        promises.forEach((promise) => {
            promise.then(val => {
                resolve(val)
            }, err => {
                count++
                if (count === promises.length) {
                    reject(new AggregateError('All promises were rejected'))
                }
            })
        })
    })
  }
}

其他部分

算法

数据结构

简介

数据结构是计算机存储、组织数据的方式,算法是系统描述解决问题的策略。了解基本的数据结构和算法可以提高代码的性能和质量。

栈

栈的特点：先进后出； 正常插入，移除数组最后一项；

数组栈方法

• push() 可以接收任意数量的参数，把他们逐个添加到数组的末尾，返回修改后数组的长度；
• pop() 从数组末尾移除最后一项，返回移除的项；

class Stack {
  constructor() {
    this.items = [];
  }
  // 入栈
  push(element) {
    this.items.push(element);
  }
  // 出栈
  pop() {
    return this.items.pop();
  }
  // 清空栈
  clear() {
    this.items = [];
  }
  // 末位
  get peek() {
    return this.items[this.items.length - 1];
  }
  // 是否为空栈
  get isEmpty() {
    return !this.items.length;
  }
  // 长度
  get size() {
    return this.items.length;
  }
}
// 实例化一个栈
const stack = new Stack();
console.log(stack.isEmpty); // true

// 添加元素
stack.push(5);
stack.push(8);

// 读取属性再添加
console.log(stack.peek); // 8
stack.push(11);
console.log(stack.size); // 3
console.log(stack.isEmpty); // false

队列

队列：先进先出; 正常插入，移除数组第一项；

数组队列方法

• unshift() 向数组前端添加任意个项并返回新数组的长度；
• shift() 移除数组的第一项并返回该项 ；

class Queue { 
  constructor(items) { 
    this.items = items || []; 
  }
  enqueue(element) {
    this.items.unshift(element);
  }
  dequeue() {
    return this.items.shift();
  }
  front() {
    return this.items[0];
  }
  clear() {
    this.items = [];
  }
  print() {
    console.log(this.items.toString());
  }
  get size() {
    return this.items.length;
  }
  get isEmpty() {
    return !this.items.length;
  }
}

const queue = new Queue();
console.log(queue.isEmpty); // true

queue.enqueue("John");
queue.enqueue("Jack");
queue.enqueue("Camila");
console.log(queue.size); // 3
console.log(queue.isEmpty); // false
queue.dequeue();
queue.dequeue();
queue.dequeue();
console.log(queue.isEmpty); // true

字典

字典：类似对象，以key，value存贮值

class Dictionary { 
  constructor() { 
    this.items = {}; 
  }   
  set(key, value) {
    this.items[key] = value;
  }
  get(key) {
    return this.items[key];
  }
  remove(key) {
    delete this.items[key];
  }
  get keys() {
    return Object.keys(this.items);
  }
  get values() { // 在这里我们通过循环生成一个数组并输出
    return Object.keys(this.items).reduce((r, c, i) => {
      r.push(this.items[c]);
      return r;
    }, []);
  }
}
const dictionary = new Dictionary();
dictionary.set("Gandalf", "gandalf@email.com");
dictionary.set("John", "johnsnow@email.com");
dictionary.set("Tyrion", "tyrion@email.com");

console.log(dictionary);
console.log(dictionary.keys);
console.log(dictionary.values);
console.log(dictionary.items);

链表

• 链表: 存贮有序元素的集合;
• 但是不同于数组; 每个元素是一个存贮元素本身的节点和指向下一个元素引用组成;
• 要想访问链表中间的元素, 需要从起点开始遍历找到所需元素;

class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}
// 链表
class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }
  // 追加元素
  append(element) {
    const node = new Node(element);
    let current = null;
    if (this.head === null) {
      this.head = node;
    } else {
      current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.length++;
  }

  // 任意位置插入元素
  insert(position, element) {
    if (position >= 0 && position <= this.length) {
      const node = new Node(element);
      let current = this.head;
      let previous = null;
      let index = 0;
      if (position === 0) {
        this.head = node;
        node.next = current;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        node.next = current;
        previous.next = node;
      }
      this.length++;
      return true;
    }
    return false;
  }

  // 移除指定位置元素
  removeAt(position) {
    if (position > -1 && position < this.length) {// 检查越界值
      let current = this.head;
      let previous = null;
      let index = 0;
      if (position === 0) {
        this.head = current.next;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
      }
      this.length--;
      return current.element;
    }
    return null;
  }

  // 寻找元素下标
  findIndex(element) {
    let current = this.head;
    let index = -1;
    while (current) {
      if (element === current.element) {
        return index + 1;
      }
      index++;
      current = current.next;
    }
    return -1;
  }
  // 删除指定文档
  remove(element) {
    const index = this.findIndex(element);
    return this.removeAt(index);
  }
  isEmpty() {
    return !this.length;
  }
  size() {
    return this.length;
  }
  // 转为字符串
  toString() {
    let current = this.head;
    let string = "";
    while (current) {
      string += ` ${current.element}`;
      current = current.next;
    }
    return string;
  }
}
const linkedList = new LinkedList();

console.log(linkedList);
linkedList.append(2);
linkedList.append(6);
linkedList.append(24);
linkedList.append(152);

linkedList.insert(3, 18);
console.log(linkedList);
console.log(linkedList.findIndex(24));  

二叉树

特点：每个节点最多有两个子树的树结构

class NodeTree { 
  constructor(key) { 
    this.key = key; this.left = null; this.right = null; 
  } 
}
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insert(key) {
    const newNode = new NodeTree(key);
    const insertNode = (node, newNode) => {
      if (newNode.key < node.key) {
        if (node.left === null) {
          node.left = newNode;
        } else {
          insertNode(node.left, newNode);
        }
      } else {
        if (node.right === null) {
          node.right = newNode;
        } else {
          insertNode(node.right, newNode);
        }
      }
    };
    if (!this.root) {
      this.root = newNode;
    } else {
      insertNode(this.root, newNode);
    }
  }

  //访问树节点的三种方式:中序,先序,后序
  inOrderTraverse(callback) {
    const inOrderTraverseNode = (node, callback) => {
      if (node !== null) {
        inOrderTraverseNode(node.left, callback);
        callback(node.key);
        inOrderTraverseNode(node.right, callback);
      }
    };
    inOrderTraverseNode(this.root, callback);
  }

  min(node) {
    const minNode = node => {
      return node ? (node.left ? minNode(node.left) : node) : null;
    };
    return minNode(node || this.root);
  }

  max(node) {
    const maxNode = node => {
      return node ? (node.right ? maxNode(node.right) : node) : null;
    };
    return maxNode(node || this.root);
  }
}
const tree = new BinarySearchTree();
tree.insert(11);
tree.insert(7);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.inOrderTraverse(value => {
  console.log(value);
});

console.log(tree.min());
console.log(tree.max());

深度/广度遍历

对于算法来说 无非就是时间换空间 空间换时间

• 深度优先不需要记住所有的节点, 所以占用空间小, 而广度优先需要先记录所有的节点占用空间大；
• 深度优先有回溯的操作(没有路走了需要回头)所以相对而言时间会长一点；
• 深度优先采用的是堆栈的形式, 即先进后出；
• 广度优先则采用的是队列的形式, 即先进先出；

算法实践

LRU算法

场景：浏览器缓存淘汰策略和Vue的keep-alive学习LRU算法

原理

LRU （ Least Recently Used ：最近最少使用 ）缓存淘汰策略，故名思义，就是根据数据的历史访问记录来进行淘汰数据，其核心思想是 如果数据最近被访问过，那么将来被访问的几率也更高 ，优先淘汰最近没有被访问到的数据。

图解

手写实现

vue 源码看 keep-alive 的实现

核心：

// 如果命中缓存，则从缓存中获取 vnode 的组件实例，并且调整 key 的顺序放入 keys 数组的末尾
if (cache[key]) {
  vnode.componentInstance = cache[key].componentInstance;
  remove(keys, key); // make current key freshest
  keys.push(key);
}
// 如果没有命中缓存,就把 vnode 放进缓存
else {
  cache[key] = vnode;
  keys.push(key); // prune oldest entry
  // 如果配置了 max 并且缓存的长度超过了 this.max，还要从缓存中删除第一个
  if (this.max && keys.length > parseInt(this.max)) {
    pruneCacheEntry(cache, keys[0], keys, this._vnode);
  }
}
vnode.data.keepAlive = true;// keepAlive标记位
}

斐波那契数列

特点：第三项等于前面两项之和; 1、1、2、3、5、8、13、21

递归实现：

function Fibonacci (n) {//测试：不使用尾递归
  if ( n <= 2 ) {return 1};
  return Fibonacci(n - 1) + Fibonacci(n - 2);// return 四则运算
}
// Fibonacci(10) // 89
// Fibonacci(100) // 超时
// Fibonacci(100) // 超时
console.log(Fibonacci(7));

function Fibonacci2 (n , f1 = 1 , f2 = 1) {//测试：使用尾递归
  if( n <= 2 ) {return f2};
  return Fibonacci2 (n - 1, f2, f1 + f2);
}
// Fibonacci2(100) // 573147844013817200000
// Fibonacci2(1000) // 7.0330367711422765e+208
// Fibonacci2(10000) // Infinity
console.log(Fibonacci2(7));

普通实现：

function fn(n){
       var num1 = 1, num2= 1, num3 = 0;
       for(var i=0;i<n-2;i++){
           num3 = num1+num2;
           num1 = num2;
           num2 = num3;
       }
       return num3;
   }
console.log(fn(7)) //13

动态规划

特点：通过全局规划,将大问题分割成小问题来取最优解

案例：最少硬币找零

• 美国有以下面额(硬币）：d1=1, d2=5, d3=10, d4=25
• 如果要找36美分的零钱，我们可以用1个25美分、1个10美分和1个便士（ 1美分)

class MinCoinChange {
  constructor(coins) {
    this.coins = coins
    this.cache = {}
  }
  makeChange(amount) {
    if (!amount) return []
    if (this.cache[amount]) return this.cache[amount]
    let min = [], newMin, newAmount
    this.coins.forEach(coin => {
      newAmount = amount - coin
      if (newAmount >= 0) {
        newMin = this.makeChange(newAmount)
      }
      if (newAmount >= 0 && 
          (newMin.length < min.length - 1 || !min.length) && 
          (newMin.length || !newAmount)) {
        min = [coin].concat(newMin)
      }
    })
    return (this.cache[amount] = min)
  }
}
const rninCoinChange = new MinCoinChange([1, 5, 10, 25])
console.log(rninCoinChange.makeChange(36))// [1, 10, 25]
const minCoinChange2 = new MinCoinChange([1, 3, 4])
console.log(minCoinChange2.makeChange(6))// [3, 3]

贪心算法

特点：通过最优解来解决问题 ； 用贪心算法来解决上面中的案例

function MinCoinChange(coins) {
  var coins = coins;
  var cache = {};
  this.makeChange = function(amount) {
    var change = [],
        total = 0;
    for (var i = coins.length; i >= 0; i--) {
      var coin = coins[i];
      while (total + coin <= amount) {
        change.push(coin);
        total += coin;
      }
    }
    return change;
  };
}

var minCoinChange = new MinCoinChange([1, 5, 10, 25]);
// console.log(minCoinChange.makeChange(36));//[ 25, 10, 1 ]
// console.log(minCoinChange.makeChange(34));//[ 25, 5, 1, 1, 1, 1 ]
console.log(minCoinChange.makeChange(6));//[ 5, 1 ]

设计模式

设计模式原则

• S – Single Responsibility Principle 单一职责原则
  • 一个程序只做好一件事
  • 如果功能过于复杂就拆分开，每个部分保持独立
• O – OpenClosed Principle 开放/封闭原则
  • 对扩展开放，对修改封闭
  • 增加需求时，扩展新代码，而非修改已有代码
• L – Liskov Substitution Principle 里氏替换原则
  • 子类能覆盖父类
  • 父类能出现的地方子类就能出现
• I – Interface Segregation Principle 接口隔离原则
  • 保持接口的单一独立
  • 类似单一职责原则，这里更关注接口
• D – Dependency Inversion Principle 依赖倒转原则
  • 面向接口编程，依赖于抽象而不依赖于具体
  • 使用方只关注接口而不关注具体类的实现

设计模式分类(23种)

• 创建型
  • 单例模式
  • 原型模式
  • 工厂模式
  • 抽象工厂模式
  • 建造者模式
• 结构型
  • 适配器模式
  • 装饰器模式
  • 代理模式
  • 外观模式
  • 桥接模式
  • 组合模式
  • 享元模式
• 行为型
  • 观察者模式
  • 迭代器模式
  • 策略模式
  • 模板方法模式
  • 职责链模式
  • 命令模式
  • 备忘录模式
  • 状态模式
  • 访问者模式
  • 中介者模式
  • 解释器模式

常用设计模式

tips：常用的**【工原简单，装适观代】** 谐音：公(工)园(原)简单，装饰(适)现代；

简单工厂模式

定义

又叫静态工厂方法，就是创建对象，并赋予属性和方法

应用

抽取类相同的属性和方法封装到对象上

let UserFactory = function (role) {
  function User(opt) {
    this.name = opt.name;
    this.viewPage = opt.viewPage;
  }
  switch (role) {
    case 'superAdmin':
      return new User(superAdmin);
      break;
    case 'admin':
      return new User(admin);
      break;
    case 'user':
      return new User(user);
      break;
    default:
      throw new Error('参数错误, 可选参数:superAdmin、admin、user')
  }
}
let superAdmin = UserFactory('superAdmin');
let admin = UserFactory('admin') 

通过一个类获取不同类的实例

class Cat {}
class Dog {}
function Factory(type, args) {
    switch (type){
        case 'cat':
            return new Cat(args);
            break;
        default:
            return new Dog(args);
            break;
    }
}
const cat = new Factory('cat', {name: 'cat'});
const dog = new Factory('dog', {name: 'dog'});
console.log(cat, dog)

class Man {
  constructor(name) {
    this.name = name
  }
  alertName() {
    alert(this.name)
  }
}
class Factory {
  static create(name) {
    return new Man(name)
  }
}
Factory.create('samy').alertName()

工厂方法模式

定义

对产品类的抽象使其创建业务主要负责用于创建多类产品的实例

作用：工厂起到的作用就是隐藏了创建实例的复杂度，只需要提供一个接口，简单清晰。

应用

创建实例

var Factory=function(type,content){
  if(this instanceof Factory){
    var s=new this[type](content);
    return s;
  }else{
    return new Factory(type,content);
  }
}
Factory.prototype={//工厂原型中设置创建类型数据对象的属性
  Java:function(content){
    console.log('Java值为',content);
  },
  Python:function(content){
    console.log('Python值为',content);
  },
}
Factory('Python','我是Python');

在 Vue 源码中，你也可以看到工厂模式的使用，比如创建异步组件

export function createComponent (
  Ctor: Class<Component> | Function | Object | void,
  data: ?VNodeData,
  context: Component,
  children: ?Array<VNode>,
  tag?: string
): VNode | Array<VNode> | void {
    // 逻辑处理...
  const vnode = new VNode(
    `vue-component-${Ctor.cid}${name ? `-${name}` : ''}`,
    data, undefined, undefined, undefined, context,
    { Ctor, propsData, listeners, tag, children },
    asyncFactory
  )
  return vnode
}

原型模式

定义

原型模式会创建新的对象，而不是创建未初始化的对象，它会返回使用从原型或样本对象复制的值进行初始化的对象。原型模式也称为属性模式。

应用

实现继承

function Animal (name) {
  this.name = name || 'Animal';// 属性
  this.sleep = function(){  // 实例方法
    console.log(this.name + '正在睡觉！');
  }
}
Animal.prototype.eat = function(food) {// 原型方法
  console.log(this.name + '正在吃：' + food);
};
function Cat(){ }
Cat.prototype = new Animal();
Cat.prototype.name = 'cat';

var cat = new Cat();
console.log(cat.name);//cat
console.log(cat.eat('fish'));//cat正在吃：fish  undefined
console.log(cat.sleep());//cat正在睡觉！ undefined
console.log(cat instanceof Animal); //true 
console.log(cat instanceof Cat); //true  

单例模式

定义

确保一个类仅有一个实例，并提供一个访问它的全局访问点。

使用的场景

比如线程池、全局缓存等。我们所熟知的浏览器的window对象就是一个单例，在JavaScript开发中，对于这种只需要一个的对象，我们的实现往往使用单例。

应用实现

实现单例模式 （不透明的）

function Singleton(name) {
  this.name = name;
  this.instance = null;
}
Singleton.prototype.getName = function() {
  console.log(this.name)
};
Singleton.getInstance = function(name) {
  if(!this.instance) {
      this.instance = new Singleton(name);
  }
  return this.instance
};
var a = Singleton.getInstance('a');
var b = Singleton.getInstance('b');
console.log(a === b);

也可以使用闭包来实现：【要点】

function Singleton(name) {
    this.name = name;
}
Singleton.prototype.getName = function() {
    console.log(this.name)
};
Singleton.getInstance = (function() {
    var instance = null;
    return function(name) {
        if(!this.instance) {
            this.instance = new Singleton(name);
        }
        return this.instance
    }       
})();
var a = Singleton.getInstance('a');
var b = Singleton.getInstance('b');
console.log(a === b);

class方式：【要点】

class Singleton {
    constructor() {}
}
Singleton.getInstance = (function() {
    let instance
    return function() {
        if (!instance) {
            instance = new Singleton()
        }
        return instance
    }
})()
let s1 = Singleton.getInstance()
let s2 = Singleton.getInstance()
console.log(s1 === s2) // true

实现单例模式 （透明的）

function CreateSingleton (name) {
  this.name = name;
  this.getName();
};
CreateSingleton.prototype.getName = function() {
  console.log(this.name)
};
var Singleton = (function(){
  var instance;
  return function (name) {
      if(!instance) {
          instance = new CreateSingleton(name);
      }
      return instance;
  }
})();
var a = new Singleton('a');
var b = new Singleton('b');
console.log(a===b);//true

在 Vuex 源码中的使用，虽然它的实现方式不大一样，通过一个外部变量来控制只安装一次 Vuex

let Vue // bind on install
export function install (_Vue) {
  if (Vue && _Vue === Vue) {
    // ...
    return
  }
  Vue = _Vue
  applyMixin(Vue)
}

惰性单例模式

应用实例

实现一个单例的遮罩

在开发中并不会单独使用遮罩层，遮罩层和弹出窗是经常结合在一起使用，前面提到过登陆弹窗使用单例模式实现也是最适合的。当然我们还有好的实现方式，那就是将上面单例中代码变化的部分和不变的部分，分离开来。

在下面的实现中将单例模式的惰性实现部分提取出来，实现了惰性实现代码的复用

var singleton = function(fn) {
  var instance;
  return function() {
      return instance || (instance = fn.apply(this, arguments));
  }
};
var createMask = function(){// 创建遮罩层
  var mask = document.createElement('div');
  mask.style.position = 'fixed';
  mask.style.top = '0';
  mask.style.right = '0';
  mask.style.bottom = '0';
  mask.style.left = '0';
  mask.style.opacity = 'o.75';
  mask.style.backgroundColor = '#000';
  mask.style.display = 'none';
  mask.style.zIndex = '98';
  document.body.appendChild(mask);
  mask.onclick = function(){
      this.style.display = 'none';
  }
  return mask;
};
var createLogin = function() {// 创建登陆窗口
  var login = document.createElement('div');
  login.style.position = 'fixed';
  login.style.top = '50%';
  login.style.left = '50%';
  login.style.zIndex = '100';
  login.style.display = 'none';
  login.style.padding = '50px 80px';
  login.style.backgroundColor = '#fff';
  login.style.border = '1px solid #ccc';
  login.style.borderRadius = '6px';
  login.innerHTML = 'login it';
  document.body.appendChild(login);
  return login;
};

<button id="btn">click it</button>
document.getElementById('btn').onclick = function() {
  var oMask = singleton(createMask)();
  oMask.style.display = 'block';
  var oLogin = singleton(createLogin)();
  oLogin.style.display = 'block';
  var w = parseInt(oLogin.clientWidth);
  var h = parseInt(oLogin.clientHeight);
}

装饰者模式

定义

不改变原对象的基础上,给对象添加属性或方法

应用

基本上每天都在用的设计模式...

案例

#

封装输入控件事件

let decorator=function(input,fn){
  let input=document.getElementById(input);
  if(typeof input.onclick=='function'){
    let oldClickFn=input.onclick;//缓存事件源原有的回调函数
    input.onclick=function(){//为事件源定义新事件
      oldClickFn();//事件源原有回调函数
      fn();//执行事件源新增回调函数
    }
  }else{
    input.onclick=fn;//未绑定绑定
  }
}
decorator('textInp',function(){
  console.log('文本框执行啦');
})
decorator('btn',function(){
  console.log('按钮执行啦');
})

偏函数的部分实现；【要点】

const after = function(fn, afterFn) {
    return function() {
        fn.apply(this, arguments)
        afterFn.apply(this, arguments)
    }
}
const myAfter = after(after(fn1, fn2), fn3)
myAfter()

使用了 ES7 中的装饰器语法【要点】

function readonly(target, key, descriptor) {
  descriptor.writable = false
  return descriptor
}
class Test {
  @readonly
  name = 'samy'
}
let t = new Test()
t.samy = '111' // 不可修改

vue中源码的实现：重写数组的7个方法；

import { def } from '../util/index'

/*取得原生数组的原型*/
const arrayProto = Array.prototype
/*创建一个新的数组对象，修改该对象上的数组的七个方法，防止污染原生数组方法*/
export const arrayMethods = Object.create(arrayProto)

 /*这里重写了数组的这些方法，在保证不污染原生数组原型的情况下重写数组的这些方法，截获数组的成员发生的变化，执行原生数组操作的同时dep通知关联的所有观察者进行响应式处理*/
;[
  'push',
  'pop',
  'shift',
  'unshift',
  'splice',
  'sort',
  'reverse'
]
.forEach(function (method) {
  // cache original method
  /*将数组的原生方法缓存起来，后面要调用*/
  const original = arrayProto[method]
  def(arrayMethods, method, function mutator () {
    // avoid leaking arguments://重写的方法
    // http://jsperf.com/closure-with-arguments
    let i = arguments.length
    const args = new Array(i)
    while (i--) {
      args[i] = arguments[i]
    }
    /*调用原生的数组方法*/
    const result = original.apply(this, args)

    /*数组新插入的元素需要重新进行observe才能响应式*/
    const ob = this.__ob__
    let inserted
    switch (method) {
      case 'push':
        inserted = args
        break
      case 'unshift':
        inserted = args
        break
      case 'splice':
        inserted = args.slice(2)
        break
    }
    if (inserted) ob.observeArray(inserted)//取出插入的值
      
    // notify change
    /*dep通知所有注册的观察者进行响应式处理*/
    ob.dep.notify()
    return result
  })
})

适配器模式

定义

适配器模式（Adapter）是将一个类（对象）的接口（方法或属性）转化成客户希望的另外一个接口（方法或属性），适配器模式使得原本由于接口不兼容而不能一起工作的那些类（对象）可以一些工作。速成包装器（wrapper）。适配器用来解决两个接口不兼容的情况，不需要改变已有的接口，通过包装一层的方式实现两个接口的正常协作。

应用

适配函数参数

案例

class Plug {
  getName() {
    return '港版插头'
  }
}
class Target {
  constructor() {
    this.plug = new Plug()
  }
  getName() {
    return this.plug.getName() + ' 适配器转二脚插头'
  }
}
let target = new Target()
target.getName() // 港版插头 适配器转二脚插头

在 Vue 中，比如父组件传递给子组件一个时间戳属性，组件内部需要将时间戳转为正常的日期显示，一般会使用 computed 来做转换这件事情，这个过程就使用到了适配器模式。

观察者模式

定义

事件订阅及发布; 观察者对象和被观察者对象 之间的订阅和触发事件; 由观察者和观察者组成。通过观察者调用被观察者的实例。发布-订阅模式也叫做观察者模式。通过一对一或者一对多的依赖关系，当对象发生改变时，订阅方都会收到通知。

应用

**“Vue 双向绑定实现”；**在 Vue 中，如何实现响应式也是使用了该模式。对于需要实现响应式的对象来说，在 get 的时候会进行依赖收集，当改变了对象的属性时，就会触发派发更新。

简单的观察者模式: （仿 Vue 实现）

class Dep {// 观察者
    constructor() {
        this.subs = []
    }
    addSub(sub) {
        this.subs.push(sub)
    }
    depend() {
        if (Dep.target) { 
            Dep.target.addDep(this);
        }
    }
    notify() {
        this.subs.forEach(sub => sub.update())
    }
}

class Watcher {// 被观察者
    constructor(vm, expOrFn) {
        this.vm = vm;
        this.getter = expOrFn;
        this.value;
    }
    get() {
        Dep.target = this;
        var vm = this.vm;
        var value = this.getter.call(vm, vm);
        return value;
    }
    evaluate() {
        this.value = this.get();
    }
    addDep(dep) {
        dep.addSub(this);
    }
    update() {
        console.log('更新, value:', this.value)
    }
}
// 观察者实例
var dep = new Dep();
//  被观察者实例
var watcher = new Watcher({x: 1}, (val) => val);
watcher.evaluate();//通过 `watcher.evaluate()` 将自身实例赋值给 `Dep.target`

// 观察者监听被观察对象
dep.depend()//调用 `dep.depend()` 将dep实例的 watcher 实例 push 到 dep.subs中
dep.notify()//通过数据劫持，在调用被劫持的对象的set方法时，调用 dep.subs 中所有的 `watcher.update()`

发布/订阅者模式：是观察者模式的变体，比观察者模式多了一个调度中心

• 发布者发布信息到调度中心
• 调度中心和订阅者直接完成订阅和触发事件事件

使用场景案例：“DOM 的 addEventListener 事件”;

点击一个按钮触发了点击事件就是使用了该模式

<ul id="ul"></ul>
<script>
    let ul = document.querySelector('#ul')
    ul.addEventListener('click', (event) => {
        console.log(event.target);
    })
</script>

一个简单的发布/订阅者模式实现：（仿 EventBus 实现）

class EventTarget {// EventTarget 就是一个调度中心
    constructor() {
        this.dep = {}
    }
    on(key, fn) {
        this.dep[key] = fn;
    }
    emit(key) {
        typeof this.dep[key] === 'function' ? this.dep[key]() : ''
    }
}
let eventTarget = new EventTarget()
eventTarget.on('click', function() {console.log(1)})
eventTarget.emit('click')

代理模式

定义

将抽象部分与它的实现部分分离，使它们都可以独立地变化; 代理是为了控制对对象的访问，不让外部直接访问到对象。在现实生活中，也有很多代理的场景。比如你需要买一件国外的产品，这时候你可以通过代购来购买产品。

应用

比如事件代理就用到了代理模式

<ul id="ul">
    <li>1</li>
    <li>2</li>
    <li>3</li>
    <li>4</li>
    <li>5</li>
</ul>
<script>
    let ul = document.querySelector('#ul')
    ul.addEventListener('click', (event) => {
        console.log(event.target);
    })
</script>

因为存在太多的 li，不可能每个都去绑定事件。这时候可以通过给父节点绑定一个事件，让父节点作为代理去拿到真实点击的节点。

另外一个案例：

常用的虚拟代理形式：某一个花销很大的操作，可以通过虚拟代理的方式延迟到这种需要它的时候才去创建（例：使用虚拟代理实现图片懒加载）

图片懒加载的方式：先通过一张loading图占位，然后通过异步的方式加载图片，等图片加载好了再把完成的图片加载到img标签里面。

var imgFunc = (function() {
    var imgNode = document.createElement('img');
    document.body.appendChild(imgNode);
    return {
        setSrc: function(src) {
            imgNode.src = src;
        }
    }
})();
var proxyImage = (function() {
    var img = new Image();
    img.onload = function() {
        imgFunc.setSrc(this.src);
    }
    return {
        setSrc: function(src) {
            imgFunc.setSrc('./loading,gif');
            img.src = src;
        }
    }
})();
proxyImage.setSrc('./pic.png');

使用代理模式实现图片懒加载的优点还有符合单一职责原则。减少一个类或方法的粒度和耦合度。

策略模式

定义

策略模式最大的好处是：减少if-else的使用，同时增加代码可读性;

策略模式的目的就是将算法的使用算法的实现分离开来。

一个基于策略模式的程序至少由两部分组成。第一个部分是一组策略类（可变），策略类封装了具体的算法，并负责具体的计算过程。第二个部分是环境类Context（不变），Context接受客户的请求，随后将请求委托给某一个策略类。要做到这一点，说明Context中要维持对某个策略对象的引用。

应用

简单的年终奖计算。（策略模式放在必填项/规则验证会很便捷）

/*策略类*/
var levelOBJ = {
  "A": function(money) {
    return money * 4;
  },
  "B" : function(money) {
    return money * 3;
  },
  "C" : function(money) {
    return money * 2;
  } 
};
/*环境类*/
var calculateBouns =function(level,money) {
  return levelOBJ[level](money);
};
console.log(calculateBouns('A',10000)); // 40000

再比如vue中的源码实现mixin；

/*合并两个option对象到一个新的对象中*/
export function mergeOptions(
  parent: Object,
  child: Object,
  vm?: Component
): Object {
  if (process.env.NODE_ENV !== "production") {
    /*检查是否是有效的组件名*/
    checkComponents(child);
  }

  if (typeof child === "function") {
    child = child.options;
  }

  /*确保所有props option序列化成正确的格式*/
  normalizeProps(child);
  /*将函数指令序列化后加入对象*/
  normalizeDirectives(child);
  /*
    https://cn.vuejs.org/v2/api/#extends
    允许声明扩展另一个组件(可以是一个简单的选项对象或构造函数),而无需使用 
    将child的extends也加入parent扩展
  */
  const extendsFrom = child.extends;
  if (extendsFrom) {//递归合并extends
    parent = mergeOptions(parent, extendsFrom, vm);
  }
  /*child的mixins加入parent中*/
  if (child.mixins) {//递归合并mixin
    for (let i = 0, l = child.mixins.length; i < l; i++) {
      parent = mergeOptions(parent, child.mixins[i], vm);
    }
  }
  const options = {}; //属性及生命周期的合并
  let key;
  for (key in parent) {
    mergeField(key);
  }
  /*合并parent与child*/
  for (key in child) {
    if (!hasOwn(parent, key)) {
      mergeField(key);
    }
  }
  function mergeField(key) {
    /*strats里面存了options中每一个属性（el、props、watch等等）的合并方法，先取出*/
    const strat = strats[key] || defaultStrat;
    /*根据合并方法来合并两个option*/
    options[key] = strat(parent[key], child[key], vm, key);
  }
  return options;
}

#