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

C>>Ознакомился.
WH>Значит теперь ты сможешь осознать что гапнуть ропу зиппером ни разу не проблема.
А зачем?

WH>>>2)А если рассматривать задачу в комплексе те вспомнить про undo/redo то кто кого порвет мы еще посмотрим...
C>>А что с ними не так у gap buffers?
WH>А то что их нужно делать.
Как и верёвки...

WH>Нужно придумать структуры данных.
Как и верёвки...

WH>Реализовать без ошибок.
Как и верёвки...

WH>Поддерживать их в актуальном состоянии.
Как и верёвки...

WH>А в случае с rope у нас все получается бесплатно.
WH>Все что нужно это добавить 2 односвязных списка.
WH>Один для undo второй для redo.
WH>А односвязные списки как ты понимаешь в любом функциональном языке буквально везде.
Такая структура называется "finger tree" — http://en.wikipedia.org/wiki/Finger_tree

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

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

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

PD>>Я са могу создать иммутабл тип ? Есть такие средства в языке ?
S>Конечно. Будет ничуть не хуже, чем строка. См. DateTime.

Ну ин пусть так.

PD>>Ладно, оставим твои аппеляции к потокобезопасности в стороне. Не всегда она нужна, и уж тебе ли не знать, что большинство классов .Net не являются потокобезопасными, а значит, эту безопасность придется делать вне. Также и здесь можно было бы поступить. Но я даже и это обсуждать не хочу. Допустим, у меня вообще один всего поток — почему я должен платить за эту самую потокобезопасность, если она мне не нужна.
S>Потому что это не С++ здесь некоторые решения приняты за тебя. В частности, написать свою потокобезопасную строку намного сложнее, чем взять готовую.

Ну это что-то не очень ясное. Готовая отличается от моей тем, что писал ее не я, вот и все. Если это не так, это лишь значит, что МС использует нечто, что не дает мне использовать. Это, кстати, за ней не раз замечалось еще с ДОС времен.

PD>>Слушай, не наводи тень на плетень. Хоть какие вргументы приводи — не докажешь, что не выполнять лишних действий лучше, чем их выполнять
S>Не хочешь — не буду. Это твое дело, насколько неэффективные программы ты будешь писать на управляемых языках.

Не, не буду. Я вообще , когда речь идет об эффективнсти, их использовать не буду

PD>>И потом — а скорость уборки GC всей этой кунсткамеры тоже пренебрежимо мала ?
S>Стоимость уборки строк равна нулю — у них нет финализатора.

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


PD>>Да нет, в общем-то, угадал. В сущности этот самый m_StringValue и есть кусок из short, точнее, ссылка на него .
S>Не наводи тень на плетень. Ты спрашивал "где строки" — я показал тебе строки. Еще раз тебе объясняю: в управляемой среде в 99% случаев не надо ни "мешать" сборщику мусора, ни "помогать" ему. Понять, что ты попал в 1%, можно исключительно с помощью профайлера. Рассуждения типа "ой, тут что-то копируется, наверное без этого будет дешевле" не работают. Работает только профайлер.

Это твое утверждение можно преобразовать в эквивалентное "сделаем что-то, а потом посмотрим, что из этого получилось". Профалер же не дух святой, а просто средство посмотреть, что в итоге вышло. И не очень хорошо, что нельзя a priory сделать какие-то соображения, а можно только a posteriory смотреть, что вышло. Да, ты мне сейчас прочтешь лекцию в очередной раз о том, где использовать string, а где StringBuilder , но это частный случай, а применять такой подход в общем случае не очень хорошо.

А теперь по существу этой самой иммутабельности. Все же это должно быть свойство не типа , а экземпляра. Экземпляр может быть константой, порождаемой в рантайме, а тип вообще-то не должен. Если нам надо число PI вычислить , то результат должен впоследствии не изменяться, но не потому, что он float или double, а потому что он по смыслу не должен изменяться. А сам тип — не должен быть иммутабельным. Это и к строкам относится.

Что же касается решения Java/.Net о константности типов, то это полурешение, со своими недостатками, о которых тут говорили. И со своими плюсами, о которых тоже говорили.

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


PD>А блоки памяти в большом количестве порожденные все же надо убирать ? пусть по алгоритму GC, но все же надо...
Убирать, то есть дефрагментировать нужно живые блоки. Если живых блоков нет, то просто сдвинется учазатель конца кучи.

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


