PythonのSortedContainersで一番大きい要素にアクセスしたいときは-1でアクセスした方がいい

結論

PythonのSortedContainersで最大の要素にアクセスしたいときは、SortedSet[-1]とアクセスするのが高速です。

計算量

-1でアクセスを行ったとき

SortedSet[-1]のようにアクセスを行った場合は、$O(1)$で最大の値を取得することができます。
SortedListのソースコードを見ると、indexが0と-1のときに高速に取得ができるようになっています。

size - 1でアクセスを行ったとき

SortedSet[len(SortedSet) - 1]のようにアクセスを行った場合は、一般のランダムアクセスと同様の計算量になります。
計算量は$M$をSortedListの内部の値である内部の値_loadとすると、$O(\log(\frac{N}{M}))$になります。

max関数を利用したとき

max関数で最大値を取得しようとすると、SortedListやSortedSetの__iter__が呼ばれ、これを走査するため$O(N)$かかります。

実測

プログラム

以下のようなプログラムで100000回最大値を取得するのにかかる時間の平均値を測定します。
maxについては遅すぎるためここでは測定しません。

from sortedcontainers import SortedSet, SortedList, SortedDict
from random import randint
from time import time

times_1 = []
times_2 = []

for i in range(100):
    st = SortedSet()

    # 適当な値を500000個入れる。
    for j in range(500000):
        st.add(randint(1,10**9))

    # 100000回最大値を取得する時間を計測する
    start = time()
    for j in range(100000):
        st[-1]
    times_1.append(time() - start)
    start = time()
    
    for j in range(100000):
        st[len(st)-1]
    
    times_2.append(time() - start)
    start = time()
    

print('SortedSet[-1]:', sum(times_1) / len(times_1))
print('SortedSet[len(st)-1]:', sum(times_2) / len(times_2))

結果

CPython(3.10.6)

SortedSet[-1]: 0.037901742458343504
SortedSet[len(st)-1]: 0.23942818403244018

PyPy(7.3.11)

SortedSet[-1]: 0.0003316068649291992
SortedSet[len(st)-1]: 0.013397564888000488