5

インタビュークラッカーへの質問です。

機器から一定の速度でサンプルを受け取り、一定のストレージ スペースがあるとすると、いつ見てもデータの代表的な読み取り値を取得できるストレージ アルゴリズムをどのように設計しますか? つまり、これまでのシステムの動作の代表です。

私はそれについての考えを得ることができませんでした。ということで、アイデア募集中です。

4

2 に答える 2

27

k要素を格納するためのメモリがあると仮定します。kメモリ内の最初の要素を配列に格納します。ここで、n番目の要素（ここで）を受け取ったら、との間n > kの乱数を生成します。th要素を破棄する場合。それ以外の場合は、配列内のth要素をth要素に置き換えます。r1nr > knrn

kこのアプローチにより、どの段階でも、これまでに受け取った入力要素から均一にランダムに選択された要素が配列に含まれるようになります。

証明帰納法により、k任意の段階の代表的な要素が均一にランダムに分布していることを示すことができます。要素を受け取った後n-1、任意の要素が確率で配列に存在すると仮定しk/(n-1)ます。

n番目の要素を受け取った後、その要素が配列に挿入される確率= k/n。

その他の要素の場合、現在の反復で表される確率=前の反復で表される確率*現在の反復で置き換えられない確率

= (k/(n-1)) * (n-1)/n = k/n.
于 2012-10-04T18:29:34.470 に答える
2

まず、それが属するクレジット。krjampani のアプローチを置き換えるのではなく、詳しく説明します。本当に素晴らしく明快です。

調査すべき点が 1 つありますが、それほど重要ではありません。そこから、問題の関連する、やや隠れた点に到達します。

最初に、結果を再定式化し、別の角度から見ることができることに注意してください。任意の期間について、ゼロとその時間の間の時間間隔からのポイント (データ) は (たとえば、であると仮定) 間隔 [1-n] に均一に分布し、そこから (記述された結果)、固定間隔 [1-k] でのそれらの相対カウントは k/n であることがわかります。 .

これはすべて「統計」であることを理解する必要があります。ストレージ内の古いデータを新しいデータに置き換えることを制御するために、ランダムなポイントを生成します。したがって、記載されている結果は正確な結果ではなく、(統計的に)「期待される値」です。

ただし、統計的な「期待値」はもちろん、実際に得られるものではありません。それは、同じことを再試行する概念的に無限の回数の平均にすぎません。間隔 [1-n] におけるある「期間」からのデータの実際の分布と、[1-k] におけるそれらの相対カウントの関連する派生値が (完全) に近い可能性があるかどうかこの場合、期待値は、乱数 (1 から n の間) を生成する方法に依存します。それが本当にランダムである場合、モンテカルロ型のサンプリングを行い、ガウス型の結果の分布、つまり、同じことを何度も繰り返した場合の実際の点分布が得られます。私たちは目指しました。結果として、非常に多くのポイントが得られるまで、

少し考えてみれば、追加するたびに常に保持する方法がないことが明らかになります。古いポイントを新しいポイントに置き換えることをどのように決定したとしても、完全に均一な分布です。したがって、私たちの目標は、期待偏差を可能な限り大きくすることでなければなりません。

再定式化された問題は次のとおりです。間隔が与えられた場合、その間隔にポイントを無制限に配置する必要があり、その分布が常に「可能な限り」均一になるようにします。その方法は、前のポイントに対して各ポイントに固定の「ステップ」を採用することです。ここで、ステップサイズは間隔の長さに対して相対的に素数であり、できれば 2 つの大きな素数を持ちます。小さい数値の例: 間隔は 11 (ある単位では: '本当の' 値は整数ではなく実数である可能性があります)、ステップ長は 5 と見なされます。ステップは (k*5)mod11: 0, 5, 10, 4, 9, 3, 8, ..です。私たちの場合、間隔の長さが変化するという追加の複雑さがあります。たとえば、ポイント生成を適応させる必要があるかもしれません (I' m わかりません) 元のパラメータ (サイズ、ステップ) が固定されている場合に新しいポイントが配置され、その位置が実際の間隔の長さで拡大されるように調整することによって: 間隔は 11 で、毎回 1 ずつ増加、およびステップ= 5; ポイント: 0、5*(12/11)、10*(13/11) など。私たちの場合、格納された値を置き換える (または置き換えない) ために整数の「スロット」が必要なため、最も近い整数に丸める必要があります (統計に対するその丸めの結果により、ポイント ジェネレータがさらに調整される可能性があります)。 . ここにはこれ以上何もありません。解決すべきことがまだいくつかあります。格納された値を置き換える (または置き換えない) 整数の「スロット」が必要な場合は、最も近い整数に丸める必要があります (統計に対するその丸めの結果により、ポイント ジェネレータがさらに調整される可能性があります)。ここにはこれ以上何もありません。解決すべきことがまだいくつかあります。格納された値を置き換える (または置き換えない) 整数の「スロット」が必要な場合は、最も近い整数に丸める必要があります (統計に対するその丸めの結果により、ポイント ジェネレータがさらに調整される可能性があります)。ここにはこれ以上何もありません。解決すべきことがまだいくつかあります。

最後に、隠れた問題を取り上げます。上記のすべてにおいて、代表的な結果を得るには、均一なサンプリング (一定間隔でポイントを均等に分散させる) が最善の方法であると暗黙のうちに想定してきました。おそらく、「代表的な結果」を、たとえば、特定の測定値を見ていると解釈できます。特定の期間にわたるその値の公正な平均です。測定される値が時間の経過とともに特定の関数として動作することを想像すると、実際には、時間間隔 (間隔の長さで除算) にわたってその関数の INTEGRAL を見ています。さて、その機能の時間の経過による変化が完全にワイルドでない限り、飛び跳ねたり、あらゆる種類の空想的なことをしたりする - その場合、すべての賭けはオフになり、ランダムに何でもすることができます - (「通常の動作」) 関数をどのようにサンプリングするかについて (理論的および実際的に) 確立された方法があります。その積分の「最適な」近似を取得するために、ある間隔にわたって。ランダム (モンテカルロ) は本当に悪いです (サンプル点数 N で 1/sqrt(N) として収束します)。均一なサンプリングははるかに優れています (1/N) - いくつかの特別なケースでは見事に最適ですが、どちらも通常、特定の多項式のゼロでサンプリングすることによって小さくなります。 ONE MORE ポイントのみを追加するたびに DIGITS。

上記を視点として、私たちは次のように元の問題に直面します: どのようにして着実に増加する間隔で点を体系的に生成し、常に間隔全体の点の分布がそれらの特定の（サンプルしたい関数について知っていることによって異なりますが、特定の情報がない場合：ルジャンドル）その間隔にわたる多項式のゼロ（[-1：1]に正規化）。

私の (理論的な) アプローチは、「一定のステップ オーバー 相対プライム インターバル」メソッドを使用することです。間隔に沿って、ステップを「計算」するために、(ルジャンドル) 多項式のゼロの分布 (関数) によって重み付けされます。

于 2012-10-04T23:10:12.217 に答える