c# - 着信番号の最小、最大、および平均の高速計算

Question

プログラムは毎秒約50,000の番号を受信して​​います。

任意の時点で、最後の1秒間に到着した値（数値）の最小値、最大値、および平均を計算する必要があります（特定の瞬間に関して）。

配列またはリスト（バッファー）を使用せずにこれを実行して、到着した数値を格納し、結果を計算する方法はありますか？

バッファを使用する必要がある場合、これを達成するための効率的な方法は何でしょうか？

（バッファからの数値も時々効率的に削除する必要があることに注意してください）

Answer 1

これは、特定の場合に効率を節約するためにいくらか機能するアルゴリズムです。

1. イベントが発生したら、それらを完全にバッファリングし、実行sum中countのmin、、、max（自明）を計算します。

2. average、、、minまたはの要求maxが行われると、バッファの後ろからループスルーし、1秒より古い値の削除を開始します。sumあなたが行くようにそしてあなたが行くように減算しcountます。

   • 値がすべて上記のmin場合は、を保持できますmin。値が以下の場合はmax、を保持できますmax。このシナリオではaverage、、、を効率的minにmax更新しています。

   • 値が下minまたは上maxにある場合は、配列の残りの部分をループして再計算する必要があります。

3. バッファがいっぱいになりすぎないように、ステップ2を1秒に1回程度実行します。このコードは、すべてのバッファー挿入で実行することも、意味のある場所で実行することもできます。

この種の作業に最適な構造は、メモリ割り当てとGCの邪魔にならないようにするための循環バッファです。1秒あたりのメッセージサイズの最悪のシナリオをカバーするのに十分な大きさである必要があります。

更新

使用シナリオに応じて、もう1つ行うことは、上記のアルゴリズムを実行することですが、1x1000msのピースではなく10x100msのチャンクで実行します。つまり、実行中の最小、最大、合計を維持し、それらの10個のチャンクをカウントします。次に、「無効化」シナリオに到達した場合、通常は、最新の100ミリ秒のデータを調べるか、他の9つのチャンクの最小値と最大値をすばやくパスするだけで済みます。

---

@ ja72は、最小値と最大値が無効になっている場合にそれらを見つける手間を省くための優れたアイデアを提供しました。

最小/最大値x_minを保持する代わりに、x_maxは、i_minおよびi_maxを使用してx[i]配列内のそれらが配置されている場所のインデックスを保持します。次に、それらを見つけるのは簡単な場合もありますが、考慮される最後の値が最小値と最大値を保持する場合、新しい制限を確立するためにリスト全体をスキャンする必要があります。

---

サムホルダーはコメントで別の良いアイデアを持っていました-常にソートされている並列配列を維持します。これにより、数値を上または下から外して、新しい最小値と最大値を簡単に見つけることができます。ただし、ここでの挿入速度は少し低下します（順序を維持する必要があります）。

---

最終的に、正しい選択はプログラムの使用特性に依存します。値が読み取られる頻度と挿入される頻度はどれくらいですか？

Answer 2

各要素にタイムスタンプとデータがあり、循環バッファーのサイズとして1秒あたりの要素の最大数を持つ循環バッファーを使用します。

各要素がバッファヘッドに挿入されたら、バッファの反対側で有効期限を確認し、要素を削除します。

削除された要素が最小または最大の場合、新しい最小/最大を計算する必要があります。そうでない場合は、新着に応じて最小/最大を更新します。

平均については、合計を保持し、カウントを保持し、除算します。

Answer 3

キュー内の現在の最大値と最小値（おそらく同じ最小/最大で値の数をカウントし続ける必要があります）とすべての合計値とともに、自分の番号とその到着時刻をキューに保持することはできませんキュー内の数と要素の数。

次に、番号が到着したら、それをキューに追加し、最小/最大/値とカウントを調整します。次に、キューのもう一方の端を見て、最後の番号の到着から1秒以内にないすべての要素を削除し、最大/最小/カウント/合計値を再度調整します。

次に、瞬時に何かを計算し続ける必要はありません。事前に計算されたものを返すだけです（つまり、最小/最大または合計/カウントの現在の値を読み取ります）

