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（引用）らしいですが、ベンチマーク見る限り速いですし良さそうです。