[Numpy-discussion] how to optimize numpy code for Markovian path

Jianhong Wang jianhong.wang at gmail.com
Thu Mar 19 22:31:30 EDT 2015


Below is a python function to generate Markov path (the travelling salesman
problem).

def generate_travel_path(markov_matrix, n):
    assert markov_matrix.shape[0] == markov_matrix.shape[1]
    assert n <= markov_matrix.shape[0]

    p = markov_matrix.copy()
    path = [0] * n
    for k in range(1, n):
        k1 = path[k-1]
        row_sums = 1 / (1 - p[:, k1])
        p *= row_sums[:, np.newaxis]
        p[:, k1] = 0
        path[k] = np.random.multinomial(1, p[k1, :]).argmax()

    assert len(set(path)) == n
    return path

markov_matrix is a predefined Markov transition matrix. The code generates
a path starting from node zero and visit every node once based on this
matrix.

However I feel the function is quite slow. Below is the line-by-line
profile with a 53x53 markov_matrix:

Timer unit: 3.49943e-07 s
Total time: 0.00551195 sFile: <ipython-input-29-37e4c9b5469e>Function:
generate_travel_path at line 1Line #      Hits         Time  Per Hit
% Time  Line Contents==============================================================
     1                                           def
generate_travel_path(markov_matrix, n):
     2         1           31     31.0      0.2      assert
markov_matrix.shape[0] == markov_matrix.shape[1]
     3         1           12     12.0      0.1      assert n <=
markov_matrix.shape[0]
     4
     5         1           99     99.0      0.6      p = markov_matrix.copy()
     6         1           12     12.0      0.1      path = [0] * n
     7        53          416      7.8      2.6      for k in range(1, n):
     8        52          299      5.8      1.9          k1 = path[k-1]
     9        52         3677     70.7     23.3          row_sums = 1
/ (1 - p[:, k1])
    10        52         4811     92.5     30.5          p = p *
row_sums[:, np.newaxis]
    11        52         1449     27.9      9.2          p[:, k1] = 0
    12        52         4890     94.0     31.0          path[k] =
np.random.multinomial(1, p[k1, :]).argmax()
    13
    14         1           51     51.0      0.3      assert len(set(path)) == n
    15         1            4      4.0      0.0      return path

If I ran this function 25000 times, it will take me more than 125
seconds. Any headroom to improve the speed?

Below is a simple function to generate a Markov matrix.

def initial_trans_matrix(n):
    x = np.ones((n, n)) / (n - 1)
    np.fill_diagonal(x, 0.0)
    return x
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20150319/498db47c/attachment.html>


More information about the NumPy-Discussion mailing list