配列内の数字の数

少しの背景。 この投稿は2つの目的で作成しました。 まず、Markdown + Markup Converterを実行します 偶然のように。 第二に、データストリーミングの興味深いタスクについてお話しします。 執筆の終わりに向かって、私は4年前にLogLogに関する投稿を見つけました。 幸運なことに、前の投稿の著者は実装を強調しました。 私は、に依存しています 数学について詳しく説明します。

ルーターがあると想像してみましょう。 多くのパケットがルーターを介して異なるアドレスに送られます。 通信に関与しているアドレスの数に関する統計を取得することに関心があります。 いくつかの問題があります。

• 非常に多くのパッケージがあるので、それらすべてを思い出すことはできません。 出発したパッケージに「戻ってきて！ 私はすべてを許します」
• すべての可能なアドレス 。 ルータにそれほど多くのメモリがありません。

チャレンジ 。 整数のシーケンスがあります 、すべての数値は 前に 。 を使用して異なる数の数を数えるために1つのパスで必要です メモリ

確率的近似Flageaulette-Martinアルゴリズムについて説明します。 TTXアルゴリズム：

• 使用する 記憶！
• 任意の入力で動作します。
• 正確な答えと異なる確率で3回以下の答えを見つける ：
  
  
  
  
  確率は、アルゴリズムのランダムビットによって取得されます。

投稿の最後に、正確な決定論的アルゴリズムが必要な理由を説明します メモリ。

Flageaulette Martinアルゴリズム

実数のセグメントがあると想像してください 。 セグメントでは、独立してランダムにスローします 均一分布によるポイント。 左端の点とゼロの間の距離はどうなりますか？

点がセグメントを分割すると仮定することができます ほぼ同じ長さの小さなサブセグメント。 距離の期待値を慎重に記述し、積分を取ると、


誰かが誤ってセグメントにいくつかのポイントを投げさせ、そして -ゼロから左端の点までの距離。 注文の合計ポイントがあると推定できます 。

Phagelet-Martinアルゴリズムの考え方は、シーケンス内のすべての数値をランダムにスローすることです セグメントごと そして、ゼロから左端の点までの距離を見つけます。 同じ番号が常に1つのポイントに表示され、異なる番号が間隔全体に独立して分布している場合、答えを見つけることができます。

2つの独立したハッシュ関数

ランダムハッシュ関数を使用して、セグメントに数値をスローします。

定義 ハッシュファミリー いずれかの場合、2独立と呼ばれます そして


定義の意味は次のとおりです。 任意の2つのキーを修正します そして 。
キーは異なります。 ランダム変数を見てみましょう そして 。 ランダム性は、関数の選択によって決まります 。 次に、定義により、数量 そして 独立して行動します。

その結果、キーを1つだけ取る場合 その後、量 均等に分配されます 。

たとえば、素数を取る 。 させる 。 すべての線形マッピングのモジュロです ：


のために 。 それから


以来 、システムには1つのソリューションがあります 可能な：


2つの重要なポイントを理解します。 まず、そのような関数のコストを メモリ、これは非常に少ないです。 第二に、よく見ると、フィールドで計算が行われていることがわかります。 、および任意の有限体に一般化できます。

テストコードでは、ガロア体を使用します 。 以下の説明では、ハッシュ関数のファミリーがあると仮定できます。 どこで -二度。 1つの機能の保管にかかる メモリ。

アルゴリズム

させる -二度。
開始する前に、アルゴリズムはランダムにハッシュ関数を選択します 2人の独立した家族から。

シーケンスの要素をセグメントにスローします 。 次の価値を 書き込み：ゼロ、ポイント、 バイナリ形式。 たとえば、 その後、我々は番号を取得 。

で示す バイナリの先行ゼロの数 。 させる 。 最小値は そして 。

アルゴリズムの答え： 。

def init(): h = H.sample() z = 0 def process(a): z = max(z, zero(h(a)) def answer(): return 2**(z + 0.5) 

分析

アルゴリズムの応答は、真の応答よりも3倍大きく、確率が低いことを示すつもりです。 。 同様に、アルゴリズムは、真の確率の3倍小さい応答を返しますが、確率はより低くなります 。 数学の詳細を学習する予定がない場合は、次のパートに進んでください。

で示す すべての異なるシーケンス番号のセット 、そして -その数。

アルゴリズムを分析するには、2組の確率変数が必要です。

• 。 バイナリレコードの先行ゼロの数が1の場合、値は1 少なくとも ; そうでなければ- 。
• 。 価値 変数がゼロより大きい場合 アルゴリズムの完了時に劣らずでした 。

確率に注意してください ：値 セグメント全体に均等に分散 ; -二度 すべて持っている との数字 先行ゼロ。

だから期待 。 上からの分散を制限する


の分散は 線形。 任意の2つ そして




以来 そして 独立した 。 手段


また、 、量 -2独立。

今、量を考えます 。

• 期待の線形性によって。
• 2独立量の線形分散。

させる -最小数は次のとおりです 。 イベント「アルゴリズムが必要なものの3倍の答えを与えた」は、イベントと同等です そしてイベントに等しい 。 マルコフ不等式を適用して、確率を制限します


させる -最大数は次のとおりです 。 同様に、「アルゴリズムが必要な回答の3倍少ない答えを出した」というイベントは、イベントと同等です そしてイベントに等しい 。 チェビシェフの不等式を適用すると、

最終和音：中央値

エラーを減らす方法を理解することは残っています。 アルゴリズムの答えが大きすぎる場合を考えてみましょう。 アルゴリズムを並行して実行する 一度答えの中で中央値を返します。 もしそうなら 、その後、アルゴリズムは、もう確率がないミスをします。 。 同様に、他の方向の誤差を制限すると、


中央値がこのように機能するのはなぜですか？ チェルノフの不等式による。 ランダム変数を取得します 。 価値 アルゴリズムの応答が1の場合 逃げる 。 このイベントの確率は0.52以上です。

中央値 より多くのアルゴリズムが開始します 、これは、アルゴリズムの少なくとも半分の時間がより大きな答えを与えたことを意味します そして 。 その後、 ヘフディング・チェルノフの不等式により


どこで いくつかの定数です。 別のケースも同じように表示されます。

正確なアルゴリズムの下限

誰かが実際に1回のパスで異なる要素の正確な数を1回のパスで見つける決定論的アルゴリズムを思いついたと想像してみましょう。 このようなアルゴリズムは次を使用する必要があることを示します メモリ。

たくさん取る サイズ そしてそれをシーケンスの始まりとして置きます。 アルゴリズムのこの部分をフィードし、そのメモリを調べます。

アルゴリズムメモリのみから、セット全体を抽出できます。 。 現在の状態で数値を入力すると 、アルゴリズムの応答は変わりません。 もし 、それから1ずつ増加します。したがって、各セットに メモリの一意の状態と一致する必要があります。

のさまざまなサブセット サイズ について 。 各セットをビット文字列と一致させたい場合は、

何を読む

1. 「データベースアプリケーションの確率的カウントアルゴリズム」、Flajolet、Martin、1983、 link
2. 「周波数モーメントを近似する空間の複雑さ」、Alon、Matias、Szegedy、1999、 link 。