0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Karentia

TypeScriptでSkip Listを実装する：確率的な多段リンクで探索をO(log n)にする

0
Posted at

参考資料：William Pugh, “Skip Lists: A Probabilistic Alternative to Balanced Trees”
https://www.cs.umd.edu/~pugh/skiplist.pdf

本稿は上記のアイデアを TypeScript で書き直し、実装上の不変条件と境界テストを整理したものです。

TypeScriptでSkip Listを実装する：確率的な多段リンクで探索をO(log n)にする

先に結論

Skip List（スキップリスト）は、ソート済みの単方向リストに「ショートカットの層」を重ねるデータ構造です。

  • 検索・挿入・削除：期待計算量 O(log n)
  • 最悪計算量：O(n)
  • 空間計算量：O(n)
  • 実装の中心：各ノードの高さを確率的に決め、各層の直前ノードを同時に覚える

平衡二分探索木のような回転処理を使わずに、順序付き集合を実装できます。面接では「なぜ平均 O(log n) になるのか」と「削除時にどのリンクを更新するのか」を説明できると、単なるコード暗記から一歩進めます。

Skip Listのレベル構造

1. どこが速いのか

通常の単方向リストで値を探すと、先頭から一つずつ比較するため O(n) です。

Skip Listでは、ノードに複数のnextを持たせます。下の層は全要素をつなぎ、上の層は一部の要素だけをつなぎます。検索は最上層から始め、次へ進むと値を越えてしまう直前まで進み、そこで一つ下の層へ降ります。

各ノードが次の層へ昇格する確率を p = 0.5 とすると、層 l に残るノード数の期待値は n × p^(l-1) です。したがって、層を上り下りする回数の期待値は O(log n) になります。

ただし確率的な構造なので、入力によっては高さが偏ります。これは「常に O(log n)」ではなく「期待 O(log n)」と説明するのが正確です。

2. 実装で守る不変条件

実装を複雑にしないため、次の条件を固定します。

  1. 各層のリンクは値の昇順になっている。
  2. ノードが高さ h を持つとき、next[0]からnext[h - 1]までが存在する。
  3. 上位層に存在するノードは、必ず下位層にも存在する。
  4. headは実データではなく、すべての層の先頭を表す番兵ノードである。
  5. levelは現在使っている最高層（1始まり）である。

挿入・削除の前に、検索と同じ経路をたどって各層の「直前ノード」をupdateに保存します。これが多段リンクを一度に更新する鍵です。

3. TypeScript実装

addは重複値を拒否する集合として実装します。重複を許したい場合は、比較条件を変更し、同値の挿入位置を仕様として決めてください。

type RNG = () => number;

type Node = {
  value: number;
  next: Array<Node | null>;
};

class SkipList {
  private readonly head: Node;
  private level = 1;

  constructor(
    private readonly maxLevel = 16,
    private readonly probability = 0.5,
    private readonly rng: RNG = Math.random,
  ) {
    if (maxLevel < 1 || probability <= 0 || probability >= 1) {
      throw new RangeError("invalid skip-list parameters");
    }
    this.head = {
      value: Number.NEGATIVE_INFINITY,
      next: Array(maxLevel).fill(null),
    };
  }

  private randomLevel(): number {
    let level = 1;
    while (level < this.maxLevel && this.rng() < this.probability) {
      level += 1;
    }
    return level;
  }

  has(value: number): boolean {
    let current = this.head;

    for (let i = this.level - 1; i >= 0; i -= 1) {
      while (current.next[i] && current.next[i]!.value < value) {
        current = current.next[i]!;
      }
    }

    return current.next[0]?.value === value;
  }

  add(value: number): boolean {
    const update: Node[] = Array(this.maxLevel).fill(this.head);
    let current = this.head;

    for (let i = this.level - 1; i >= 0; i -= 1) {
      while (current.next[i] && current.next[i]!.value < value) {
        current = current.next[i]!;
      }
      update[i] = current;
    }

    if (update[0].next[0]?.value === value) return false;

    const nodeLevel = this.randomLevel();
    if (nodeLevel > this.level) {
      for (let i = this.level; i < nodeLevel; i += 1) {
        update[i] = this.head;
      }
      this.level = nodeLevel;
    }

    const node: Node = {
      value,
      next: Array(nodeLevel).fill(null),
    };

    for (let i = 0; i < nodeLevel; i += 1) {
      node.next[i] = update[i].next[i];
      update[i].next[i] = node;
    }
    return true;
  }

