2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Текстовый редактор
Сообщение21.10.2015, 23:24 


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

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

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

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

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

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

 Профиль  
                  
 
 Re: Текстовый редактор
Сообщение22.10.2015, 00:39 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Текстовый редактор
Сообщение22.10.2015, 08:24 


20/10/12
235
Dmitriy40,
спасибо

 Профиль  
                  
 
 Re: Текстовый редактор
Сообщение28.10.2015, 02:20 


16/05/14
11
Распространённая ошибка многих разработчиков - делать сложное проще! Из-за этого программы (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 Гб тут задача не стоит, поэтому не буду подробно...

 Профиль  
                  
 
 Re: Текстовый редактор
Сообщение28.10.2015, 05:01 
Заслуженный участник


20/08/14
11067
Россия, Москва
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мс! На два порядка медленнее необходимого! И тут уж никакое усложнение структуры данных не спасёт, только или загрузка файла в память или кэш (в том числе системный). Это конечно аномалия, но вполне возможная.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group