Zenn
🔗

RustでSkipListを作った話

2023/09/06に公開
Rust
algorithm
tech

Skip Listとは

乱択アルゴリズム用いた，ノードが複数レベルの遷移を持つソートされた連結リストです．
1989年にウィリアム・ピューという方が発表したデータ構造らしいです．[1]
SkipListの例
SkipListの例 (Wikipediaより引用)

上の図のようにSkip Listはノードが複数レベルの遷移を持っています．
上位の遷移でノードを飛び越すことによって高速に操作することが出来ます．

Skip Listの性能は遷移の構成の仕方に依存することが見て取れると思います．例えば，全てのノードが同じレベルであった場合を考えると，単なる連結リストと同じ性能になってしまいますね．
Skip Listの最悪ケース
Skip Listの最悪ケース

最もよい繋ぎ方を考えてみましょう．二分木から連想すれば，一回の遷移で半分の要素を飛び越せればよさそうです．

Skip Listの最良ケース
Skip Listの最良ケース

上の図の様な繋ぎ方が最良の繋ぎ方になります．これを見ると確率的である必要は感じないかもしれません．

削除するノードに印をつけたSkip List

ここで，高いレベルのノードを削除してみます．

高いノードを削除したSkip List

連結リストと同じ構造になってしまいました．これでは性能が劣化してしまいますね．

この様に，決定的にノードの高さを選ぶと故意に性能を劣化させることが出来てしまいます．
こういった攻撃に耐性を持つために確率的にノードの高さを選択する必要があったわけです．

具体的に高さは，パラメータ0 \leq p \leq 1に対し，高さnになる確率がp^{n-1}となるようにします．このパラメータpによってメモリと速度のトレードオフをとります．

余談

p = 0の場合は高さが常に1になり，p = 1の場合は高さが常に最大になります．これらは常に最悪のケースになります．

p > 1 / 2になると，一部の列が全て埋まることが期待されます．つまり，pと1 - pは同じ効率になります．pが大きい場合はノードが高くなり空間効率が落ちるため，p > 1 / 2を選択する理由はないことが分かります．

単に確率で高さを選ぶと上限なくノードが高くなってしまいます．不必要にノードを高くしないために，要素数に応じた高さの上限を設けます．例えばp = 1 / 2でありn = 2^{16}であれば上限は16といった具合です．具体的に求める方法は論文にはありませんでしたが，上限は\log_{1 / p}(n)と考えてよさそうです．

次の章ではRustでこれを実装します．

参考にした論文は以下です．
Skip Lists: A Probabilistic Alternative to Balanced Trees

実装

Skip Listの構造上，同じノードを複数のノードが所有します．これはRustの所有権と相性が悪く，ポインタを多用した実装になります．

また，ノードを可変長にしましたがRustは可変長構造体を直接インスタンス化する方法がなく，fat pointerを作成する機能がnightlyであるためu8のポインタをそのまま使います．

Node

// key: K + value: V + level: usize + nexts: [MaybeNode<K, V>]
pub struct Node<K: Ord, V> {
    ptr: NonNull<u8>,
    marker: PhantomData<(K, V)>,
}

pub struct MaybeNode<K: Ord, V> {
    ptr: *mut u8,
    marker: PhantomData<(K, V)>,
}

nullを表す必要があるので，MaybeNodeとNodeで型を分けます．
複数のNodeが同じポインタを所有することがあります．

MaybeNodeにはtakeというメソッドがあり，Option<Node>を返します．

Nodeにはkey, value, level, nextsというメソッドがあり，無制限のライフタイムを持つ参照を返します．

list

pub struct SkipList<K: Ord, V, G: Generator<bool>> {
    gen: G,
    count: usize,
    nodes: Vec<MaybeNode<K, V>>,
}

nodesが各レベルの先頭要素への参照になり，常に最大レベル以上の長さを持ちます．

