[競プロ python] ふんわりと理解！SortedListの仕組み

対象者

• SortedListを使いたい人
• 厳密な理解よりも、イメージで動作を知りたい人

ソースコードを見たい人はこちら(https://github.com/grantjenks/python-sortedcontainers/tree/master/src/sortedcontainers)

SortedListとは

• Sorted Containersというライブラリにある、ソート状態で要素の追加・削除が可能なリスト

利点は？

• ソート状態を保ったまま、要素の追加、削除、検索が O(logN) で可能

実現する仕組み - _lists, _maxes, _indexの3つのリストを使うことで計算量の削減

• _listsは[[1, 2, 3], [4, 5, 6], [7, 8, 9]]のようにオリジナルのリストを分割して格納したリスト
• _maxesは各サブリストの最大値が格納されたリスト
• _indexは各サブリストの要素数が木構造上に格納されたリスト
• 追加
  1. 追加するサブリストの特定 - O(log$\sqrt{N}$))
  2. サブリスト内の挿入する場所の特定 - O(log$\sqrt{N}$)
  3. サブリストへの挿入 - O(logN)
• 削除
  1. 削除するサブリストの特定 - O(log$\sqrt{N}$)
  2. サブリスト内の削除する要素の場所の特定 - O(log$\sqrt{N}$)
  3. サブリストからの削除 - O(logN)
• 検索
  1. 検索するサブリストの特定 - O(log$\sqrt{N}$)
  2. サブリスト内の検索する場所の特定 - O(log$\sqrt{N}$)
  3. サブリストの位置からオリジナルのソートされたリストの位置を特定 - O(logN)

具体例

import sortedcontainers
origin_list = [0,1,2,3,4,5,6,7,8,9]
# SortedListの作成
sl = sortedcontainers.SortedList(origin_list)
# 分かりやすさのため、リストの分割サイズを1000 -> 3に調整
sl._reset(3)
# 説明のため、_indexリストの作成
sl._build_index()
# 3つのリストの出力
print("_lists:", sl._lists)
print("_maxes:", sl._maxes)
print("_index:", sl._index)

_lists: [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9]]
_maxes: [2, 5, 8, 9] # [max(_lists[0]), max(_lists[1]), max(_lists[2]), max(_lists[3])]
_index: [10, 6, 4, 3, 3, 3, 1] # [len(_lists), len(_lists[:len(_lists)//2]), len(_lists[len(_lists)//2:]), len(_lists[0]), len(_lists[1]), len(_lists[2]), len(_lists[3])]

• 追加
  6を追加する場合

# 6を追加
sl.add(6)
# 3つのリストの出力
print("_lists:", sl._lists)
print("_maxes:", sl._maxes)
print("_index:", sl._index)

_lists: [[0, 1, 2], [3, 4, 5], [6, 6, 7, 8], [9]]
_maxes: [2, 5, 8, 9]
_index: [11, 6, 5, 3, 3, 4, 1]

追加する仕組み

1. _maxesを二分探索して6が入るサブリストを特定 → 8が最大値のサブリスト(_lists[2])
2. _lists[2]を二分探索して挿入する位置を特定し、挿入
3. [6,7,8] → [6,6,7,8]
4. [[0, 1, 2], [3, 4, 5], [6, 6, 7, 8], [9]]

• 削除
  8を削除する場合

# 8を削除
sl.discard(8)
# 3つのリストの出力
print("_lists:", sl._lists)
print("_maxes:", sl._maxes)
print("_index:", sl._index)

_lists: [[0, 1, 2], [3, 4, 5], [6, 7], [9]]
_maxes: [2, 5, 7, 9]
_index: [9, 6, 3, 3, 3, 2, 1]

1. _maxesを二分探索して8があるサブリストを特定 → 8が最大値のサブリスト(_lists[2])
2. _lists[2]を二分探索して削除する位置を特定し、削除
3. [6,7,8] → [6,7]
4. [[0, 1, 2], [3, 4, 5], [6,7], [9]]

ポイント リストを分割して保持することで、追加・削除を行ってもリスト全体を修正せずに済む。これにより計算量の削減を実現する。

追加や削除を行うときには、必要に応じて_maxesや_indexも修正されていることに注意！

• 検索
  6の位置を検索する場合

# 説明のため、6がある_maxesの位置と_lists内の位置を出力
pos_in_maxes = bisect.bisect_left(sl._maxes, 6)
print("pos in _maxes:", pos_in_maxes)
print("pos in _lists[pos_in_maxes]:", bisect.bisect_left(sl._lists[pos_in_maxes], 6))
# 6の元のリストの位置を出力
print("pos in origin_list", sl.bisect_left(6))

pos in _maxes: 2
pos in _lists[pos_in_maxes]: 0
pos in origin_list: 6

1. _maxesを二分探索して6があるサブリストを特定 → 8が最大値のサブリスト(_lists[2])
2. _lists[2]を二分探索して検索する位置を特定(_lists[2][0])
3. _lists[x][y]のx, yから_indexをnodeからrootまで探索し、元リストにおける位置を特定

まとめ

SortedListは高速なデータ検索、追加、削除を可能にするための効率的なデータ構造。
これはリストをサブリストに分割して保持することで、追加・削除時にリスト全体を修正する必要がなく、計算量の削減を実現。