Skip to main content
 首页 » 编程设计

用于评估随机游走的 python 库

2024年10月24日18dflying

我正在尝试评估随机游走结束位置的概率,但我在程序速度方面遇到了一些问题。基本上我想做的是将包含随机游走概率的字典作为输入(例如 p = {0:0.5, 1:0.2.-1:0.3} 意味着 X 保持在 50% 的概率0,20%的概率X增加1,30%的概率X减少1)然后计算n次迭代后所有可能的 future 状态的概率。

例如,如果 p = {0:0.5, 1:0.2。 -1:0.3} 和 n = 2 那么它将返回 {0:0.37, 1:0.2, -1:0.3, 2:0.04, -2:0.09} 如果 p = {0:0.5, 1:0.2。 -1:0.3} 和 n = 1 那么它将返回 {0:0.5, 1:0.2. -1:0.3}

我有工作代码,如果 n 很低并且 p 字典很小,它运行得相对较快,但是当 n > 500 并且字典有大约 50 个值时,它需要超过 5 分钟的时间来计算。我猜这是因为它只在一个处理器上执行,所以我继续修改它以便它使用 python 的多处理模块(因为我读到多线程不会提高并行计算性能,因为 GIL)。

我的问题是,多处理没有太多改进,现在我不确定是因为我实现错误还是因为 python 中多处理的开销。我只是想知道是否有某个库可以并行评估 n > 500 时随机游走的所有可能性的所有概率?如果我找不到任何东西,我的下一步是用 C 编写我自己的函数作为扩展,但这将是我第一次这样做,尽管我已经用 C 编写了一段时间。

原始非多进程代码

def random_walk_predictor(probabilities_tree, period): 
    ret = probabilities_tree 
    probabilities_leaves = ret.copy() 
    for x in range(period): 
        tmp = {} 
        for leaf in ret.keys(): 
            for tree_leaf in probabilities_leaves.keys(): 
                try: 
                    tmp[leaf + tree_leaf] = (ret[leaf] * probabilities_leaves[tree_leaf]) + tmp[leaf + tree_leaf] 
                except: 
                    tmp[leaf + tree_leaf] = ret[leaf] * probabilities_leaves[tree_leaf] 
        ret = tmp 
    return ret 

多处理代码

from multiprocessing import Manager,Pool 
from functools import partial 
 
def probability_calculator(origin, probability, outp, reference): 
    for leaf in probability.keys(): 
        try: 
            outp[origin + leaf] = outp[origin + leaf] + (reference[origin] * probability[leaf]) 
        except KeyError: 
            outp[origin + leaf] = reference[origin] * probability[leaf] 
 
def random_walk_predictor(probabilities_leaves, period): 
    probabilities_leaves = tree_developer(probabilities_leaves) 
    manager = Manager() 
    prob_leaves = manager.dict(probabilities_leaves) 
    ret = manager.dict({0:1}) 
    p = Pool() 
 
    for x in range(period): 
        out = manager.dict() 
        partial_probability_calculator = partial(probability_calculator, probability = prob_leaves, outp = out, reference = ret.copy()) 
 
        p.map(partial_probability_calculator, ret.keys()) 
        ret = out 
 
    return ret.copy() 

请您参考如下方法:

往往有解析解来精确求解这种 problem看起来类似于二项式分布,但我假设您真的是在为更一般的问题寻求计算解决方案。

与其使用 python 字典,更容易从底层数学问题的角度考虑这一点。构建一个矩阵 A 来描述从一种状态转到另一种状态的概率。构建一个状态 x 来描述在某个时间处于给定位置的概率。

因为在 n 转换之后,您最多可以从原点(在任一方向)开始 n 步 - 您的状态需要有 2n+1 行,并且 A 必须是正方形,大小为 2n+1 x 2n+1。

对于两个时间步长的问题,您的转换矩阵将为 5x5,如下所示:

[[ 0.5  0.2  0.   0.   0. ] 
 [ 0.3  0.5  0.2  0.   0. ] 
 [ 0.   0.3  0.5  0.2  0. ] 
 [ 0.   0.   0.3  0.5  0.2] 
 [ 0.   0.   0.   0.3  0.5]] 

你在时间 0 的状态将是:

[[ 0.] 
 [ 0.] 
 [ 1.] 
 [ 0.] 
 [ 0.]] 

系统的一步演化可以通过乘以A和x来预测。

所以在 t = 1 时,

 x.T = [[ 0.   0.2  0.5  0.3  0. ]] 

在 t = 2 时,

x.T = [[ 0.04  0.2   0.37  0.3   0.09]] 

因为即使是适度的时间步数,这也可能会占用相当多的存储空间(A 需要 n^2 存储空间),但是非常稀疏,我们可以使用稀疏矩阵来减少我们的存储(并加快我们的计算速度)。这样做意味着 A 需要大约 3n 个元素。

import scipy.sparse as sp 
import numpy as np 
 
def random_walk_transition_probability(n, left = 0.3, centre = 0.5, right = 0.2): 
    m = 2*n+1 
    A  = sp.csr_matrix((m, m)) 
    A += sp.diags(centre*np.ones(m), 0) 
    A += sp.diags(left*np.ones(m-1), -1) 
    A += sp.diags(right*np.ones(m-1),  1) 
    x = np.zeros((m,1)) 
    x[n] = 1.0 
    for i in xrange(n): 
        x = A.dot(x) 
    return x 
 
print random_walk_transition_probability(4) 

时间

%timeit random_walk_transition_probability(500) 
100 loops, best of 3: 7.12 ms per loop 
 
%timeit random_walk_transition_probability(10000) 
1 loops, best of 3: 1.06 s per loop