概要
pythonでソート済みコレクションを扱う際に標準ライブラリで候補に上がるのが
heapq
モジュール使うqueue.PriorityQueue
使う最後に
sorted
かけてソートする
とかでしょうか。どれも簡単に処理かけるのですが、専用のコレクションあったほうがやっぱりなんか嬉しいです。
C#とかだと SortedList
、SortedDictionary
、SortedSet
ってのがあるんですが
pythonにも似たような名前のライブラリないかなって探すと以下が見つかりました。
そのとおりのコレクションがあるみたいですね!!
pure-python で作成されてて、パフォーマンスもいいみたいです。
比較対象に、blist
モジュールがいますね。
てことで、ちょこっと使ってみました。
といっても、欲しかったのが SortedList
だったので、SortedDict
と SortedSet
については調べてません。
インストール
いつもどおり、conda
で入りました。
$ conda install sortedcontainers -y
SortedList
以下、メモ書き程度ですが。
""" sortedcontainers ライブラリのサンプル 参考情報:: http://www.grantjenks.com/docs/sortedcontainers/ """ import bisect as bs import contextlib as cx import heapq as hq import queue as que import typing as ty import unittest as ut import sortedcontainers as sc class D(ty.NamedTuple): id: int val: ty.AnyStr class SortedListTest(ut.TestCase): def test_list(self): """リストをソート無し使用""" l = list() l.append(D(100, 'hello')) l.append(D(110, 'world')) l.append(D(10, 'hoge')) self.assertEqual([x.id for x in l], [100, 110, 10]) def test_list_sorted(self): """リストをソートする""" l = list() l.append(D(100, 'hello')) l.append(D(110, 'world')) l.append(D(10, 'hoge')) sl = sorted(l, key=lambda x: x.id) self.assertEqual([x.id for x in sl], [10, 100, 110]) def test_sortedlist(self): """SortedListを使用""" l = sc.SortedListWithKey(key=lambda x: x.id) # SortedListの場合、ソートしながら要素を追加するには # append() ではなく add() を使う # append() を使う場合は自分で挿入する順番を担保しておかないと駄目 # つまり、これから追加する項目がソート順でも最終番目の場合 append() しても大丈夫 # そうじゃない場合例外が発生する l.add(D(100, 'hello')) l.add(D(110, 'world')) l.add(D(10, 'hoge')) with cx.suppress(ValueError): l.append(D(11, 'fuga')) # これはエラーになる self.assertEqual([x.id for x in l], [10, 100, 110]) def test_heapq(self): """heapqを使用""" l = [] d = D(100, 'hello') hq.heappush(l, (d.id, d)) d = D(110, 'world') hq.heappush(l, (d.id, d)) d = D(10, 'hoge') hq.heappush(l, (d.id, d)) self.assertEqual([hq.heappop(l)[0] for x in range(len(l))], [10, 100, 110]) def test_bisect_insort(self): """bisect.insortを使用""" l = [] d = D(100, 'hello') bs.insort(l, (d.id, d)) d = D(110, 'world') bs.insort(l, (d.id, d)) d = D(10, 'hoge') bs.insort(l, (d.id, d)) self.assertEqual([x[0] for x in l], [10, 100, 110]) def test_priorityqueue(self): """queue.PriorityQueueを使用""" q = que.PriorityQueue() d = D(100, 'hello') q.put_nowait(d) d = D(110, 'world') q.put_nowait(d) d = D(10, 'hoge') q.put_nowait(d) self.assertEqual([q.get_nowait()[0] for x in range(q.qsize())], [10, 100, 110]) if __name__ == '__main__': ut.main()
参考情報
SortedContainers — sortedcontainers 1.5.9 documentation
blist: an asymptotically faster list-like type for Python — blist 1.3.6 documentation
過去の記事については、以下のページからご参照下さい。
- いろいろ備忘録日記まとめ
サンプルコードは、以下の場所で公開しています。
- いろいろ備忘録日記サンプルソース置き場