python库评估随机散步？

Question

我试图评估随机游走结束位置的概率，但我在计划速度方面遇到了一些麻烦。基本上，我想要做的是将包含随机游走概率的字典作为输入（例如p = {0：0.5,1：0.2。-1：0.3}，这意味着X保持在50％的概率0，20％概率X增加1，30％概率X减少1），然后计算n次迭代后所有可能的未来状态的概率。

因此，例如，如果p = {0：0.5,1：0.2。 -1：0.3}且n = 2时，如果p = {0：0.5,1：0.2，则它将返回{0：0.37,1：0.2，-1：0.3,2：0.04，-2：0.09} 。 -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() 

Answer 1

有往往是分析解决方案正好解决这类problem看上去类似二项分布，但我会假设你真的在为一个更普遍的问题寻求一个计算解决方案。

与其使用python字典，更容易从底层数学问题的角度来思考这个问题。建立一个矩阵A，描述从一个州到另一个州的可能性。建立一个状态x，描述某个时间在某个特定位置的可能性。

因为经过n过渡您可以逐步从原点最多n步骤（在任一方向） - 你的国家需要有2N + 1行，并A需求是正方形大小为2N和+ 1的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