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 plt

def morris_counter(stream_length):
    X = 0
    counts = []  
    for _ in range(stream_length):
        if random.random() < (1 / (1 << X)):
            X += 1
        counts.append(X)
    return (1 << X) - 1, counts

stream_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 math


def morris_plus_algorithm(event_stream, delta, epsilon):
    n = math.ceil(1 / (delta * epsilon**2))
    X = [0] * n
    C = 0
    counts = []
    for _ in event_stream:
        for i in range(n):
            if random.random() < 1 / (2**X[i]):
                X[i] += 1
        temp_c = 0
        for i in range(n):
            temp_c += 2**X[i] - 1
        C = temp_c / n
        counts.append(C)
    return counts

event_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 math

def 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] * n
    counts = []
    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] += 1
                C[i] += 2**X[i][j] - 1
            C[i] /= m
        counts.append(np.median(C))
    return counts


event_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++算法更快更好一些（没有试过）。