Текстовый редактор

[shukshin]

Помогите придумать хорошую структуру данных для реализации Т.Р. (я пишу на Win API, используя С) с таким функционалом:

1)вывод текста в окне с двумя режимами:
-обычный вывод текста со скроллами
и
-режим свертки, то есть текст срезается по ширине окошка и переносится
при ресайзе, ширина обрезки подгоняется под ширину окна, но позиция в тексте все та же.
!!! при переключении между режимами позиция в тексте сохраняется

2)реакция на кнопки вниз-вверх (построчный перегон)
на page up - page down (постраничный)

3)беспроблемное чтение файлов ~50 Мб

4)эффективность кода(вот где я погорел) так как в качестве структуры у меня - обычный буфер char-ов,
буферно прочитанный fread из файла. Я сохранял позицию вывода текста в виртуальном пространстве приложеньки и для поиска участка текста для вывода бегал по нему за O(n).

жду советов, материалов, комментариев. заранее спасибо.

[Dmitriy40]

При открытии файла один раз пройти по нему и сохранить адреса (смещения) начала всех строк. Вся дальнейшая работа со строками заметно ускорится.
Учитывая что в 50МБ может влезть и миллион строк, то возможно удобнее будет не простой одномерный массив и не линейный список, а что-то более сложное, двухсвязный список, двоичное (сбалансированное) дерево, хэштаблица.
Хранить весь файл в памяти нет необходимости, достаточно хранить несколько сотен строк (на пару страниц выше и ниже отображаемого куска, страницы 3 с начала файла, страницы 3 до конца файла), при перемещении по тексту подгружать строки в фоне. Грубо говоря простейший кэш строк. А можно и не простейший, а стандартный кэш организовать. Он поможет и при редактировании отдельных строк в несвязанных частях текста (запоминать лишь изменённые относительно файла строки).
Собственно для более точной оценки эффективности структур хранения надо бы знать какие предполагаются операции с текстом и как часто каждая. Особенно удаление строки, вставка строки в середину, добавление строки в конец, изменение строки. Ну и есть ли ограничение на длину одной строки или весь файл в 50МБ может состоять из одной (десяти, сотни) строки.

[shukshin]

Dmitriy40,
спасибо

[DenCoder]

Распространённая ошибка многих разработчиков - делать сложное проще! Из-за этого программы (IDA, Wordpad, например) подвисают при больших объёмах данных(например, прошивка ARM-процессора в 20 мб для иды, и текстовый файл в несколько мб под вордпадом).

Возможно, потребуется реализовать более сложный механизм, но без привлечения кешей и других излишних структур. Деревьями(словарями) нужно пользоваться в меру! Например, при объёме данных до 1 мб обходиться обычным массивом (кстати, и по массиву можно лазить, как по дереву, если он как-то предсказуем). При объёме данных свыше 1 мб делить этот объём на группы, и эти группы засовывать уже в дерево. Отдельные ветви дерева можно сделать подгружаемыми динамически, выгружаемыми.

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

Есть проверенный MFC-компонет Rich Edit, его можно доработать по своему усмотрению и сделать свёртку. У него есть скролбокс, обработку нажатий на его стрелочки можно задать как угодно в обработчике сообщения WM_VSCROLL. Может, в MSDN описаны какие-то более продвинутые компоненты, позволяющие делать аутлайнинг(свёртку), как в Visual Studio. Но у меня такая задача не стояла, если есть время на поиски и эксперименты - ищите в MSDN.

Dmitriy40 в сообщении #1065283 писал(а):

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

Смотря какая обработка данных предполагается. Если 1 действие в секунду в редакторе, то терпимо. А при нормальном уровне в 180-300 зн./мин. (это будет 3-5 действий в секунду) могут нервы не выдержать. Вообще говоря, будет зависеть от характерстик накопителя. Но, хотя и скорость рандомного доступа у ssd выше, чем у sata, она заметно уступает скорости оперативной памяти. Файлы всегда лучше читать полностью перед преобразованием (если оно вообще понадобится) в требуемый спецификой вид, если размер файла не превышает половины - двух третих свободной оперативной памяти. Если для широких масс пользователей, то кол-во используемой памяти для подгрузки желательно сделать регулируемым, а его дефолтную настройку можно предрасчитать, исходя из определений объёмов общей и свободной оперативки.

Для файлов свыше 1 Гб тут задача не стоит, поэтому не буду подробно...

[Dmitriy40]

DenCoder в сообщении #1067634 писал(а):

Например, при объёме данных до 1 мб обходиться обычным массивом

Не всегда, зависит от типа данных и типичных действий над ними. Контрпример: массив текстовых строк общим объёмом текста 1МБ, количеством строк до 30000, средней длиной строки ~33 символа, максимальной длиной строки 1200 символов, основные действия: удаление случайной строки по её номеру, добавление новой строки случайной длины (1..1200) в случайное место. Двухсвязный список (или дерево) строк выиграет перед линейным массивом во много раз (а то и на порядки). Правда человек всё равно не заметит, оба варианта уложатся в считанные миллисекунды.

DenCoder в сообщении #1067634 писал(а):

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

Если файл можно целиком прочитать в память - проблем (в редакторах) и нет. Тем более при современных скоростях работы и процессоров и памяти.
Вопрос что делать когда свободной памяти не хватает для загрузки всего файла (а у меня вот прямо сейчас занято 99% памяти расчётными задачами - это мне что, теперь и 100МБ файлик не отредактировать?! Или мучиться со свопом?).

Ну а ориентироваться на SSD вообще ... некрасиво. Не у всех они ещё есть и не все рабочие файлы лежат исключительно на них. Про внешние USB флешки и SD карты даже и не вспоминаю.

(Оффтоп)

Кстати чтоб Вы знали, далеко не все из драйверов USB/SD поддерживают быстрый произвольный доступ, оказывается читать блоки "вперёд" может быть в тысячи раз быстрее чтения их же "назад" (сам лично не наблюдал, утверждение от человека, для которого писал стороннюю утилиту, мне пришлось подчиниться и переделывать программу под доступ только "вперёд").

DenCoder в сообщении #1067634 писал(а):

Смотря какая обработка данных предполагается. Если 1 действие в секунду в редакторе, то терпимо. А при нормальном уровне в 180-300 зн./мин. (это будет 3-5 действий в секунду)

При средней длине абзаца (который в памяти представлен одной строкой) в пару-тройку строк или 100-200 символов это будет всего лишь 2-4 действия в минуту - обычно не требуется сохранять каждый набранный символ сразу в файл, достаточно сохранять готовые строки.
А вот нажатия клавиш PgDn, PgUp могут быть до 30 в секунду и каждая потребовать чтения до 50 строк (причём для PgUp - назад по файлу!), при размерах строк даже полстраницы это уже полтора мегабайта в секунду, если файл сильно размазан по диску, то все ~400 блоков по 4КБ будут читаться за 9-13мс каждый, т.е. порядка 4с, вместо ожидаемых 30мс! На два порядка медленнее необходимого! И тут уж никакое усложнение структуры данных не спасёт, только или загрузка файла в память или кэш (в том числе системный). Это конечно аномалия, но вполне возможная.

В общем, надо чётче ограничивать задачу и потом уже подбирать варианты решений.