12

有限集合からランダムな値を取得することに関する この質問は、私に考えさせました...

Y値のセットからX個の一意の値を取得したいという人はかなり一般的です。たとえば、カードのデッキから手を配りたい場合があります。私は5枚のカードが欲しいです、そして私はそれらがすべてユニークであることを望みます。

今、私はこれを素朴に行うことができます。ランダムなカードを5回選び、複製を取得するたびに、5枚のカードを取得するまで再試行します。ただし、これは、大きなセットからの多数の値の場合はそれほど大きくありません。たとえば、1,000,000のセットから999,999の値が必要な場合、このメソッドは非常に悪くなります。

問題は、どれほど悪いのかということです。O（）値を説明してくれる人を探しています。x番目の数を取得するにはy回の試行が必要です...しかし、いくつですか？任意の値についてこれを理解する方法を知っていますが、シリーズ全体でこれを一般化し、O（）値を取得する簡単な方法はありますか？

（問題は、「これをどのように改善できるか」ではありません。これは、修正が比較的簡単であり、他の場所でも何度も取り上げられていると確信しているためです。）

4

8 に答える 8

5

変数

n =セット内のアイテムの合計量
m =n個のアイテムのセットから取得される一意の値の量
d（i） =ステップiで値を達成するために必要な予想試行回数
i =は1を示します特定のステップ。i∈[0、n-1]
T（m、n） =ナイーブアルゴリズムを使用してn個のアイテムのセットからm個の一意のアイテムを選択するための予想される合計試行回数

推論

最初のステップ、i = 0は、簡単です。どの値を選択しても、最初の試行で一意の値を取得します。したがって：

d（0）= 1

2番目のステップi=1では、少なくとも1回の試行（有効な一意の値を選択する試行）が必要です。さらに、間違った値を選択する可能性があります。このチャンスは（以前に選んだアイテムの量）/（アイテムの合計量）です。この場合は1/nです。間違ったアイテムを選んだ場合、1/nの確率で間違ったアイテムをもう一度選ぶ可能性があります。これに1/nを掛けると、両方の時間で間違ったものを選ぶ確率の合計であるため、（1 / n）2が得られます。これを理解するには、決定木を描くと便利です。ユニークでないアイテムを2回選んだので、もう一度やり直す可能性があります。これにより、（1 / n）3が追加されます。ステップi=1で予想される試行の合計数に。間違った番号を選ぶたびに、間違った番号をもう一度選ぶ可能性があります。これにより、次のようになります。

d（1）= 1 + 1 / n +（1 / n）2 +（1 / n）3 +（1 / n）4 +..。

同様に、一般的なi：番目のステップでは、1つの選択肢で間違ったアイテムを選択する可能性はi / nであり、結果として次のようになります。

d（i）= 1 + i / n +（i / n）2 +（i / n）3 +（i / n）4 + ... =
= sum（（i / n）k）、ここでk∈ [0、∞]

これは等比数列であるため、合計を計算するのは簡単です。

d（i）=（1-i / n）-1

次に、各ステップで予想される試行回数を合計することにより、全体的な複雑さが計算されます。

T（m、n）= sum（d（i））、ここでi∈[0、m-1] =
= 1 +（1-1 / n）-1 +（1-2 / n）-1 +（ 1-3 / n）-1 + ... +（1-（m-1）/ n）-1

上記のシリーズの分数をnで拡張すると、次のようになります。

T（m、n）= n / n + n /（n-1）+ n /（n-2）+ n /（n-3）+ ... + n /（n-m + 2）+ n /（n-m + 1）

次の事実を利用できます。

n /n≤n/（n-1）≤n/（n-2）≤n/（n-3）≤...≤n/（n-m + 2）≤n/（n-m + 1 ）。

シリーズにはm個の項があり、各項は上記の不等式を満たすため、次のようになります。

T（m、n）≤n/（n-m + 1）+ n /（n-m + 1）+ n /（n-m + 1）+ n /（n-m + 1）+..。 + n /（n-m + 1）+ n /（n-m + 1）=
= m * n /（n-m + 1）

（項の量）*（最大の項）の大まかな方法​​で制限する代わりに、何らかの手法を使用して級数を評価することにより、わずかに厳しい上限を確立することが可能である可能性があります（おそらく可能です）。

結論

これは、Big-Oの順序がO（m * n /（n-m + 1））であることを意味します。この表現を現状から単純化する方法は見当たらない。

結果を振り返って意味があるかどうかを確認すると、nが一定で、mがnに近づくと、分母が非常に小さくなるため、結果が急速に増加することがわかります。たとえば、「1,000,000のセットから999,999の値」を選択することについての質問で与えられた例を考えた場合、これは私たちが期待することです。代わりに、mを一定にして、nを実際に大きく成長させると、複雑さはn→∞の限界でO（m）に向かって収束します。これは、「近い」無限サイズのセットから一定数のアイテムを選択するときに、以前に選択した値を選択する確率が基本的に0であるため、私たちが期待することでもあります。衝突。

