1

この質問は、リンクの下の質問の延長です。

加重乱数

私の質問は、各要素の重みが頻繁に動的に変更されるという追加の条件で重み付けされた乱数をサンプリングすることです。

編集異なる重みで選択する N 個の要素があるとします。

静的な重みの場合、Walker のエイリアス メソッドでは、エイリアスのセットアップに O(N) の時間が必要ですが、サンプリング コストは O(1) であるため、目標を達成するのに最適な方法の 1 つです。

また、二分探索法では、累積配列を作成するために O(N) も必要であり、サンプリング コストは log(N) です。

ただし、私の場合、重みは頻繁に変更されるため、重みを変更する時間の複雑さも重要です。

したがって、データ構造の変更と O(N) 未満のサンプリングの両方に時間の複雑さを持つ既存のライブラリまたはアルゴリズムがあることを知りたいです。

編集コメントを読んでいるうちに、追加の条件を課す必要があることに気付きました。各修正フェーズでは、数個 (ほとんどが 2 つ) の重みのみが修正され、それらの修正によって重みの合計が変更されることはありません (正規化条件)。

解決策があれば、重みが実数の場合にも使用できるかどうかも知りたいです。

4

1 に答える 1

2

私は同じ問題に直面しています。それを解決するための現在の計画について説明しますが、他の提案や実装の指針に感謝します。

14.1私の現在の計画は、Cormen/Leiserson/Rivest による「Introduction to Algorithms」のセクションで説明されているように、Dynamic Order Statistics のアルゴリズムを適応させることです。重みをキーとして、赤黒木などのバランスの取れた二分木に要素を配置します。各ノードがそのサブツリーに重みの合計を格納するように、ツリーを拡張します。ルートは、ツリー全体の重みの合計を格納しますS。サブツリーの合計は、動的順序統計のサブツリー サイズと同じ方法で、ツリー操作中に更新できます。加重サンプリングを行うには、数値を[0..S]均一にサンプリングしますx。次に、順序通りのトラバーサルでN先行するノードの重みの合計がであるが、合計との重みがN<xN>x-- 動的順序統計の OS-Select 操作に似ています。

于 2012-09-24T17:18:09.337 に答える