optimization - 基本的なキューの最適化

Question

典型的なキューをどのように最適化するでしょうか。

アクセス/ストア

メモリ使用量

とにかく圧縮アルゴリズムを実行しようとする以外にメモリを削減するかどうかはわかりませんが、トレードオフとしてかなりの保存時間がかかります-私が考えるすべてを再圧縮する必要があります。

そういうものとして、私はポインタ付きの典型的なリンクリストを考えています....サークルキュー？

何か案は？

ありがとう

編集：上記に関係なく; 基本的に、どのようにして最速/最小のメモリを集中的に使用する基本的なキュー構造を作成しますか？

Answer 1

リンクリストは実際にはあまり一般的ではありません（関数型言語の場合、またはリンクリストが動的配列よりも高速であると初心者が誤って考えている場合を除く）。動的循環バッファがより一般的です。拡大（およびオプションで縮小）の動作は、動的配列の場合とは少し異なります。「データ保持部分」が配列の端を横切る場合、データは連続したままになるように新しいスペースにコピーする必要があります（配列を拡張するだけで、データの中央にギャップが生じます）。

いつものように、それにはいくつかの利点といくつかの欠点があります。

欠点：

• もう少し複雑な実装
• ロックフリー同期には適していません

利点：

• よりコンパクト：最悪の場合（成長したばかり、または縮小しようとしているがまだ縮小していない場合）、スペースのオーバーヘッドは約100％ですが、単一リンクリストのオーバーヘッドはほとんどの場合100％以上です（ただし、データ要素はポインタよりも大きい）、二重リンクリストはさらに悪いです。
• キャッシュ効率：読み取りは前の読み取りの近くで行われ、書き込みは前の書き込みの近くで行われます。したがって、キャッシュミスはまれであり、発生した場合、ほとんどの場合関連性のあるデータを読み取ります（または、書き込みの場合：キャッシュラインを取得します。キャッシュラインはすぐに再度書き込まれる可能性があります）。リンクリストでは、ローカリティが低く、すべてのキャッシュミスの約半分がオーバーヘッド（他のノードへのポインタ）で無駄になっています。

通常、これらの利点は欠点を上回ります。