Do cache (oblivious|optimal|aware) アルゴリズムは通常、モデルでシーク時間を考慮します。そうでない場合は、シーク時間を考慮したモデルの例があり、このモデルのアルゴリズムの分析があります。
1 に答える
4
はい、個人的にシーク センシティブ アルゴリズムを作成しました。ファイル システムは、シーク センシティブなデータ構造 (アルゴリズムに似ています) を確実に使用します。
たとえば、NTFS (および他の多くのファイルシステム) はデータをB ツリー形式で保存して、シークを最小限に抑え、順次読み取りを最適化します。
残念ながら、ソリッド ステート ドライブやその他のテクノロジが回転メディアを完全に置き換えようとしている 2014 年に、あなたがこの質問をしているのです。SSD はいくらかのシーク ペナルティを受けますが、1 秒あたり 100 回のシークを処理できない回転 HDD と比較して、1 秒あたり数万回のシークを処理できます。これにより、シークの問題は過去数年間に比べてはるかに少なくなります。
同様のより関連性の高い問題は、CPU でのキャッシュラインの一貫性です。RAM の速度が CPU の速度に追いついておらず、マルチコア CPU によってNUMAが実際のパフォーマンスの問題になっています。パフォーマンスを最適化するために、多くのアルゴリズムの実装は、使用するメモリをできるだけ少なくし、遠くのメモリよりも近くのメモリをより頻繁に使用するようにプッシュされています。
たとえば、ヒープ データ構造は、ツリーよりもはるかにキャッシュに適しています。パフォーマンスに敏感なコードは、実用的な選択である場合、ツリーよりもヒープを使用することを選択します。
このキャッシュの問題は、少なくとも過去 10 年間、最優先のパフォーマンスの問題でした。ほとんどすべての重要なプログラムは、速度よりもサイズを最適化すると高速に実行され、キャッシュ ミスが原因です。
于 2014-06-24T23:40:25.670 に答える