PD>А теперь по существу этой самой иммутабельности. Все же это должно быть свойство не типа , а экземпляра. Экземпляр может быть константой, порождаемой в рантайме, а тип вообще-то не должен. Если нам надо число PI вычислить , то результат должен впоследствии не изменяться, но не потому, что он float или double, а потому что он по смыслу не должен изменяться. А сам тип — не должен быть иммутабельным. Это и к строкам относится.

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

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

WH>>>>2)А если рассматривать задачу в комплексе те вспомнить про undo/redo то кто кого порвет мы еще посмотрим...
C>>>А что с ними не так у gap buffers?
WH>>А то что их нужно делать.
C>Как и верёвки...

Т.е. тот факт, что undo/redo для персистентной структуры это два списка, а для неперсистентной нечто принципиально другое по сложности, трудозатратам и эффективности — это значения не имеет? А имеет значение, что и то и другое надо делать? Интересное мнение.

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

WH>>Значит теперь ты сможешь осознать что гапнуть ропу зиппером ни разу не проблема.
C>А зачем?
За тем чтобы ее можно было эффективно использовать в редакторе?

WH>>А то что их нужно делать.
C>Как и верёвки...
Это сделал разработчик стандартной библиотеки.

WH>>Нужно придумать структуры данных.
C>Как и верёвки...
Это сделал разработчик стандартной библиотеки.

WH>>Реализовать без ошибок.
C>Как и верёвки...
Это сделал разработчик стандартной библиотеки.

WH>>Поддерживать их в актуальном состоянии.
C>Как и верёвки...
Тут тебя вообще куда то понесло.
Я говорил про то что эти самые структуры для undo/redo нужно во время редактирования текста постоянно обновлять.
В случае с ропами это тривиально и сводится к добавлению текущего состояния в список undo состояний.

C>Такая структура называется "finger tree" — http://en.wikipedia.org/wiki/Finger_tree
Это вообще не про то.
Пальчиковые деревья альтернатива ропам, а не undo/redo стеку.

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

WH>>>Значит теперь ты сможешь осознать что гапнуть ропу зиппером ни разу не проблема.
C>>А зачем?
WH>За тем чтобы ее можно было эффективно использовать в редакторе?
Некоторые вещи в делаются проще с gap-буффером.

WH>>>Реализовать без ошибок.
C>>Как и верёвки...
WH>Это сделал разработчик стандартной библиотеки.
И что?

Это не отменяет тот факт, что обе структуры

WH>Тут тебя вообще куда то понесло.
WH>Я говорил про то что эти самые структуры для undo/redo нужно во время редактирования текста постоянно обновлять.
WH>В случае с ропами это тривиально и сводится к добавлению текущего состояния в список undo состояний.
Примерно аналогично это делается для gap-буффера — просто достаточно запоминать его позицию и состояние. Причём у нас будет гарантия O(1) сложности по времени и памяти для стека undo/redo.

C>>Такая структура называется "finger tree" — http://en.wikipedia.org/wiki/Finger_tree
WH>Это вообще не про то.
WH>Пальчиковые деревья альтернатива ропам, а не undo/redo стеку.
Rope с undo/redo стеком в них вырождается.

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

C>>>Такая структура называется "finger tree" — http://en.wikipedia.org/wiki/Finger_tree
WH>>Пальчиковые деревья альтернатива ропам, а не undo/redo стеку.
C>Rope с undo/redo стеком в них вырождается.

Finger Tree — это дерево с "с пальцем" для быстрого доступа к элементу, а "палец" — это скорее такой прото-зиппер. Может я что-то не так понимаю, но как тут одно в другое выражается не вижу, можно это как-то продемонстрировать?

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

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

S>> За счет чего можно рвать непрерывную неизменяемую память?
S>>Что касается изменяемой то очень сильно зависит как от размера так и действий.
WH>RTFM
Хороший ответ. Попрбую по друному задать вопрос.
Если мы выделили строку из 10 строк один раз, и пользуем как ключ или поиска в достаточно большом объеме, то затраты по поиску будут одинаковы для непрерывной памяти или списка из 10 строк.
При сборке мусора не будут ли дефрагментироваться эти 10 строк, и по сути получать те же затраты по копирования при слиянию строк?

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

ГВ>>Это ты из принципа? Очень дешёвая — но всё равно же не нуль.
WH>А модификация типа нуль?

