2016年7月の記事一覧
ヒープの拡張であるところのheapdict
Pythonでは標準で「普通の」ヒープがついてくるが，Dijkstra法などの最短路で使うと遅くなる．DecreaseKeyがついていないためである．
以前，NetworkXの最短路を試したときに，あまりに遅いのでソースを読んでみたら，以前は普通のヒープを使っていた．そのため余分な情報をヒープに追加してしまうので，大規模問題例だとメモリがパンクしてしまう．
そのためには，自分でDecrease
区間木
仕事で区間木（interval tree）を使うことになったので，Pythonのモジュールを探したところ，以下のモジュールがあった．
https://github.com/chaimleib/intervaltree
簡単に解説しておく．
インストールはpipで行う．
pip install intervaltree
Python 2.6+ もしくはPython 3.2+で動作する．以下