@yamanが指摘したように、最小値と最大値だけを保持することはできません。1つを削除すると、新しいものがわからなくなる可能性があります。この場合、おそらくリスト内のすべての番号の2番目のコピーを保持しますが、到着時間で並べ替えるのではなく、値で並べ替えます。次に、このリストから各数値を追加および削除するだけなので、常に最大値と最小値を知ることができます。これにより、2つのコピーを保持することを犠牲にして、バッファ内のすべての要素をスキャンして新しい最大/最小を見つける必要がなくなりますが、このリストの更新はすでに注文されているため安価です。

Answer 4

通常、そのウィンドウ内に到着したすべての数値を保存する必要なしに、特定の時間ウィンドウ内の最小（または最大）値を追跡する効率的な方法があります。（ただし、最悪のシナリオでもすべての数値を格納する必要があるため、すべての数値用にスペースを予約するか、誤った結果が得られる場合があることを受け入れる必要があります。）

秘訣は、次のような値のみを保存することです。

1. 時間枠内に到着し、
2. それ以降の値よりも小さい（または大きい）。

これを実装するための適切なデータ構造は、値とその到着時間を格納する単純な循環バッファです。バッファに2つのインデックスを保持する必要があります。アルゴリズムの簡単な英語の説明は次のとおりです。

起動時：

• 値のN要素バッファーとタイムスタンプの対応するN要素バッファーを割り当てます。valtime
• = 0（または0からN -1までのその他の値）とし、=imaxとします。これは、バッファが現在空であることを示しています。inextimax

時刻に新しい値 new を受け取ったとき t：

• imax≠inextでtime[imax]間隔外にある間は、1ずつインクリメントしますimax（モジュロN）。
• imax≠inextおよびval[inext-1]≥newの場合、1ずつデクリメントしますinext（モジュロN）。
• =とval[inext]=とします。newtime[inext]t
• inext≠の場合、1imax-1ずつインクリメントinextします（モジュロN）; それ以外の場合は、「バッファがいっぱい」の状態を適切に処理します（たとえば、より大きなバッファを割り当てるか、例外をスローするか、単に無視して最後の値が正しく記録されなかったことを受け入れます）。

最小値が要求された場合：

• imax≠inextでtime[imax]間隔外にある間は、1ずつインクリメントしますimax（モジュロN）。
• imax≠の場合、 ;inextを返します。val[imax]それ以外の場合は、時間間隔内に値が受信されなかったことを示すエラーを返します。

受け取った値が独立していて同じように分布している（そしてポアソン過程として到着している）場合、任意の時点でリストに格納されている値の平均数はln（n +1）であることが示されると思います。ここで、nは時間間隔内に受信された値の平均数。n = 50,000の場合、ln（n +1）≈10.82。ただし、これは平均的なものであり、場合によっては数倍のスペースが必要になる可能性があることに注意してください。

---

平均すると、残念ながら同じトリックは機能しません。可能であれば、指数関数的に移動する平均に切り替えることができます。これは、ごくわずかなスペースで簡単に追跡できます（平均の数値と、最後に更新された日時を示すタイムスタンプが1つだけです）。

それが不可能であるが、平均値で少量の平滑化を受け入れても構わないと思っている場合は、たとえば1ミリ秒ごとに平均を計算できます。このように、最後の1秒間の値の平均が要求されるたびに、最後の1001ミリ秒の平均を取得し、それらのミリ秒のうちのどれだけが間隔内にあるかに応じて、最も古いものと新しいものを重み付けすることができます。

起動時：

• 間隔を平均する時間間隔の長さとし、nをサブ間隔の数とします。
• dt =間隔/ nとします。
• 値のn +1要素のバッファーと非負の整数のn+1要素のバッファーを割り当て、両方をゼロで埋めます。sumcnt
• 任意prevの値を設定します。（それは本当に重要ではありません。）

時刻に新しい値 new を受け取ったとき t：

• i= floor（t/ dt）mod（n +1）とします。
• i≠の場合prev：
  • sum[i]からtotalおよびcnt[i]から減算しcountます。
  • Let sum[i]= 0、cnt[i]= 0、let prev= i。
