Здравствуйте, Cyberax, Вы писали:
C>Для редактора текстов заметно лучше подходят строки с gap-буффером.
1)Советую ознакомиться с паттерном zipper.
2)А если рассматривать задачу в комплексе те вспомнить про undo/redo то кто кого порвет мы еще посмотрим...
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
ГВ>>Просто такой подход сработает только на длинных строках и только для модификаций. На коротких дешевле будет обычный буфер (в который, в общем-то и должен бы превратиться rope). Ну и иммутабельность должна ещё повлиять: модификации иммутабельного rope будут, конечно, быстрее, чем модификации длинных иммутабельных буферов, но прилично медленнее, чем мутабельных rope-ов. WH>С какой стати? WH>Создание узлов операция очень дешевая.
Это ты из принципа? Очень дешёвая — но всё равно же не нуль.
WH>>>>>Нет. Им достаточно хранить количество символов в собственной подстроке. ГВ>>>>Нет, этого мало. WH>>>Для чего конкретно этого не хватает? ГВ>>Для доступа по индексу, очевидно. WH>Те по твоему нельзя реализовать доступ по индексу если каждый узел знает только размер своей подстроки? WH>Я правильно тебя понял?
Нет, не правильно ты меня понял. Реализовать-то можно, только потери по скорости будут.
ГВ>>rope тут всегда проиграет буферу, опять таки, за исключением коротких строк или случая с небольшой глубиной дерева — здесь они будут практически равны. WH>Опять таки зачем конкретно нужен доступ по индексу к одиночному элементу?
Есть, например, EDI-протоколы, формат сообщений которых предполагает фиксированные позиции элементов.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, WolfHound, Вы писали:
ГВ>>P.S.: Ссылку посмотрел, спасибо. Причины заморочек, ИМХО, понятны — похоже, как раз из-за индексного доступа или требования преобразования к линейному буферу. WH>Нет. WH>Там заморочки из серии: WH>
WH>Astute readers might wonder why charAt is more than seven times faster than the iterator, given that both provide O(1) access time. This difference is due to the fact that in the Java language, Iterators must return Objects. Although the charAt implementation directly returns char primitives, the iterator implementation must box each char into a Character object. Auto-boxing might sooth the syntactic pain of primitive boxing, but it can't eliminate the performance penalties.
Ну боксинг, так боксинг.
WH>.NET 2.0 и старше конкретно этой заморочкой не страдает. WH>Хотя и он весьма ущербен.
И .Net ущербен, и Java — не язык, и C++ — убожество. Инверсный Блаб-парадокс в действии.
WH>Короче тут нужно делать нормальную ВМ с нормальным оптимизатором.
Понеслась коза по рельсам...
WH>Тогда ропы или пальчиковые деревья (надо смотреть что лучше) будут рулить со страшной силой.
Ну "нормальная ВМ" с "нормальным оптимизатором" вообще будет рулить не по-детски и анализировать граф исполнения сможет с учётом всех возможных данных за время, стремящееся к нулю, кто ж спорит?!
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Sinclair, Вы писали:
WF>>В терминах O-большого или с учётом константы? S>По идее — без. Короткие rope выродятся в полный аналог String.
Да, но Wolfhound предлагает устранить и StringBuilder.
Мне непонятно, как тогда rope получится эффективно удовлетворить оба пункта:
1) Иммутабельные строки, конкатенация длинных строк <-- вот тут rope замечательно подходят (опуская проблемы отдельно взятых VM)
2) Эффективная конкатенация мелочёвки (скажем, по нескольку символов). <-- А тут как быть? Создавать новые листья или узлы деревьев? Как-то неэффективно.
Здравствуйте, WFrag, Вы писали:
WF>1) Иммутабельные строки, конкатенация длинных строк <-- вот тут rope замечательно подходят (опуская проблемы отдельно взятых VM) WF>2) Эффективная конкатенация мелочёвки (скажем, по нескольку символов). <-- А тут как быть? Создавать новые листья или узлы деревьев? Как-то неэффективно.
Не вижу, почему бы это было неэффективно.
В случае
всё будет работать как минимум не хуже, чем со StringBuilder:
1. Буфер под узел выделен с запасом; поэтому можно дописывать ему в конец символы, не разрушая предыдущие значения rope.
2. Когда кончится буфер, создадим новый узел. Это недорого.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
S>всё будет работать как минимум не хуже, чем со StringBuilder: S>1. Буфер под узел выделен с запасом; поэтому можно дописывать ему в конец символы, не разрушая предыдущие значения rope. S>2. Когда кончится буфер, создадим новый узел. Это недорого.
А как же иммутабельность? Получается, либо мы создаём новый объект кадый раз (например, rope, который указывает на то же дерево данных, НО имеет длину + 1), либо мы меняем существующий объект. Но у нас нет разделения неизменямый/изменяемый (String/StringBuilder), состояние какого объекта мы будем менять?
Здравствуйте, WFrag, Вы писали:
WF>А как же иммутабельность? Получается, либо мы создаём новый объект кадый раз (например, rope, который указывает на то же дерево данных, НО имеет длину + 1), либо мы меняем существующий объект. Но у нас нет разделения неизменямый/изменяемый (String/StringBuilder), состояние какого объекта мы будем менять?
А в чём проблема? Ну создали мы новый rope; он показывает на дерево данных, построенное на тех же буферах, что и предыдущий rope.
Представь, что ты решаешь обратную задачу:
rope1 = rope0.Left(rope0.Length-1);
Ведь понятно же, почему при этой операции не нужно никаких копирований буферов? Ну вот конкатенация делает то же самое, только наоборот.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>А в чём проблема? Ну создали мы новый rope; он показывает на дерево данных, построенное на тех же буферах, что и предыдущий rope. S>Представь, что ты решаешь обратную задачу: S>
S>rope1 = rope0.Left(rope0.Length-1);
S>
S>Ведь понятно же, почему при этой операции не нужно никаких копирований буферов? Ну вот конкатенация делает то же самое, только наоборот.
Да, но тут нужно создавать новый экземпляр rope (а это память). Добавляя 10 раз по одному символу создадутся 10 экземпляров rope (пусть даже и разделяющих общий буффер с данными). А в случае «классического» StringBuilder-а ничего создавать не нужно (пока хватает capacity буффера) — увеличиваем длину и меняем элементы массива.
Если бы речь шла просто о замене внутренней структуры String и StringBuilder-а с массива на rope (с тем отличием, что StringBuilder может менять своё состояние), то я бы согласился — никаких проблем, можно сделать не хуже обычных String/StringBuilder на массивах. Но, насколько я понял, речь-то идёт о том, что оставить один контракт, иммутабельный String.
Здравствуйте, WFrag, Вы писали:
WF>Да, но тут нужно создавать новый экземпляр rope (а это память).
Э-э, как только память станет проблемой, её уберёт GC.
С System.String корень неэффективности именно в копировании буферов, т.е. стоимость любой операции в O(N). В rope это будет O(Log(N)), стремящийся к O(1) в простых случаях.
WF>Если бы речь шла просто о замене внутренней структуры String и StringBuilder-а с массива на rope (с тем отличием, что StringBuilder может менять своё состояние), то я бы согласился — никаких проблем, можно сделать не хуже обычных String/StringBuilder на массивах. Но, насколько я понял, речь-то идёт о том, что оставить один контракт, иммутабельный String.
Тут нужно много чего мерить, и следить за поведением VM. Я так понял, что не всякая VM даст реализовать rope с такой эффективностью, чтобы забить StringBuilder на всех сценариях.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
WF> Если бы речь шла просто о замене внутренней структуры String и StringBuilder-а с массива на rope (с тем отличием, что StringBuilder может менять своё состояние), то я бы согласился — никаких проблем, можно сделать не хуже обычных String/StringBuilder на массивах. Но, насколько я понял, речь-то идёт о том, что оставить один контракт, иммутабельный String.
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, WFrag, Вы писали:
WF>>Да, но тут нужно создавать новый экземпляр rope (а это память). S>Э-э, как только память станет проблемой, её уберёт GC. S>С System.String корень неэффективности именно в копировании буферов, т.е. стоимость любой операции в O(N). В rope это будет O(Log(N)), стремящийся к O(1) в простых случаях.
При этом пробег по непрерывной памяти значительно эффективней. Затраты одного создания может быть значительно меньше, затрат на прыжки по узлам.
Плюс GC так или иначе будет дефрагментировать память вместе со строками вкучу, и эффект не копирования буферов сведется если не на нет, то значительно.
Сильно зависит от отношения поиска по строке, и изменением размера строки.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, CreatorCray, Вы писали: S>>>Thread_safe_string крайне труден в написании. CC>>Да ну??? Неужто написать COW строку на refcounterах так сложно? S>И она будет прямо таки вся thread safe?
Будет.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Здравствуйте, WolfHound, Вы писали:
CC>>Да ну??? Неужто написать COW строку на refcounterах так сложно? WH>Чтобы она еще и работала быстро на многопроцессорной тачке очень сложно.
Не очень. Никто в здравом уме не станет делать полную копию интерфейса мутабельной строки.
По сути по использованию (интерфейсу) thread_safe_string получится почти такая же immutable string как и в шарпе. Некоторые фичи mutable строк (напр. неконстантный operator[] и т.п.) будут разумеется отрезаны.
Ну и GC будет заменен refcounter-ами на буфер строки.
WH>Ибо даже InterlockedIncrement/InterlockedDecrement весьма не бесплатны на многопроцессорных машинах.
Не бесплатны, но и не экстра-дороги.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>char szString[N]; PD>>gets(szString); PD>>strupr(szString);
PD>>и ни одного лишнего байта. Можно такое сделать ? WH>Что сделать? WH>Проезд по памяти?
Угу. С преобразованием к верхнему регистру для каждого проезжаемого символа.
WH>Конечно нет.
Напугали ежа
В большинстве случаев это не нужно (потому что шаблоны используют утиную типизацию), а если понадобилось все-таки это использовать, то достаточно просто повесить ассерт на is_base_of (в числе прочих ассертов, кстати — мало ли что тебе понадобится, ко/контравариантностью дело не исчерпывается обычно, простейший пример — контейнер).
Шаблонов у вас нету в шарпе нормальных, вот и приходится извращаться.
Здравствуйте, WolfHound, Вы писали:
C>>Для редактора текстов заметно лучше подходят строки с gap-буффером. WH>1)Советую ознакомиться с паттерном zipper.
Ознакомился.
WH>2)А если рассматривать задачу в комплексе те вспомнить про undo/redo то кто кого порвет мы еще посмотрим...
А что с ними не так у gap buffers?
Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>Это ты из принципа? Очень дешёвая — но всё равно же не нуль.
А модификация типа нуль?
ГВ>Нет, не правильно ты меня понял. Реализовать-то можно, только потери по скорости будут.
С какой стати?
Решение в каждом узле принимается за O(1) с весьма маленьким О.
ГВ>Есть, например, EDI-протоколы, формат сообщений которых предполагает фиксированные позиции элементов.
Дай ссылку на толковое описание. А то я что-то один маркетинговый булщит нахожу.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, CreatorCray, Вы писали:
CC>Не очень. Никто в здравом уме не станет делать полную копию интерфейса мутабельной строки.
И не надо. Счетчика ссылок достаточно.
CC>Ну и GC будет заменен refcounter-ами на буфер строки.
Во-во...
WH>>Ибо даже InterlockedIncrement/InterlockedDecrement весьма не бесплатны на многопроцессорных машинах. CC>Не бесплатны, но и не экстра-дороги.
Достаточно дороги чтобы в большинстве случаев было выгоднее копирование, а не счетчик ссылок.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Cyberax, Вы писали:
WH>>1)Советую ознакомиться с паттерном zipper. C>Ознакомился.
Значит теперь ты сможешь осознать что гапнуть ропу зиппером ни разу не проблема.
WH>>2)А если рассматривать задачу в комплексе те вспомнить про undo/redo то кто кого порвет мы еще посмотрим... C>А что с ними не так у gap buffers?
А то что их нужно делать.
Нужно придумать структуры данных.
Реализовать без ошибок.
Поддерживать их в актуальном состоянии.
...
А в случае с rope у нас все получается бесплатно.
Все что нужно это добавить 2 односвязных списка.
Один для undo второй для redo.
А односвязные списки как ты понимаешь в любом функциональном языке буквально везде.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
