Как организовать память для текстового редактора? [Архив] - Speccy

vinxru

28.03.2013, 01:18

На процессоре 8080

Как хранить текст, что бы можно было без тормозов удалять, добавлять строки? Удалять, добавлять символы в строке?

Единственное, что приходит в голову, это:
1) Грузим текст в память, убеждаемся, что там нет символов с кодом 1
2) Составляем массив, в который записываем адреса строк.
3) При редактировании, если потребуется увеличить размер строки, мы копируем строку в конец текста. И подправляем указатель на строку. В начале старой строки пишем символ с кодом 1. Дальше можно увеличивать строку, пока хватит адресного пространства.
4) При редактировании, если потребуется уменьшить размер строки, в конец строки дописываем код 1
5) Когда ОЗУ закончится, мы запускаем дефрагментацию памяти/сборку мусора. Все строки в начале которых 1 выкидываются. 1 выкидывается из конца строк.
(Сборку мусора можно и по фону сделать.)
6) Возможно стоит размещать новые строки не в конце памяти, а в свободных строках подходящего размера. Поиск таких строк можно оптимизировать, построив упорядоченный массив.

esl

28.03.2013, 01:31

Ещё как вариант
Текст до курсора - от начала памяти и до курсора
Текст после курсора в конце памяти
Т.е свободное место в середине
При перемещении курсора - перемещаем строки в памяти
А т.к в основном перемещение в ближайших строках то вообще нет тормозов
Да и своп в такую схему легко добавить

Зато нет необходимости сдвигать блок при вставке в начало текста
Да и доп расходом по памяти мало

vinxru

28.03.2013, 01:39

Отличная идея.

jerri

28.03.2013, 09:15

чо во флейме то? хоть в программировании бы опубликовался

Error404

28.03.2013, 14:59

При перемещении курсора - перемещаем строки в памяти
А т.к в основном перемещение в ближайших строках то вообще нет тормозов

PgUp, PgDown, Ctrl+Home, Ctrl+End - куча копирования.
Вообще в сети есть исходники редакторов для CP/M, в т.ч. и с виртуализацией тестового буфера.

esl

28.03.2013, 15:06

PgUp, PgDown, Ctrl+Home, Ctrl+End - куча копирования.
Вообще в сети есть исходники редакторов для CP/M, в т.ч. и с виртуализацией тестового буфера.

pgUp/pgDn - копейки (максимум размер экрана)
Ctrl+Home/End - пользователь ожидает что это займет чуть дольше (подсознательно), да и редко это надо
а раздражаеют постоянные тормоза

да и тут получаем за очень не дорого строки произвольной длины.

собственно это вариант
правда есть подозрение что в TASM был как раз он ;)
вроде как он был в MIM (микромир -korvet/msx/etc), TOR-MSX

HardWareMan

28.03.2013, 15:16

Ну вы слишком много кушать. Микрон, конечно, тормозная скотина, но ED^7000, он же "Редактор текстов *Практик*" вполне сносно работал с текстами, занимающими от 1200H до 7EFFH (т.е. 27КБ) на Специалисте с его 2МГц. А я переместил его на Орион с адреса A000H, увеличив размер буфера. и там он у меня в 90е тоже вполне нормально бегал. Его основная болезнь - это медленный вывод текста. После подмены штатной ПСПЗУ на NCшную с быстрым выводом - он таки летал. Ну а текст у него сплошным куском был, с разбивочкой строк кодом 0D.
http://image.kz/img/ab/abe583d2d7629cbc6024c8cbf6adcea3.jpg

vinxru

28.03.2013, 15:31

esl

28.03.2013, 16:40

Тормоза будут не такие и больше.

Переместить 36 Кб текста в памяти, а это как раз оперативка Специалиста, будет быстрее, чем перерисовать экран размером в 12 Кб шрифтом в 6 пикселей. То есть шрифтнадо двигать и AND+OR накладывать на экран.

эт понятно ;)
в таком случае можно выводить построчно, и проверять, не надо ли еще скролить (и если надо - не обновлять что осталось)
скорость реакции будет заметно выше, а "временный бред" на экране - терпимо

так было на Корвете в ChiWorker сделано.

Hacker VBI

29.03.2013, 14:52

А если работать с буффером? и обрабатывать блоки при выходе курсора за его пределы?

ram_scan

01.04.2013, 07:04

Подавляющее количество (если не все) текстовых редакторов устроены так как написал esl во втором посте (когда текст расположен вначале и конце памяти а в месте курсора - буфер).

Только процедуру печати экрана целиком нужно делать тоже "двухстороннюю", когда выше курсора текстпечатается снизу вверх (к началу экрана) а ниже курсора - сверху вниз.

Реализация такого редактора получается тривиальной, скорость работы чумовая независимо от размера текста.

При этом больше страницы текста за раз приходится двигать только в случае навигации в начало и конец документа.

bigral

02.04.2013, 01:49

Даже не знаю как назвать структуру данных которая предложена(массив с элементами разной длинны и маркером в конце + перемещаемый свободный буфер в средине этого "типо-массива"). Самое интересное что сейчас такие задачи пишутся с какими нибудь двух-связными списками которые сами по себе будут занимать по 6 байт на каждую строку текста :) + еще при выделении памяти в самой OS будет хранится куча инфы про выделенные блоки (КОРОЧЕ - МРАКОБЕСИЕ)

Может есть еще у этого алгоритма "продолжение" про то как его расширить для редактирования файлов большего размера чем свободное пространство?

vinxru

02.04.2013, 02:34

Просто загружаем файл кусками по 16 Кб (из расчета, что у нас 32 Кб памяти под текст). Экран при этом занимать больше чем 16 Кб не должен. Сложность лишь при сохранении, придется весь файл сдвигать, если редактируемый кусок изменил размер

esl

02.04.2013, 03:04

Может есть еще у этого алгоритма "продолжение" про то как его расширить для редактирования файлов большего размера чем свободное пространство?

Связные списки всякие - слишком расточительно для ограниченной памяти, там каждый байт на учёт

Я ж писал что микро мир на корвете/ямахе легко работал с файлами больше свободной памяти
Создавал `своп` и работал
Неудобства были ТОЛЬКО при переходах в начало/конец текста
Мог подчитать блок с диска при выходе за границы экрана иногда
Запись файла при выходе - это конечно уже некий процесс, но он не частый, может и потерпеть

Vitamin

02.04.2013, 06:51

А какая операция в типичном текстовом редакторе выполняется чаще- навигация по тексту или редактирование в начале большого текста?

jerri

02.04.2013, 09:12

Vitamin, Редактирование в произвольном месте. не?

Vitamin

02.04.2013, 09:37

Vitamin, Редактирование в произвольном месте. не?
Самый тяжелый случай в плане переброса памяти- редактирование в начале большого текста.

esl

02.04.2013, 10:13

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

Vitamin

02.04.2013, 10:21

для описываемой выше схемы - это вообще не играет роли где редактировать
Ага. Все одинаково тормозит:)

локальное редактирование - всегда быстрое
Что такое локальное редактирование и где оно медленное?

а вот перемещение по тексту уже стоит, и тем больше нм дальше перемещение
Ну да. В предлагаемой схеме перемещение по тексту будет стоить. В обычных редакторах- не стОит (тупо поиск следующего/предыдущего перевода строки).

jerri

02.04.2013, 10:41

Может есть еще у этого алгоритма "продолжение" про то как его расширить для редактирования файлов большего размера чем свободное пространство?

Для чего?
Зачем на машине с 16к свободной памяти редактировать тексты больше чем 16 к?

esl