• に追加newして1sum[i]ずつ増やしますcnt[i]。
• に追加newして1totalずつ増やしますcount。

時間に平均値が要求された場合 t：

• i= floor（t/ dt）mod（n +1）とします。
• i≠の場合prev：
  • sum[i]からtotalおよびcnt[i]から減算しcountます。
  • Let sum[i]= 0、cnt[i]= 0、let prev= i。
• j=（i− n ）mod（n +1）=（ + 1）mod（n +1）とします。i
• = frac w（t/ dt）=（t/ dt）− floor（t/ dt）とします。
• total（ − w× sum[j]）/（count− w× ）を返しcnt[j]ます。

Answer 5

@DanReduxは正しいです。入力が変化するため、毎回計算する必要があります。ここで、結果が必要になる頻度に応じて、これらの数値をオンデマンドまたは事前に（つまり、新しいバッチを取得するときに）計算することをお勧めします。

たとえば、平均的なユースケースでこれらの統計を約30秒ごとにポーリングする場合、おそらくオンデマンドで計算し、新しいバッチが入るまで結果をキャッシュします。ただし、実際には使用シナリオに依存します。

どうやって保管するかというと、本当に選択肢はありませんよね？メモリ内の50,000個すべての数値用のスペースが必要です。だから...あなたはそれらを保持するのに十分な大きさのメモリのチャンクが必要です。新しいシーケンスが来るたびに常に2KBを割り当てるのを避けるには、可能な限り最大のデータセットを保持するのに十分な大きさの配列を宣言し、それを再利用する方がよいでしょう。繰り返しますが、これは要件に帰着します。つまり、可能な最大のデータセットが何であるかを知っていますか？新しいメモリチャンクを割り当てると、時間の経過とともにアプリケーションに問題が発生しますか？

Answer 6

N最後の値の平均が（は最新の値であり、最後に考慮された値）である場合、値の平均はすべてを1つのインデックスだけ押し戻し、値を追加すると次のようになりx[0]ます。x[N-1]m_1x[0]x[N-1]m_2x

 m_2 = m_1+(x-x[N-1])/N;
 for(i=N-1;i>0;i--) { x[i]=x[i-1]; }
 x[0] = x;

最小値/最大値x_minを保持する代わりに、配列x_max内のどこにあるかのインデックスをとで保持します。次に、それらを見つけるのは簡単な場合もありますが、考慮される最後の値が最小値と最大値を保持する場合、新しい制限を確立するためにリスト全体をスキャンする必要があります。x[i]i_mini_max

Answer 7

悲しいことに、ありません。それが不可能な理由は、2番目に古いものだけを考慮する必要があるためです。つまり、毎回結果を再計算する必要があります。つまり、ループが大きくなります。

最後の40,000の数値、またはそれらすべてを計算する場合は簡単ですが、時間ベースであるため、毎回リスト全体をループする必要があります。

Answer 8

配列またはリスト（バッファー）を使用せずにこれを実行して、到着した数値を格納し、結果を計算する方法はありますか？

いいえ。あなたが言ったように、情報を保存せずにこれを行うことはおそらく不可能です。ただし、バッファの必要性をなくすために、要件を少し調整することもできます。

バッファを使用する必要がある場合、これを達成するための効率的な方法は何でしょうか？

これにはキューを使用する必要があります。

アイテムが追加されたときに、それが新しい最大値または最小値である場合は、それに応じてそれらの変数を調整します。ここの式を使用して、平均を段階的に調整できます。新しい値から平均を差し引いたものを、セット内の新しいアイテム数（つまり、キューのサイズに1を加えたもの）で割って、古い平均に加算するだけです。

次に、多かれ少なかれ次のようなものがあります。

while(queue.Peek < oneSecondAgo)
{
  oldItem = queue.Peek
  queue.Dequeue();
  if(oldItem == min) //recalculate min
  if(oldItem == max) //recalculate max
  mean += SubtractValueFromMean(oldItem.Value, queue.Count);
}

