私は要素のリストを2つの要素で構成しています：数値と文字列です。私はしたい： i）リストの各要素について、与えられた入力（実行時）と組み合わされた番号から始まる確率を生成する。 ii）対応する確率に従ってリストから文字列をランダムに選択する。リスト内の要素を選択するためのC++高速メソッド
これは最速の方法ですか？
例： 入力：[2.0、 'A']、[1.0、 'B']、[2.5、 'C']、ランタイム
（I）：[0.3、「 「]、[0.2、 'B']、[0.5、 'C']]
（II）：選択して 'C'
を私はあなたのリストは潜在的に非常に大きいと仮定していますので、あなたはそれをしたいですこの小さな3要素の例ではなく、スケールが速くなければなりません。私の提案はおそらく小さな配列のアルゴリズムを遅くするでしょう。
あなたのリストを1つに変換します。ここでの数字は、あなたの古い数字と前の合計の合計です。これにより、数字が昇順になるため、バイナリ検索が可能になります。
[[2.0, 'a'],[3.0, 'b'],[5.5, 'c']]
次に、乱数を生成するときは、0と最後の合計（0-5.5）の間で乱数を生成します。
次に、中央の要素を見てください。その数があなたの生成した数よりも少ない場合は、その点と終わりの中間を見ますが、それより大きい場合は、最初の数が見つかるまでその点と開始点の中間を見ますこれは選択した要素である生成された番号よりも大きくなります。 （上記で0.5を生成すると、 "a"を選択する、つまり2.1を生成した場合、 "b"を選択する）
バイナリ検索はコストがもう1つだけであるため効率的です2つのオプションのセットを倍増する（アレイ内の32個の読み込みでは、40億個以上の要素で正しい答えが見つかるでしょう）
どのようなテクニックを試しましたか？ – Rotem
「与えられた入力（ランタイム）と組み合わせた数から始まる確率を生成する」 – sameerkn
1.数字の合計を計算し、確率を正規化する2.乱数[0..1]をとり、乱数がなるまでリストを反復する前の項目の合計より大きく、sum + current probより小さい場合は、このリスト要素3を取ります。高速検索のために、スキップリストを実装します –