Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 57
Tехнологии, разработанные для старых компьютеров с ограниченными возможностями, оказываются в наше время забытымиСейчас у нас куча новых компьютеров с ограниченными возможностями — это смартфоны и планшеты. Но погроммисты, видимо, расчитывают, что если их программа не работает из-за нехватки памяти, то через полгода Самсунг выпустит новый смартфон, в котором будет в два раза больше оперативки.
> Сейчас у нас куча новых компьютеров с ограниченными возможностями — это смартфоны и планшеты…
Даже первые WP7 были с 512М памяти, это как бы порядочно больше тех «640Кбайт, которых хватит на все случаи жизни».
Вспомнилось, делал в 90х простой текстовый редактор на ASM, так там была одна страница 64k, текст в которой делился на две части: от начала до курсора хранилось в начале блока 64k, а остальной текст — в конце блока. Ограничение размера текста 65536 байт.
PS: Прочел, оказывается я как обычно открыл ранее открытое ))))
Даже первые WP7 были с 512М памяти, это как бы порядочно больше тех «640Кбайт, которых хватит на все случаи жизни».
Вспомнилось, делал в 90х простой текстовый редактор на ASM, так там была одна страница 64k, текст в которой делился на две части: от начала до курсора хранилось в начале блока 64k, а остальной текст — в конце блока. Ограничение размера текста 65536 байт.
PS: Прочел, оказывается я как обычно открыл ранее открытое ))))
Памяти не бывает много. К примеру, в аппсторах полно программ для редактирования фоточек, фильтры там, кроп, демотиватор сделать. Когда мне нужно было обрезать фотки с 16-мегапиксельного фотоаппарата, загрузить джипег-фотку не смогла НИ ОДНА ПРОГРАММА включая платные, включая адобовские. Все падали при загрузке. Как-то выкрутился открывая фотки штатным просмотрщиком и делая скриншоты — скриншоты уже обрезал и постил в бложик. Ещё можно было послать фотки самому себе по почте — почтовая программа предлагала при отправке уменьшить фотки, причём реально посылать было не обязательно — достаточно поставки на отправку, потом можно было вытащить уменьшенные фотки из неушедших писем в «Исходящих».
Почитайте ради интереса про, например, открытие картинок на android'е.
Одному приложению/потоку выделяется много меньше, чем вся память, если не ошибаюсь, 16 мб. на процесс вроде. Так что открытие большой картинки или большого числа данных одним куском превращается если не в хитрый, то уж точно в не банальный код «открыли и поехали».
Одному приложению/потоку выделяется много меньше, чем вся память, если не ошибаюсь, 16 мб. на процесс вроде. Так что открытие большой картинки или большого числа данных одним куском превращается если не в хитрый, то уж точно в не банальный код «открыли и поехали».
48MB стандартно, 128MB если android:largeHeap=true.
Так что всё должно бы влазить, но нужно с этой памятью очень аккуратно распоряжаться. У современных программистов так не принято.
Так что всё должно бы влазить, но нужно с этой памятью очень аккуратно распоряжаться. У современных программистов так не принято.
Да, могу путать размеры. Другое дело, String Builder'ом я «в лоб» ~14 мб. текста в сумме, падало нафиг после 12 мб… Хотя очень может быть, что я чего-то не понял.
Вот не зря выше упоминается (правда, не адроид) что с картинками проблемы — а там видимо происходит следующее: картинку в 16мб в Jpeg пытается програмка расжать, а 16 мб. сжатого в виде несжатого битмапа скорее всего мнооого больше весит.
Не то что бы не принятно, а нынче «быстрее, быстрее выпустить продукт», поэтому многие действия делаются безхитростно, даже наверное не думаю — работает, с нормальной скоростью — и ладно. Мысли появляются только при возникновении проблем и поисках пути оптимизации. Плохо ли это? Возможно.
Вот не зря выше упоминается (правда, не адроид) что с картинками проблемы — а там видимо происходит следующее: картинку в 16мб в Jpeg пытается програмка расжать, а 16 мб. сжатого в виде несжатого битмапа скорее всего мнооого больше весит.
Не то что бы не принятно, а нынче «быстрее, быстрее выпустить продукт», поэтому многие действия делаются безхитростно, даже наверное не думаю — работает, с нормальной скоростью — и ладно. Мысли появляются только при возникновении проблем и поисках пути оптимизации. Плохо ли это? Возможно.
Ну а как ей можно аккуратно распорядиться, когда неизвестна не то что разрядность, но даже архитектура процессора (x86 или arm), сам код выполняется на Dalvik-машине с её непредсказуемым сборщиком мусора, а в фоне висит ещё N процессов, которые так или иначе могут влиять на работу нашего?
Всё очарование старых машин было основано на том, что там не было такой уж зверской фрагментации (во времена digger'а даже таймеры на тактовую частоту процессора завязывали!), а вся система, от портов ввода-вывода и прерываний до самой последней ячейки памяти была под полным и абсолютным контролем программиста, без 100500 слоёв абстракции и прочей виртуальщины.
Когда же программисты погрязли во фрагментации и виртуализации, то все эти старые трюки стали восприниматься грязными хаками, которые потенциально снижают переносимость. Поэтому никто не будет их специально искать. Проблема решается как можно проще, идеально — «прямо в лоб». Ну а если чуток тормозит, так и не страшно: главное, что вообще хоть как-то работает на всём зоопарке устройств и прошивок, тут уж не до мелких тормозов.
Всё очарование старых машин было основано на том, что там не было такой уж зверской фрагментации (во времена digger'а даже таймеры на тактовую частоту процессора завязывали!), а вся система, от портов ввода-вывода и прерываний до самой последней ячейки памяти была под полным и абсолютным контролем программиста, без 100500 слоёв абстракции и прочей виртуальщины.
Когда же программисты погрязли во фрагментации и виртуализации, то все эти старые трюки стали восприниматься грязными хаками, которые потенциально снижают переносимость. Поэтому никто не будет их специально искать. Проблема решается как можно проще, идеально — «прямо в лоб». Ну а если чуток тормозит, так и не страшно: главное, что вообще хоть как-то работает на всём зоопарке устройств и прошивок, тут уж не до мелких тормозов.
Да что ж вы всех всякими ужасами пугаете? Всё уже украдено до нас. Было бы желание. И нет проблем ни в непредсказуемостью сборщика мусора, ни с архитектурой процессора. Но да, желанию-то как раз часто и нету.
У меня интересный вопрос: а как в такой структуре с поиском/заменой регулярных выражений? Кроме того, если вы берёте какой‐либо редактор с встроенным API для расширений на каком‐либо языке, то вы наверняка встретитесь как с возможностью вставки текста в любом месте, а не только в месте нахождения курсора, так и с дополнениями, которые хотят эту возможность использовать. Поиск/замена является частным случаем возможности вставки/удаления в произвольном месте.
Очевидно, в этих случаях базовая версия Gap Buffer оказывается неэффективной. Но возможны вариации на его основе. Например, хранение текста в цепочке из нескольких Gap Buffer, с распределением свободной памяти между ними. Каждый такой буфер имеет свой «теневой курсор», и сложность вставки и удаления в пределах каждого из них не превышает O(n), где n — размер каждого буфера.
И для полного эффекта можно вспомнить sublime text, с возможностью сделать себе кучу курсоров сразу :)
GC решает проблему фрагментации не хуже, чем это можно сделать руками.
Я бы вообще делал какое-нибудь immutable-дерево. Получил бы бесплатное undo, и возможность пускать всякие операции типа индексирования, подсветки, сохранения и проверки орфографии в отдельном потоке.
Я бы вообще делал какое-нибудь immutable-дерево. Получил бы бесплатное undo, и возможность пускать всякие операции типа индексирования, подсветки, сохранения и проверки орфографии в отдельном потоке.
Делал на ZX Spectrum совершенно иначе, текст непрерывным куском, редактируемая строка (или её часть) держится в спец буфере (ограниченного размера), по мере заполнения буфера или смены строки, буфер скидывается в текст. Опять же сюда хорошо вписалась и загрузка текста частями (с дискеты).
Интересное решение. Undo/redo реализуемо несложными модификациями. Rich text editing тоже можно придумать как реализовать. Чуствую, что подстава всё же есть. Видимо, самый простой пример, как уже написали, find&replace. Но всё равно интересно.
Для длинных текстов и Rich Text можно такую оптимизацию сделать: разбить текст на блоки, и оперировать как отдельными блоками, так списком блоков по изложенному алгоритму. Кажется, такой вариант не описывался в статье.
Спасибо, статья заставляет думать.
Для длинных текстов и Rich Text можно такую оптимизацию сделать: разбить текст на блоки, и оперировать как отдельными блоками, так списком блоков по изложенному алгоритму. Кажется, такой вариант не описывался в статье.
Спасибо, статья заставляет думать.
А ещё специально для тектовых редакторов придумана такая структура данных как Rope. (И это дерево.)
И мне кажется в вашей статье слишком много пафоса.
И мне кажется в вашей статье слишком много пафоса.
Я в своём редакторе использовал комбинацию Gap Buffer и Ropes. Представлял текст в виде AVL-дерева, каждый узел которого хранил immutable-подстроку текста и количество символов в поддеревьях для поиска символа по индексу (наподобие Rope, но в моей реализации значения могли содержать не только листья, но и узлы). Если пользователь начинал редактировать подстроку данного узла дерева, она динамически подменялась GapBuffer-строкой. Затем, если строка долго не изменяется, она заменяется обратно immutable-версией для экономии памяти.
Получалось довольно эффективно.
Минус полностью immutable-деревьев — создание log(N) нодов на каждую операцию изменения текста.
Получалось довольно эффективно.
Минус полностью immutable-деревьев — создание log(N) нодов на каждую операцию изменения текста.
По-моему, этот минус (если он так уж беспокоит) преодолим посредством «выворачивания» дерева в месте последней модификации на манер finger tree. Я подумывал скомбинировать органицацию набора блоков приличной длины (а не по несколько символов, как если бы finger tree использовалось в лоб для хранения массива символов) с выворачиванием, а ещё рассматривал забавную идею immutable блока с гэп-буфером: давайте контрольную запись (указатель на блок плюс индексы краёв гэпа) хранить отдельно от самого блока. Тогда при добавлении символов на краях гэпа блок клонировать не надо — создаются новые контрольные записи с обновленными индексами краёв гэпа (гэп сужается) — старые контрольные записи продолжают оставаться в том же состоянии (immutable), указывая на тот же блок!
Со временными файлами, на мой взгляд, заморачиваться не надо.
mmap()-ируйте файл любого размера. Операционная система сама разберётся, что держать в памяти, а что нет.
Сооружение собственного свопа на уровне приложения, как правило, неоправданно (лишнее время, никакой пользы).
mmap()-ируйте файл любого размера. Операционная система сама разберётся, что держать в памяти, а что нет.
Сооружение собственного свопа на уровне приложения, как правило, неоправданно (лишнее время, никакой пользы).
А как выбирать рамзер окна? Переполнение окна ведь приведет к копированию остатка, а заводить просто так значительных размеров окно — расход памяти.
И как-то мне не очевидно как сделать undo-redo для всех этих случаев.
Не проще ли в целом сделать какую-то «карту» файла который редактируется, в которой хранилися бы список блоков текста, к примеру в таком виде: файл в котором текст, адрес начала блока в файле и адрес конца блока.
При открытии файла для редактирования — создается один блок, файл = тот самый файл который открыли, адрес начала = 0, адрес конца = размер файла. При вставке внутри блока он разбивается на два блока до и после места вставки, + между ними добавляется третий блок с вставляемым содержимым — который можно хранить в новом временном файле. Удаление с начала или конца блока просто перемещает указатель начала/конца блока. Чтоб уменьшить фрагментацию, можно держать изменения в буффере пока они происходят в рамках одного нового блока.
При сохранении все это можно собрать в один файл пройдясь по списку блоков.
Undo/redo реализуется тоже элементарно — присваивать блокам не только номера порядка следования в результирующем тексте, но и номера порядка их создания. И удалять/возвращать из/в списка блоков последний блок по порядку создания.
Вроде могло бы работать.
И как-то мне не очевидно как сделать undo-redo для всех этих случаев.
Не проще ли в целом сделать какую-то «карту» файла который редактируется, в которой хранилися бы список блоков текста, к примеру в таком виде: файл в котором текст, адрес начала блока в файле и адрес конца блока.
При открытии файла для редактирования — создается один блок, файл = тот самый файл который открыли, адрес начала = 0, адрес конца = размер файла. При вставке внутри блока он разбивается на два блока до и после места вставки, + между ними добавляется третий блок с вставляемым содержимым — который можно хранить в новом временном файле. Удаление с начала или конца блока просто перемещает указатель начала/конца блока. Чтоб уменьшить фрагментацию, можно держать изменения в буффере пока они происходят в рамках одного нового блока.
При сохранении все это можно собрать в один файл пройдясь по списку блоков.
Undo/redo реализуется тоже элементарно — присваивать блокам не только номера порядка следования в результирующем тексте, но и номера порядка их создания. И удалять/возвращать из/в списка блоков последний блок по порядку создания.
Вроде могло бы работать.
Деревья, кучи, кольцевые буфера, ассоциативные массивы и прочие структуры и вовсе неприменимы для хранения текста в редакторе
B-дерево очень даже применимо.
Я бы даже сказал, любые сбалансированные деревья очень даже применимы, при условии, что хранить мы будем не символы, а подстроки исходного текста.
А потом кому-нибудь приспичит окрыть XML-документ на пару мегабайт из одной строки и вся ваша машинерия станет раком. Обидно когда старые древние emacs и vim отлично работают с многосотмегабайтными файлами, а новомодные игрушки начинают тормозить на файлах, которые и на дискету бы влезли!
Scintilla (Notepad++, TexnicCenter), например, тормозит по-чёрному.
Как раз, древовидное представление файла никак не завязано на то, сколько символов содержится в строке.
Проблема современных редакторов не в том, как они хранят текст, а в том, как они его отображают. Если у вас есть стомегабайтный файл, записанный в одну строку, редактор должен рассчитать ширину всей строки в пикселях, как минимум, для того, чтобы правильно рассчитать максимальное значение горизонтального скроллбара. Это легко сделать в случае моноширинных шрифтов, но если вы выставили пропорциональный шрифт, всё сильно усложняется.
Скажем, проскроллили мы на миллион пикселей вправо. Какой символ нужно отобразить первым слева? У vim и emacs таких проблем не возникает, потому что они используют моноширинные шрифты — делим миллион на ширину символа в пикселях, вот и наш индекс. В случае пропорциональных шрифтов необходимо сложить ширину всех символов вплоть до того, который даст результат равный миллиону.
Конечно, всё это можно оптимизировать, но главный вопрос — зачем? Часто ли вы редактируете многомегабайтные файлы, записанные в одну строку?
Проблема современных редакторов не в том, как они хранят текст, а в том, как они его отображают. Если у вас есть стомегабайтный файл, записанный в одну строку, редактор должен рассчитать ширину всей строки в пикселях, как минимум, для того, чтобы правильно рассчитать максимальное значение горизонтального скроллбара. Это легко сделать в случае моноширинных шрифтов, но если вы выставили пропорциональный шрифт, всё сильно усложняется.
Скажем, проскроллили мы на миллион пикселей вправо. Какой символ нужно отобразить первым слева? У vim и emacs таких проблем не возникает, потому что они используют моноширинные шрифты — делим миллион на ширину символа в пикселях, вот и наш индекс. В случае пропорциональных шрифтов необходимо сложить ширину всех символов вплоть до того, который даст результат равный миллиону.
Конечно, всё это можно оптимизировать, но главный вопрос — зачем? Часто ли вы редактируете многомегабайтные файлы, записанные в одну строку?
У Vim огромные проблемы с подсветкой таких файлов. Кроме того, как вы в Vim проскроллите на миллион пикселей вправо? Горизонтальной полосы прокрутки в нём отродясь не было.
И ещё: с какой стати в моноширинном шрифте ширина всех символов одинакова? Это не так. В моноширинном шрифте символ «Ａ» занимает ровно две ячейки (это относится ко всем символам, которые имеют свойство east_asian_width равное ́«F» (и, кажется, «W»), а иногда также и «A» (последнее зависит от шрифта и настроек терминала)). А три символа «а́݅» (русская «а» и два диакритических знака) занимают одну ячейку. Я не говорю уже о том, что для отрисовки текста с некоторой позиции нужен индекс байта, а не символа.
Моноширинные шрифты дают преимущество в смысле, что не нужно запускать рендерер, чтобы узнать, насколько текст широк. Но оно не настолько велико, как вы здесь описываете. Складывать ширину всех символов нужно всегда. Просто с моноширинными шрифтами не нужно рендерить глифы, чтобы её узнать.
И ещё: с какой стати в моноширинном шрифте ширина всех символов одинакова? Это не так. В моноширинном шрифте символ «Ａ» занимает ровно две ячейки (это относится ко всем символам, которые имеют свойство east_asian_width равное ́«F» (и, кажется, «W»), а иногда также и «A» (последнее зависит от шрифта и настроек терминала)). А три символа «а́݅» (русская «а» и два диакритических знака) занимают одну ячейку. Я не говорю уже о том, что для отрисовки текста с некоторой позиции нужен индекс байта, а не символа.
Моноширинные шрифты дают преимущество в смысле, что не нужно запускать рендерер, чтобы узнать, насколько текст широк. Но оно не настолько велико, как вы здесь описываете. Складывать ширину всех символов нужно всегда. Просто с моноширинными шрифтами не нужно рендерить глифы, чтобы её узнать.
Просто с моноширинными шрифтами не нужно рендерить глифы, чтобы её узнать.Данное утверждение тоже, кстати, не всегда верно. Современные системы отображения текста умеют брать отсутствующие глифы из шрифтов, где они присутствуют. Если основной шрифт моноширинный, и при том отображающая шрифт программа расчитывает на определённые размеры символа, то это приводит к различным глюкам отображения, так как символ из другого шрифта имеет другие размеры.
Согласен с каждым пунктом =) Я в своём сообщении сделал обобщение «моноширинный шрифт» == «консольное приложение», имея в виду что в консольных редакторах не нужно измерять ширину текста. Конечно, это упрощение не работает в GIU-редакторах.
По поводу символов типа "Ａ" — я проверял шрифты Consolas, Lucida Console и другие, и все глифы в них имеют одинаковую ширину. Только что ради интереса открыл Sublime Text (который по умолчанию использует Consolas) и вставил туда этот символ. Закономерно, он заменился символом из другого шрифта. Все GUI-редакторы разделяют текст на spans (не знаю, как правильно перевести), каждый спан имеет свои атрибуты форматирования, в том числе шрифт. Я думаю, Sublime просто создаёт отдельный спан для таких символов. Так вот, ширина строки текста складывается из ширины отдельных спанов, и их можно посчитать только один раз, если текст внутри спана не меняется.
По поводу символов типа "Ａ" — я проверял шрифты Consolas, Lucida Console и другие, и все глифы в них имеют одинаковую ширину. Только что ради интереса открыл Sublime Text (который по умолчанию использует Consolas) и вставил туда этот символ. Закономерно, он заменился символом из другого шрифта. Все GUI-редакторы разделяют текст на spans (не знаю, как правильно перевести), каждый спан имеет свои атрибуты форматирования, в том числе шрифт. Я думаю, Sublime просто создаёт отдельный спан для таких символов. Так вот, ширина строки текста складывается из ширины отдельных спанов, и их можно посчитать только один раз, если текст внутри спана не меняется.
Дело в том, что все эмуляторы консоли, которые я проверял, считают глифы из других шрифтов имеющими размеры символа данного шрифта, не зависимо от реального размера глифа. Но для FULLWIDTH символов и терминал, и Vim считают ширину равной двум. Я, правда, не смог найти ни одного моноширинного шрифта, в котором fontforge показал бы наличие глифов для данных символов. А я‐то считал (из‐за отсутствия обычных проблем с отображением, обычно отличающих отсутствующие глифы) «Ａ» присутствующей в шрифте.
Эмуляторы терминала со спанами явно не заморачиваются: слишком широкий символ из другого шрифтав зависимости от расположения звёзд может либо перекрываться другим символом, либо двигать все прочие символы. Причём состояние «перекрывается»/«двигает» может меняться даже без изменения отображаемого текста (например, при выделении).
Эмуляторы терминала со спанами явно не заморачиваются: слишком широкий символ из другого шрифта
Хочу заметить, сугубо практически, что у xapi (компонента XenServer) база данных хранится в виде xml-файла. Разумеется, в одну строку.
Работать в vim'е с такой строкой (в 40-50Мб в размере) невозможно, даже при отключении подстветки синтаксиса.
Работать в vim'е с такой строкой (в 40-50Мб в размере) невозможно, даже при отключении подстветки синтаксиса.
У vim память, кажется, выделяется блоками на N≥1 строк. Целых строк. Кроме того, даже если найдётся кто‐то, кто перепишет memline.c, чтобы работать с большими строками, средства навигации по таким строкам практически отсутствуют. И вывод на экран тоже под такие строки не рассчитан. Но я не работаю с настолько большими файлами в одну строку, так что у меня всё почти всегда упирается в подстветку синтаксиса.
Я бы эту проблему решал с помощью пары фильтров:
Я бы эту проблему решал с помощью пары фильтров:
xmllint --format - при чтении и xmllint --noblanks - при записи.
К слову, в последней стабильной ветке ядра Linux (3.11) добавили новый флаг для системного вызова open(), позволяющий безопасно создавать и использовать временные файлы — O_TMPFILE.
kernelnewbies.org/LinuxChanges
kernelnewbies.org/LinuxChanges
Думаю, что в контексте обсуждения структуры данных Gap Buffer, надо обязательно упомянуть и про текстовый движок Scintilla (и редактор SciTE), который как раз на нем основан. В свое время мне довелось тесно с ним работать. Из недостатков Gap Buffer отмечу, что притормаживает при работе с большими объемами текста. По теме, могу порекомендовать к прочтению отличную работу
Идея интересная, но я со скрипом представляю себе отработку поиска-и-замены в такой конструкции. Если у нас искомая подстрока встречается в каждой сотой строке, то вместо того, чтобы потревожить 1% строк, мы будем вынуждены перетягивать все 100%.
В студенческое время мы над этой проблемой думали (благо, компьютеры на базе 386sx стимулировали думать о производительности) и самой компромиссной версией, которая тогда придумалась, звучала как «список строк, указывающий на список массивов внутри строки». Этакое line->buffer.current[c]. Фрагментация легко устраняется с помощью SLAB-подобного аллокатора и выделения буффера одного из фиксированных размеров (а так же наличия в каждом буфере указания «откуда-докуда» текст).
При этом возникают накладные расходы на обновление всяких счётчиков, типа «сколько символов в буфере, сколько символов в строке», но они O(1) для больших текстов.
В студенческое время мы над этой проблемой думали (благо, компьютеры на базе 386sx стимулировали думать о производительности) и самой компромиссной версией, которая тогда придумалась, звучала как «список строк, указывающий на список массивов внутри строки». Этакое line->buffer.current[c]. Фрагментация легко устраняется с помощью SLAB-подобного аллокатора и выделения буффера одного из фиксированных размеров (а так же наличия в каждом буфере указания «откуда-докуда» текст).
При этом возникают накладные расходы на обновление всяких счётчиков, типа «сколько символов в буфере, сколько символов в строке», но они O(1) для больших текстов.
Сложности возникают при переходах в начало/в конец больших файлов. Если файл не вмещается в буфер, то стеки приходится хранить во временных файлах, и для больших перемещений приходится переносить содержимое одного стека в другой, да ещё и задом наперёд. Когда на «Ямахах» приходилось редактировать большие (больше 32 килобайт) файлы, то действия «открыть файл — вставить строчку — пойти в конец» приводили к задержкам в несколько минут. И с большой вероятностью места на дискете не хватало — нужно было свободное место, вдвое большее, чем редактируемый файл.
Действительно, а попробуйте на VPS в 128mb отредактировать SQL-дамп на пару-тройку гигов :)
В таких случаях очень спасает все тот олдовый редактор, который из покон веков умеет бибикать и все портить ( vi :)
В таких случаях очень спасает все тот олдовый редактор, который из покон веков умеет бибикать и все портить ( vi :)
Наш редактор использует представление документа в виде списка объектов, каждый из которых соответствует одному абзацу текста. В этом случае вставка абзаца в середину документа — это просто вставка еще одного объекта в список. Т.к. абзацы длиной 10 МБ встречаются крайне редко (я бы даже сказал, никогда не встречаются), а вот документы длиной по 50-100 тысяч абзацев — вполне реальны (объем «наибольшего» редактируемого файла в наших реалиях достигает примерно 150 МБ). И редактор прекрасно с такими объемами справляется. При этом удобно на объекты-абзацы навесить еще и дополнительную логику (т.е. объект хранит не только сам текст, но и стили (жирность, курсив), выделение цветом и т.п.).
А как вы определяете, какой абзац рендерить при изменении вертикального смещения ViewPort-а?
Если объяснять упрощенно, поверх каждого внутреннего объекта-абзаца с содержимым создается еще объект «отображаемый абзац», который отвечает за просчет размеров и отрисовку исходного абзаца. Если меняется ширина ViewPort'а, то высоты всем отображаемых абзацев считаются невалидными. Реальный пересчет высот в этот момент выполнять не обязательно, т.к. при изменении ширины ViewPort'а отображаемые на экране абзацы на должны поехать, т.е. отображаться всё равно будут они. А вот при скроллинге уже выполняется пересчет всех невалидных высот от начала документа (ну на самом деле не всегда от начала :) ), пока не дойдем до текущей позиции скроллинга. При открытии документа для определения «максимальной позиции» (диапазона) скроллинга просчитать все высоты один раз все равно придется.
То есть, получается, если верхняя координата ViewPort`а «указывает» на последнюю строку очень длинного абзаца, то при увеличении ширины ViewPort`а, эта строка может пропасть с экрана, вследствие того, что в этом абзаце может уменьшится количество строк?
И еще вопрос: если вы не пересчитываете высоту всех абзацев при изменении ширины, как вы понимаете максимальное значение вертикального скролла?
(Я сам сейчас делаю небольшой редактор, и пришёл к такому же выводу, что производить полный word-wrap всего документа на каждое изменение ширины — слишком накладно, но если просто помечать высоты как невалидные, со скроллом возникают некоторые проблемы. Хотелось бы узнать мнение людей, которые уже прошли через этот этап =) )
И еще вопрос: если вы не пересчитываете высоту всех абзацев при изменении ширины, как вы понимаете максимальное значение вертикального скролла?
(Я сам сейчас делаю небольшой редактор, и пришёл к такому же выводу, что производить полный word-wrap всего документа на каждое изменение ширины — слишком накладно, но если просто помечать высоты как невалидные, со скроллом возникают некоторые проблемы. Хотелось бы узнать мнение людей, которые уже прошли через этот этап =) )
>>если верхняя координата ViewPort`а «указывает» на последнюю строку очень длинного абзаца, то при увеличении ширины ViewPort`а, эта строка может пропасть с экрана, вследствие того, что в этом абзаце может уменьшится количество строк?
Да, так оно сейчас и происходит. Но на самом деле это мало кого беспокоит, т.к. изменение ширины окна в процессе редактирования относительно редкая операция, обычно окно либо не разворачивают, либо разворачивают сразу, до начала редактирования.
>>если вы не пересчитываете высоту всех абзацев при изменении ширины, как вы понимаете максимальное значение вертикального скролла?
Со скроллом отдельная история :). Пересчитывать высоты отображаемых абзацев по всему документу при изменении ширины окна нереально — это очень медленно, поэтому скролл у нас считается в количестве абзацев и умеет позиционироваться только на начало абзаца (имею в виду тот скролл, который выполняется вертикальным скроллером). Это может приводить к «скачкообразному» пролистыванию, например, если в абзаце есть рисунок на половину страницы. А для более точного позиционирования по строкам длинных абзацев используется скроллинг стрелками вверх-вниз и PageUp/PageDown на клавиатуре и скроллинг колесом мыши. В целом позиция скроллирования задается в виде пары (номер абзаца, номер строки). Когда нажимаем стрелку вниз на клавиатуре, увеличивается номер строки, а если он выходит за количество строк текущего отображаемого абзаца — то номер абзаца.
Да, так оно сейчас и происходит. Но на самом деле это мало кого беспокоит, т.к. изменение ширины окна в процессе редактирования относительно редкая операция, обычно окно либо не разворачивают, либо разворачивают сразу, до начала редактирования.
>>если вы не пересчитываете высоту всех абзацев при изменении ширины, как вы понимаете максимальное значение вертикального скролла?
Со скроллом отдельная история :). Пересчитывать высоты отображаемых абзацев по всему документу при изменении ширины окна нереально — это очень медленно, поэтому скролл у нас считается в количестве абзацев и умеет позиционироваться только на начало абзаца (имею в виду тот скролл, который выполняется вертикальным скроллером). Это может приводить к «скачкообразному» пролистыванию, например, если в абзаце есть рисунок на половину страницы. А для более точного позиционирования по строкам длинных абзацев используется скроллинг стрелками вверх-вниз и PageUp/PageDown на клавиатуре и скроллинг колесом мыши. В целом позиция скроллирования задается в виде пары (номер абзаца, номер строки). Когда нажимаем стрелку вниз на клавиатуре, увеличивается номер строки, а если он выходит за количество строк текущего отображаемого абзаца — то номер абзаца.
Т.к. абзацы длиной 10 МБ встречаются крайне редко (я бы даже сказал, никогда не встречаются)Я так понял, вы под «абзацами» понимаете «строки текста»? Если да, то один из любимых примеров: XML в одну строку. Мне, правда, никогда не доводилось редактировать XML, который обязан занимать одну строку, что позволяло пользоваться xmllint, но других люди говорят: им нужно. Собственно, эта необходимость упоминается фактически в каждой теме, где кто‐то говорит, что «обратка длинных строк не нужна».
Если нет, то как вы определяете границы абзаца?
Я говорю об RTF-представлении документа (не конкретно об RTF-формате, а просто о представлении текста в виде набора абзацев с оформлением). Аналогичное представление имеем в форматах Doc, RTF, WordML, ODT). Абзац — это некоторый набор символов, завершающийся признаком конца абзаца (при этом в том же Word'е абзац визуально может быть разбит на неколько строк, если он не влезает в ширину листа, но физически это один абзац). Если говорить о чисто текстовых файлах, то да, абзац — это строка, заканчивающая признаком конца строки (символами 13, 10 в Windows или только 13 в Linux).
Если говорить о чисто текстовых файлах, то да, абзац — это строка, заканчивающая признаком конца строки (символами 13, 10 в Windows или только 13 в Linux).Обычно строка — это строка. А абзац — это либо внутренняя терминология редактора (вроде «абзац — это набор строк, ограниченных строками, не содержащими не пробельных символов, либо началом/концом файла» (основное определение для Vim)), либо терминология того формата данных, в котором записан текстовый файл (свои абзацы есть и в FB2, и в *TeX), либо терминология отображающей программы (читалки при чтении текстовых файлов обычно имеют своё представление о том, как текст должен биться на абзацы, причём зачастую он бьётся совершенно не по строкам).
Т.е. видимо нужно уточнить, наш редактор работает с «высокоуровневым» представлением документа (полученным на основе чтения формата RTF или WordML), а не с исходным «чисто текстовым» файлом. Т.е. XML на 10 МБ в одну строку нашим редактором «напрямую» действительно не отредактируешь, наш редактор не предназначен для этого.
А я порекоменду книгу Craig A. Finseth — The Craft of Text Editing.
В этой книге рассказывается о том, как написать текстовый редактор: реализация, алгоритмы, организация данных и прочее (автор правда подводит к мысли, что EMACS — это лучший и надо ориентироваться на него).
Метод, Buffer Gap там также упоминается, см. главу 6.
В этой книге рассказывается о том, как написать текстовый редактор: реализация, алгоритмы, организация данных и прочее (автор правда подводит к мысли, что EMACS — это лучший и надо ориентироваться на него).
Метод, Buffer Gap там также упоминается, см. главу 6.
Просто ради полноты. Эта структура данных была описана в книжке А.Г. Кушниренко и Г.В. Лебедева «Программирование для математиков» (1988) и использовалась в широко известном в узких кругах текстовом редакторе «Микромир».
Вот здесь предлагается использовать B-tree для текстового редактора для работы с большими файлами, которые не помещаются в память: www.chiark.greenend.org.uk/~sgtatham/tweak/btree.html. Как я понял, B-tree куда круче вашего подхода (по скорости), хотя, признаюсь, читал ваш пост невнимательно
Приятно встретить человека, задумывающегося о таких "мелочах" как правильная организация данных в век шаблонного проектирования. Спасибо за статью!
Там тоже обсуждался вопрос организации памяти для текстового редактора применительно именно к ЭВМ с ограниченными ресурсами, таким как ZX Spectrum.Прошу прощения, но ЭВМ с неограниченными ресурсами ещё не создали и вряд ли когда-нибудь создадут
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Организация памяти в текстовом редакторе