Каждый, кто пытался запрограммировать хотя бы простейший редактор текста на низком уровне, сталкивался с задачей организации памяти для хранения редактируемого текста. Структура данных для хранения текста должна удовлетворять следующим требованиям:
- иметь малые накладные расходы по памяти. Большая часть доступной памяти должна использоваться для хранения текста, а не служебной информации;
- допускать эффективную вставку и удаление в произвольном месте текста.
Удовлетворить эти требования одновременно непросто. Если рассмотреть широкоизвестные структуры данных, такие как массивы, списки, деревья, стеки, очереди, кольцевые буфера — то такой структуры, которая бы позволила эффективно выполнить оба требования, не встречается. В случае массива имеем незначительные накладные расходы по памяти, но операция вставки имеет сложность O(n), где n — размер редактируемого текста. В случае списка сложность вставки и удаления составляет O(1), однако накладные расходы по памяти в несколько раз превышают размер собственно текста. Деревья, кучи, кольцевые буфера, ассоциативные массивы и прочие структуры и вовсе неприменимы для хранения текста в редакторе.
Встречаются гибридные решения, когда текст хранится в наборе массивов, которые, в свою очередь, объединены в список. Казалось бы, такой подход позволяет объединить преимущества массивов и списков (быстрая вставка/удаление при низких накладных расходах по памяти). Однако такое решение сложно в реализации. Также оно приводит к фрагментации памяти.
Предлагаю вашему вниманию эффективную структуру данных для хранения редактируемого текста, которая проста в реализации, имеет константные накладные расходы по памяти и быструю вставку/удаление в произвольном месте. Также она позволяет эффективно редактировать файлы, которые целиком не умещаются в оперативную память.
Несмотря на то, что эта структура данных была открыта давно и использовалась в текстовых редакторах на старых ЭВМ в 8-битную эпоху, это тайное знание предков было в значительной мере утеряно и в современных редакторах встречается редко. Попробуйте открыть файл, состоящий из одной строки мегабайт на 10, в Notepad или Far. Вставка и удаление символов будет длиться секундами.
Описание
Берем блок памяти фиксированного размера (в старых 8-битных ЭВМ под этот блок берется вся свободная память) и размещаем в начале этого блока редактируемый текст до курсора, а в конце блока — текст после курсора. Текст хранится в памяти двумя непрерывными кусками, а в промежутке между ними находится вся доступная для текста свободная память. В процессе редактирования текста поддерживаем этот инвариант: в начале буфера находится текст до курсора, а в конце — текст после курсора. Всё!
Такая структура данных называется в английской терминологии Gap Buffer. Русское название мне неизвестно, встречается только термин «буферное окно» в русской Википедии. Не знаю, правда, доверять такому переводу термина или нет.
Анализ
- Операции вставки и удаления — дешевые: O(1) как при вставке отдельного символа, так и их группы (например, вставка из буфера обмена).
- Накладные расходы по памяти — низкие: O(1). Нужно хранить только положение курсора и общий размер буфера.
- Операция поиска элемента по индексу — дешевая: O(1).
- Операция копирования участка содержимого (например, для копирования в буфер обмена или сохранения текста на диск) — O(n), где n — размер копируемого участка. Сложность такая же, как для массива.
Иными словами, для перечисленных операций удалось реализовать все те преимущества, какие дает массив.
При использовании Gap Buffer в текстовом редакторе появляются расходы на перемещение курсора. Ведь для обеспечения инварианта приходится копировать текст из нижнего заполненного участка буфера в верхний или наоборот. Сложность перемещения курсора — O(n), где n — расстояние, на которое перемещается курсор. При перемещениях из начала в конец текста может проявиться ощутимая пользователем задержка. Однако перемещения из начала в конец текста — относительно редкая операция при его редактировании. Чаще встречаются перемещения на символ, строку или страницу вперед или назад, и тогда приходится перемещать лишь небольшой участок текста. Задержка будет незаметна даже для 8-битных ЭВМ.
Таким образом, Gap Buffer эксплуатирует то свойство процесса редактирования текста, что операции вставки и удаления всегда происходят в том месте, где находится курсор; в свою очередь, перемещения курсора обычно бывают невелики.
Вариации
1. Теневой курсор записи
В своей базовой реализации Gap Buffer все же может вызывать нежелательные задержки. Например, при поиске текста или использовании закладок могут происходить значительные перемещения курсора. Также не всякое перемещение курсора по тексту сопровождается редактированием. Отсюда решение: ввести невидимый пользователю «курсор записи», который соответствует разрыву в Gap Buffer. Этот курсор перемещается только тогда, когда пользователь начинает вставку или удаление текста. При простых же перемещениях видимого курсора по тексту или замене (то есть когда общий размер текста не меняется) курсор записи не перемещать. Тем самым устраняются задержки при любых случайных перемещениях видимого курсора при просмотре текста, использовании закладок, поиска и т.д.
2. Редактирование файлов, которые не умещаются в оперативную память
В нашу эпоху оперативной памяти гигабайтного размера мало кто реализует редакторы, которые обходятся без полной загрузки текста в память. Большинство созданных людьми документов умещаются в нее, поэтому просто нет смысла усложнять редактор. Однако иногда возникает необходимость редактировать большие файлы, которые не умещаются даже в память сегодняшних компьютеров. Это могут быть машинно-генерированные данные, такие как лог-файлы или текстовое представление записи с каких-нибудь датчиков или приборов.
С помощью Gap Buffer можно эффективно реализовать редактирование файлов, размер которых превышает размер оперативной памяти компьютера. Можно заметить, что Gap Buffer фактически представляет собой два стека, один из которых хранит данные до курсора, а второй — после курсора. Первый из стеков растет вверх, а второй — вниз. Отсюда идея: реализовать оба стека в виде файлов, при этом храня в оперативной памяти только те их участки, которые находятся ближе к вершине.
Стек в памяти может расти вверх или вниз, а стек, реализованный в виде файла, может расти только вверх. Только к концу файла мы можем дописывать данные или наоборот, удалять их оттуда. Если вернуться теперь к операциям с памятью и рассмотреть стеки, растущие в разные стороны — то видно, что в стеке, растущем вверх, данные располагаются в прямом порядке по отношению к последовательности помещения их на стек, а в стеке, растущем вниз — в обратном порядке. Так что, если мы хотим реализовать Gap Buffer в виде двух стеков, растущих вверх — нам придется поменять порядок элементов во втором стеке, который хранит текст после курсора. Поэтому тот временный файл, который содержит данные после курсора, должен их содержать в обратном порядке, задом наперед.
Во временных файлах мы будем хранить не все содержимое стеков, а только их нижнюю часть. Верхняя часть будет располагаться в оперативной памяти, образуя как бы «локальный» Gap Buffer и позволяя пользователю, как и прежде, быстро редактировать текст и перемещаться по нему в некоторых пределах. При перемещениях курсора по тексту за пределы загруженного в память участка, его часть, наиболее далекая от курсора, будет сохраняться в один из временных файлов, а из другого будет подгружаться недостающая часть.
По окончании редактирования текста мы просто перемещаем курсор в его конец. Весь текст попадает в первый стек, растущий вверх, то есть первый временный файл. В оперативной памяти, возможно, остается еще кусок текста — его просто дописываем к файлу. После этого первый временный файл содержит сохраненный текст.
Можно реализовать еще несколько оптимизаций. При открытии файла, например, курсор обычно находится в его начале. Весь текст поэтому должен располагаться во втором стеке, то есть мы должны практически всё исходное содержимое редактируемого файла скопировать во второй временный файл задом наперед. Это длительная операция. Ее можно избежать, если отложить создание второго временного файла до тех пор, пока в этом не возникнет необходимость. То есть до тех пор, пока содержимое хвоста исходного файла полностью совпадает с содержимым второго стека. В этот период, вместо использования второго временного файла, мы можем подгружать информацию из исходного файла. Для создания второго временного файла, таким образом, придется сначала переместить курсор по тексту на расстояние, превышающее размер свободной оперативной памяти, потом что-нибудь там отредактировать, а потом вернуться назад, к началу текста.
Такую же оптимизацию можно реализовать и для первого временного файла. Не создавать его до тех пор, пока в нем не возникнет необходимость. А возникнет она не ранее, чем содержимое находящейся на диске части первого стека перестанет совпадать с начальным участком исходного файла. Также можно использовать «теневой курсор записи» и тем самым избежать ненужных операций копирования при перемещениях курсора по тексту без редактирования. Тогда, если пользователь далеко перемещает курсор по тексту без редактирования, скорость работы будет не хуже, чем у программы простого просмотра текста без полной его загрузки в память.
Реализованное описанным способом редактирование текста без полной его загрузки в память имеет, таким образом, умеренные накладные расходы по дисковому пространству: для временных файлов требуется место, равное размеру текста.
Интересно, что даже если текст большого объема в принципе влезает в оперативную память, при использовании редактора, который не загружает его целиком, такой документ будет быстрее открываться. Снова-таки повышение удобства для пользователя.
Заключение
Я уже не первый раз сталкиваюсь с тем, что некоторые технологии, разработанные для старых компьютеров с ограниченными возможностями, оказываются в наше время забытыми, что приводит к распространению неэффективных решений. Надеюсь, что описанное в этой статье «тайное знание предков» поможет появлению на свет хороших текстовых редакторов.
Автор: MichaelBorisov
