2

あなたが卸売業者で、顧客を持つ顧客がいると想像してください。取引は顧客の顧客によって行われますが、すべての取引を確認しながら、顧客に請求するだけで、顧客の預金が使い果たされることだけを心配する必要があります。プリペイドサービスです。

トランザクションはサービスに対するものであり、その値はサービスの期間 * レートの関数です。

顧客が蓄積している料金を集計することにより、何百万もの顧客のアカウントの預金の枯渇を監視する方法が必要です。私は私の顧客の顧客と金銭的な取り決めを持っていません。

特定のサービス インスタンスが開始されると、特定のサービスの料金レートが、顧客に代わって提供されるすべての進行中のサービスの累積レートに追加されるため、顧客の BurnRate が増加します。サービスが終了すると、BurnRate も同様に減少します。

良い候補はmin heap、またはpriority queueのように見えますが、左端のノード、つまりイテレータから読み取られる最初のノードが同じ情報を生成するため、従来のツリー/マップも機能することがわかりました。

少なくとも、N 人の顧客の預金が枯渇する瞬間がまったく同じになる可能性があります。これは、「現在」+ (CurrentBalance/BurnRate) として計算される別名 Time-To-Live (TTL) であるため、ヒープよりもマルチマップの方が適している可能性があります。繰り返しますが、経験に基づく洞察は非常に役立ちます。

私の主な質問は、ヒープとマップ/マルチマップのどちらがパフォーマンスが優れているかです。次に、ヒープは重複した値を適切に処理しますか?

TVMIA は、特に経験やベンチマークから、パフォーマンスに関する洞察を得ることができます。

PS:文献を確認したところ、重要な要件が省略されていました。新しいサービスが開始されるか、進行中のサービスが終了すると、顧客の古い TTL ノードを削除してデータ構造を更新し、新しい TTL を持つ新しいノードを挿入する必要があります。priority_queue はこれらの操作をサポートしていないようです。

また、 Stroustrup は、 The C++ Programming Language, 4th Edition の第 31 章の 924 ページで、priority_queue の実装にツリーを使用することが推奨される方法であることを強く示唆しています。上記の「おっと」要件はツリーによってのみ満たすことができるため、私の選択は明確であるため、少なくともこのプロジェクトが完了するまでは、2 つのアプローチを比較するためのベンチマークは行われません。

出席 (または潜伏) し、知識と経験を共有してくれたすべての人に感謝します。

4

1 に答える 1