QFile искать производительность

Question

Похоже, что QFile при работе с обычным файлом (не специальным файлом устройства ввода-вывода Linux) является произвольным доступом, что означает, что операция поиска имеет постоянную сложность O (1).

Однако я не смог подтвердить это. Как правило, при переходе к определенной позиции в файле (для записи или чтения) std::fstream и QFile обеспечивают сложность времени выполнения в постоянном времени?

Answer 1

Краткий ответ: «да, для практических целей».Длинный ответ ... Это сложно.

Поиск потока файлов в конечном счете вызывает lseek () для базового файлового дескриптора, производительность которого зависит от ядра.

Время выполнения будет зависетьв какой файловой системе вы используете и насколько большие файлы.Поскольку файлы становятся больше, для случайных поисков требуется больше уровней «косвенных» блоков индексации.Но даже для файлов размером до 2 ^ 64 байт количество уровней - всего несколько.

Поэтому в теории поиск, вероятно, равен O (log n);но на практике это по существу постоянно для современной файловой системы.