从一个越写越慢的编辑器中聊聊优化思路

### 一个*斜体*标题

parsedContent = [`<h3>一个<i>斜体</i>标题</h3>`]

data: {
  // 缓存对象
  memo: {}
}
watch： {
  // 当编辑器的value变动时将尝试直接获取缓存，如果没有缓存才解析内容
  value (n，o) {
    if (this.memo[n]) {
      this.parsedValue = this.memo[n]
    } else {
      this.memo[n] = this.parsedValue = parseMDToHTML(n)
    }
  }
}

value = [1，2，3，...，n-1，n].join('')
memo == {
  '1': '1',
  '12': '12',
  '123': '123',
  // ...
  '12345...n-1': '12345...n-1',
  '12345...n': '12345...n',
}

function Node (config) {
  this.key = config.key
  this.prev = null
  this.next = null
  this.data = config.data || {
    val: null,
    weight: 1
  }
}
// 将当前节点的next指向另一节点
Node.prototype.linkNextTo = function (nextNode) {
  this.next = nextNode
  nextNode.prev = this
}
// 将当前节点插入某一结点后
Node.prototype.insertAfterNode = function (prevNode) {
  const prevNextNode = prevNode.next
  prevNode.linkNext(this)
  this.linkNext(prevNextNode)
}
// 删除当前节点，除非节点是头节点/尾节点
Node.prototype.unLink = function () {
  const prev = this.prev
  const next = this.next

  if (!prev || !next) {
    console.log(`Node : ${this.key} cant unlink`)
    return false
  }
  prev.linkNext(next)
}

数组可以直接通过下标去获取某个特定的元素，而链表不行，在缓存类中我使用一个备忘录对象去记录每一个节点的访问地址，充当数组下标的作用，详见下代码中`nodeMemo`的使用

function LFU (limit) {
  this.headNode = new Node({ key: '__head__'，data: { val: null，weight: Number.MAX_VALUE } })
  this.tailNode = new Node({ key: '__tail__'，data: { val: null，weight: Number.MIN_VALUE } })
  this.headNode.linkNext(this.tailNode)
  this.nodeMemo = {}
  this.nodeLength = 0
  this.nodeLengthLimit = limit || 999
}
// 通过key判断缓存中是否有某元素
LFU.prototype.has = function (key) {
  return !!this.nodeMemo[key]
}
// 通过key获取缓存中某一元素值
LFU.prototype.get = function (key) {
  let handle = this.nodeMemo[key]
  if (handle) {
    this.addNodeWeight(handle)
    return handle.data.val
  } else {
    throw new Error(`Key : ${key} is not fount in LFU Nodes`)
  }
}
// 通过key获取缓存中某一元素权重
LFU.prototype.getNodeWeight = function (key) {
  let handle = this.nodeMemo[key]
  if (handle) {
    return handle.data.weight
  } else {
    throw new Error(`Key : ${key} is not fount in LFU Nodes`)
  }
}
// 添加新的缓存元素
LFU.prototype.set = function (key，val) {
  const handleNode = this.nodeMemo[key]
  if (handleNode) {
    this.addNodeWeight(handleNode，10)
    handleNode.data.val = val
  } else {
    if (this.nodeLength < this.nodeLengthLimit) {
      this.nodeLength++
    } else {
      const deleteNode = this.tailNode.prev
      deleteNode.unLink()
      delete this.nodeMemo[deleteNode.key]
    }
    const newNode = new Node({ key，data: { val，weight: 1 } })
    this.nodeMemo[key] = newNode
    newNode.insertAfter(this.tailNode.prev)
  }
}
// 打印缓存中全部节点
LFU.prototype.showAllNodes = function () {
  let next = this.headNode.next
  while (next && next.next) {
    console.log(`Node : ${next.key} has data ${next.data.val} and weight ${next.data.weight}`)
    next = next.next
  }
}
// 对某一元素进行加权操作
LFU.prototype.addNodeWeight = function (node，w = 1) {
  const handle = node
  let prev = handle.prev

  handle.unLink()
  handle.data.weight += w
  while (prev) {
    if (prev.data.weight <= handle.data.weight) {
      prev = prev.prev
    } else {
      handle.insertAfter(prev)
      prev = null
    }
  }
}

import LFU from '@/utils/suites/teditor/LFU'

describe('LFU测试'，() => {
  const LFU = new LFU(4)
  it('能够正确维护链表长度'，() => {
    LFU.set('1'，1)
    LFU.set('2'，2)
    LFU.set('3'，3)
    LFU.set('4'，4)
    LFU.set('5'，5)
    expect(LFU.has('4')).to.equal(false)
  })
  it('节点的数据应该正确'，() => {
    expect(LFU.get('1')).to.equal(1)
    expect(LFU.get('2')).to.equal(2)
    expect(LFU.get('3')).to.equal(3)
    expect(LFU.get('5')).to.equal(5)
    LFU.get('5')
    LFU.get('3')
    LFU.get('3')
    LFU.get('3')
    LFU.get('3')
    LFU.set('5'，6)
    expect(LFU.get('5')).to.equal(6)
  })
  it('节点的权重应该正确'，() => {
    expect(LFU.getNodeWeight('5')).to.equal(14)
    expect(LFU.getNodeWeight('3')).to.equal(6)
  })
})