algorithm - インタビュー : 挿入、削除、ランダム値の生成を最適化するデータ構造を提案する

Question

以下の 3 つの操作すべてを最適化できるデータ構造を提案します。

1. 挿入
2. 消す
3. 既存の値のセットからランダムな値を返します

整数/数値を入れていると仮定します。

Answer 1

動的配列 + ハッシュマップ = O(1) 3 つの操作すべて

• 挿入

配列 O(1) の末尾に追加し、値とインデックスのペアをハッシュマップ O(1) に追加します。

• 消す

ハッシュマップ O(1) の値でインデックスを見つけ、配列のインデックスで削除し、最後の要素をスロット O(1) にスワップし、(以前は) 最後の要素の値とインデックスのペアを更新しますO(1)。

• ランダムに返す

配列 O(1) のランダム インデックスを生成します。

Answer 2

Python の O(1):

from collections import defaultdict
from random import choice

class DataStructure(list):
    def __init__(self):
        self.values = []
        self.locations = defaultdict(list)

    def add(self, val):
        i = len(self.values)
        self.locations[val].append(i)
        self.values.append(val)
        assert self.values[i] == val

    def delete(self, val):
        locations = self.locations[val]
        if locations:
            i = locations.pop()
            self.values[i] = self.values[-1]
            self.values.pop()

    def random(self):
        return choice(self.values)

ds = DataStructure()

ds.add(3)
ds.add(5)
print ds.random()
print ds.random()
print ds.random()
print ds.random()
ds.delete(5)
print ds.random()
ds.delete(3)

"""
5
3
3
5
3
"""

List および Dict 操作の時間の複雑さを参照して確認してください

(リストの最後からポップするため、pop は O(1) であることに注意してください)

Answer 3

オープンアドレスのハッシュテーブルを使用します。必要に応じて再ハッシュすることにより、負荷率をαとβの間に保ちます。発振を避けるために、αとβの間の値に再ハッシュします。ほとんどのオープンハッシュスキームの実装では、テーブルが2の累乗や素数などの便利なサイズである必要があります。αとβの一般的な値は0.25と0.75で、目標負荷率は0.5です。

オープンアドレスのハッシュテーブルは、負荷率が1に近づかない限り、O（1）ルックアップであり、指数サイズ変更はO（1）で償却されるため、挿入はO（1）で償却されます。削除を処理する最も簡単な方法は、lazy-deleteです。削除された要素は削除済みとしてマークされますが、削除されないため、挿入中に上書きできます。この場合も、指数関数的なサイズ変更はO（1）で償却され、削除操作自体はルックアップのみに依存します。

ランダム選択は、ハッシュメカニズムを完全にバイパスし、削除されていないレコードが見つかるまで、基になる配列にランダムに突き刺します。負荷率は少なくともαであるため、予想される突き刺しの数は最大で1 /αであり、これもO（1）です。