python sortedcontainers
date: 2022-11-26 excerpt: pythonのsortedcontainersの使い方
pythonのsortedcontainersの使い方
概要
- python3の3.10には
dict,set,listの木実装がなさそう- dictのキーやsetの値でbisect(二分探索)ができない
- 値の探索、データの追加、削除が遅い
- dictのキーやsetの値でbisect(二分探索)ができない
- これらを補完する意味で、
sortedcontainersがある- おそらく実装はB-tree
- 二分探索をサポート
add,removeの速度が二分探索なので十分に早い- 自分で類似のデータ構造を実装しようとすると大変
インストール
$ python3 -m pip install sortedcontainers
SortedListの具体例
from sortedcontainers import SortedList
lst = [1,5,9,1,5,9]
slst = SortedList(lst)
# slst; SortedList([1, 1, 5, 5, 9, 9])
assert list(slst) == sorted(lst)
assert(slst.bisect_left(5) == 2)
assert(slst.bisect_right(5) == 4)
slst.add(10) # 値の追加
SortedDictの具体例
from sortedcontainers import SortedDict
sd = SortedDict({2: "a", 1: "c", 3: "b"})
print(sd) # SortedDict({1: 'c', 2: 'a', 3: 'b'})
sd[0] = "z"
print(sd) # SortedDict({0: 'z', 1: 'c', 2: 'a', 3: 'b'})
assert(sd.bisect_left(1) == 1)
assert(sd.popitem() == (3, "b"))