02.04.2013, 11:10

Для чего?
Зачем на машине с 16к свободной памяти редактировать тексты больше чем 16 к?

в случае если редактор ТОЛЬКО для конкретной машины/случая - може и не стоит
но MIM был (и использовался для работы с БОЛЬШИМИ текстами)
на Ямахе/Корвете/УКНЦ/СМхх
у нас преподы набирали методички в нем, и очень ценили что есть ОДИН файл а не кучка.

хотя это вопрос привычки конечно ;)

в том-же мим очень не привычная для большинства схема копирования/вставки, отдельные буфера для "символов"/"строк"/"кадратных блоков"

при этом уже тогда (1988 как минимум)
было Undo/Redo
Квадратные блоки
"бесконечный" текст
"псевдо директории"

jerri

02.04.2013, 11:11

вопрос в том
зачем сейчас писать такой редактор? :)
сфера применения?

esl

02.04.2013, 11:21

Ага. Все одинаково тормозит:)

нет, с чего бы

Что такое локальное редактирование и где оно медленное?

пример(только что открыл на корвете редактор E, там оказалась обычная вставка в текст со сдвигом)
открываем большой текст (~30k, почти вся память свободная у редактора)
в начале текста добавляем строку
пока редактируем ее - все быстро и хорошо
как только выходим из строки (например вниз)
сразу ЗАМЕТНАЯ пауза на копирование хвоста текста

Ну да. В предлагаемой схеме перемещение по тексту будет стоить. В обычных редакторах- не стОит (тупо поиск следующего/предыдущего перевода строки).

так прикол в том что в обычной жизни большие копирования будут только в местах где пользователь их нормально воспринимает (типа переход в другой конец текста)
зато при локальном редактировании (в пределах экрана) паузы нет вообще
а при PgUp/Dn она минимальна но тоже вполне ожидаема пользователем)

---------- Post added at 10:21 ---------- Previous post was at 10:19 ----------

вопрос в том
зачем сейчас писать такой редактор? :)
сфера применения?

как в том анекдоте, ну во первых это красиво ;)
писать сейчас что угодно для тех компов - чистый фан
а вариант - не более чем альтернатива плоскому тексту

vinxru

02.04.2013, 11:25

Что такое локальное редактирование и где оно медленное?

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

Медленно будет, если мы каждую строку разместим в динамической куче. При этом 50% ОЗУ из из фрагментации может оказаться недоступным, а при увеличении строки придется выделать новый кусок из кучи. А это долго по факту. Это основная причина тормозов Java/.NET на современных компах, не то что 8080

---------- Post added at 10:25 ---------- Previous post was at 10:22 ----------

Причем, этот способ можно считать вообще бестормозным. Ибо скорость отрисовки целого экрана будет меньше, чем скорость копирования 30 Кб текста в ОЗУ.

Vitamin

02.04.2013, 11:30

нет, с чего бы
Потому что при навигации по тексту придется перебрасывать блоки памяти из начала в конец.

пример(только что открыл на корвете редактор E, там оказалась обычная вставка в текст со сдвигом)
открываем большой текст (~30k, почти вся память свободная у редактора)
в начале текста добавляем строку
пока редактируем ее - все быстро и хорошо
как только выходим из строки (например вниз)
сразу ЗАМЕТНАЯ пауза на копирование хвоста текста
Сделай то же самое на acedit. Текст можешь 64к сделать.

так прикол в том что в обычной жизни большие копирования будут только в местах где пользователь их нормально воспринимает (типа переход в другой конец текста)
Вопрос в другом- во имя чего эти копирования? Если я листаю постранично, ожидаю, что бОльшая часть процессорного времени уйдет на перерисовку, а не на невнятное копирование из пустого в порожнее.

---------- Post added at 11:30 ---------- Previous post was at 11:26 ----------

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

Медленно будет, если мы каждую строку разместим в динамической куче. При этом 50% ОЗУ из из фрагментации может оказаться недоступным, а при увеличении строки придется выделать новый кусок из кучи. А это долго по факту. Это основная причина тормозов Java/.NET на современных компах, не то что 8080
А разумно подходить не пробовал к вопросу? Или только как в рекламе "опустим газету в серную кислоту, а журнал в дистиллированную воду".

Назови хоть один plain текстовый редактор, в котором используется фрагментарное хранение текста. Желательно на тормозном Java/.NET

ZEK

02.04.2013, 11:38

Это основная причина тормозов Java/.NET
наоборот в .net/java память в куче выделяется мгновенно, там же сборщик дефрагментирует

esl

02.04.2013, 11:56

Назови хоть один plain текстовый редактор, в котором используется фрагментарное хранение текста. Желательно на тормозном Java/.NET

сейчас (когда много памяти) этого делать нет вообще смысла
дешевле построить связные списки ;)
а тут речь в борьбе за каждый такт

кстати, про скорость, посчитал тут
на 8080 ldir одного байта - 48 тактов
и для корвета получаем время в фреймах
>>> 16к*1024*48/50000
15
>>> 30к*1024*48/50000
29
30 фреймов это почти пол секунды, уже ОЧЕНЬ заметно ;)

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

Vitamin

02.04.2013, 12:04

сейчас (когда много памяти) этого делать нет вообще смысла
дешевле построить связные списки
Вот я и говорю- назови plain текстовый редактор на Java/.NET, где используется хранение редактируемого текста в виде связных списков.

30 фреймов это почти пол секунды, уже ОЧЕНЬ заметно
А кто сказал, что необходимо блокировать все на время переброски данных? Что мешает заполнить буфер редактирования следующей строкой и дать пользователю его дальше редактировать? Например, редактирование на прерываниях, переброска- в основном режиме.

esl

02.04.2013, 12:08

Вот я и говорю- назови plain текстовый редактор на Java/.NET, где используется хранение редактируемого текста в виде связных списков.

я думаю что основная масса plain редакторов просто вызывает метод "редактируй мне этот буфер" и не парится ;)

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

фигасе, да такая схема будет в РАЗЫ сложнее любых буферов ;)
тем более что как я понимаю на целевом компе (специалист) вообще нет прерываний ;)

Vitamin

02.04.2013, 12:12

я думаю что основная масса plain редакторов просто вызывает метод "редактируй мне этот буфер" и не парится
Ну и как работает редактирование-то?

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

vinxru

02.04.2013, 12:17

А разумно подходить не пробовал к вопросу? Или только как в рекламе "опустим газету в серную кислоту, а журнал в дистиллированную воду".

Назови хоть один plain текстовый редактор, в котором используется фрагментарное хранение текста. Желательно на тормозном Java/.NET

Все. Текст хранится в виде массива/списка строк.

---------- Post added at 11:14 ---------- Previous post was at 11:12 ----------

Твоя схема тоже сложнее, нежели редактирование сплошного куска. Всему своя цена. Разве на 8080 нет прерываний?

На Специалисте, 86РК, Апогее, Микроше, Львове ПК01, Искре 1080 нет... Мало где есть, потому что контроллер прерываний - это отдельная дорогая микросхема, на нем экономили.

---------- Post added at 11:17 ---------- Previous post was at 11:14 ----------

А кто сказал, что необходимо блокировать все на время переброски данных? Что мешает заполнить буфер редактирования следующей строкой и дать пользователю его дальше редактировать?

1) Длина строки ограничена размером буфера редактирования. Размер буфера редактирования ограничивает размер текста.

В обсуждаемом способе, буфер редактирования не требуется.

2) При вставке буфера редактирования в текст потребуется сдвигать весь текст. А это может занять очень существенное время, пользователь продолжит печатать после нажатия ENTER и редактор пропустит первые символы в строке.