Ну я не знаю... Вставить один узел или Log(N). ИМХО, разница есть.

ГВ>>Нет, не правильно ты меня понял. Реализовать-то можно, только потери по скорости будут.
WH>С какой стати?
WH>Решение в каждом узле принимается за O(1) с весьма маленьким О.

Даже очень маленькая O это всё равно не нуль. И потом, поиск символа ближе к концу строки будет уже O(N) — нужно будет перебрать все узлы.

ГВ>>Есть, например, EDI-протоколы, формат сообщений которых предполагает фиксированные позиции элементов.
WH>Дай ссылку на толковое описание. А то я что-то один маркетинговый булщит нахожу.

Вот, например. Правда, протокол, скорее всего, малораспространённый. Поищу на выходных ещё ссылки, точно помню, что были и другие. Потом, в тех же форматах EDI нередко встречаются такие описания сегментов, как, скажем YYYYMMDD — тоже, в общем, формат представления с фиксированными позициями элементов. Хотя такой пример, наверное, уже крайность.

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

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

C>Некоторые вещи в делаются проще с gap-буффером.
Какие?

WH>>Это сделал разработчик стандартной библиотеки.
C>И что?
И то что автору редактора ее писать не придется.

C>Это не отменяет тот факт, что обе структуры
Только автору редактора с гап буфером придется придумывать и реализовывать структуру для undo/redo, а автору редактора на ропах нет.

C>Примерно аналогично это делается для gap-буффера — просто достаточно запоминать его позицию и состояние. Причём у нас будет гарантия O(1) сложности по времени и памяти для стека undo/redo.

Что ты будешь делать с удалением?
Или когда дырка закончилась?
Короче сложность реализации просто не сравнима.

C>Rope с undo/redo стеком в них вырождается.
Я думаю ты что-то где-то очень сильно путаешь.

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

C>>Некоторые вещи в делаются проще с gap-буффером.
WH>Какие?
Массовые операции замены, разбиение на строки, text wrapping и т.д.

C>>Это не отменяет тот факт, что обе структуры
WH>Только автору редактора с гап буфером придется придумывать и реализовывать структуру для undo/redo, а автору редактора на ропах нет.
Если она есть в стандартной библиотеке.

C>>Примерно аналогично это делается для gap-буффера — просто достаточно запоминать его позицию и состояние. Причём у нас будет гарантия O(1) сложности по времени и памяти для стека undo/redo.
WH>
WH>Что ты будешь делать с удалением?
А с ним надо что-то особое делать? Точно так же запоминаем позицию и содержание дырки.

WH>Или когда дырка закончилась?
Единственный сложный случай.

WH>Короче сложность реализации просто не сравнима.
Очень даже. Весь код gap string помещается в сотню строк (я знаю, сам их реализовывал). Вместе с undo/redo.

C>>Rope с undo/redo стеком в них вырождается.
WH>Я думаю ты что-то где-то очень сильно путаешь.
Я написал очень длинный пост на эту тему, но RSDN вчера его съел. Сейчас вот снова буду писать.

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

WH>>А модификация типа нуль?
ГВ>Ну я не знаю... Вставить один узел или Log(N). ИМХО, разница есть.
Это если говорить про оптимистический случай.
А в среднем разницы не будет.

ГВ>Даже очень маленькая O это всё равно не нуль. И потом, поиск символа ближе к концу строки будет уже O(N) — нужно будет перебрать все узлы.
Чё? С какой это стати O(N)?
Log(N) гарантировано.
Попробуй объяснить откуда ты взял O(N). Я не понимаю.

ГВ>Вот, например. Правда, протокол, скорее всего, малораспространённый. Поищу на выходных ещё ссылки, точно помню, что были и другие. Потом, в тех же форматах EDI нередко встречаются такие описания сегментов, как, скажем YYYYMMDD — тоже, в общем, формат представления с фиксированными позициями элементов. Хотя такой пример, наверное, уже крайность.
Понятно.
Только эта задача к строкам не относится.
Тут у нас сериализация/десериализация в/из бинарного потока.
Решается декларативно на любом языке с нормальными макросами или хотя бы рефлексией.

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

C>Массовые операции замены,
Что-то не верится.

C>разбиение на строки,
Куда проще то?

C>text wrapping и т.д.
Чего?

C>Если она есть в стандартной библиотеке.
Библиотеках функциональных языков должна быть.

