ハッシュテーブルから与えられた確率に従ってアイテムをピックアップしたいと思います。たとえば、文字列「リンゴ」「バナナ」「パイナップル」をハッシュテーブルに格納しています。「りんご」が 30%、「バナナ」が 30%、「パイナップル」が 40% になる確率を指定して、ハッシュテーブルからアイテムを取り出したいと思います。誰でもこれで私を助けることができますか？
Hashtable を使用する必要がある理由は、特定の本の単語である大量の文字列を実際に扱っているからです。単語の確率は、本での出現に依存します。たとえば、ある本に 100,000 の単語があり、「犬」という単語が 1,000 回出現するとします。関数から呼び出しているときに「犬」を取得する確率は、1,000/100,000 のはずです。
これはあなたのアイテムの配列です：
[apple, banana, pineapple]
これは確率の配列です:
[0.3, 0.3, 0.4]
これは、累積確率の配列です。
[0.3, 0.6, 1.0]
確率に従ってランダムなアイテムを選択するには、[0, 1] の範囲で乱数 R を選択し、累積確率が R 以上である最初のアイテムを選択します。
たとえば、R = 0.52839 を生成する場合、0.6 は累積確率が R 以上の最初のアイテムであるため、バナナを選択します。
Rで指定した項目を二分探索できるので、これはlog(n)解です。
ここでハッシュテーブルがどのように役立つかはわかりません。単純な配列で十分です。
Alias Tableの使用を検討する必要があります。これは、多数の不等確率を処理するための非常に効率的な方法です。