順序付き集合 (スキップリスト)
(DataStructure/SortedSet/SortedSetSkipList.py)

• View this file on GitHub
• Last update: 2021-05-09 21:08:49+09:00

概要

スキップリストによる順序付き集合。B-Tree による実装の方が高速なのでそちらを使いましょう。

使い方

SortedSetSkipList()
空の順序付き集合を作成する。ノードの高さを $H$ (デフォルトでは $H = 20$) としたときに、計算量 $O(H)$

• __contains__(key: int) -> bool
  要素 key が集合に属しているかどうかを返す。計算量 $\mathrm{expected}\ O(H + \log N)$

• __len__() -> int
  集合の大きさを返す。計算量 $O(1)$

• __iter__() -> Iterator[int]
  要素の小さい順のイテレータオブジェクトを返す。オブジェクト生成の計算量 $O(1)$。イテレーション1回の計算量 $O(1)$

• add(key: int) -> bool
  要素 key を集合に追加する。追加に成功した場合は True を、失敗した場合 (既に key が集合に属していた場合) は False を返す。計算量 $\mathrm{expected}\ O(H + \log N)$

• remove(key: int) -> bool
  集合から key を削除する。削除に成功した場合は True を、失敗した場合 (key が集合に属していなかった場合) は False を返す。計算量 $\mathrm{expected}\ O(H + \log N)$

• iterate(lower: int) -> Iterator[int]
lower 以上の要素に対して、小さい順のイテレータオブジェクトを返す。オブジェクト生成の計算量 $\mathrm{expected}\ O(H + \log N)$。イテレーション1回の計算量 $O(1)$

• next_val(lower: int) -> int
lower 以上の最小の要素を返す。そのような要素が存在しない場合は None を返す。 $\mathrm{expected}\ O(H + \log N)$

• prev_val(upper: int) -> int
upper よりも小さい最大の要素を返す。そのような要素が存在しない場合は None を返す。 $\mathrm{expected}\ O(H + \log N)$

Depends on

• 乱数生成 (Xorshift) (misc/xorshift.py)

Verified with

• TestCase/AOJ/ITP2_7_C.SkipList.test.py

Code

from misc.xorshift import xorshift32


class SLSSNode:
    Nil = None

    def __init__(self, val, height):
        self.val = val
        self.next = [self.Nil] * height


class SortedSetSkipList:
    MAX_HEIGHT = 20
    LENGTH = 1 << MAX_HEIGHT
    INF = 1 << 64
    Nil = SLSSNode(INF, MAX_HEIGHT)
    SLSSNode.Nil = Nil
    Nil.next = [Nil] * MAX_HEIGHT

    def __init__(self, MAX_HEIGHT=20):
        self.sentinel_nd = SLSSNode(-self.INF, self.MAX_HEIGHT)
        self.size = 0
        self.rand32 = xorshift32()

    def __contains__(self, key):
        return self._search(key)

    def __len__(self):
        return self.size

    def __iter__(self):
        nd = self.sentinel_nd
        while nd.next[0].val != self.INF:
            yield nd.next[0].val
            nd = nd.next[0]

    def _pick_height(self):
        return self.MAX_HEIGHT - (self.rand32() & (self.LENGTH - 1)).bit_length() + 1

    def _search(self, val):
        nd = self.sentinel_nd
        for r in reversed(range(self.MAX_HEIGHT)):
            while nd.next[r].val < val:
                nd = nd.next[r]
        if nd.next[r].val == val:
            return True
        return False

    def add(self, val):
        nd = self.sentinel_nd
        stack = []

        h = self._pick_height()
        for r in reversed(range(self.MAX_HEIGHT)):
            while nd.next[r].val < val:
                nd = nd.next[r]
            if nd.next[r].val == val:
                return False
            elif r < h:
                stack.append(nd)

        nd = SLSSNode(val, h)
        for r, st_nd in enumerate(reversed(stack)):
            nd.next[r] = st_nd.next[r]
            st_nd.next[r] = nd
        self.size += 1
        return True

    def remove(self, val):
        del_nd = self.Nil
        nd = self.sentinel_nd
        for r in reversed(range(self.MAX_HEIGHT)):
            while nd.next[r].val < val:
                nd = nd.next[r]
            if nd.next[r].val == val:
                del_nd = nd.next[r]
                nd.next[r] = nd.next[r].next[r]
        if del_nd is self.Nil:
            return False
        self.size -= 1
        return True

    def iterate(self, lower):
        nd = self.sentinel_nd
        for r in reversed(range(self.MAX_HEIGHT)):
            while nd.next[r].val < lower:
                nd = nd.next[r]
        while nd.next[0].val != self.INF:
            yield nd.next[0].val
            nd = nd.next[0]

    def next_val(self, lower):
        nd = self.sentinel_nd
        for r in reversed(range(self.MAX_HEIGHT)):
            while nd.next[r].val < lower:
                nd = nd.next[r]
        return None if nd.next[r].val == self.INF else nd.next[r].val

    def prev_val(self, upper):
        nd = self.sentinel_nd
        for r in reversed(range(self.MAX_HEIGHT)):
            while nd.next[r].val < upper:
                nd = nd.next[r]
        return None if nd.val == -self.INF else nd.val

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page