Сложность времени модификации файла?

Question

Какова временная сложность (по размеру файла) этих модификаций файлов?

• Перезапись
• добавляющих (вставка в конце)
• Предварения (вставку в начале)
• Вставки в середине.

Я ожидаю, что перезапись и добавление будут быстрыми. Я вижу, что добавление будет достаточно быстрым, если файлы структурированы как C++ deque s, но я никогда не видел языка, допускающего низкоуровневое добавление. Я сомневаюсь, что вставка посередине будет быстрой, хотя я полагаю, что есть структуры данных, которые могли бы ускорить работу.

Answer 1

В большинстве файловых систем:

• Перезапись файла О (п), где п число байтов, которые должны быть записаны.
• Добавление файла O (n), где n - количество записываемых байтов.
• Prepending is O (n + m), где n - количество записываемых байтов, а m - количество байтов, находящихся в данный момент в файле.
• Вставка - это O (n + m), где n - количество записываемых байтов, а m - количество байтов, находящихся в данный момент в файле.

O (n + m) для вставки - наихудший случай. Когда вы вставляете в файл, вам нужно переместить все байты, находящиеся в данный момент в файле, с точки вставки вниз, чтобы сделать отверстие для n байтов, которые нужно вставить. Так что если у вас есть:

This is a test system. 

И вы хотите вставить «аварийное вещание» после «теста», то вы должны сначала сделать отверстие для вставленного текста:

This is a test       system. 

И тогда вставьте новый текст:

This is a test of the emergency broadcast system. 

Таким образом, файл концептуально очень похож на массив. Если вы хотите вставить что-то спереди или посередине, вы должны сделать отверстие для него. Если вы хотите что-то удалить, вы должны заполнить пустое пространство.

Существуют файловые системы, позволяющие вам патч-файлы вместе с несмежными блоками. То есть, вы можете иметь то, что логически, как:

<pointer to "This is a test" chunk> 
<pointer to "of the emergency broadcast" chunk> 
<pointer to "system." chunk> 

Файловая система заботится о расщеплении и сливающихся ломти по мере необходимости. Эти файловые системы не совсем редки, но эта функциональность обычно не используется обычными программами.