Morris算法（大数据作业）

我只能说，概率证明真的好难啊！(；′⌒`)

这也证明我的概率论真的学的很差劲，有时间一定要补补/(ㄒoㄒ)/~~

算法不难证明难！

---

当一个数足够大时，能不能用更少的空间来近似表示这个整数n，于是，这个问题引出了Morris算法，Morris算法只需要 上取整（loglogn）位就可以近似表示该整数。

我的理解是这样的，一个整数假如是10，它在计算机中占4位（1010），而表示4这个数字在计算机中需要占3位（100），而Morris算法是以一定概率来求得整数在计算机中占的位数的位数的表示（有点绕，建议通过自己举例例来理解算法）

再举一个例子：

比如 ：整数  5，在计算机中占3位（101），而3这个数字在计算机中占2位（11），Morris算法求得是这个2，最后通过C =  - 1，来求得估计值C。

---

 Morris算法

算法描述

Python 代码 

import random
import matplotlib.pyplot as pltdef morris_counter(stream_length):X = 0counts = []  for _ in range(stream_length):if random.random() < (1 / (1 << X)):X += 1counts.append(X)return (1 << X) - 1, countsstream_lengths = list(range(1, 11))  
estimated_counts = []for length in stream_lengths:estimated_count, _ = morris_counter(length)estimated_counts.append(estimated_count)

Morris+算法

算法描述

 Python 代码

import random
import matplotlib.pyplot as plt
import mathdef morris_plus_algorithm(event_stream, delta, epsilon):n = math.ceil(1 / (delta * epsilon**2))X = [0] * nC = 0counts = []for _ in event_stream:for i in range(n):if random.random() < 1 / (2**X[i]):X[i] += 1temp_c = 0for i in range(n):temp_c += 2**X[i] - 1C = temp_c / ncounts.append(C)return countsevent_stream = list(range(1, 11))
delta = 0.1
epsilon = 0.2
counts = morris_plus_algorithm(event_stream, delta, epsilon)

 Morris++算法

算法描述

Python 代码 

import random
import matplotlib.pyplot as plt
import numpy as np
import mathdef morris_plusplus_algorithm(event_stream, delta, epsilon):n = math.ceil(1 / delta)m = math.ceil(1 / epsilon)X = np.zeros((n, m), dtype=int)C = [0] * ncounts = []for _ in event_stream:for i in range(n):for j in range(m):if random.random() < 1 / (2**X[i][j]):X[i][j] += 1C[i] += 2**X[i][j] - 1C[i] /= mcounts.append(np.median(C))return countsevent_stream = list(range(1,11))
delta = 0.1
epsilon = 0.2
counts = morris_plusplus_algorithm(event_stream, delta, epsilon)

总结 

根据课本，知道Morris++算法比Morris+算法的时间复杂度要低。Morris+算法取得是平均值来获得一个较好的近似估计，Morris++算法去的是中位数来获得一个较好的近似估计。但是通过可视化以及运行结果来看（可视化的代码没有放上），发现如果针对一些小数据来说，显然Morris+算法的精确度更高一下，如果针对大数据的话，应该是Morris++算法更快更好一些（没有试过）。