В обсуждаемом способе, при нажатии Enter тормозов не будет вообще. Это лишь запись в память одного байта. Да перерисовка экрана, которую можно прервать при нажатии клавиши.

esl

02.04.2013, 12:19

На Специалисте, 86РК, Апогее, Микроше, Львове ПК01, Искре 1080 нет... Мало где есть, потому что контроллер прерываний - это отдельная дорогая микросхема, на нем экономили.
справедливости ради, у Вектор-06ц нет контроллера но есть прерывания ;)
как и положено одно VBL -> RST7
контроллер нужен если прерываний >1
или нужны всякие фокусы с ними, типа приоритетов

Vitamin

02.04.2013, 12:22

Все. Текст хранится в виде массива/списка строк.
BCE - это типа Binary Container Editor чтоли? Ссылочку на исходник можно? :lol:

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

vinxru

02.04.2013, 12:35

наоборот в .net/java память в куче выделяется мгновенно, там же сборщик дефрагментирует

Это кажется. Свободная память описана в виде дерева. Поиск блока подходящего размера в дереве хоть и быстр log(N), но когда программа выделяет память тысячами блоков в секунду, все тормозит. Кеш процессора засоряется и общая производительность падает.

К тому же, есть проблемы многопоточности. Приходтистя строить дерево свободных блоков для каждого потока и иногда их балансировать.

Забегаем в другу тему. Но даже MS это сообразила и в C# уже можно кое-где создавать объекты на стеке. Вот там действительно выделение и освобождение памяти бесплатно. C++ возвращается :)

---------- Post added at 11:26 ---------- Previous post was at 11:24 ----------

Зато будут постоянные тормоза при нажатии вверх-вниз (а это таки делается чаще, чем нажатие ентера). И чем длиннее строки текста, тем больше тормоза.

Не будет. При средней длине строки в 64 байта, это копирование 65 байт в ОЗУ.

Это выполнится быстрее, чем функция опроса клавиатуры, а тем более прокрутки экрана. На их фоне это вообще незаметно (моментально) будет.

---------- Post added at 11:27 ---------- Previous post was at 11:26 ----------

Ссылочку на исходник можно? :lol:

Я не собираюсь работать на тебя бесплатно :) Ты опять споришь о таких банальных вещах, что я подозреваю тебя в троллинге.

---------- Post added at 11:35 ---------- Previous post was at 11:27 ----------

справедливости ради, у Вектор-06ц нет контроллера но есть прерывания
как и положено одно VBL -> RST7
контроллер нужен если прерываний >1
или нужны всякие фокусы с ними, типа приоритетов

Ага. На микросхемах выставляющих код команды RST7 в ответ на ответ процессора на прерывание то же экономили.

Что в Intel сразу не доперли сделать вывод у процессора для генерации определенного прерывания (Хотя бы NMI или IRQ0) прямо на процессоре, непонятно.

Vitamin

02.04.2013, 12:40

Не будет. При средней длине строки в 64 байта, это копирование 65 байт в ОЗУ.

Это выполнится быстрее, чем функция опроса клавиатуры, а тем более прокрутки экрана. На их фоне это вообще незаметно (моментально) будет.
Что быстрее делается- поиск символа в ближайших 65 байтах или переброс этих самых 65 байт? Проанализируй, что чаще выполняется в текстовых редакторах- перемещение между строками или непосредственно редактирование. Будешь удивлен.

Я не собираюсь работать на тебя бесплатно Ты опять споришь о таких банальных вещах, что я подозреваю тебя в троллинге.
А я тебя- в демагогии ("это всем известно", но никаких доказательств) и трепачестве. Сделал заявление- будь готов подтвердить. Истинность уже не так важна.

vinxru

02.04.2013, 12:47

А я тебя- в демагогии ("это всем известно", но никаких доказательств) и трепачестве. Сделал заявление- будь готов подтвердить. Истинность уже не так важна.

Я не один день потратил на доказательства тебе, бессмысленно, надоело. И никаких благодарностей.

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

И сейчас я писал не тебе, а людям, которые могут случайно прочитать этот сырбор. Что бы они поняли шикарность этой задумки.

---------- Post added at 11:47 ---------- Previous post was at 11:44 ----------

Что быстрее делается- поиск символа в ближайших 65 байтах или переброс этих самых 65 байт? Проанализируй, что чаще выполняется в текстовых редакторах- перемещение между строками или непосредственно редактирование. Будешь удивлен.

Не буду удивлен.

В этом способе есть незаметные для пользователя тормоза (копирование 65 байт) при перемещении курсора. При перемещении в начало/конец текста надо будет скопировать 36 Кб, но перерисовка экрана будет происходить дольше. Поэтому даже это не будет заметно.

Но в твоем способе тормоза будут возникать при любом редактировании строки (копирование ~18 Кб после редактирования любой строки. Надо же вставить буфер в текст.)

Vitamin

02.04.2013, 12:48

Я не один день потратил на доказательства тебе, бессмысленно, надоело. И никаких благодарностей.
И что ты доказал? Ни-че-го. "Простейшую" (по твоим словам) задачу не смог решить, одно словоблудие. Хотя гонору было- выше крыши. Потому и трепач.

vinxru

02.04.2013, 12:51

И что ты доказал?

Склероз, да?

Vitamin

02.04.2013, 12:53

Что бы они поняли шикарность этой задумки.
Безусловно, задумка имеет все права на жизнь и даже реализацию. Только это не серебряная пуля.

---------- Post added at 12:53 ---------- Previous post was at 12:52 ----------

Склероз, да?
Да. Не припомню ни одной законченной реализации задачи от тебя. Максимум- перечисление ассемблерных команд для использования.

vinxru

02.04.2013, 12:54

Безусловно, задумка имеет все права на жизнь и даже реализацию. Только это не серебряная пуля.

Это лучший из обсуждаемых здесь способов, с точки зрения:
1) Заметных для пользователя тормозов.
2) Рационального использования ОЗУ.
3) Простоты алгоритма.

Vitamin

02.04.2013, 12:58

1) Заметных для пользователя тормозов.
Для случая перемещений на короткие дистанции. Тормоза при переходе в начало текста могут вызвать вопросы.

2) Рационального использования ОЗУ.
В смысле отсутствие накладных расходов на индексы-указатели? Классический способ точно так же рационален.

3) Простоты алгоритма.
Он сложнее классического. Такова цена за п.1

vinxru

02.04.2013, 13:07

Не припомню ни одной законченной реализации задачи от тебя. Максимум- перечисление ассемблерных команд для использования.

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

---------- Post added at 12:06 ---------- Previous post was at 12:03 ----------

Для случая перемещений на короткие дистанции. Тормоза при переходе в начало текста могут вызвать вопросы.

Нет. Я написал это уже много раз. Перерисовка экрана происходит значительно дольше.

Потому что шрифт 6 пикселей, а в байте 8 пикселей. Шрифт надо сдвигать и накладывать через AND OR на исходное изображение дважды, так как символ может быть на границе байта. (Само собой, этонадо делать лишь когда перемещение происходит дальше 25 строк.)

---------- Post added at 12:07 ---------- Previous post was at 12:06 ----------

В смысле отсутствие накладных расходов на индексы-указатели? Классический способ точно так же рационален.

Всмысле того, что буфер для редактирования строки не нужен.

Vitamin

02.04.2013, 13:21

