Лучший подход к хранению в памяти больших редактируемых документов
https://stackoverflow.com/questions/838712
-
22-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Мне нужно сохранить представление документа в памяти, и я ищу наиболее эффективный способ сделать это.
Предположения
- Документы могут быть довольно большими, до до 100МБ.
- Чаще всего документ останется неизменным - (т.е.Я — нет Хотите сделать ненужное заранее переработки).
- Изменения, как правило, происходят довольно близко друг другу в документе (т.е.как пользователь вводит текст).
- Должна быть возможность быстрого применения изменений (без копирования всего документа).
- Изменения будут применены в части смещения и новый/удаленный текст (не как line/col).
- Работать на C#
Текущие соображения
- Хранение данных в виде строки.Легко код, быстро устанавливается, очень медленно устанавливается обновлять.
- Массив строк, довольно простой в кодировании, медленнее задается (поскольку нам приходится разбирать строку на строки), быстрее обновляется (поскольку мы можем легко вставлять строки удаления, но для поиска смещений требуется суммировать длины строк).
Для подобных вещей должно быть множество стандартных алгоритмов (это не миллион миль выделения и фрагментации диска).
Спасибо за ваши мысли.
Решение
Я бы предложил разбить файл на блоки.Все блоки имеют одинаковую длину при их загрузке, но длина каждого блока может измениться, если пользователь редактирует эти блоки.Это позволяет избежать перемещения 100 мегабайт данных, если пользователь вставляет один байт спереди.
Для управления блоками достаточно лишь объединить их — вместе со смещением каждого блока — в список.Если пользователь изменяет длину блоков, вам необходимо обновить только смещения блоков после этого.Чтобы найти смещение, вы можете использовать двоичный поиск.
Размер файла: 100 МБ
Размер блока: 16 КБ
Блоки:6400
Поиск смещения с помощью двоичного поиска (худший случай): 13 шагов
Изменение блока (худший случай): скопировать данные размером 16384 байта и обновить смещения блоков 6400
Изменение блока (средний случай): скопировать данные размером 8192 байта и обновить смещения блоков 3200
Размер блока 16 КБ — это всего лишь случайный пример — вы можете сбалансировать затраты на операции, выбрав размер блока, возможно, исходя из размера файла и вероятности операций.Выполнив простые математические действия, вы получите оптимальный размер блока.
Загрузка будет довольно быстрой, потому что вы загружаете блоки фиксированного размера, и сохранение тоже должно работать хорошо, потому что вам придется писать несколько тысяч блоков, а не миллионы отдельных строк.Вы можете оптимизировать загрузку, загружая блоки только по требованию, и оптимизировать сохранение, сохраняя только все измененные блоки (содержимое или смещение).
Наконец, реализация тоже не будет сложной.Вы можете просто использовать StringBuilder класс для представления блока.Но это решение не будет хорошо работать для очень длинных строк, длина которых сравнима с размером блока или больше, потому что вам придется загружать много блоков и отображать только небольшие части, а остальные будут располагаться слева или справа от окна.Я предполагаю, что в этом случае вам придется использовать двумерную модель разделения.
Другие советы
Хорошая Математика, Плохая Математика написали отличную статья о веревках и буфере разрываНекоторое время назад здесь подробно описывались стандартные методы представления текстовых файлов в текстовом редакторе и даже сравнивались их простота реализации и производительность.В двух словах:буфер пробелов — большой массив символов с пустой секцией сразу после текущей позиции курсора — это ваш самый простой и лучший выбор.
Эта статья может оказаться вам полезной --- Структуры данных для текстовых последовательностей который описывает и экспериментально анализирует несколько стандартных алгоритмов и сравнивает [среди прочего] буферы пробелов и таблицы частей.
Кстати, он приходит к выводу, что в целом таблицы фигур немного лучше;хотя net.wisdom, похоже, предпочитает буферы с пробелами.
Я бы посоветовал вам взглянуть на Файлы, отображаемые в памяти (ММФ).
Некоторые указатели:
Я бы использовал b-дерево или список пропуска строк или блоки большего размера, если вы не собираетесь много редактировать.
У вас не будет особых дополнительных затрат на определение концов строки при загрузке, поскольку вам все равно придется посещать каждого символа при загрузке.
Вы можете перемещать линии внутри узла без особых усилий.
Общая длина текста в каждом узле сохраняется в узле, а изменения распространяются до родительских узлов.
Каждая строка представлена массивом данных, а также начальным индексом, длиной и емкостью.Возвраты разрыва строки/каретки не помещаются в массив данных.Обычные операции, такие как разрыв строк, требуют только изменения ссылок на массив;для редактирования строк требуется копия, если емкость превышена.Подобная структура может временно использоваться для каждой строки при редактировании этой строки, чтобы вам не приходилось выполнять копирование при каждом нажатии клавиши.
Внезапно я подумал, что индексированный связанный список будет достаточно эффективен для такого рода вещей, если у вас нет каких-либо очень длинные линии.
Связанный список предоставит вам эффективный способ хранения данных и добавления или удаления строк по мере редактирования пользователем.Индексирование позволяет быстро перейти к определенной точке файла.Идея такого рода хорошо подходит для операций типа отмены/повтора, поскольку должно быть достаточно легко сортировать изменения на небольшие атомарные операции.
Хотя я бы согласился с точкой зрения Крисба, вероятно, лучше сначала заставить что-то простое работать, а затем посмотреть, действительно ли это работает. является медленный..
Судя по вашему описанию, похоже, что ваш документ представляет собой только неформатированный текст, поэтому построитель строк подойдет.
Если это отформатированный документ, я был бы склонен использовать API-интерфейсы MS Word или аналогичные и просто переложить на них обработку вашего документа - это сэкономит вам очень много времени, поскольку анализ документа часто может быть занозой в заднице **: - )
Я бы пока не слишком беспокоился о производительности - похоже, что вы еще ее не реализовали, поэтому вы также не знаете, какие характеристики производительности имеет остальная часть вашего приложения - возможно, вы не можете на самом деле позволить себе хранить в памяти несколько документов, когда вы действительно приступите к их профилированию.
