我只能说,概率证明真的好难啊!(;′⌒`)

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

算法不难证明难!


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

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

再举一个例子:

比如 :整数  5,在计算机中占3位(101),而3这个数字在计算机中占2位(11),Morris算法求得是这个2,最后通过C = 2^{x} - 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++算法更快更好一些(没有试过)。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部