Закрепление материала: Файл и вектор

Модуль "Файл и вектор" • урок 5 из 6 • ~6 минут

Суть урока. Мы разобрали две базовые структуры данных с противоположными свойствами: файл со строго последовательным доступом и динамический вектор с мгновенным доступом по индексу. Пора проверить, насколько хорошо вы усвоили их логические и физические особенности.

Сравнение файла и вектора: у файла строго последовательный доступ шаг за шагом за O(N), у вектора доступ по индексу сразу в нужную ячейку за O(1) — Файл против вектора: два вида доступа

Краткое резюме модуля

В этом модуле мы рассмотрели спецификацию и реализацию двух фундаментальных структур:

Файл - долговременная последовательность. Логически он определяется строгими правилами конкатенации, что делает доступ к элементам строго последовательным. Физически это поток данных, который пишется на внешние носители (диски) крупными порциями через буфер оперативной памяти.
Вектор - динамическая последовательность переменной длины. Логически вектор предоставляет набор из восьми операций, включая мгновенный доступ к любому элементу. Физически вектор опирается на сплошной блок памяти, что обеспечивает скорость O(1), но делает изменение длины дорогой операцией (O(N)).

Ключевые идеи

Время жизни: Вектор существует только в оперативной памяти во время работы программы. Внешний файл живет дольше программы и имеет собственное имя в операционной системе.
Доступ O(1): Возможен только при сплошном расположении элементов в памяти (как у вектора). Формула адреса: база + индекс × размер элемента. Именно поэтому индексация начинается с нуля.
Буферизация: Чтобы скрыть огромную разницу в скорости между оперативной памятью и внешним диском, запись в файл всегда идет через промежуточный буфер. Важно закрывать файлы, чтобы буфер сбросился на диск.
Компромисс вектора: Мгновенный доступ оплачивается необходимостью полного копирования данных (операция ИЗМЕНИТЬ_ДЛИНУ), если при росте вектора за сплошным блоком памяти не оказывается свободного места.

Коротко: главное

Файл - строго последовательный доступ, долговременное хранение, буферизация.
Вектор - произвольный доступ за O(1), в памяти как сплошной блок, индексация с нуля.
Главный минус вектора - дорогая операция изменения длины (O(N) при нехватке памяти).

Проверьте себя

Вопрос 1

В чем главное отличие доступа к элементам в векторе по сравнению с файлом?

Файл можно читать с любого места, а вектор - только с начала. В векторе доступ к любому элементу происходит мгновенно за O(1), а в файле - строго последовательно. В векторе можно получить доступ только к последнему элементу за O(1).

Вопрос 2

Почему операция изменения длины вектора (ИЗМЕНИТЬ_ДЛИНУ) может занимать время O(N)?

Потому что нужно пересчитать индексы всех элементов в массиве. Из-за работы сборщика мусора, который должен удалить старые значения. При нехватке памяти за текущим блоком требуется выделить новый сплошной блок и скопировать в него все элементы.

Вопрос 3

Зачем нужна буферизация при записи данных в файл на внешний диск?

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

Как вам урок? Спасибо за отзыв!