Здравствуйте, Klapaucius, Вы писали:

K>Есть текст (не разделен на строки одинаковой длины), который можно редактировать. Т.е. вставлять, удалять, добавлать в начало, в конец символ/блок символов. Должен поддерживаться "бесконечный" (пока есть свободная память) undo/redo на каждое изменение + дерево версий. Также, желательно, иметь возможность сравнивать версии. Понятно, что для хранения версии следует занимать разумный объем, сопоставимый с объемом изменений сделанных в этой версии, а не хранить весь текст.

Убедительная просьба — дочитать до конца, прежде чем комментировать.

Начнем с требования "бесконечный" (пока есть свободная память) undo/redo на каждое изменение + дерево версий.

Пройдем по виртуальному пространству (как — описано у Рихтера), найдем максимальный блок (обычно это 1.7-1.8 Гб). Захватим его с помощью VirtualAlloc. Это и будет наша свободная память. Все нижеописанные структуры будут храниться там. Назовем эту область буфером (Б).

Б будет заполняться чисто последовательно, то есть запишем туда n байт чего бы то ни было и продвинем текущий указатель на n — и т.д, пока не исчерпаем память. В дальнейшем, говоря о занесении в Б, я об этом упоминать больше не буду.

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

Заведем дерево версий (ДВ). Это дерево произвольной арности. Элемент дерева содержит

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

Заведем список фрагментов (СФ). Элемент списка содержит указатель на начало фрагмента, на конец фрагмента, и указатель на следующий фрагмент.

Создадим корень ДВ и поместим его в Б. После него разместим в Б исходный текст. СФ в корневом элементе имеет один элемент , показывающий на начало и конец текста. Текущий узел — корень.

Подготовка закончена.

Начнем с удаления символов или подстроки.

Строим нового чайлда от текущего узла. Копируем его список и производим в нем изменения.

Например

Исходный текст abcdefg, исходный список — (a,g). Требуется удалить cd. Новый список (a,b)-(e,g)

Естественно, под a,b,e,g здесь понимаются указатели на соответствующие места в Б.

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

Добавление.

Мне вообще-то все равно, в начало, в конец или куда-то еще.
Добавляемый фрагмент — в Б. Без длины и разделителей.
Строим нового чайлда от текущего узла. Копируем его список и производим в нем изменения.

Например, пусть после предыдущего удаления нужно добавить "xyz" после a. "xyz" записываем в Б.

Получим

(a,a)-(x,z)-(b,b)-(e,g).

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

Замена. Кстати, в задаче отсутствует. Решается элементарно — удаление и последующая вставка в одной операции.

Можно после получения нового списка попробовать "сжать" его. Пусть у нас образовался в нем кусок из 5 элементов, а каждый элемент показывает на однобуквенный фрагмент. Ясно, что 5 элементов списка занимают больше места, чем один элемент списка + 5. Объединим эти 5 букв в новый фрагмент и добавим его в Б. 5 элементов ликвидируем, заведем один и пусть он показывает на этот новый фрагмент

Все новые фрагменты текста, узлы ДВ, СФ хранятся в Б. До его исчерпания.

Undo — перейти к родителю в ДВ
Redo — перейти к младшему чайлду в ДВ.
Сравнение версий — получить указатели на два узла ДВ и сравнить тексты.

//////////////////////////////////////////////////////////////////////////////

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

>Понятно, что для хранения версии следует занимать разумный объем, сопоставимый с объемом изменений сделанных в этой версии, а не хранить весь текст

Весь текст я не храню. Более того, по объему хранимых байтов текста тут явный минимум. Но вот насчет "объем, сопоставимый с объемом изменений сделанных в этой версии" — как сказать. Список-то я копирую каждый раз. Так что с одной стороны я вроде этому требованию удовлетворяю, а с другой — нет

