対数時間ランダムアクセス/挿入/削除可能リスト (スキップリスト)
(DataStructure/List/SkipList.py)

• View this file on GitHub
• Last update: 2022-07-31 03:52:21+09:00

概要

要素のランダムアクセス、挿入、削除を $\mathrm{expected}\ O(H + \log N)$ で行えるリスト。

使い方

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

• __getitem__(i: int) -> int
  $i$ 番目の要素を返す。計算量 $\mathrm{expected}\ O(H + \log N)$

• __setitem__(i: int, val: int) -> None
  $i$ 番目の要素に val を代入する。計算量 $\mathrm{expected}\ O(H + \log N)$

• __len__() -> int
  リストの長さを返す。計算量 $O(1)$

• insert(i: int, val: int) -> None
  $i$ 番目の位置に val を挿入する。計算量 $\mathrm{expected}\ O(H + \log N)$

• delete(i: int) -> None
  $i$ 番目の要素を削除する。計算量 $\mathrm{expected}\ O(H + \log N)$

• dump() -> List[int]
  リストの要素を列挙した結果を返す。計算量 $O(N)$

Depends on

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

Verified with

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

Code

from misc.xorshift import xorshift32


class SLNode:
    def __init__(self, val, height):
        self.val = val
        self.next = [None] * height
        self.length = [0] * height


class SkipList:
    def __init__(self, MAX_HEIGHT=20):
        self.MAX_HEIGHT = MAX_HEIGHT
        self.LENGTH = 1 << MAX_HEIGHT
        self.sentinel_nd = SLNode(-1, self.MAX_HEIGHT)
        self.size = 0
        self.rand32 = xorshift32()

    def __getitem__(self, i):
        return self._find_nd(i).next[0].val

    def __setitem__(self, i, val):
        self._find_nd(i).next[0].val = val

    def __len__(self):
        return self.size

    def _find_nd(self, i):
        nd = self.sentinel_nd
        idx = -1
        for r in reversed(range(self.MAX_HEIGHT)):
            while nd.next[r] is not None and idx + nd.length[r] < i:
                idx += nd.length[r]
                nd = nd.next[r]
        return nd

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

    def insert(self, i, val):
        if i > self.size:
            raise IndexError
        nd = self.sentinel_nd
        h = self._pick_height()
        new_nd = SLNode(val, h)
        idx = -1
        for r in reversed(range(self.MAX_HEIGHT)):
            while nd.next[r] is not None and idx + nd.length[r] < i:
                idx += nd.length[r]
                nd = nd.next[r]
            nd.length[r] += 1
            if r < h:
                new_nd.next[r] = nd.next[r]
                nd.next[r] = new_nd
                new_nd.length[r] = nd.length[r] - (i - idx)
                nd.length[r] = i - idx
        self.size += 1

    def delete(self, i):
        if i >= self.size:
            raise IndexError
        nd = self.sentinel_nd
        idx = -1
        for r in reversed(range(self.MAX_HEIGHT)):
            while nd.next[r] is not None and idx + nd.length[r] < i:
                idx += nd.length[r]
                nd = nd.next[r]
            nd.length[r] -= 1
            if idx + nd.length[r] + 1 == i and nd.next[r] is not None:
                nd.length[r] += nd.next[r].length[r]
                deleted = nd.next[r]
                nd.next[r] = nd.next[r].next[r]
        del deleted
        self.size -= 1

    def dump(self):
        res = []
        nd = self.sentinel_nd.next[0]
        while nd is not None:
            res.append(nd.val)
            nd = nd.next[0]
        return res

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