Лучший подход к хранению больших редактируемых документов в памяти

Question

Мне нужно хранить представление документа в памяти, и я ищу наиболее эффективный способ сделать это.

Предположения

• Документы могут быть довольно большими, до до 100 МБ.
• Чаще всего документ останется неизменным - (т.е. я не хочу сделать ненужное заранее обработка).
• Изменения, как правило, будут довольно близки друг другу в документе (т.е. как пользователь вводит).
• Должна быть возможность быстро применить изменения (без копирования всего документа)
• Изменения будут применяться с точки зрения смещения и новый / удаленный текст (не как линия / цв).
• Для работы в C #

Текущие соображения

• Хранение данных в виде строки. Легко код, быстро устанавливаемый, очень медленно обновить.
• Массив строк, умеренно простой для кодирования, более медленный для установки (так как мы должны разобрать строку в строки), более быстрый для обновления (поскольку мы можем легко вставить удаляемые строки, но для поиска смещений требуется суммирование длин строк).

Должно быть множество стандартных алгоритмов для такого рода вещей (это не миллион миль выделения и фрагментации диска).

Спасибо за ваши мысли.

Answer 1

Good Math, Bad Math недавно написал отличную статью о канатах и ​​буфере разрыва sa, в которой подробно описываются стандартные методы представления текстовых файлов в текстовом редакторе и даже сравниваются их для простоты реализации и производительности. , В двух словах: буфер пробела - большой массив символов с пустым разделом сразу после текущей позиции курсора - это ваша самая простая и лучшая ставка.

Answer 2

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

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

Размер файла: 100 МиБ
Размер блока: 16 КБ
блоков: 6400

Нахождение смещения с использованием бинарного поиска (наихудший случай): 13 шагов
Модификация блока (наихудший случай): Копировать 16384 байта данных и обновить 6400 смещений блока
Изменение блока (средний регистр): копировать 8192 байта данных и обновлять 3200 смещений блока

Размер блока 16 КБ - это случайный пример - вы можете сбалансировать стоимость операций, выбрав размер блока, возможно, исходя из размера файла и вероятности операций. Выполнение простой математики даст оптимальный размер блока.

Загрузка будет довольно быстрой, потому что вы загружаете блоки фиксированного размера, и сохранение также должно работать хорошо, потому что вам придется писать несколько тысяч блоков, а не миллионы отдельных строк. Вы можете оптимизировать загрузку, загружая блоки только по требованию, и вы можете оптимизировать сохранение, сохраняя только те блоки, которые были изменены (содержимое или смещение).

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

Answer 3

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

FWIW, он заключает, что таблицы фигур в целом немного лучше; хотя чистая мудрость, похоже, предпочитает гэп-буферы.

Answer 4

Я бы использовал b-дерево или пропустил список строк или блоков большего размера, если вы не собираетесь много редактировать.

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

Вы можете перемещать линии внутри узла без особых усилий.

Общая длина текста в каждом узле сохраняется в узле, и изменения распространяются до родительских узлов.

Каждая строка представлена ​​массивом данных и начальным индексом, длиной и емкостью. Разрыв строки / возврат каретки не помещаются в массив данных. Обычные операции, такие как разрыв строки, требуют только изменения ссылок на массив; для редактирования строк требуется копия, если емкость превышена. Аналогичная структура может временно использоваться для каждой строки при редактировании этой строки, поэтому вы не выполняете копирование при каждом нажатии клавиши.

Answer 5

Я бы предложил вам взглянуть на Файлы с отображением в памяти (MMF).

Некоторые указатели:

Файлы с отображением в памяти .NET

http://msdn.microsoft.com/en-us/library/ms810613.aspx

Answer 6

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

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

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

Answer 7

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

Если это отформатированный документ, я был бы склонен использовать API-интерфейсы MS Word или аналогичные и просто перенести на них обработку вашего документа - это сэкономит вам очень много времени, так как при разборе документов часто возникает боль *: -)

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