Я может бы за тебя всю программу написал, но мне не нравится твой стиль общения. Ты каждое свое сообщение строишь так, что мне приходится оправдываться. Ни под одним моим сообщением ты не нажал - спасибо.
Я вытаскиваю важную и интересную для себя информацию. Поскольку пока ничего нового для себя не встретил, спасибо говорить не за что. Плюс мне тоже не нравится твой стиль общения- "это и так все знают, ты тоже знаешь, но делаешь вид что нет- ты тролль". Если я знаю что-то по этому вопросу (использование SIMD), так это то, что я слишком мало знаю чтоб делать выводы на основе неполных данных.

Нет. Я написал это уже много раз. Перерисовка экрана происходит значительно дольше.
Ну это не повод делать операцию еще дольше.

Всмысле того, что буфер для редактирования строки не нужен.
А вот это зря. Буфер редактирования- очень полезная штука. В частности, можно легко сделать undo.

vinxru

02.04.2013, 13:30

Ну это не повод делать операцию еще дольше.

Повод - это сделать быстрым реакцию на Enter. И длину строки ограниченную лишь объемом ОЗУ.

esl

02.04.2013, 13:30

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

Ну это не повод делать операцию еще дольше.

А вот это зря. Буфер редактирования- очень полезная штука. В частности, можно легко сделать undo.

господа, флеймить давайте во флейме!

vinxru

02.04.2013, 13:31

А вот это зря. Буфер редактирования- очень полезная штука. В частности, можно легко сделать undo.

Один UNDO не панацея. Под UNDO можно завести буфер, где каждое действие пользователя будет занимать 1-2 байта.

Причем, второй буфер делаем REDO и копируем туда отмененные поправки.

P.S. Уже обкатано лет 10 назад (http://vinxru.livejournal.com/9277.html)

psb

02.04.2013, 13:58

если чо... был такой редактор на спеке - zx-word, вот там было:

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

bigral

02.04.2013, 16:55

В смысле отсутствие накладных расходов на индексы-указатели? Классический способ точно так же рационален.

1. Что считать "классическим способом" может это тот редактор который в zxspeccy ROM? когда мы в буфер редактирования копируем строчку которую хотим отредактировать? Если да, то это бесполезное копирование строчки ПЕРЕД редактированием и ПОСЛЕ редактирования + надо ж как-то с размером разобраться, так как старая и новая строчки явно разные по размеру. Ну а если это сдвигание раздвигание всего текста при нажатии каждой кнопки то это вообще мракобесие особенно для файлов гигабайтного размера.

2. Навигация по тексту в режиме read only и спец-режим "редактирование" (например в редакторе EX он же VI) решает вопрос с ненужным копированием строк при простом перемещении курсора по строчкам (возможно зделать это и неявно, скажем создавать этот буфер тогда когда юзверь нажал кнопку которая должна изменить строку).

3. По поводу БОЛЬШИХ файлов я так и не понял что с ними делать, вот у меня есть логи на работе размерами по 1GB ни один из редакторов под linux c ними нормально не работает (помнится под DOS были редакторы которые и по 10Mb логи смотрели без проблем). Это конечно другая задача НО все же, как создать swap file и как его использовать эфективно?

Vitamin

02.04.2013, 17:14

1. Что считать "классическим способом" может это тот редактор который в zxspeccy ROM? когда мы в буфер редактирования копируем строчку которую хотим отредактировать? Если да, то это бесполезное копирование строчки ПЕРЕД редактированием и ПОСЛЕ редактирования + надо ж как-то с размером разобраться, так как старая и новая строчки явно разные по размеру. Ну а если это сдвигание раздвигание всего текста при нажатии каждой кнопки то это вообще мракобесие особенно для файлов гигабайтного размера.
Скорее, сочетание буфера редактирования и сдвигание/раздвигание текста при возврате буфера назад.
Если редактирования нет, заполнять буфер совсем не обязательно. Если есть- заполнение делается элементарно, указатель на следующую строку должен быть уже известен (навигация же).

(возможно зделать это и неявно, скажем создавать этот буфер тогда когда юзверь нажал кнопку которая должна изменить строку).
Ну да. Примерно это и сказал. И даже одно время имплементил в редакторе.

3. По поводу БОЛЬШИХ файлов я так и не понял что с ними делать, вот у меня есть логи на работе размерами по 1GB ни один из редакторов под linux c ними нормально не работает (помнится под DOS были редакторы которые и по 10Mb логи смотрели без проблем). Это конечно другая задача НО все же, как создать swap file и как его использовать эфективно?
У гугла совет спрашивал? http://stackoverflow.com/questions/159521/text-editor-to-open-big-giant-huge-large-text-files

vinxru

02.04.2013, 17:37

(возможно зделать это и неявно, скажем создавать этот буфер тогда когда юзверь нажал кнопку которая должна изменить строку).

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

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

P.S. Хотя я этот способ то жена первых страницах предложил в качестве альтернативы.

Vitamin

02.04.2013, 17:41

Тогда при первом нажатии клавиши возникнут тормоза и даже если первые символы не потеряются, это будет не очень приятно.
Откуда тормоза? От копирования 65 символов?

vinxru

02.04.2013, 17:46

Откуда тормоза? От копирования 65 символов?

А если я перемещусь в конец текста и там нажму кнопку?

Vitamin

02.04.2013, 17:48

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

Barmaley_m

02.04.2013, 17:57

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

К слову о связных списках: подобный подход, по-моему, применяется в редакторе Far. Он позволяет иметь строки произвольного размера и/или редактировать большие файлы.

bigral

02.04.2013, 18:15

Он позволяет иметь строки произвольного размера и/или редактировать большие файлы.

Вот тут не понял. Собственно про это уже спросил 2 раза но внятно никто не ответил как это сделать.

Детально можно описать алгоритм как отредактированный кусок текста из памяти "вклеится" в то "окно" которое занимал старый текст (отредактированный текст может быть длинее или короче)?

По-моему возникает проблема аналогичная той ситуации что возникает в памяти редактора с "классическим" подходом, нужно вычислить размер нового текста и передвинуть остаток файла вперед или назад а потом вписать содержимое памяти в "подогнанное" окно на диске (довольно муторная и дорогая операция по-моему, особенно с такой файловой системой как в TR-DOS).

esl

02.04.2013, 19:13

3. По поводу БОЛЬШИХ файлов я так и не понял что с ними делать, вот у меня есть логи на работе размерами по 1GB ни один из редакторов под linux c ними нормально не работает (помнится под DOS были редакторы которые и по 10Mb логи смотрели без проблем). Это конечно другая задача НО все же, как создать swap file и как его использовать эфективно?

это можно пременить к большим файлам, но смысла нет,
эт скорее схема для экономии памяти

но все-же,
собственно этому методу в памяти "нужно" держать только то что сейчас на экране
все что вне экрана спокойно может быть в "свопе"
и догружаться в память по надобности.

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

vinxru

02.04.2013, 20:17

Вот тут не понял. Собственно про это уже спросил 2 раза но внятно никто не ответил как это сделать.

Детально можно описать алгоритм как отредактированный кусок текста из памяти "вклеится" в то "окно" которое занимал старый текст (отредактированный текст может быть длинее или короче)?

По-моему возникает проблема аналогичная той ситуации что возникает в памяти редактора с "классическим" подходом, нужно вычислить размер нового текста и передвинуть остаток файла вперед или назад а потом вписать содержимое памяти в "подогнанное" окно на диске (довольно муторная и дорогая операция по-моему, особенно с такой файловой системой как в TR-DOS).

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

Этого не избежать, в любом случае придется сдвигать байты на диске. Хоть ты весь файл в оперативку загрузи.

---------- Post added at 19:17 ---------- Previous post was at 19:13 ----------

А алгоритм получается простой. Перерисовка экрана происходит от положения курсора вверх и вниз. Если при перерисовке мы достигаем конца ОЗУ, то есть еще не всё нарисовали, а данные кончились, значит надо младшие 16 Кб скинуть на диск (или сколько там получилось после редактирования), переместить оставшиеся 16 Кб в начало и загрузить в конец следующие 16 Кб из файла.

Barmaley_m

02.04.2013, 20:20

а гигабайтный логи в редактор грузить - имхо изврат редкий
их же не нужно редактировать, их нужно смотреть, другая задача ...
Почему же? Идея вполне имеет право на существование. Логи разные бывают. Например, если софт, который сохраняет логи, содержит баг, что приводит к нечитаемости логов другим софтом. С помощью редактора иногда можно подправить лог, чтобы он читался как надо. Когда пишешь и отлаживаешь свою программу, сохраняющую логи, такая ситуация может встречаться часто.

Ну и потом, что гигабайты на современных компах - то сотни килобайт на Speccy. Подход тот же самый. Прочитать или записать 300кБ с дискеты занимает примерно то же время, а в стандартную память такой файл не влезает.

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

esl

02.04.2013, 20:38

Почему же? Идея вполне имеет право на существование. Логи разные бывают. Например, если софт, который сохраняет логи, содержит баг, что приводит к нечитаемости логов другим софтом. С помощью редактора иногда можно подправить лог, чтобы он читался как надо. Когда пишешь и отлаживаешь свою программу, сохраняющую логи, такая ситуация может встречаться часто.

не, эт неправильно, логи парсить надо не редакторм а скриптом на ruby/perl/python
они на это заточены, и ворочают ими с сумашедшими скоростями
сколько раз уж делал такие "фиксеры" ;)

