これは私がインタビューで少し前に尋ねられた質問です、私は答えを見つけることができませんでした。
いくつかのサンプルS1、S2、... Snとそれらの確率分布（または重み、それが呼ばれるものは何でも）P1、P2、.. Pnが与えられると、その確率を考慮してサンプルをランダムに選択する設計アルゴリズム。私が持ってきた解決策は次のとおりです。
重みCiの累積配列を作成します。
C0 = 0; Ci = C [i-1]+Pi。
同時に、T = P1 + P2 +...Pnを計算します。O（n）時間かかります
ここで、実際の質問は次のとおりです。初期の重みPjの1つを変更したいとします。O（n）時間よりも良い時間でこれを行う方法は？他のデータ構造も受け入れられますが、ランダムサンプリングアルゴリズムはO（logN）より悪くなることはありません。
これを解決する1つの方法は、累積合計を含む二分探索木がどのように構築されるかを再考することです。二分探索木を構築するのではなく、各ノードを次のように解釈することを検討してください。
たとえば、イベントA、B、C、D、E、F、およびGの重みが3、2、2、2、2、1、および1であるとします。このバイナリツリーは、A、B、C、 D、E、F、およびG：
D
/ \
B F
/ \ / \
A C E G
ここで、ツリーに確率で注釈を付けます。A、C、E、およびGはすべて葉であるため、それぞれに確率質量1を与えます。
D
/ \
B F
/ \ / \
A C E G
1 1 1 1
ここで、Bのツリーを見てください。Bには重み2が選択され、Aには重み3が選択され、Cには確率2が選択されます。これらを[0、1）の範囲に正規化すると、Aは確率の3/7を占め、BとCはそれぞれ2/7を占めます。したがって、Bのノードは、範囲[0、3/7）のすべてが左側のサブツリーに移動し、範囲[3 / 7、5/7）のすべてがBにマップされ、範囲[5 / 7、1）適切なサブツリーにマップします。
D
/ \
B F
[0, 3/7) / \ [5/7, 1) / \
A C E G
1 1 1 1
同様に、Fを処理してみましょう。Eには選択の重み2があり、FとGにはそれぞれ選択の確率重み1があります。したがって、ここではEのサブツリーが確率質量の1/2を占め、ノードFが1/4を占め、Gのサブツリーが1/4を占めます。これは、確率を次のように割り当てることができることを意味します
D
/ \
B F
[0, 3/7) / \ [5/7, 1) [0, 1/2) / \ [3/4, 1)
A C E G
1 1 1 1
最後に、ルートを見てみましょう。左側のサブツリーの合計の重みは3+2 + 2=7です。右側のサブツリーの合計の重みは2+1 + 1 = 4です。したがって、D自体の重みは2です。したがって、左側のサブツリーの確率は7/13です。選択されると、Dは選択される確率が2/13になり、右側のサブツリーは選択される確率が4/13になります。したがって、確率を次のように確定できます。
D
[0, 7/13) / \ [9/13, 1)
B F
[0, 3/7) / \ [5/7, 1) [0, 1/2) / \ [3/4, 1)
A C E G
1 1 1 1
ランダムな値を生成するには、次の手順を繰り返します。
ツリーが構築されるときに、確率自体を再帰的に決定できます。
この再定式化が役立つ理由は、更新された確率ごとにO（log n）時間で確率を更新する方法を提供するためです。特に、特定のノードの重みを更新した場合にどの不変条件が変化するかを考えてみましょう。簡単にするために、今のところノードがリーフであると仮定しましょう。リーフノードの重みを更新しても、確率はリーフノードに対しては正しいですが、そのノードのサブツリーの1つの重みが変更されているため、そのすぐ上のノードに対しては正しくありません。したがって、上記と同じ式を使用するだけで、（O（1）時間で）親ノードの確率を再計算できます。ただし、サブツリーの重みの1つが変更されたため、そのノードの親は正しい値を持たなくなり、そこで確率を再計算することもできます。このプロセスは、ツリーのルートまでさかのぼって繰り返され、レベルごとにO（1）計算を実行して、各エッジに割り当てられた重みを修正します。したがって、ツリーのバランスが取れていると仮定すると、1つの確率を更新するためにO（log n）の合計作業を実行する必要があります。ノードがリーフノードでない場合、ロジックは同じです。ツリーのどこかから始めます。
要するに、これは
お役に立てれば！
配列の代わりに、平衡二分木として構造化された検索を保存します。ツリーのすべてのノードには、含まれる要素の合計の重みが格納されている必要があります。の値に応じてR、検索プロシージャは現在のノードを返すか、左または右のサブツリーを検索します。
要素の重みが変更された場合、検索構造の更新は、要素からツリーのルートまでのパスの重みを調整することです。
ツリーはバランスが取れているため、検索と重みの更新操作は両方ともO（log N）です。
コードが必要な方のために、Pythonの実装を以下に示します。
import numpy
class DynamicProbDistribution(object):
""" Given a set of weighted items, randomly samples an item with probability
proportional to its weight. This class also supports fast modification of the
distribution, so that changing an item's weight requires O(log N) time.
Sampling requires O(log N) time. """
def __init__(self, weights):
self.num_weights = len(weights)
self.weights = numpy.empty((1+len(weights),), 'float32')
self.weights[0] = 0 # Not necessary but easier to read after printing
self.weights[1:] = weights
self.weight_tree = numpy.zeros((1+len(weights),), 'float32')
self.populate_weight_tree()
def populate_weight_tree(self):
""" The value of every node in the weight tree is equal to the sum of all
weights in the subtree rooted at that node. """
i = self.num_weights
while i > 0:
weight_sum = self.weights[i]
twoi = 2*i
if twoi < self.num_weights:
weight_sum += self.weight_tree[twoi] + self.weight_tree[twoi+1]
elif twoi == self.num_weights:
weight_sum += self.weights[twoi]
self.weight_tree[i] = weight_sum
i -= 1
def set_weight(self, item_idx, weight):
""" Changes the weight of the given item. """
i = item_idx + 1
self.weights[i] = weight
while i > 0:
weight_sum = self.weights[i]
twoi = 2*i
if twoi < self.num_weights:
weight_sum += self.weight_tree[twoi] + self.weight_tree[twoi+1]
elif twoi == self.num_weights:
weight_sum += self.weights[twoi]
self.weight_tree[i] = weight_sum
i /= 2 # Only need to modify the parents of this node
def sample(self):
""" Returns an item index sampled from the distribution. """
i = 1
while True:
twoi = 2*i
if twoi < self.num_weights:
# Two children
val = numpy.random.random() * self.weight_tree[i]
if val < self.weights[i]:
# all indices are offset by 1 for fast traversal of the
# internal binary tree
return i-1
elif val < self.weights[i] + self.weight_tree[twoi]:
i = twoi # descend into the subtree
else:
i = twoi + 1
elif twoi == self.num_weights:
# One child
val = numpy.random.random() * self.weight_tree[i]
if val < self.weights[i]:
return i-1
else:
i = twoi
else:
# No children
return i-1
def validate_distribution_results(dpd, weights, samples_per_item=1000):
import time
bins = numpy.zeros((len(weights),), 'float32')
num_samples = samples_per_item * numpy.sum(weights)
start = time.time()
for i in xrange(num_samples):
bins[dpd.sample()] += 1
duration = time.time() - start
bins *= numpy.sum(weights)
bins /= num_samples
print "Time to make %s samples: %s" % (num_samples, duration)
# These should be very close to each other
print "\nWeights:\n", weights
print "\nBins:\n", bins
sdev_tolerance = 10 # very unlikely to be exceeded
tolerance = float(sdev_tolerance) / numpy.sqrt(samples_per_item)
print "\nTolerance:\n", tolerance
error = numpy.abs(weights - bins)
print "\nError:\n", error
assert (error < tolerance).all()
#@test
def test_DynamicProbDistribution():
# First test that the initial distribution generates valid samples.
weights = [2,5,4, 8,3,6, 6,1,3, 4,7,9]
dpd = DynamicProbDistribution(weights)
validate_distribution_results(dpd, weights)
# Now test that we can change the weights and still sample from the
# distribution.
print "\nChanging weights..."
dpd.set_weight(4, 10)
weights[4] = 10
dpd.set_weight(9, 2)
weights[9] = 2
dpd.set_weight(5, 4)
weights[5] = 4
dpd.set_weight(11, 3)
weights[11] = 3
validate_distribution_results(dpd, weights)
print "\nTest passed"
if __name__ == '__main__':
test_DynamicProbDistribution()
Kenのコードに関連するバージョンを実装しましたが、最悪の場合のO（log n）操作では赤黒木とバランスが取れています。これは、 https：//github.com/google/weighted-dictでweightedDict.pyとして入手できます。
（私はこれをケンの答えへのコメントとして追加したでしょうが、それを行うという評判はありません！）