平均から値を削除するには、同じ式を追加に使用できるはずですが、正ではなく負の値を使用してください...と思います。より良い数学者がここであなたを助ける必要があるかもしれません。

Answer 9

数字が次々と来る場合は、ストップウォッチとwhileループを使用して、すべての数字を1秒間ずつ取得し、最小、最大、および平均を計算します。

double min = double.MaxValue;
double max = double.MinValue;
double sum = 0;
int count = 0;
double avg;
StopWatch sw = new StopWatch();
sw.Start();
while(sw.Elapsed.TotalSeconds <= 1)
{
   // Get the next number in the stream of numbers
   double d = GetNextNumber();

   // Calculate min
   if(d < min) min = d;
   // Calculate max
   if(d > max) max = d;

   // Calculate avg = sum/ count
   sum += d;
   count++;
}

avg = sum/count;

次に、最小、最大、および平均を返します。

Answer 10

バッファまたはキュー内の番号を保持せずに行うことはできません。

その理由は単純です。最大値が期限切れになると（1秒のウィンドウから外れる）、新しい最大値は最後の1秒以内に到着した他の数値であるため、になる可能性のある候補の記録が必要です。新しい最大値。

平均が必要なということは、すべての値が期限切れになったときに効果があり、1秒経過するまでは何も破棄できないことを意味します。

キューを使用するというSamHolderの提案は良いものですが、リストを2つの順序で同時に保持できる特殊なものが必要になる可能性があります。番号を受け取った順序（到着時間）と最大から最小の順序です。 。

次の2つのポインタと前の2つのポインタ（1つは一時的に、もう1つはサイズの点で）を持つ単一のノードオブジェクトを使用すると、両方のリストから要素を同時に削除できます。要素が一時リストから期限切れになると、次のアクセス権があります。サイズリストのポインタは、同じノードオブジェクトにあるためです。

平均は、現在の合計と現在のカウントを維持し、削除された要素を減算し、作成された要素を追加することで維持できるため、平均を計算するためにリスト全体を毎回繰り返す必要はありません。

btillyがSamHolderの投稿へのコメントで示唆したように、リストを使用するよりも最大ヒープと最小ヒープを使用する方が効率的であるため、ヒープとリストの両方にポインターを持つ単一のノードを使用する必要があります。要素を削除するために要素を検索する必要はありません。O（log n）の挿入と削除の保証を維持しながら、ヒープの最上部にない要素を適切に削除する方法を検討する必要がある場合があります。

Answer 11

平均して、考慮すべき3つのケースがあります。

1. あなたの数は整数です。現在の合計とカウントを保持し、合計に新しい値を追加し、合計から古い値を減算し、必要に応じてカウントで除算します。精度の低下を心配する必要がないため、これは簡単です。
2. 数値は浮動小数点であり、精度を0にする必要があります。平均を計算するには、1秒のリスト全体を反復処理する必要があります。
3. 数値は浮動小数点であり、精度がいくらか失われる可能性があります。整数平均の場合と同様に操作し、1000個程度ごとに完全な再計算を実行します。

最小および最大の場合（上記の＃1および＃3にのみ関連）：

• 値でインデックス付けされたtreapの値を保持します。
• また、時間順に二重にリンクされたリストの値を保持します。リストの最初と最後を保存します。
• リストの最初から削除し、リストの最後に追加します。
• 新しい値ごとに：時間リンクリストの先頭に追加します。必要に応じて、時間リンクリストの最後から値を削除します。

リンクリストに値を追加したり、リンクリストから値を削除したりするときに、対応する操作をtreapで実行します。treapから最小値と最大値を取得するには、log（n）時間でfind_minimumおよびfind_maximum操作を実行するだけです。リンクリストの右端から一定時間で物事を削除するときは、log（n）時間でそれらをtreapからも削除します。

Treapは、log（n）時間で最小値を見つけ、log（n）時間で最大値を見つけ、log（n）時間で任意の値を見つけることができます。一般に、データにアクセスするために必要な方法が多ければ多いほど、treapのようなバランスの取れたデータ構造が見栄えが良くなります。