java мир ух как любит многопоточные логи ....

Barmaley_m

02.04.2013, 21:01

Придумал, как редактировать большие файлы.

Для этого требуется не один, а два своп-файла. Их совокупный размер может вырасти вплоть до размеров оригинального файла минус объем доступной в качестве буфера оперативной памяти, так что если имеется дискета на 800кБ - то на ней можно будет редактировать файлы до ~400кБ размера, если хранить своп-файл на ней же.

Сначала в оперативку загружается часть оригинального файла - по доступному размеру буфера, но оставляя некоторое место для текущих вставок. При выходе курсора за пределы этой области отредактированный текст сохраняется на диск в первый своп-файл, а данные подгружаются в память из оригинального файла. Таким образом, при далеких перемещениях курсора только в направлении конца текста (и малых - в локальной области в любом направлении) когда курсор окажется в конце текста, в своп-файле окажется почти полная отредактированная копия исходного файла. Если теперь переместить курсор далеко назад, за пределы находящегося в памяти куска - то информация с конца текста начинает записываться во второй своп-файл, задом наперед - потому что файлы могут расти или обрезаться только с конца. В освободившуюся память подгружаются данные из первого своп-файла, и редактирование продолжается. При перемещениях курсора за пределы "окна ОЗУ" информация из начала или конца ОЗУ-буфера дописывается в один из своп-файлов, в освободившуюся память подгружаются данные из другого своп-файла, и один из своп-файлов обрезается с конца.

По окончании редактирования в конец первого своп-файла дописываются весь текст из ОЗУ-буфера, после этого все содержимое второго своп-файла дописывается к первому своп-файлу задом наперед. После этого первый своп-файл содержит полный вариант отредактированного текста, второй своп-файл пуст. Он удаляется, удаляется также оригинальный файл, а первый своп-файл переименовывается под имя оригинального файла. Если оригинал и своп-файлы хранились на разных дисках - то процедура немного отличается, но суть, надеюсь, ясна.

Очень эффективно. При таком подходе копирование больших кусков данных на диске сводится к минимуму.

---------- Post added at 20:01 ---------- Previous post was at 19:58 ----------

не, эт неправильно, логи парсить надо не редакторм а скриптом на ruby/perl/python
Если изменения большие - то можно скриптом, а если небольшие - то сойдет и редактор. Это быстрее, чем писать и отлаживать скрипт. Я часто этим занимался по работе (патчил логи), правда, от их размера редактор (Far) не усирался.

А MIM - это очень мощный редактор. На нем я набирал и редактировал свой диплом, хотя на дворе был уже 2000й год, и мне тогда были доступны редакторы на PC (Far, Word и др.). Тем не менее по совокупности критериев был выбран MIM как наиболее удобный и экономящий время/усилия.

esl

02.04.2013, 21:01

ну сосбтвенно в работе это уже лет как 25+ можно посмотреть в МикроМире ;)

psb

02.04.2013, 22:05

логи парсить надо не редакторм а скриптом на ruby/perl/python
ага, ага, особенно когда не знаешь что искать в них и искать надо всё. почему не хватит просмотрщика? потому что поиском и заменой лог можно чистить находу, адаптивно (что не сможет ни один скрипт).

Sergey

02.04.2013, 22:46

В порядке обсуждения, чисто теоретическая идея. Показываю на интуитивнопонятном примере:

Строка до правки:
"Моя Родина - Союз Советских Республик!"

Строка после правки:
"Моя Родина - Союз Советских Социалистических Республик!"

Как должно выглядеть:

Состояние памяти до правки:
адрес_1: "Моя Родина - Союз Советск"
адрес_2: "их "
адрес_3: "Республик!"
адрес_4:

Состояние памяти после правки:
адрес_1: "Моя Родина - Союз Советск"
адрес_2: [управляющий код][адрес4]
адрес_3: "Республик!"
адрес_4: "их Социалистических "[управляющий код][адрес_3]

(управляющий код и адрес занимают 3 байта)

Плюсы:

Не нужно двигать текст вообще.

Минусы:

Вероятно, усложняется и замедляется процедура вывода текста на экран.
Перед сохранением текста необходима дополнительная обработка.

jerri

02.04.2013, 22:55

Sergey, Хорошая годная трава.
только зачем?

bigral

02.04.2013, 23:38

Не нужно двигать текст вообще.

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

esl

03.04.2013, 00:23

ага, ага, особенно когда не знаешь что искать в них и искать надо всё. почему не хватит просмотрщика? потому что поиском и заменой лог можно чистить находу, адаптивно (что не сможет ни один скрипт).

ага, на практике даже во много итераций но скриптом анализировать проще
просто у скрипта сильо больше возможностей править логи

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

опять же, это для меня, и я достаточно давно в эти игры играю

мне проще написать скрипт в пару строк чем в редакторе править руками
да и поиск/замена в редакторах (даже так реализована как в с Sublime text 2) - бледное подобие возможностей скрипта

Barmaley_m

03.04.2013, 00:39

просто у скрипта сильо больше возможностей править логи
Это оффтопик, но раз уж сам модератор его поддерживает, то я не могу не ответить. Иногда баги в софте, который пишет лог, таковы, что правила правки лога сложно формализовать в виде скрипта. Может получиться так, что скрипт превратится в парсер лога с конкретными нарушениями структуры с последующей генерацией исправленного лога. Огромный объем кода. Также появляется необходимость отладки скрипта и его проверки, что он не портит лог где-то, где этого совсем не ждешь. Ладно если баг в скрипте приведет к синтаксической ошибке в логе, что парсер лога впоследствии выругается. А если произойдет незаметная порча данных? В моей практике, когда объем правок невелик, а формализация затруднена, как правило было удобнее редактировать логи вручную.

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

---------- Post added at 23:39 ---------- Previous post was at 23:33 ----------

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

bigral

03.04.2013, 01:11