探索アルゴリズムはシンプルで，keyを探す場合，

  1. 最も高いレベルから探索を始める
  2. そのレベルにおいて見つけたい要素未満で最も大きい要素を見つける．
  3. レベルが0なら5.へ移動．
  4. レベルを1下げ，2.へ移動．
  5. 次の要素が，keyであればその要素を返す．そうでなければ失敗．

pub fn search(&self, key: &K) -> Option<&V> {
    // SkipListかNodeの遷移テーブル
    let mut forwards = self.nodes.as_slice();
    
    // 最も高いレベルから0までループ
    for level in (0..forwards.len()).rev() {
    	// 次の要素がnullか，探しているkey以上になるまで前方に進める．
	// -> forwardsはnullの手前か，key未満で最大の要素の手前の要素のテーブルになる．
        loop {
            let Some(next) = forwards.get(level).and_then(|e| e.take()) else {
                break;
            };
            if next.key() >= key {
                break;
            }
            forwards = next.nexts();
        }
    }

    // 次の要素がnullなら失敗
    let Some(node) = forwards.get(0).and_then(|e| e.take()) else {
        return None;
    };

    if node.key() == key {
        Some(node.value())
    } else {
        None
    }
}

insert

insertもsearchと同様にレベルごとに前に進めていく形になります．

ですが，insertと異なりノードを繋ぎ直す必要があるため，経路を記憶する必要があります．

そのため，レベルごとに再帰を行って，そのレベルでの一番前の遷移テーブルを記憶します．

pub fn insert(&mut self, key: K, value: V) -> Result<(), (K, V)> {
    let len = self.nodes.len();
    let level = len - 1;
    let forwards = unsafe { std::slice::from_raw_parts_mut(self.nodes.as_mut_ptr(), len) };
    let inserted = self.insert_impl(forwards, level, key, value)?;

    // 挿入されたノードのレベルが今までの最大レベルより高い場合，先頭を拡大する必要がある．
    if let Some(d) = inserted.level().checked_sub(len) {
        self.nodes
            .extend(repeat::<MaybeNode<K, V>>(inserted.into()).take(d));
    }

    Ok(())
}

// 各レベル毎でforwardsを保存しておく必要があるため，
// searchでのlevelに関するforループに当たるものを再帰で行う．
fn insert_impl(
    &mut self,
    mut forwards: &mut [MaybeNode<K, V>],
    level: usize,
    key: K,
    value: V,
) -> Result<Node<K, V>, (K, V)> {
    loop {
        //前方に進める．
        assert!(level < forwards.len());

        let Some(next) = forwards[level].take() else {
            break;
        };

        if next.key() == &key {
            return Err((key, value));
        }

        if next.key() > &key {
            break;
        }

        forwards = next.nexts_mut();
    }

    let node = if level == 0 {
        let n = self.alloc(key, value);
        self.count += 1;
        n
    } else {
        self.insert_impl(forwards, level - 1, key, value)?
    };

    if level >= node.level() {
        return Ok(node);
    }

    node.nexts_mut()[level] = forwards[level];
    forwards[level] = node.into();

    return Ok(node);
}

論文ではinsertに再帰を用いず，最大レベルの長さを持つ配列を使って，変更すべき遷移を記憶していました．
しかし，Rustには可変長配列のスタック確保の方法はなく，再帰深度の上限も対数スケールであるため，再帰で実装しました．

removeはinsertとほぼ同じコードで実装できます．

まとめ

二分木と比べるとアルゴリズムはシンプルであると思いますが，Rustとは相性が悪く，可変長型と所有権によって実装が複雑になってしまいました．

プログラム全体は以下のリポジトリに公開しています．

https://github.com/maemon4095/skip_list_rs

追記

  • 2023/09/07:
    • ライフタイム制限を避けるためポインタを経由していた部分をunbound lifetimeを利用する形にしました．
    • insertの図において経路に誤りがあったため修正しました．
脚注

  1. スキップリスト - Wikipedia ↩︎

Discussion