c++ - Qファイルシーク性能

Question

通常のファイル (特別な Linux I/O デバイス ファイルではない) を操作する場合、QFileはランダム アクセスであると思われます。つまり、シーク操作は一定時間の複雑さ O(1) を持つことを意味します。

ただし、これを確認することはできませんでした。一般に、(書き込みまたは読み取りのために) ファイル内の特定の位置にジャンプするとき、一定時間の実行時間の複雑さstd::fstreamを提供しますか?QFile

Answer 1

短い答えは「はい、実用的な目的のために」です。長い答えは... 複雑です。

ファイル ストリームでのシークは、最終的に、基になるファイル記述子で lseek() を呼び出します。そのパフォーマンスはカーネルに依存します。

実行時間は、使用しているファイル システムとファイルの大きさによって異なります。ファイルが大きくなるにつれて、ランダム シークではより多くのレベルの「間接的な」インデックス ブロックを追跡する必要があります。しかし、最大 2^64 バイトのファイルでも、レベル数はほんの一握りです。

したがって、理論的には、シークはおそらく O(log n) です。しかし実際には、最新のファイル システムでは基本的に一定です。