一定時間での追加とランダムな削除を可能にするRandomQueueを作成する必要があります（O（1））。
配列はインデックスを介して常にアクセスできるため、最初に考えたのは、ある種の配列（ArrayListを選択）でバックアップすることでした。
しかし、ドキュメントを見ると、ArrayListsの追加は、基礎となる配列（O（n））の再割り当てが必要になる可能性があるため、償却定数時間と見なされることがわかりました。
償却された一定時間と一定時間は実質的に同じですか、それともすべての追加で完全な再割り当てを必要としない構造を調べる必要がありますか？
配列ベースの構造は別として（私が知る限り、常に償却定数時間の追加があります）、要件を満たすものは何も考えられないので、これを求めています：
- ツリーベースの場合は、せいぜいO（log n）アクセスが可能です
- リンクリストには、O（1）が追加される可能性があります（テールへの参照が保持されている場合）が、ランダムな削除はせいぜいO（n）である必要があります。
ここに完全な質問があります。いくつかの重要な詳細を確認した場合：
RandomQueueを設計および実装します。これは、remove（）操作が、現在キューにあるすべての要素の中からランダムに均一に選択された要素を削除するQueueインターフェイスの実装です（ RandomQueueは、要素を追加したり、ランダムな要素に到達して盲目的に削除したりできるバッグです。）RandomQueueのadd（x）およびremove（）操作は、操作ごとに一定の時間で実行する必要があります。
コメントs
回答
償却された一定時間は、ほとんどの場合、アプリケーションの詳細や実行する予定の使用法の種類を知らなくても、一定時間と同等と見なすことができます。このキューでは、ほとんどの場合、カバーされる可能性があります。
配列リストには、容量の概念があります。これは、基本的に、アイテムの最大サイズ/長さ/数と同じです。これまでに必要とされてきました。したがって、最初は、配列リストにアイテムを追加し続けると、配列リスト自体が再割り当てされて容量が増加しますが、ある時点で、単位時間あたりに追加されるアイテムの平均数は、必然的にアイテムの平均数と一致します。単位時間ごとに削除され（そうしないと、いずれにしても最終的にメモリが不足します）、その時点で配列はそれ自体の再割り当てを停止し、すべての追加はO（1）の一定時間に満たされます。
ただし、 、デフォルトでは、配列リストからのランダムな削除はO（1）ではなく、O（N）であることに注意してください。配列リストは、削除されたアイテムの後のすべてのアイテムを1つ下に移動して、削除されたアイテムの代わりになります。 。 O（1）を実現するには、デフォルトの動作をオーバーライドして、削除されたアイテムを配列リストの最後のアイテムのコピーに置き換えてから、最後のアイテムを削除して、アイテムが移動されないようにする必要があります。ただし、そうすると、キューが正確になくなります。
コメント
- くそー、削除の良い点です。 'それについては考えていませんでした。また、'はランダムに要素を削除しているため、'技術的には'とにかく、その意味でもはやキューではありませんか？
- はい、それはあなたが実際にそれをキューとして扱っていないことを意味します。しかし、削除するアイテムをどのように見つける予定かはわかりません。それらを見つけるメカニズムが、それらが追加された順序でキューに存在することを期待している場合、あなたは運が悪いです。アイテムの順序が文字化けしてもかまわない場合は、問題ありません。
-
RandomQueueがQueueインターフェース、および提供されているremoveメソッドの場合、ヘッドをポップする代わりにランダムに削除するため、'特定の順序に依存する方法はありません。そのときのランダムな性質を考えると、ユーザーは'特定の順序を維持することを期待すべきではないと思います。明確にするために、質問の中で課題を引用しました。ありがとうございます。 - はい、提案した方法でアイテムの削除が行われていることを確認すれば問題ないようです。
- 最後にもう1つ'気にしないでください。 'よく考えましたが、'そうではないようです' s " true " O（1）の追加と" true <の両方を持つことができますdiv id = "9d98d1f06a">
O（1）ランダム削除。 ' 2の間のトレードオフになります。削除はできるが加算はできない単一割り当て構造（配列など）、またはリンクリストのようなチャンク割り当て構造があります。追加はするが削除はしないリスト。これは本当ですか？繰り返しになりますが、ありがとうございます。
回答
質問は、一定時間の償却。したがって、引用された質問に関しては、いいえ、それらは事実上同じではありません*。ただし、実際のアプリケーションでは使用されますか？
償却定数の一般的な問題は、累積債務を支払わなければならない場合があることです。そのため、挿入は通常一定ですが、新しいブロックが割り当てられたときにすべてを再挿入するオーバーヘッドが発生する場合があります。
一定時間と償却一定時間の違いがアプリケーションに関連するかどうかは、この時折の非常に遅い速度は許容されます。非常に多くのドメインの場合、これは一般的に問題ありません。特に、コンテナの有効な最大サイズ（キャッシュ、一時バッファ、作業コンテナなど）がある場合は、実行中に1回だけコストを効果的に支払うことができます。
重要なアプリケーションでは、これらの時間は受け入れられない場合があります。短時間のターンアラウンド保証を満たす必要がある場合は、それを超えることがあるアルゴリズムに頼ることはできません。私は以前にそのようなプロジェクトに取り組んだことがありますが、それらは非常にまれです。
これは実際のコストの高さにも依存します。ベクトルは、再割り当てコストが比較的低いため、パフォーマンスが向上する傾向があります。ただし、ハッシュマップに移動すると、再割り当てがはるかに高くなる可能性があります。繰り返しになりますが、ほとんどのアプリケーション、特にコンテナ内のアイテムに上限がある長寿命のサーバーではおそらく問題ありません。
*ここには少し問題があります。汎用コンテナを作成するために挿入の時間は一定である必要があります。
- コンテナの最大サイズは固定されている必要があります。または
- 個々の要素のメモリ割り当ては一定時間であると想定できます。 。
コメント
- "肝臓サーバー"ここで使用するのは奇妙な言い回しのようです。"ライブサーバー"のことですか？
回答
スループットとレイテンシのどちらを最適化するかによって異なります：
- レイテンシ-機密性の高いシステムには一貫したパフォーマンスが必要です。このようなシナリオでは、システムの最悪の場合の動作を強調する必要があります。例としては、次のようなソフトリアルタイムシステムがあります。 ■一貫したフレームレートを達成したいゲーム、または特定の厳しい時間枠内に応答を送信する必要があるWebサーバー：CPUサイクルを無駄にすることは、遅れるよりも優れています。
- スループットが最適化されたシステムは気にしません。最大量のデータを長期的に処理できる限り、時折ストールします。ここでは、主に償却実績に関心があります。これは通常、数値計算やその他のバッチ処理ジョブに当てはまります。
1つのシステムに異なるコンポーネントを含めることができ、それらを異なる方法で分類する必要があることに注意してください。例えば。最新のテキストプロセッサには、レイテンシに敏感なUIスレッドがありますが、スペルチェックやPDFエクスポートなどの他のタスク用にスループットが最適化されたスレッドがあります。
また、アルゴリズムの複雑さは、私たちが思うほど重要ではないことがよくあります。考える：問題が特定の数に限定されている場合、実際のパフォーマンス特性と測定されたパフォーマンス特性は、「非常に大きい n 」の動作よりも重要です。
コメント
- 残念ながら、私には背景がほとんどありません。質問は次のように終わります：" RandomQueueのadd（x）およびremove（）操作は、操作ごとに一定時間で実行する必要があります"。
- @Carcigenicateは、システムがレイテンシに敏感であるという事実を知らない限り、データ構造を選択するために償却された複雑さを使用することで絶対に十分なはずです。
- これはおそらくそうかもしれないという印象があります。プログラミング演習またはテスト。そして確かに簡単なものではありません。それが問題になることはめったにないことは絶対に真実です。
回答
「償却された一定時間」を求められた場合アルゴリズムの場合、アルゴリズムに時間がかかる場合があります。 たとえば、C ++でstd :: vectorを使用する場合、そのようなベクトルは10個のオブジェクトにスペースを割り当てている可能性があります。11番目のオブジェクトを割り当てると、20個のオブジェクトにスペースが割り当てられ、10個のオブジェクトがコピーされ、11番目が追加されます。かなりの時間がかかります。ただし、100万個のオブジェクトを追加すると、999,980回の高速操作と20回の低速操作が可能になり、平均時間は高速になります。
「定数時間」アルゴリズムを求められた場合、アルゴリズムはすべての操作で常に高速である必要があります。これは、各単一操作が常に高速であることを保証する必要があるリアルタイムシステムにとって重要です。 「一定時間」はほとんどの場合必要ありませんが、「償却一定時間」とは間違いなく 同じではありません。
1/aの可能性があります）が、定数係数a > 1は追加のためにO（1）で償却されます：O（n）操作の(1/a)^nの可能性がありますが、それは大きなnの確率はゼロに近づきます。