[memo] Python Tuning

• Tuning tools
  • Calculation time
  • Memory
• Tips
  • numpy
  • k-shortest-paths

Tuning tools

Calculation time

• install

pip install line_profiler

• run

測定対象関数の前行に @profile 追加し実行:

kernprof -l ***.py

• check run-time

python -m line_profiler ***.lprof

Memory

pip install memory_profiler
pip install psutil (計測時間向上のため)

python -m memory_profiler ***.py

Tips

numpy

xi = np.zeros(nxi)
for n in range(nxi):
    for i in range(a_nrow):
        xi[n] += np.dot(a[i], self.bitarray[n+i+selfn_bound])

x … for 文

xi = np.zeros(nxi)
for n in range(nxi):
    vb = self.bitarray[n+self.n_bound:n+self.n_bound+a_nrow].flatten()
    xi[n] = np.dot(a.flatten(), vb)

o … 1次元化して内積

k-shortest-paths

$(n,m)=(| V| ,| E| )$

• Yen’s algorithm: $\mathcal{O}(kn(m+n\log n))$¹ » networkx
• Eppstein’s algorithm: $\mathcal{O}(m+n\log n + k\log k)$² » JGraphT jgrapht.algorithms.shortestpaths.eppstein_k³

pip install jgrapht

jgrapht.create_graph() » weighted graph, then Eppstein’s algorithm

Pulp

---

1. Jin Y. Yen, “Finding the K Shortest Loopless Paths in a Network”, Management Science, Vol. 17, No. 11, pp. 712-716, (1971) ↩

2. D. Eppstein, “Finding the k Shortest Paths,” SIAM J. Comput. 28 (2): pp. 652–673 (1998) ↩

3. JGraphT Algorithms Shortest-Paths ↩