CUC day2

leetcode を解いていたら知らなかったアルゴリズムを知れたので解説してみます。

記事

元記事

leetcode.com

2行まとめ

  • 与えられたリストから等確率でランダムな値を得るアルゴリズム
  • 追加のメモリ確保を必要としないので、サイズが未知でも大丈夫

問題の要約

  • 連接リストが与えられて等確率でランダムな値を返したい
  • もし与えられるリストのサイズがわからなかったときはどうする？

という問題

真っ先に思いつくのは配列に戻してやって、ランダムなインデックスを得て参照してやるという方法かと思います。連結リストが要素の参照に O(N)かかるのに対して、配列だと O(1)で可能ですが、リストが巨大だったときに配列のためのメモリを確保しすぎてしまうという問題があります。

Reservoir sampling

追加のメモリを確保せずに、等確率のランダム値が得られたら嬉しいということで解説ではReservoir Samplingが紹介されていた。

ここではそのアルゴリズムと本当に等確率なランダム値になるのかの証明を説明する。また、一番シンプルな Reservoir sampling についてのみ紹介する。

アルゴリズム

R がreservoir(ため池)、S が入力

f:id:tjmtmmnk:20201221171212p:plain
アルゴリズムのイメージ

キーアイデア

  1. まずSのk個のアイテムをRに埋めておく
  2. 残りの n-k 個のアイテムをイテレートしてランダム値を生成してk以下なら置換

実装

1

for(i := 1..n) {
    R[i] = S[i]
}

2

for(i := k+1..n) {
  j := 1..i からランダムな値
  if(j <= k) {
    R[j] = S[i]
  }
}

等確率なランダム値が得られることの証明

S内の要素が最終的なRに選択されるということは一度選択されたら置換されないということです。

例えば、インデックスi で生成されたランダム値がk以下ならRに追加され、その後のi+1, i+2, ... でその値が置換されないということです。

これを確率にすると2つの独立な事象の確率になります。

  1. インデックスi でRに追加される確率
  2. i+1, i+2, ... で置換されない確率

1 は図のようになるので確率は k/i です。 f:id:tjmtmmnk:20201221175233j:plain

2 は図のようになるので確率は \frac{i}{i+1}\cdot \dots \cdot \frac{n-1}{n} です。 f:id:tjmtmmnk:20201221175924j:plain

1と2の確率は独立なので、1と2の確率の積は k/n となり、等確率となっていることが証明できました。

問題の解法

今回は1つのランダム値を返したいので、Rのサイズが1、つまりk=1と見なした Reservoir sampling を実行すると良いです。

コードにすると次のようになります。(https://leetcode.com/problems/linked-list-random-node/solution/ から引用)

/** Returns a random node's value. */
    public int getRandom() {
        int scope = 1, chosenValue = 0;
        ListNode curr = this.head;
        while (curr != null) {
            // decide whether to include the element in reservoir
            if (Math.random() < 1.0 / scope)
                chosenValue = curr.val;
            // move on to the next node
            scope += 1;
            curr = curr.next;
        }
        return chosenValue;
    }

感想

今回紹介したのは一番シンプルなやつでしたが wikipediaにはまだまだ色んな種類のアルゴリズムが載っていて奥が深いな〜となりました