Pythonでsortedなset
Pythonでsetを書くときに困ったのでメモ。
setはC++では赤黒木実装でsortedなので、Pythonでもそうだと思っていたら違ったようです。。。
公式ドキュメント http://docs.python.jp/2/library/sets.html より一部抜粋
>>> from sets import Set >>> engineers = Set(['John', 'Jane', 'Jack', 'Janice']) >>> engineers.add('Marvin') # add element >>> print engineers Set(['Jane', 'Marvin', 'Janice', 'John', 'Jack'])
はい。ソートされていませんね。
どういう内部実装なのか調べていないのでわからないですが、set([4,3,2,1])
などは[1,2,3,4]
とソートされているように見えるので誤解を招きやすいですね。。。
まぁ公式に実装されてなければ誰かが実装しているものですね。
SortedContainers
http://www.grantjenks.com/docs/sortedcontainers/
このパッケージを使いましょう。
pipではいってくれます。
pip install sortedcontainers
早速実験
ipdb> from sortedcontainers import SortedSet ipdb> set([234,4,3453,6545,23,3426756,657856,4,345]) set([657856, 3426756, 234, 6545, 23, 4, 3453, 345]) ipdb> SortedSet([234,4,3453,6545,23,3426756,657856,4,345]) SortedSet([4, 23, 234, 345, 3453, 6545, 657856, 3426756], key=None, load=1000)
はい、いい感じですね。
内部実装は赤黒木ではなく、B-Treeに似たsegmented-list data structure
(引用)らしいですが、ベンチマーク見る限り速いですし良さそうです。