于 2009-08-18T20:36:22.097 に答える
4

すでにi値を選択している場合、y値のセットから新しい値を選択する確率は次のとおりです。

(y-i)/y.

したがって、（i + 1）番目の要素を取得するための期待試行回数は次のようになります。

y/(y-i).

したがって、x個の一意の要素を選択するための予想される試行回数は合計です。

 y/y + y/(y-1) + ... + y/(y-x+1)

これは、調和数を使用して次のように表すことができます。

y（H y -H y-x）。

ウィキペディアのページから概算を取得します

H x = ln（x）+ガンマ+ O（1 / x）

したがって、y個の要素のセットからx個の一意の要素を選択するために必要な試行回数は次のようになります。

y (ln(y) - ln(y-x)) + O(y/(y-x)).

必要に応じて、H xのより正確な近似を使用することにより、より正確な近似を得ることができます。特に、xが小さい場合、結果を大幅に改善することができます。

于 2009-08-18T17:40:06.273 に答える
3

特定の抽選で以前に表示された値に戻る前に、乱数ジェネレーターが常に一意の値を見つけると仮定したい場合、このアルゴリズムはO（m ^ 2）です。ここで、mは一意の数です。描画している値。

したがって、n個の値のセットからm個の値を描画する場合、最初の値では、一意の値を取得するために最大1個を描画する必要があります。2番目は最大2つ（最初の値、次に一意の値が表示されます）、3番目の3、...m番目のmが必要です。したがって、合計で1 + 2 + 3 + ... + m = [m *（m + 1）] / 2 =（m ^ 2 + m）/2回のドローが必要です。これはO（m ^ 2）です。

この仮定がなければ、アルゴリズムが完了することをどのように保証できるかわかりません。（特にサイクルを持つ可能性のある疑似乱数ジェネレーターを使用すると）同じ値が何度も表示され続け、別の一意の値に到達しない可能性があります。

==編集==

平均的な場合：

最初のドローでは、正確に1回ドローします。2回目の抽選では、1（成功した抽選）+ 1 / n（リピートを引く可能性を表す「部分的な」抽選）を期待します。3回目の抽選では、1（成功した抽選）+を期待します。 2 / n（「部分的な」ドロー...）... m回目のドローでは、1 +（m-1）/nドローを行うことを期待します。

したがって、平均的なケースでは、1 +（1 + 1 / n）+（1 + 2 / n）+ ... +（1 +（m-1）/ n）の描画を行います。

これは、[1 + i/n]のi=0から（m-1）までの合計に等しくなります。そのsum（1 + i / n、i、0、m-1）を示しましょう。

それで：

sum(1 + i/n, i, 0, m-1) = sum(1, i, 0, m-1) + sum(i/n, i, 0, m-1)
                        = m + sum(i/n, i, 0, m-1)
                        = m + (1/n) * sum(i, i, 0, m-1)
                        = m + (1/n)*[(m-1)*m]/2
                        = (m^2)/(2n) - (m)/(2n) + m

低次の項と定数を削除すると、これはO（m ^ 2 / n）であることがわかります。ここで、mは描画される数、nはリストのサイズです。

于 2009-08-18T14:02:15.417 に答える
2

このアルゴリズムの最悪のケースは、N個のアイテムのフルセットを選択する場合です。これは、質問するのと同じです。平均して、各面が少なくとも1回現れる前に、N面のダイを何回転がす必要がありますか。

回答：N * H N、ここでH NはN番目の調和数であり、

代替テキスト
で有名な値で近似されlog(N)ます。

これは、問題のアルゴリズムがであるということを意味しますN log N。

楽しい例として、通常の6面ダイスを各数字のいずれかが表示されるまでロールすると、平均して6 H 6 =14.7ロールかかります。

于 2009-10-20T22:09:09.737 に答える
2

あなたの実際の質問は、実際には私が答えたものよりもはるかに興味深い（そして難しい）ものです。私は統計が得意ではありませんでしたが（そして、統計を行ってからしばらく経ちました）、直感的には、そのアルゴリズムの実行時の複雑さはおそらく指数関数のようなものになると思います。選択された要素の数がアレイのサイズと比較して十分に少ない限り、衝突率は非常に小さいため、線形時間に近くなりますが、ある時点で、衝突の数はおそらく急速に増加し、実行されます。 -時間は無駄になります。

これを証明したい場合は、必要な要素数に応じて、予想される衝突数を適度に巧妙に処理する必要があると思います。誘導によっても可能かもしれませんが、そのルートをたどるには、最初の選択肢よりも賢さが必要だと思います。

編集：それにいくつかの考えを与えた後、ここに私の試みがあります：

