Redis持久化

• what is 摊还分析

  • 即求数据结构的一个操作序列中所执行所有操作的平均时间。
  • 不考虑概率，保证最坏情况下每个操作的平均性能

• Methods

  • aggregate analysis 聚合分析
  • counting method 核算法
  • potential method 势能法

17.1聚合分析

• 聚合分析令每个操作的摊还代价相等。
  算出n个操作的总时间上界T(n),则每个操作的的摊还代价是T(n)/n

  For example:

  • 栈操作 PUSH,POP,POP(k)

    • n个操作的代价之至多是O(n) 为什么？
      每个操作的摊还代价是O(n)/n=O(1)

  • 二进制计数器递增 Increment

    • T(n)=O(n) O(n)/n=O(1)

17.2 accounting method

• credit

• accounting method 为每一种操作分配一个摊还代价c。对于n个操作，若当操作的实际代价real小于摊还代价，则结余credit,为c-real;
  若当前操作的实际代价real小于摊还代价，则从之前存储的credit中取出real-c

  For example:

• 栈操作

  	分配摊还代价	实际代价
  PUSH	2	1
  POP	0	1
  POP(k)	0	k

• 则每一次PUSH操作，摊还代价一个用于实际代价，一个存入credit，用于pop时使用、 每一个栈中的值都具有一个额外的credit
  pop指令，使用已经存储的一个credit

  • 二进制计数递增器 略

17.3 potential method

略略略

习题解答

• solutions for CLRS
  链接:http://pan.baidu.com/s/1mikmehU 密码:pbon

• 17.1.1
  O(k) 考虑最坏情形即为此

• 17.1.2
  略

• 17.1.3
  求和即可

• 17.2.1
  push 2 1pop+1copy
  pop pop(k) 0

• 17.2.2
  设摊还代价为0，若i is a power of 2
  其他情况下，摊还代价为2，即可

• 17.2.3
  略

• 17.3.1
  设𝞥’(Di)=𝞥(Di)-𝞥(Di-1),𝞥(0)=0即可

• 17.3.2
  略

• 17.3.3
  设𝞥(D)=nlgn

• 17.3.4
  O(n) + sn-s0

• 本章余略

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 rat_racer@qq.com