# [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 == markov_matrix.shape
assert n <= markov_matrix.shape

p = markov_matrix.copy()
path =  * 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 == markov_matrix.shape
3         1           12     12.0      0.1      assert n <=
markov_matrix.shape
4
5         1           99     99.0      0.6      p = markov_matrix.copy()
6         1           12     12.0      0.1      path =  * 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>
```