  remove(value: number): boolean {
    const update: Node[] = Array(this.maxLevel).fill(this.head);
    let current = this.head;

    for (let i = this.level - 1; i >= 0; i -= 1) {
      while (current.next[i] && current.next[i]!.value < value) {
        current = current.next[i]!;
      }
      update[i] = current;
    }

    const target = update[0].next[0];
    if (!target || target.value !== value) return false;

    for (let i = 0; i < this.level; i += 1) {
      if (update[i].next[i] !== target) break;
      update[i].next[i] = target.next[i] ?? null;
    }

    while (this.level > 1 && this.head.next[this.level - 1] === null) {
      this.level -= 1;
    }
    return true;
  }

  values(): number[] {
    const values: number[] = [];
    for (let current = this.head.next[0]; current; current = current.next[0]) {
      values.push(current.value);
    }
    return values;
  }
}

update配列の意味

たとえば値8を挿入する場合、update[0]は最下層で8の直前にあるノード、update[1]は第2層での直前ノードです。

新しいノードの高さが3なら、次の3本をそれぞれ差し替えます。

update[0] -> new -> update[0].next[0]
update[1] -> new -> update[1].next[1]
update[2] -> new -> update[2].next[2]

削除では逆に、対象ノードを指している層だけをつなぎ直します。対象の高さより上の層は対象を指していないので、そこでループを打ち切れます。

4. 境界を含むテスト

乱数をそのまま使うとテストが再現できないため、テストでは線形合同法の小さな疑似乱数生成器を渡します。実運用の乱数品質を評価するものではなく、構造を固定して回帰テストを再現するためのものです。

let seed = 0x12345678;
const rng = () => {
  seed = (Math.imul(seed, 1664525) + 1013904223) >>> 0;
  return seed / 0x1_0000_0000;
};

const list = new SkipList(12, 0.5, rng);
console.assert(list.values().length === 0);
console.assert(list.add(8));
console.assert(list.add(3));
console.assert(list.add(13));
console.assert(list.add(5));
console.assert(!list.add(8));
console.assert(list.has(3) && list.has(13) && !list.has(7));
console.assert(JSON.stringify(list.values()) === JSON.stringify([3, 5, 8, 13]));
console.assert(list.remove(8) && !list.has(8));
console.assert(!list.remove(8));
console.assert(JSON.stringify(list.values()) === JSON.stringify([3, 5, 13]));

const reference = new Set<number>();
const randomList = new SkipList(16, 0.5, rng);
for (let i = 0; i < 500; i += 1) {
  const value = (i * 73) % 211;
  randomList.add(value);
  reference.add(value);
}
console.assert(
  JSON.stringify(randomList.values()) ===
    JSON.stringify([...reference].sort((a, b) => a - b)),
);
console.log("skip-list tests: ok");

このテストで確認しているのは次の点です。

  • 空のリストから開始できる
  • 乱序で追加しても最下層は昇順になる
  • 重複追加はfalseを返し、要素を増やさない
  • 存在する値と存在しない値を正しく判定する
  • 同じ値を2回削除できない
  • 500回の追加結果が、参照実装のSetをソートした結果と一致する

実行結果：

skip-list tests: ok

5. 面接で説明するなら

「なぜ配列や通常のリンクリストではなくSkip Listを使うのですか？」

順序を保った検索・挿入・削除が必要で、平衡木の回転処理を自前で持ちたくない場合の選択肢です。実装は比較的局所的で、期待 O(log n) の性能を得られます。一方、厳密な最悪計算量の保証が必要なら、AVL木や赤黒木など別の構造を選びます。

「乱数に依存するのは危険ではありませんか？」

性能保証は期待値です。maxLevelで高さを制限し、監視対象のレイテンシやノード分布を確認します。攻撃者が乱数や入力を制御できる環境で厳密な上限が必要なら、決定的な平衡木のほうが適切です。

「削除で全層を走査する必要はありますか？」

必要ありません。検索時に各層の直前ノードをupdateへ保存しているため、対象ノードの高さまでリンクを更新できます。最後に空になった最高層をlevelから下げます。

まとめ

Skip Listの要点は、単方向リストを捨てることではなく、同じ順序を保ったまま複数の探索経路を持つことです。

  • 下位層が正しい順序を保証する
  • 上位層が探索距離を短くする
  • updateが挿入・削除の全層更新を可能にする
  • 計算量は「最悪」ではなく「期待」と表現する
  • 疑似乱数と参照実装で、構造と境界を再現可能に検証する

この4点をコードと一緒に説明できれば、Skip Listを知っているだけでなく、設計上のトレードオフまで理解していることを示せます。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?