Этого не избежать, в любом случае придется сдвигать байты на диске. Хоть ты весь файл в оперативку загрузи.

Интересно было бы написать сам редактор отдельным модулем от модуля сохранения. Да еще и на С, тогда бы можно было б портировать везде. К тому же предвижу что потом нужны будут plugin-ы для подсветки;find\replace;соmpare;bin edit by template и т.д.

SfS

03.04.2013, 20:14

psb

04.04.2013, 00:15

и мало того, скрипт можно будет и завтра использовать ....
еще раз: только когда знаешь, что искать. ну, и про остальное Barmaley_m уже сказал.

esl

04.04.2013, 00:39

еще раз: только когда знаешь, что искать. ну, и про остальное Barmaley_m уже сказал.[/QUOTE]

:-)
Ещё раз:
Мне огромные логи удобнее чистить скриптами
После их прохода и сильной чистке лога гораздо легче искать глазами в редакторе

По работе постоянно надо искать в логах инфу
Так правильные скрипты легко из 10ка гиг делают 10к :)

bigral

04.04.2013, 02:38

Для редактора я бы кучу организовал.
Максимальную длину строки ограничил бы 1024 байта, например.
Тогда всё довольно просто - пока в пределах одной строки редактируешь - всё в буфере. Как строку бъёшь - так в куче место выделяется-освбождается. Для 48К накладно, а 128 уже прекрасно.

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

Т.е. текст при загрузке попадает в массив элементов (в массиве все элементы одного размера), каждая строка имеет свой собственный буфер редактирования (это типа как отдельный текстовый редактор для каждой строки, даже парралельно 2 и больше процессора могут редактировать разные строки). Памяти жрет такое решение уйму и ограничивает длинну строки. Ну и наверное строки хранить тут имеет смысл в том же виде как и предложенно ранее - строка идет сначала елемента массива и до курсора потом пустое место и остаток строки в конце элемента массива.

vinxru

04.04.2013, 10:22

памяти море? скорости много?

Вчера залез почитать. DDR4 с частотой 4.3 ГГц имеет скорость обмена 34 Гб/c. Офигеть.

SfS

04.04.2013, 11:48

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

Дорогой Критик, я Кучу реализовывал для AVR 4MГЦ c внешним ОЗУ. Очень даже хорошо получилось. На элемент кучи - динамический заголовок (от 1 до 3 байт). Этого достаточно для хранении всей информации об элементе, даже если побить память на странички по 16К.

Это сильно большие расходы - 3 байта на длинную стоку? ИМХО - нет, скорость выделения памяти и освобождения всё это оправдывает.

Принцип такой:
Каждый элемент хранит заголовок, в котором указаны длина элемента, занят он или свободен.
После инициализации - каждая страница кучи состоит из одного элемента, размером "Размер страницы-Размер элемента".
Старшие два бита (6 и 7) указывают размер заголовка - 1,2 или 3 байта.
Бит 5 - показывает занят элемент или свободен.
Бит 4 - резерв
Биты [3..0] - размер элемента для 1байтового заголовка.

Что получаем? Очень просто -
для эл-тов кучи от 0 до 15 байт - заголовок 1байт,
для 16-255 байт - 4095 байт.
и для эл-тов 4096-16381 байт (размер страницы 16К - 3б) - 3 байта

Где тут нужно "море памяти"? Где тут "мегатактовые частоты"? На АВР 4 МГЦ в реалтайме работает и не глючит.

При таком хранении как раз память выделяется крайне быстро. Алгоритм прост и прозрачен. Работает автоосвобождение памяти (объединение нескольких свободных элементов подряд в 1 большой свободный элемент).

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

Т.е. текст при загрузке попадает в массив элементов (в массиве все элементы одного размера), каждая строка имеет свой собственный буфер редактирования (это типа как отдельный текстовый редактор для каждой строки, даже парралельно 2 и больше процессора могут редактировать разные строки).

Какой "свой собственный буфер"? Один буфер на все строки. Переместился на строку - она в буфер, ушёл на другую - другая в буфер. Скопировать килобайт байт - спек может быстро и незаметно для юзера. Хотя.. Где ты видел килобайтовые строки в реальных текстах?! Обычно не более 80 байт при спековском разрешении.

Памяти жрет такое решение уйму и ограничивает длинну строки.

В чём накладыне расходы? на пустую строку - 1 байт. На среднюю строку ( 30-150 байт) - 2 байта.

Ну и буфер 1024 байта - это более чем достаточно. Мало - выделяй динамически. Или сделай 16384 байта. Только я живу в реальном мире, где тексты пишутся, чтобы читать, а не чтобы мучаться.

Для текстового редактора реально ещё нужен массив адресов строк - 3 байта на строку (с учётом банки). Тогда - если 1 банка под массив - то максимальный размер текста - 5450 строк примерно. Часто ты такие тексты пишешь в одном файле?

Мне кажется - исходить надо из удобства и скорости. Пользователю пофиг как там у вас чего организовано. Но если при вставлении символа текста он по 3 секунды ждать будет - то заплюёт.

vinxru

04.04.2013, 11:57

alone

04.04.2013, 12:22

на 8080 ldir одного байта - 48 тактов
Что-то многовато.
Можно же развернуть последовательность типа
ld a,(hl)
inc hl
ld (de),a
inc de

jerri

04.04.2013, 12:26

Что-то многовато.
Можно же развернуть последовательность типа
ld a,(hl)
inc hl
ld (de),a
inc de

bc проверять будем?

SfS

04.04.2013, 12:32

Что бы найти блок, необходимо проверить все блоки кучи. Было бы организовано дерево, потребовалось бы LOG(N) операций.

То есть у каждого блока два укзателя. На правую ветвь (блоки большего размера) и на левую ветвь (блоки меньшего размера).

Найти свободный блок? Не всё - а до первого свободного с длиной не менее заданной.

Я проще делал. Искал сначала кучи. Чем больше элементов в куче - тем медленнее поиск. Но реально - всё равно быстро. Там же просто - проверил бит - если занят - к следующему. если свободен - проверяем длину. если длины хватает - то выделяем, если нет - опять к следующему.

В пределе - файл из 16384 элементов 0й длины :) Это фантастика)

vinxru

04.04.2013, 12:38

POP DE
MOV M, E
INX H
MOV M, D
INX H

17 тактов на байт.

BC проверять будем один раз на 8 операций (или больше). Причем даже просто C. Эта функция будет копировать блоки по 16 байт, а вызывающая функция будет сначала копировать блоки по 16 байт, а потом остаток медленным способом.

---------- Post added at 11:38 ---------- Previous post was at 11:34 ----------

Найти свободный блок? Не всё - а до первого свободного с длиной не менее заданной.

Это не рационально. Это очень сильно фрагментирует ОЗУ, из за чего половина будет пропадать.

alone

04.04.2013, 12:46

Защитники буферизации строк забыли про одну важную проблему: если строку буферизировать для редактирования, то длина строки будет ограничена. Обычно в таких редакторах это 256 байт. В ACEdit было сделано именно так с самых первых версий. Потом добавлена (глючная) подгрузка остатка строки в буфер при ломании строки Enter'ом. В реальном тексте строки могут быть любой длины. Бывает так, что строка=абзац. А бывает так, что надо отредактировать строку в бинарнике.

Были другие идеи: например, двигать текст либо назад, либо вперёд по зацикленному буферу. Или редактировать в окне, а то, что до или после, "подгружать" из памяти или диска. Или разбить текст на блоки по 256 байт, у каждого из которых указан циклический сдвиг в байтах: при вставке символа нужно в каждом последующем блоке только пересчитать сдвиги и переместить 1 символ.