WH>>Или когда дырка закончилась?
C>Единственный сложный случай.
Не верю что единственный.

C>Очень даже. Весь код gap string помещается в сотню строк (я знаю, сам их реализовывал). Вместе с undo/redo.
Ну тогда код в студию.
Только обязательно вместе с undo/redo.

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

WH>>>А модификация типа нуль?
ГВ>>Ну я не знаю... Вставить один узел или Log(N). ИМХО, разница есть.
WH>Это если говорить про оптимистический случай.
WH>А в среднем разницы не будет.

Здравствуйте?! И в среднем разница будет. Хотя бы потому что мутабельный rope не требует дублировать корневой узел и весь путь от корня до модифицируемого узла.

ГВ>>Даже очень маленькая O это всё равно не нуль. И потом, поиск символа ближе к концу строки будет уже O(N) — нужно будет перебрать все узлы.
WH>Чё? С какой это стати O(N)?
WH>Log(N) гарантировано.
WH>Попробуй объяснить откуда ты взял O(N). Я не понимаю.

Извини, я не уточнил, что в данном случае N — количество узлов дерева сегментов.

ГВ>>Вот, например. Правда, протокол, скорее всего, малораспространённый. Поищу на выходных ещё ссылки, точно помню, что были и другие. Потом, в тех же форматах EDI нередко встречаются такие описания сегментов, как, скажем YYYYMMDD — тоже, в общем, формат представления с фиксированными позициями элементов. Хотя такой пример, наверное, уже крайность.
WH>Понятно.
WH>Только эта задача к строкам не относится.

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

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

ГВ>Здравствуйте?! И в среднем разница будет. Хотя бы потому что мутабельный rope не требует дублировать корневой узел и весь путь от корня до модифицируемого узла.
А у изменяемой ропы типа новые узлы создавать не надо?
А для массовых вставок есть зипперы. Или можно сразу взять пальчиковое дерево которое по сути хитрая помесь ропы с зиппером.

ГВ>Извини, я не уточнил, что в данном случае N — количество узлов дерева сегментов.
Да как ни крути, а пройтись придется только по узлам от корня до нужного листа.
Короче давай объясняй откуда взял O(N).

ГВ>Ты спросил, где может потребоваться индексный доступ, я ответил.
А я пояснил что:
1)К строкам это отношения не имеет.
2)Учитывая опциональные поля по индексу ходить не получится.

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

ГВ>>Здравствуйте?! И в среднем разница будет. Хотя бы потому что мутабельный rope не требует дублировать корневой узел и весь путь от корня до модифицируемого узла.
WH>А у изменяемой ропы типа новые узлы создавать не надо?

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

WH>А для массовых вставок есть зипперы. Или можно сразу взять пальчиковое дерево которое по сути хитрая помесь ропы с зиппером.

Это сейчас к делу не относится.

ГВ>>Извини, я не уточнил, что в данном случае N — количество узлов дерева сегментов.
WH>Да как ни крути, а пройтись придется только по узлам от корня до нужного листа.

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

WH>Короче давай объясняй откуда взял O(N).

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

ГВ>>Ты спросил, где может потребоваться индексный доступ, я ответил.
WH>А я пояснил что:
WH>1)К строкам это отношения не имеет.

Имеет самое прямое.

WH>2)Учитывая опциональные поля по индексу ходить не получится.

Отнюдь. Посмотри спецификацию внимательней — сегменты фиксированной длины расположены в начале каждой строки.

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

WH>>А для массовых вставок есть зипперы. Или можно сразу взять пальчиковое дерево которое по сути хитрая помесь ропы с зиппером.
ГВ>Это сейчас к делу не относится.
Еще как относится.

ГВ>Кстати, как ты этот узел искать будешь? Либо с узлом должно быть сопоставлено его смещение в строке, либо нужно перебирать все узлы с начала (с самого левого).
А как в бинарных деревьях поиска ищут?

ГВ>Оттуда и взял — из твоего высказывания, что в каждом узле лежит длина только его собственной подстроки. Напоминаю, что N — число узлов дерева в данном случае.
Понятно. Как устроены ропы представления не имеешь.

WH>>1)К строкам это отношения не имеет.
ГВ>Имеет самое прямое.
Ну если на все смотреть чисто с точки зрения С/С++ программиста то может и имеет.
А вот я предпочитаю более высокоуровневые языки.
В любом случае общение с внешнем миром происходит не при помощи строк, а при помощи блобов.
Соответственно задача сводится к сериализации/десериализации некой объектной модели в блоб этого формата.
А если учесть что для действительно эффективного разбора этой гадости нужно генерировать весьма специфичный конечный автомат то все апелляции к ручному разбору мягко говоря идут лесом.

