それぞれに重みのあるアイテムのリストがあり、ランダムなアイテムを選びたいとします。これを実装する最も簡単な方法は、アイテムのリストと、合計でソートされた重みの現在の合計を保持することです。次に、最大重量からランダムな int を選択し、バイナリ検索を実行して、ランダム値に一致するアイテムを見つけます。難しいことではありません。
問題は、バイナリ検索よりもアイテムを選択するためのより最適な方法はありますか?
私の場合、50,000 個のアイテムがあり、重みは同様の大きさ (int) であるため、アイテムを単純に複製することはできず、単純な配列参照になります。
これを行う方法を知る必要はありません。より高速なアルゴリズムがあるかどうか疑問に思っています。私はこれらの多くをしたいかもしれないので、速度は便利かもしれませんが、メモリは無制限ではありません.
この場合、C++ を使用していますが、特定の言語である必要はありません。