Но для этого пришлось бы переписать половину редактора.

Вариант с разрезанием по курсору пока самый лучший. При движении на страницу назад или вперёд всё равно требуется пройтись по каждому символу (чтобы отсчитать нужное число строк), так что их переброска не сильно затруднит. К тому же, это один из немногих методов, где сохранение на диск не требует предварительной обработки. Сохранение идёт прямо из памяти, мгновенно. А в случае хранения строк в куче перед сохранением потребуется безумная дефрагментация, которая займёт немалое время. Либо придётся сохранять через промежуточный буфер по 1-2 сектора, что тоже не быстро.

---------- Post added at 11:46 ---------- Previous post was at 11:44 ----------

bc проверять будем?
Не будем. Вход в развёрнутый код с нужного места, а зацикливание - в конце кода. Можно по 8-битному счётчику.

Vitamin

04.04.2013, 12:50

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

SfS

04.04.2013, 13:05

Это не рационально. Это очень сильно фрагментирует ОЗУ, из за чего половина будет пропадать.

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

ну это у меня было так. Но я не редактор писал.)

alone

04.04.2013, 13:31

Даже для блочного ввода-вывода?
Это будет гуляние по списку, копирование в буфер плюс постоянное ожидание оборотов диска. А идеал - один-два системных вызова (в ACEdit именно так, даже для Merge).

Vitamin

04.04.2013, 13:50

Это будет гуляние по списку, копирование в буфер плюс постоянное ожидание оборотов диска. А идеал - один-два системных вызова (в ACEdit именно так, даже для Merge).
Это к чему?

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

esl

04.04.2013, 16:50

Не будем. Вход в развёрнутый код с нужного места, а зацикливание - в конце кода. Можно по 8-битному счётчику.

вроде бились за каждый байт, а теперь циклы разворачиваем ;P
хотя конечно этот вариант крут
а потом еще 16(стек)+хвост(этот) ...

по поводу записи, перед записью надо будет "перейти в конец текста"
но при записи эт будет не заметно ;)

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

---------- Post added at 15:50 ---------- Previous post was at 15:50 ----------

Поменяйте Витамину статус Vitamin C++ на Тролль :)

тогда уж на Троль ++

alone

04.04.2013, 17:12

Цитата:
Сообщение от alone Посмотреть сообщение
Это будет гуляние по списку, копирование в буфер плюс постоянное ожидание оборотов диска. А идеал - один-два системных вызова (в ACEdit именно так, даже для Merge).
Это к чему?

Ты сказал, что хранение текста в разделенном по курсору виде не требует дополнительных действий при сохранении на диск. У меня возникли сомнения по поводу этого заявления применительно к блочному вводу-выводу.
Что конкретно ты не понял в моём ответе?

Vitamin

04.04.2013, 17:20

Что конкретно ты не понял в моём ответе?

Вот из этой цитаты:

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

я сделал вывод, что фраза (следующая за предыдущим предложением):

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

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

С учетом того, что разделение делается в произвольном месте, а ввод-вывод у нас блочный, над стыком таки потребуется дополнительная обработка. И она будет сложнее, если свободное окно между кусками меньше размера блока. Я в чем-то ошибся? Если да, то в чем?

vinxru

04.04.2013, 17:28

С учетом того, что разделение делается в произвольном месте, а ввод-вывод у нас блочный, над стыком таки потребуется дополнительная обработка. И она будет сложнее, если свободное окно между кусками меньше размера блока. Я в чем-то ошибся? Если да, то в чем?

Это не проблема. Перед сохранением, перемещаем курсор в конец текста. Это один вызов уже существующей в редакторе функции. Это объединяет текст в один блок.

P.S. А потом обратно переместим. Либо можно сохранять двумя кусками, если ОС это позволит. Эти способы по любому проще сохранения из кучи.

Vitamin

04.04.2013, 17:36

Это не проблема. Перед сохранением, перемещаем курсор в конец текста. Это один вызов уже существующей в редакторе функции. Это объединяет текст в один блок.
Но ведь это уже обработка. Конечно, ее можно минимизировать, вычислив оптимальную сторону куда прыгать (в начало или в конец), но в общем случае она есть.

Эти способы по любому проще сохранения из кучи.
Понятное дело.

Кстати, была мысль при укорачивании строк не уплотнять весь текст, а оставлять окно, пометив его какими-нибудь кодами. Потом при поиске свободного места можно в обе стороны бегать уплотняя построчно.

ZEK

04.04.2013, 17:46

Но ведь это уже обработка.
Пипец задрот, одно дело из кучи собирать в буфер и записывать (а каждый очередной кусок может выходить за пределы буфера и это дополнительный танец), то ли переместить курсор в хвост, и сохранить одним куском

Vitamin

04.04.2013, 17:48

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

Для неврубающихся: лично я хранение текста построчно в куче даже и не рассматриваю.

ZEK

04.04.2013, 17:52

одно дело собирать из двух кусков
собрать это написать процедурину?

Vitamin

04.04.2013, 18:07

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

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

ZEK

04.04.2013, 18:32

То есть делаем вывод, различие вариантов когда текст уже плоский и вариант когда он состоит из двух кусков состоит из вызова из одной процедуры, следовательно как критерий упрощения записи вариант с плоских хранением очень сомнителен, выигрыш в длительности операции записи, но на фоне операций IO это не заметно, и тут стоит склоняться к варианту где работа в типовых операциях менее накладная и отзывчивая со стороны UI

alone

04.04.2013, 18:58

С учетом того, что разделение делается в произвольном месте, а ввод-вывод у нас блочный, над стыком таки потребуется дополнительная обработка. И она будет сложнее, если свободное окно между кусками меньше размера блока. Я в чем-то ошибся? Если да, то в чем?
В худшем случае копируется 255=размер_блока-1 байт (если окно меньше, то два раза). Кстати, никто не заставляет сохранять, если свободное окно между кусками меньше размера блока. Например, ACEdit может редактировать 65535 байт, но он не сохранит, если больше 65280.

Vitamin

04.04.2013, 19:31

и тут стоит склоняться к варианту где работа в типовых операциях менее накладная и отзывчивая со стороны UI
А тут уже расходятся мнения что считать "типовой операцией"- навигацию или редактирование.

Вот накидал оценки затрат:
M - размер текста
N- средний размер строки
K- размер экрана в строках

Учтены разумные оптимизации (например, известный конец текста).

\Метод| Plain | Twopart | Fragmented
Операция\ | text | text | text
-------------------------------------------
Home | O(1) | O(M) | O(1)
End | O(N*K) | O(M) | O(1)
LineUp | O(N) | O(N) | O(1)
LineDn | O(N) | O(N) | O(1)
PgUp | O(N*K) | O(N*K) | O(K)
PgDn | O(N*K) | O(N*K) | O(K)
Edit | O(M+N) | O(N) | O(N)

Умножаем веса для каждой из операций на матрицу и получаем трудоемкости для каждого из методов.

Мог чего не учесть, прошу поправлять:)

esl

04.04.2013, 19:45

оценивать только время работы с текстом в отрыве от юзер интерфейса мало смысла !
не стоит забывать что за компом сидит юзер, и этот юзер имеет некие ожидания скорости ответа компьютера
типа:
вставка/удаление символа : "Мгновенно" (он совершенно спокойно может набирать в слепую)
переход на строку вверх/вниз "Мгновенно", (он смотрит на экран, помнит его содержимое, новые данные анализировать не надо)
Страница ввер/низ : "быстро" (на экране новая инфомация, надо потратить время на ее анализ)
Начало/Конец текста "достаточно быстро" (контекст сильно изменяется, нужно только в специальны случаях)
сервисные операции (запись/поиск/etc) "желательно быстро" операции тяжелые, сложные, можно и подождать)

