いろいろ備忘録日記

主に .NET とか Java とか Python絡みのメモを公開しています。

Pythonメモ-70 (SortedList, SortedDict, SortedSet) (sortedcontainers, ソート済みコレクション)

概要

pythonでソート済みコレクションを扱う際に標準ライブラリで候補に上がるのが

  • heapq モジュール使う

  • queue.PriorityQueue 使う

  • 最後に sorted かけてソートする

とかでしょうか。どれも簡単に処理かけるのですが、専用のコレクションあったほうがやっぱりなんか嬉しいです。

C#とかだと SortedListSortedDictionarySortedSet ってのがあるんですが

pythonにも似たような名前のライブラリないかなって探すと以下が見つかりました。

github.com

そのとおりのコレクションがあるみたいですね!!

pure-python で作成されてて、パフォーマンスもいいみたいです。

比較対象に、blist モジュールがいますね。

てことで、ちょこっと使ってみました。

といっても、欲しかったのが SortedList だったので、SortedDictSortedSet については調べてません。

インストール

いつもどおり、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


過去の記事については、以下のページからご参照下さい。

サンプルコードは、以下の場所で公開しています。