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