WH>>2)Учитывая опциональные поля по индексу ходить не получится.
ГВ>Отнюдь. Посмотри спецификацию внимательней — сегменты фиксированной длины расположены в начале каждой строки.

1)Там все сегменты фиксированной длинны.
2)А с опциональными что делать будешь? С ними доступ по индексу уже не работает.
3)Плюс еще не мешало бы разобраться сегмент какого типа ты пытаешься читать.

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

Не совсем понимаю смысла в immutable rope`ах. Можно где-то скачать реализацию на дотнет?



(это не к вопросу о веревках, но в контексте дискуссии):

Небольшой тест производительности std::wstring в сравнении со StringBuilder.

std::wstring

append: elapsed: 6 seconds.
replace: (стандартной реализации нет, как ни странно, а написанная на коленке функция работала так долго, что я просто не дождался выполнения)
insert: elapsed: 22 seconds.

System.Text.StringBuilder

append: elapsed 00:00:02.0856345
replace: elapsed 00:00:02.8668542
insert: elapsed 00:00:18.0279118

Исходники

inline void replace(std::wstring &text, std::wstring &s, std::wstring &d)
{
    for(unsigned index=0; index=text.find(s, index), index!=std::string::npos;)
    {
        text.replace(index, s.length(), d);
        index+=d.length();
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
     time_t t1, t2;

    time(&t1);

    std::wstring *str1 = new std::wstring();
    
    for(int i = 0; i<100000000; i++)
    {
        str1->append(L"c1");
    }

        time(&t2);

    std::cout << "append: elapsed: " << difftime(t2, t1) << " seconds." << std::endl;
    std::cout << str1->length() << std::endl;

    time(&t1);
    int ind;
    for(int ind = 10000; ind<100000; ind+=1000)
    {
        str1->insert(ind, std::wstring(L"7"));
    }
        time(&t2);

    std::cout << "insert: elapsed: " << difftime(t2, t1) << " seconds." << std::endl;

    delete str1;

    return 0;
}

            var stopwatch = new Stopwatch();

            stopwatch.Start();
            var stringBuilder = new StringBuilder();

            for (int i = 0; i < 100000000; i++)
            {
                stringBuilder.Append("c1");
            }
            stopwatch.Stop();
            Console.WriteLine("append: elapsed {0}", stopwatch.Elapsed);
            Console.WriteLine(stringBuilder.Length);

            stopwatch.Start();
            stringBuilder.Replace('1', '2');
            stopwatch.Stop();
            Console.WriteLine("replace: elapsed {0}", stopwatch.Elapsed);

            stopwatch.Start();
            for (int ind = 10000; ind < 100000; ind += 1000)
                stringBuilder.Insert(ind, '7');
            stopwatch.Stop();
            Console.WriteLine("insert: elapsed {0}", stopwatch.Elapsed);

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

WH>>>А для массовых вставок есть зипперы. Или можно сразу взять пальчиковое дерево которое по сути хитрая помесь ропы с зиппером.
ГВ>>Это сейчас к делу не относится.
WH>Еще как относится.

Как это? Мы же, вроде, ропы обсуждали. Да ещё и весьма узкие моменты оных.

ГВ>>Кстати, как ты этот узел искать будешь? Либо с узлом должно быть сопоставлено его смещение в строке, либо нужно перебирать все узлы с начала (с самого левого).
WH>А как в бинарных деревьях поиска ищут?

Я первый спросил. И вообще — ты сам сказал, что в узле достаточно хранить только длину его собственной подстроки. Вот теперь и рассказывай, как ты будешь в таком дереве что-то искать.

ГВ>>Оттуда и взял — из твоего высказывания, что в каждом узле лежит длина только его собственной подстроки. Напоминаю, что N — число узлов дерева в данном случае.
WH>Понятно. Как устроены ропы представления не имеешь.

Ясное дело. И что такое деревья, первый раз узнал на RSDN третьего дня.

WH>>>1)К строкам это отношения не имеет.
ГВ>>Имеет самое прямое.
WH>Ну если на все смотреть чисто с точки зрения С/С++ программиста то может и имеет.

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