(Написал это и подумал — нет, не минимум. Можно еще уменьшить. При добавлении текста ищем его среди всех текстовых фрагментов Б (как подстроку). Если найдем, то в Б его не добавляем, оформляем СФ с указателями на найденный кусок

Ликвидируем СФ. Вместо него заведем ориентированный граф фрагментов (ГФ) В начальной ситуации этот граф содержит тот же список, что и выше. Назовем этот список путем в графе (ПГ). Итак, узел ДВ имеет указатель на путь в графе (который есть СФ де-факто)

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

Например

У родителя ПГ состоит из 10 фрагментов. Выясняем, что изменение касается только фрагментов 6 и 7 (замечу, что любое изменение касается только последовательных фрагментов и только один раз) и вместо них нужно добавить 1 новый фрагмент
Новый ПГ будет — 5 элементов из старого ПГ. В 5 элементе устраиваем развилку на новый элемент, а от него — на старый 8-й.

Для того, чтобы в дальнейшем найти нужный путь, помечаем все ребра в этом ПГ номером версии. В "развилке" берем то направление, которое соответствует текущей версии. Если текущей версии нет, то максимальной из версий, не большей текущей. Номер версии храним в элементе ДВ, это просто автоинкрементное значение. Впрочем, здесь надо продумать еще раз. Может, имеет смысл timestamp использовать.

Примечание 1. Если везде, где говорится об указателе, использовать смещение от начала Б, то весь Б можно выгрузить в файл, а потом загрузить заново и продолжить редактирование. Лишь бы нашелся свободный блок не меньшего чем Б размера. Естественно, замена указателя на смещение слегка замедлит работу.
Примечание 2. Для удаления всей этой конструкции необходим один вызов VirtualFree.

Здравствуйте, gear nuke, Вы писали:

GN>>>Для "указателя" достаточно полбайта.

Поля не длинные, обычно 5-10 символов

PD>>Обычно Сильно рискуешь.

GN>Применяя Хаффмана, или арифметическое кодирование?

Улучшать можно до бесконечности

Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>Ладно. Давай закончим пустые рассуждения. Вот тебе конкретная задача. Я ее не выдумал, это (с небольшими модификациями) то, что мне реально пришлось делать.
WH>Как верно заметил Klapaucius эта задача абсолютно не релевантна обработке строк.
WH>Но чтобы ты перестал гнуть пальцы веером я тебе ее решу.
WH>Но после этого ты решишь задачу которую поставил Klapaucius.

http://rsdn.ru/forum/philosophy/3557582.1.aspx

Автор: Pavel Dvorkin
Дата: 05.10.09

Здравствуйте, Pavel Dvorkin, Вы писали:

Эпиграфом к вашему посту должен был стать вот этот отрывок из "Понедельника":

На углу двое юношей возились с каким-то
механическим устройством. Один убежденно говорил: "Конструкторская мысль
не может стоять на месте. Это закон развития общества. Мы изобретем его.
Обязательно изобретем. Вопреки бюрократам вроде Чинушина и консерваторам
вроде Твердолобова". Другой юноша нес свое: "Я нашел, как применить
здесь нестирающиеся шины из полиструктурного волокна с вырожденными
аминными связями и неполными кислородными группами. Но я не знаю пока,
как использовать регенерирующий реактор на субтепловых нейтронах. Миша,
Мишок! Как быть с реактором?" Присмотревшись к устройству, я без труда
узнал велосипед.

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

PD>Список-то я копирую каждый раз. Так что с одной стороны я вроде этому требованию удовлетворяю, а с другой — нет

Верно. Поэтому от списка конкатенации нужно перейти к дереву конкатенации. И тогда нужно будет копировать не N элементов при изменении списка, а log N при изменении дерева. Это и есть последний шаг до нормального решения. Таймстампы и регенерирующие реакторы на субтепловых нейтронах тут все-таки лишние сущности.

Здравствуйте, Pavel Dvorkin, Вы писали:

>>т.е. в принципе понимаю, что будет дальше и с кем я имею дело.
PD>Выделенное тоже относится к твоей собственной несовершенной личности или же нет ?

Нет, конечно. Довольно очевидно, что тут говорится о том, что вы — великий спорщик. Чем, понятное дело, можно только гордиться.

Ну, как у Кэролла:

“I don’t think they play at all fairly,” Alice began, in rather a complaining tone, “and they all quarrel so dreadfully one can’t hear oneself speak—and they don’t seem to have any rules in particular: at least, if there are, nobody attends to them—and you’ve no idea how confusing it is all the things being alive: for instance, there’s the arch I’ve got to go through next walking about at the other end of the ground—and I should have croqueted the Queen’s hedgehog just now, only it ran away when it saw mine coming!”

“How do you like the Queen?” said the Cat in a low voice.

“Not at all,” said Alice: “she’s so extremely—” Just then she noticed that the Queen was close behind her, listening: so she went on “—likely to win, that it’s hardly worth while finishing the game.”

Здравствуйте, Pavel Dvorkin, Вы писали:

K>>Это умозрительное уражнение с высосанными из пальца граничными условиями.
PD>Мне за него деньги заплатили. Это раз. Во-вторых, если уж так — надо было сразу сказать, а не пытаться решать.

Мне кажется очень неправдоподобным, что задача ставилась заказчиком именно в такой форме.
Т.е. вот это:

Дан файл в формате CSV. 10 полей на строчку, есть пустые поля. Поля не длинные, обычно 5-10 символов. Количество строк известно, порядка 5 миллионов. Размер файла 200 Мб, известен точно.
1. Выдачу этих строк в исходном порядке
2. Выдачу строк, отсортированых по любому из первых трех полей. (SELECT * ORDER BY FIELD1)
3. Выдачу любого набора полей в любом порядке из строк, отсортированных по любому из первых трех полей (SELECT FIELD2,FIELD5 ORDER BY FIELD1)
4. Выдачу аналогично п.3, но только для тех строк, у которых поле сортировки равно чему-то (SELECT FIELD2,FIELD5 ORDER BY FIELD1 WHERE FIELD1="ABCD")

похоже на задание, но вот это:

Для п.2-4 сортировка в момент запроса не допускается. Данные должны быть готовы для выдачи в этот момент без какой бы то ни было модификации.
Вся информация должна быть в ОП, чтение из файла можно провести только один раз.
Можешь завести нужные вспомогательные структуры, массивы и т.п, но копировать строки не разрешается. Иными словами, каждая исходное текстовое поле должно присутствовать в памяти ТОЛЬКО ОДИН РАЗ. Хоть явно, хоть неявно. На вспомогательные структуры, так и быть, еще 50-70 Мб дам.

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

PD>А это и есть задача на парсинг текстового файла. А он, как всем известно, состоит из строк. Независимо от того, как они представлены — в виде char*, string всех сортов или же заканчиваются CR/LF. В CSV файле лежат текстовые строки, а это задача на их обработку.

Парсинг CSV — задача имеющая тривиальное решение. Вся работа в вашей задаче связана с разработкой структуры размещения читаемого файла в памяти. Которая после создания не изменяется.

K>>А почему заказчик не хотел пользоваться базой данных?
PD>Данные представлены из источника, который мне передать не могут. Причины обсуждать здесь не будем. Мне представлен текстовый файл в формате CSV. У меня нет оснований отказаться от его обработки.

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

PD>Асимптотика совершенно была неинтересна. Эти данные такие, как они есть, и в будущем объем этих данных может увеличиться не более чем на 5-10%.

Да какая разница увеличится он или нет? Из каких соображений вы выбираете алгоритмы и структуры данных? Возвращаясь к началу разговора — почему оптимизированная сортировка пузырьком может быть хуже неоптимизированной быстрой сортировки?

PD>Решение, не удовлетворяющее требованиям, не есть решение. Неужели это надо объяснять?

В требованиях были ограничения только на вспомогательные структуры данных — т.е. я так понял, на интдексы для сортировки и, возможно, фильтрации. Индексы для сортировки очевидно умещаются в 50-70мб. Вообще же речь идет только об организации размещения блоков с минимальными расходами. Какое отношение это имеет к теме беседы?

Здравствуйте, Klapaucius, Вы писали:

PD>>Список-то я копирую каждый раз. Так что с одной стороны я вроде этому требованию удовлетворяю, а с другой — нет

K>Верно. Поэтому от списка конкатенации нужно перейти к дереву конкатенации. И тогда нужно будет копировать не N элементов при изменении списка, а log N при изменении дерева. Это и есть последний шаг до нормального решения. Таймстампы и регенерирующие реакторы на субтепловых нейтронах тут все-таки лишние сущности.

Я же просил дочитать до конца. Там как раз список удаляется, а вместо него граф.

А с веревками я действительно не знаком

Здравствуйте, Pavel Dvorkin, Вы писали:

WH>>Если у нас есть гарантия что общая длинна строки не может быть больше 255 байт
PD>Нет такой гарантии. В условиях ничего об этом не сказано.

Ну, тогда максимальная длина блока, на которые строка разделяется. Сложение никто не отменял. Да и под сохранение числа можно выделять именно столько байт, сколько нужно для каждого конкретного случая. Очевидно, что если средняя длина блока 5-10, то больше половины байта редко когда понадобится.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Я же просил дочитать до конца. Там как раз список удаляется, а вместо него граф.

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

Здравствуйте, Klapaucius, Вы писали:

K>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>Я же просил дочитать до конца. Там как раз список удаляется, а вместо него граф.

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

Гм...

Давай так — изложи с подробностями свои веревки. Ничего не надо, только путь в дереве. Вот предположим он состоит из 20 фрагментов. Изменения касаются фрагментов с 5 по 7, остальные (1-4 и 8-20) без изменений. Что будет представлять собой новый путь ?

Здравствуйте, Klapaucius, Вы писали:

K>Здравствуйте, Pavel Dvorkin, Вы писали:

WH>>>Если у нас есть гарантия что общая длинна строки не может быть больше 255 байт
PD>>Нет такой гарантии. В условиях ничего об этом не сказано.

K>Ну, тогда максимальная длина блока, на которые строка разделяется. Сложение никто не отменял. Да и под сохранение числа можно выделять именно столько байт, сколько нужно для каждого конкретного случая.

А все же сколько ? Я не могу ничего гарантировать. В лучшем случае я могу еще предположить, что отдельное поле будет длиной не более 255. Но и на это я не хотел бы закладываться. Крайне маловероятно, а вдруг ? Если бы это было не в "сердце" алгоритма , то еще ладно, а ведь тут вся структура данных накроется медным тазом.

>Очевидно, что если средняя длина блока 5-10, то больше половины байта редко когда понадобится.

То, что редко — верно. А вот что делать будешь, если все же окажется 16 или больше ? Ну не могу я дать точного максимума, не знаю я его. И если даже знаю — нет гарантии, что для следующей версии там данные не изменятся.

Здравствуйте, Klapaucius, Вы писали:

K>Здравствуйте, Pavel Dvorkin, Вы писали:

K>>>Это умозрительное уражнение с высосанными из пальца граничными условиями.
PD>>Мне за него деньги заплатили. Это раз. Во-вторых, если уж так — надо было сразу сказать, а не пытаться решать.

K>Мне кажется очень неправдоподобным, что задача ставилась заказчиком именно в такой форме.

Ты отчасти прав. Читай внимательно

PD>Я ее не выдумал, это (с небольшими модификациями) то, что мне реально пришлось делать.

То есть я тебе дал не реальную задачу, а некоторую модификацию. Чтобы тебе скучно не было.

K>похоже на задание, но вот это:
K>

K>Для п.2-4 сортировка в момент запроса не допускается. Данные должны быть готовы для выдачи в этот момент без какой бы то ни было модификации.
K>Вся информация должна быть в ОП, чтение из файла можно провести только один раз.
K>Можешь завести нужные вспомогательные структуры, массивы и т.п, но копировать строки не разрешается. Иными словами, каждая исходное текстовое поле должно присутствовать в памяти ТОЛЬКО ОДИН РАЗ. Хоть явно, хоть неявно. На вспомогательные структуры, так и быть, еще 50-70 Мб дам.

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

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

А если серьезнее — безусловными были требования по памяти. По скорости не очень. Но все же если я на каждый запрос начну сортировать — то и по скорости никуда не пойдет. Открою небольшой секрет — эти запросы SELECT вовсе не делаются. Просто надо потом эти данные переформировать (а на это место нужно!!!) в совсем иную структуру , и при этом они должны быть упорядочены по ключам, иначе я эту структуру до второго пришествия строить буду.

K>Парсинг CSV — задача имеющая тривиальное решение. Вся работа в вашей задаче связана с разработкой структуры размещения читаемого файла в памяти. Которая после создания не изменяется.

Вполне согласен. Но asciiz меня здесь спасли. В сущности, твое решение ничем от моего не отличается. Поэтому я специально в пятницу не торопился выкладывать свое, ждал, что ты сделаешь один шаг, дойдешь до ASCIIZ, и мне останется только поздравить тебя с решением . Но тебе признать формат ASCIIZ религия не позволяет

K>Все равно непонятно. Почему нельзя загрузить CSV в базу данных, а там уже пусть БД решает что хранить на диске, что в памяти и как оптимизировать запросы?

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

PD>>Асимптотика совершенно была неинтересна. Эти данные такие, как они есть, и в будущем объем этих данных может увеличиться не более чем на 5-10%.

K>Да какая разница увеличится он или нет? Из каких соображений вы выбираете алгоритмы и структуры данных?

Исключительно из требований конкретной задачи. Я пойду на нарушение любых канонов, если в данной задачае это будет оправданно.


>Возвращаясь к началу разговора — почему оптимизированная сортировка пузырьком может быть хуже неоптимизированной быстрой сортировки?

Странный вопрос. Тебе объяснить про N^2 и NlnN ?



K>В требованиях были ограничения только на вспомогательные структуры данных — т.е. я так понял, на интдексы для сортировки и, возможно, фильтрации. Индексы для сортировки очевидно умещаются в 50-70мб. Вообще же речь идет только об организации размещения блоков с минимальными расходами. Какое отношение это имеет к теме беседы?

ASCIIZ

Здравствуйте, Klapaucius, Вы писали:

Извини, не могу удержаться. Не хочешь — не отвечай.

Модификация твоей задачи.

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

А теперь мое требование.

При записи и чтении не разрешается использовать вообще никакие сложные структуры данных. Ни явно, ни неявно. Максимум , что ты можешь себе позволить — несколько простых переменных (int, long, указатели на структуры, ссылки на экземпляры классов, но без new). Никаких новых экземпляров классов. Никаких массивов.

Сериализация дотнета ни в каком виде не проходит. Для нее внутренние буфера понадобятся.

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

Я свое решение привел. Напоминаю — вместо указателей — смещения, а запись в файл — WriteFile всего этого Б. Чтение — ReadFile. Ну и CreateFile, CloseHandle, конечно.

Здравствуйте, AndrewVK, Вы писали:

AVK>Некоторые паталогически не способны признать свою неправоту. Это очень хорошо видно, когда человек под конец начинает говорить горы абсурда, либо сваливается на грубую демагогию и хамство.

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

Невзирая на лица.

В том числе и на лица членов RSDN-team.

И даже на свое собственное лицо. Если он того заслуживает

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Да ну ? Так-таки и неоткуда ? Я уж не говорю про ввод с клавиатуры, хотя большинство строк именно такой генезис имеют.
Как мы уже выяснили пару лет назад, "ввод с клавиатуры" в наше время означает получение строки из контрола типа EDIT. В котором, естественно, как мы тоже выяснили пару лет назад, строки в момент получения уже оборудованы длиной. Печально, что преподаватель Win32 API демонстрирует столь упорное невежество в элементарных вещах.
PD>Я уж не говорю про OCR, из которого в компьютеры пришли остальные строки прежде чем их записали на диск или отправили в сеть.
PD>Но открою тебе секрет — есть еще возможность из одних строк делать другие в самой программе
А можно в студию пример такой операции в "самой программе", при которой из "одних строк", все из которых оборудованы длиной, получается строка неизвестной длины? Ну, то есть на "узнавание" длины которой нужно потратить больше, чем O(1) времени?

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Вполне согласен. Но asciiz меня здесь спасли. В сущности, твое решение ничем от моего не отличается. Поэтому я специально в пятницу не торопился выкладывать свое, ждал, что ты сделаешь один шаг, дойдешь до ASCIIZ, и мне останется только поздравить тебя с решением . Но тебе признать формат ASCIIZ религия не позволяет
Здесь спасают не ASCIIZ, а грамотная работа с данными. Поскольку они неизменны, то достаточно построить один раз индексы. Поскольку техника работы с индексами, размер которых превышает размер доступной оперативной памяти, разработана уже очень давно, никакие велосипеды тут не нужны. Можно занять хоть 900 лишних мегабайт — всё равно при выполнении типичного запроса почти всё будет уезжать прямо из кэша.

PD>Нельзя. Давай не будем это обсуждать. Есть причины, которые я не могу раскрывать.


PD>ASCIIZ

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>Да ну ? Так-таки и неоткуда ? Я уж не говорю про ввод с клавиатуры, хотя большинство строк именно такой генезис имеют.
S>Как мы уже выяснили пару лет назад, "ввод с клавиатуры" в наше время означает получение строки из контрола типа EDIT.

Даже в консольных приложениях ?


PD>>Я уж не говорю про OCR, из которого в компьютеры пришли остальные строки прежде чем их записали на диск или отправили в сеть.
PD>>Но открою тебе секрет — есть еще возможность из одних строк делать другие в самой программе
S>А можно в студию пример такой операции в "самой программе", при которой из "одних строк", все из которых оборудованы длиной, получается строка неизвестной длины? Ну, то есть на "узнавание" длины которой нужно потратить больше, чем O(1) времени?

String.Split. Правда, тут не одна строка получится, а несколько, но я и не обещал одну. Я обещал из одних — другие.

PD>Здравствуйте, Klapaucius, Вы писали:

Предлагаю небольшую модификацию твоей задачи.

Есть текст , разделен на строки неодинаковой длины, который можно редактировать. Т.е. вставлять, удалять, добавлять в начало, в конец символ/блок символов/блок строк. Можно добавлять как между строками редактируемого текста, так и внутрь какой-то строки, и если при этом добавляется блок строк — должно поддерживаться корректное разбиение на строки. Можно удалять блок, который начинается в середине одной строки, продолжатеся на нескольких (>=0) следующих строках и заканчивается в середине следующей строки. (В общем, как в обычном текстовом редакторе — вставка в любое место любого куска, удаление любого куска, который можно выделить Shift- стрелка и т.п.) Исходный текст изначально находится в текстовом файле.
Должен поддерживаться "бесконечный" (пока есть свободная память) undo/redo на каждое изменение + дерево версий. Также, желательно, иметь возможность сравнивать версии. Понятно, что для хранения версии следует занимать разумный объем, сопоставимый с объемом изменений сделанных в этой версии, а не хранить весь текст.

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

Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Даже в консольных приложениях ?
В консольных приложениях строки приезжают из двух мест:
1. Командная строка — там, естественно, весь парсинг, включая выяснение длины строки, уже выполнен заранее
2. Чтение из консоли — как уже сказали, там узким местом подсчёт символов вовсе не является.

PD>String.Split. Правда, тут не одна строка получится, а несколько, но я и не обещал одну. Я обещал из одних — другие.
И? String.Split и так занимает O(N). Вычислять заодно длину получамых фрагментов — весьма несложно.
Незачёт.

Здравствуйте, Sinclair, Вы писали:


PD>>String.Split. Правда, тут не одна строка получится, а несколько, но я и не обещал одну. Я обещал из одних — другие.
S>И? String.Split и так занимает O(N). Вычислять заодно длину получамых фрагментов — весьма несложно.
S>Незачёт.

Не пойдет. Substr тоже занимает O(M) (где M — длина вырезки), копировать-то надо. Но там длина подстроки вычисляется элементарно, а тут — нет. Ты просил пример, где нужно больше O(1), я его тебе дал. Никаких других условий не было. А если добавлять условия по ходу действия, то мы никогда не кончим.

Все, Антон, закрываю со своей стороны эту веточку. Мне дискуссии с тобой насчет строк уже изрядно надоели