要素の配列が与えられ、ランダムで異なる要素mを探します。nそうすれば、th番目の要素を選択したいときに、iすでにアクセスした要素を選択する確率がであることが簡単にわかります(i-1)/m。これは、その特定のピックで予想される衝突の数です。ピッキングn要素の場合、予想される衝突の数は、各ピックの予想される衝突の数の合計になります。これをWolframAlpha（sum（i-1）/ m、i = 1 to n）に接続すると、答えが得られます(n**2 - n)/2m。その場合、ナイーブアルゴリズムの平均ピック数はですn + (n**2 - n)/2m。

私の記憶が完全に失敗しない限り（実際には完全に可能です）、これは平均的なケースの実行時間を与えますO(n**2)。

于 2009-08-18T13:50:24.667 に答える
2

これには美しいO（n）アルゴリズムがあります。次のようになります。n個のアイテムがあり、そこからm個のアイテムを選択するとします。関数rand（）が0から1までの乱数を生成すると仮定します。アルゴリズムは次のとおりです。

items_left=n
items_left_to_pick=m
for j=1,...,n
    if rand()<=(items_left_to_pick/items_left)
        Pick item j
        items_left_to_pick=items_left_to_pick-1
    end
    items_left=items_left-1
end

証明は自明ではありませんが、このアルゴリズムが実際にm個のアイテムの各サブセットを等しい確率で選択することを証明できます。残念ながら、現時点では参考資料がありません。

編集このアルゴリズムの利点は、O（n）メモリを使用するシャッフルと比較して、O（m）メモリのみを使用することです（アイテムが単純な整数であるか、オンザフライで生成できると想定）。

于 2009-08-18T13:51:15.150 に答える
0

この質問に詳細に答える前に、フレームワークを定義しましょう。n個の個別のオブジェクトのコレクション{a1、a2、...、an}があり、このセットからm個の個別のオブジェクトを選択して、特定のオブジェクトajが結果に表示される確率がすべてのオブジェクトで等しくなるようにするとします。 。

すでにk個のアイテムを選択していて、フルセット{a1、a2、...、an}からアイテムを選択することはめったにない場合、そのアイテムが以前に選択されていない確率は（nk）/nです。これは、新しいオブジェクトを取得する前に取得する必要のあるサンプルの数が、パラメーター（nk）/ nで幾何学的であることを意味します（ランダムサンプリングの独立性を前提としています）。したがって、1つの追加アイテムを取得するために期待されるサンプル数はn /（nk）であり、kがnと比較して小さい場合は1に近くなります。

結論として、ランダムに選択されたm個の一意のオブジェクトが必要な場合、このアルゴリズムは次のようになります。

n / n + n /（n-1）+ n /（n-2）+ n /（n-3）+ .... + n /（n-（m-1））

Alderathが示したように、これは次のように見積もることができます。

m * n /（n-m + 1）。

この式からもう少しわかります。*新しい一意の要素を取得するために予想されるサンプル数は、すでに選択されているオブジェクトの数が増えるにつれて増加します（これは論理的に聞こえます）。* mがnに近い場合、特にnが大きい場合は、非常に長い計算時間が予想されます。

セットからm個の一意のメンバーを取得するには、ランダム順列を取得するためのDavidKnuthのアルゴリズムの変形を使用します。ここでは、n個のオブジェクトが配列に格納されていると仮定します。

for i = 1..m
  k = randInt(i, n)
  exchange(i, k)
end

ここで、randIntは{i、i + 1、... n}から整数をサンプリングし、交換によって配列の2つのメンバーが反転します。シャッフルする必要があるのはm回だけなので、計算時間はO（m）ですが、メモリはO（n）です（ただし、a [i]<>iのようにエントリのみを保存するように調整できます。時間とメモリの両方でO（m）ですが、定数は高くなります）。

于 2009-08-24T12:15:40.917 に答える
0

ほとんどの人は、数がすでに実行されている場合は、検索にも時間がかかることを忘れています。

必要な試行回数は、前述のように、以下から評価できます。

T(n,m) = n(H(n)-H(n-m)) ⪅ n(ln(n)-ln(n-m))

これはn*ln(n)、m

ただし、これらの「試行」ごとに、ルックアップを実行する必要があります。これは、単純なO(n)ランスルー、またはバイナリツリーのようなものである可能性があります。n^2*ln(n)これにより、またはの合計パフォーマンスが得られますn*ln(n)^2。

m（ ）の値が小さい場合は、 -inequationを使用しm < n/2て非常に適切な近似を行うことができ、次の式が得られます。T(n,m)HA

2*m*n/(2*n-m+1)

mに行くように、これは試行とパフォーマンスnの下限を与えます。O(n)O(n^2)O(n*ln(n))

ただし、すべての結果は、私が予想していたよりもはるかに優れています。これは、アルゴリズムが実際には多くの重要でないケースで問題なく動作する可能性があることを示しています。

于 2010-01-30T22:01:03.393 に答える