т.е. например пауза в 1/3 секунды при вооде символа вообще не приемлема
пауза в пару секунд при записи - терпимо

и по посту, а разве для Two part - Edit не O(1) ?

причем в любом случае, это скорость ВСЕГО редактора, с отрисовкой и прочим.

голая математика тут мало подходит, это комплекс решений ....

bigral

04.04.2013, 22:13

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

Вообще-то те алгоритмы что доступны для 8bit процов спокойно могут быть реализованны практически на ВСЕХ компах. Одним блоком желательно иметь ВСЕГДА И ВЕЗДЕ и любые данные. К тому же описанный метод своего рода "замена" классических одно-двухсвязных списков которая даст им фору по памяти и по сложности обслуживающих алгоритмов.

Vitamin

04.04.2013, 22:23

вставка/удаление символа : "Мгновенно" (он совершенно спокойно может набирать в слепую)
Использование буфера. Оно же поможет с автоформатированием.

Начало/Конец текста "достаточно быстро" (контекст сильно изменяется, нужно только в специальны случаях)
Про конец соглашусь, про начало- нет. Переход на начало чисто психологически должен быть мгновенным.

сервисные операции (запись/поиск/etc) "желательно быстро" операции тяжелые, сложные, можно и подождать)
О! Кстати о поиске. Для него накладные расходы вообще должны отсутствовать.

и по посту, а разве для Two part - Edit не O(1) ?
С чего это? Данные разве не надо положить?
Отредактировал оценку перехода на конец для plain text. Таки это надо отсчитать строки от конца.

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

esl

04.04.2013, 22:36

О! Кстати о поиске. Для него накладные расходы вообще должны отсутствовать.

а с того что надо что надо спросить у пользователя что искать, etc, etc,
есть дополнительное взаимодействие ...

С чего это? Данные разве не надо положить?
Отредактировал оценку перехода на конец для plain text. Таки это надо отсчитать строки от конца.

есть указатель на "Курсор"
в него поместили байт
увеличели X и указатель
все

Vitamin

04.04.2013, 22:43

а с того что надо что надо спросить у пользователя что искать, etc, etc,
есть дополнительное взаимодействие ...
Поскольку многопоточности нет, то незаметные задержки на спрашивания будут перемежаться с заметными задержками на перетасовку.
Т.е. начинаем искать в хвостовой части текста, как только нашли, все от начала хвоста до позиции поиска надо перекинуть.

есть указатель на "Курсор"
в него поместили байт
увеличели X и указатель
все
У тебя редактируются строки из одного символа?

esl

04.04.2013, 22:50

Вообще-то те алгоритмы что доступны для 8bit процов спокойно могут быть реализованны практически на ВСЕХ компах.

просто сейчас это уже не имеет такого смысла
когда размер сектора на диске 8к
и сейчас быстрее/надежнее сделать на хорошо известных структурах
редактор это в жизни много больше чем просто набор текста
и сложные структуры дают свои огромные плюсы.

Одним блоком желательно иметь ВСЕГДА И ВЕЗДЕ и любые данные. К тому же описанный метод своего рода "замена" классических одно-двухсвязных списков которая даст им фору по памяти и по сложности обслуживающих алгоритмов.

я вообще в курсе, зачем и описал тут этот метод ;)

---------- Post added at 21:50 ---------- Previous post was at 21:47 ----------

Поскольку многопоточности нет, то незаметные задержки на спрашивания будут перемежаться с заметными задержками на перетасовку.

Т.е. начинаем искать в хвостовой части текста, как только нашли, все от начала хвоста до позиции поиска надо перекинуть.

заметные, заметные, процесс то интерактивный
отрисовать диалог, спросить, отреагировать на результат поиска

зачем тягать при поиске ????
только когда нашли и надо отрисовать ;)

У тебя редактируются строки из одного символа?
нет конечно, но метод позволяет не использовать дополнительный буфер для редактирования строки ;)
правее курсора - свободное место ;)

Vitamin

04.04.2013, 23:08

зачем тягать при поиске ????
только когда нашли и надо отрисовать
А я что написал?

как только нашли, все от начала хвоста до позиции поиска надо перекинуть.

нет конечно, но метод позволяет не использовать дополнительный буфер для редактирования строки
правее курсора - свободное место
И сколько таки нужно операций для редактирования строки размером в N символов?

Напиши прототип. Увидишь и плюсы и минусы, может идеи какие гениальные придут. На форуме обсасывать можно до бесконечности.

esl

04.04.2013, 23:15

Напиши прототип. Увидишь и плюсы и минусы, может идеи какие гениальные придут. На форуме обсасывать можно до бесконечности.

гм, я начал с того что сказал что работал с редакторами которые по этой схеме были сделаны ;)
так что в отличии от есть некий опыт ;)

Vitamin

04.04.2013, 23:18

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

esl

04.04.2013, 23:48

Бгг. Почему-то думал, что ты топикстартер:)

Топикастер VINXRU- маг и волшебник кода и паяльника

alone

05.04.2013, 12:53

Home | O(1) | O(M) | O(1) End | O(N*K) | O(M) | O(1) LineUp | O(N) | O(N) | O(1) LineDn | O(N) | O(N) | O(1) PgUp | O(N*K) | O(N*K) | O(K) PgDn | O(N*K) | O(N*K) | O(K) Edit | O(M+N) | O(N) | O(N)
Home, End, PgUp и PgDn везде как минимум O(N*K), потому что надо перепечатать весь экран.
LineUp и LineDn на границе экрана требуют сдвига и вывода новой строки, так что оценка O(1) не имеет смысла.

Vitamin

05.04.2013, 12:56

Home, End, PgUp и PgDn везде как минимум O(N*K), потому что надо перепечатать весь экран.
LineUp и LineDn на границе экрана требуют сдвига и вывода новой строки, так что оценка O(1) не имеет смысла.
Перепечатка экрана- отдельная тема. Оценка исключительно для операций над текстом.

vinxru

09.04.2013, 13:32

Вчера ночью набросал первую версию программы, что бы оценить скорость. Скорость удовлетворительная. Реакция на Enter и Backspace (в начале строки) быстрее, чем я обычно печатаю.

http://s017.radikal.ru/i417/1304/10/e06873d7cc9a.png

vinxru

11.04.2013, 02:18

Добавил строку состояния. Обновление чисел в строке состояния происходит при каждом нажатии клавиши (деление 16 битного числа и рисование), при этом тормозов так же нет.

http://s017.radikal.ru/i442/1304/32/3d701fed9067.png

bigral

12.04.2013, 10:10

vinxru

12.04.2013, 11:37

круто, вот еще бы круче было если бы этот проект лежал открыто на каком-нибудь "google code" и вставки на асме были бы в отдельном каталоге /arch/specialist (типа чтоб легче было портировать)

Это пока первые-первые наброски. Потом так и сделаю.

Я вчера добавил вертикальный скролл. Еще буфер обмена добавлю и всё.

---------- Post added at 10:37 ---------- Previous post was at 10:19 ----------

Это будет редактор в комплекте с SD-контроллером, который я все таки планирую портировать на многие 8080 компы. На 86РК, Мирошу, Апогей в том числе.

Он нужен, что бы прямо с компьютера редактировать файл autoexec.bat и файл привязки к расширениями. То есть при запуске BAS файла, запустить бейсик. При запуске SCR запустить просмотрщик и т.п.