Здравствуйте, WolfHound, Вы писали:
WF>>А как быть с заменой символа (например, 1000-ый, в строке, созданной конкатенацией пачки других строк)? В этом случае хочется по возможности не создавать лишние объекты, а значит изменяемый кусок не должен разделяться другими строками. WH>А давай ты реалистичную задачу придумаешь где это может понадобиться.
Здравствуйте, WolfHound, Вы писали:
ГВ>>Даже с учётом immutability? WH>Это к чему? WH>Ропы сами неизменяемые.
Добавляем новый узел с конкатенацией — нужно продублировать часть узлов исходного дерева, начиная с корня. Не будь требования immutability — можно было бы просто добавить узел. Это оптимистичный случай. Если узлы хранят индексы элементов, и мы вставляем новый узел в начало, то дублировать придётся всё.
ГВ>>Обход узлов — это уже бесплатно? WH>А зачем нам их обходить?
Например, поиск символа по индексу. Что там у нас со сложностью поиска узла в B+ — дереве?
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, WFrag, Вы писали:
WF>>>А как быть с заменой символа (например, 1000-ый, в строке, созданной конкатенацией пачки других строк)? В этом случае хочется по возможности не создавать лишние объекты, а значит изменяемый кусок не должен разделяться другими строками. WH>>А давай ты реалистичную задачу придумаешь где это может понадобиться. WF>Была как-то задача в тексте case поправить.
Те задача звучала исправить регистр 1000ого символа в тексте?
Интересная задачка.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>Добавляем новый узел с конкатенацией — нужно продублировать часть узлов исходного дерева, начиная с корня. Не будь требования immutability — можно было бы просто добавить узел. Это оптимистичный случай.
Кто на ком стоял? Выражайся яснее.
ГВ>Если узлы хранят индексы элементов, и мы вставляем новый узел в начало, то дублировать придётся всё.
Какие индексы? Зачем все?
ГВ>Например, поиск символа по индексу. Что там у нас со сложностью поиска узла в B+ — дереве?
Log(N) но зачем искать символ по индексу?
У меня почему то таких задач не возникает.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, WFrag, Вы писали:
WF>>И что, даже на коротких строках (очень частый случай) «верёвки» будут эффективнее String/StringBuilder? WH>Они им не уступят.
В случае если веревки это дерево, то мы теряем да чтении DDR памяти непоследовательного участка памяти.
Правда зависит от размера непрерывной памяти
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, WolfHound, Вы писали:
WF>>Была как-то задача в тексте case поправить. WH>Те задача звучала исправить регистр 1000ого символа в тексте? WH>Интересная задачка.
Нет, во всём тексте. Включая и 1000-ый символ. Грубо «абвг, деёжз. ийклмн!» => «Абвг, деёжз. Ийклмн!». Со StringBuilder-ом пробежался — и готово.
Здравствуйте, WolfHound, Вы писали:
ГВ>>Добавляем новый узел с конкатенацией — нужно продублировать часть узлов исходного дерева, начиная с корня. Не будь требования immutability — можно было бы просто добавить узел. Это оптимистичный случай. WH>Кто на ком стоял? Выражайся яснее.
Хорошо, давай по-другому. Добавляем "самый правый" узел в бинарное дерево. Учтём, что у нас где-то есть ссылка на корневой узел этого же дерева, при этом представление дерева, получаемое по этой самой, "старой" ссылке, должно остаться неизменным.
ГВ>>Если узлы хранят индексы элементов, и мы вставляем новый узел в начало, то дублировать придётся всё. WH>Какие индексы? Зачем все?
Как минимум, узлы должны хранить индекс начального элемента собственной подстроки. Могут, конечно, не хранить, но тогда поиск фрагментов очень не кисло усложнится.
ГВ>>Например, поиск символа по индексу. Что там у нас со сложностью поиска узла в B+ — дереве? WH>Log(N) но зачем искать символ по индексу? WH>У меня почему то таких задач не возникает.
Подстроки тоже никогда не выделяешь?
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, WFrag, Вы писали:
WF>Нет, во всём тексте. Включая и 1000-ый символ. Грубо «абвг, деёжз. ийклмн!» => «Абвг, деёжз. Ийклмн!». Со StringBuilder-ом пробежался — и готово.
Если по русски: сделать заглавной каждую первую букву предложения.
Ну тогда механика типа http://www.inf.puc-rio.br/~roberto/lpeg/re.html с этим прекрасно справится.
Причем оно будет изначально заточено на работу с конкретной реализацией строки.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Serginio1, Вы писали:
S> В случае если веревки это дерево, то мы теряем да чтении DDR памяти непоследовательного участка памяти. S>Правда зависит от размера непрерывной памяти
Это все шито по вроде белыми вилами.
Реально я приводил ссылку где ропы рвали на кровавые ошметки и String и StringBuilder.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
ГВ>Как минимум, узлы должны хранить индекс начального элемента собственной подстроки. Могут, конечно, не хранить, но тогда поиск фрагментов очень не кисло усложнится.
В прочем, тут есть более оптимальная структура — хранить в узле только длину фрагмента "слева". Так что, на счёт модификации всех элементов дерева при вставке в начало я погорячился (не внимательно прочёл Боэмовскую бумагу).
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>Хорошо, давай по-другому. Добавляем "самый правый" узел в бинарное дерево. Учтём, что у нас где-то есть ссылка на корневой узел этого же дерева, при этом представление дерева, получаемое по этой самой, "старой" ссылке, должно остаться неизменным.
Ну и? Создаем Log(N) новых узлов и все.
При конкатенации особенно если глубина деревьев сравнима и того меньше.
А есть еще finger tree. Там все еще интересней.
ГВ>Как минимум, узлы должны хранить индекс начального элемента собственной подстроки. Могут, конечно, не хранить, но тогда поиск фрагментов очень не кисло усложнится.
Нет. Им достаточно хранить количество символов в собственной подстроке.
ГВ>Подстроки тоже никогда не выделяешь?
А вот на этой задачке ропы порвут всех на мелкие кровавые ошметки.
Более жестокий разрыв на куски будет только при конкатенации.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
ГВ>>Хорошо, давай по-другому. Добавляем "самый правый" узел в бинарное дерево. Учтём, что у нас где-то есть ссылка на корневой узел этого же дерева, при этом представление дерева, получаемое по этой самой, "старой" ссылке, должно остаться неизменным. WH>Ну и? Создаем Log(N) новых узлов и все. WH>При конкатенации особенно если глубина деревьев сравнима и того меньше. WH>А есть еще finger tree. Там все еще интересней.
Так собственно, речь-то о чём была? О том, что дублирование узлов при соблюдении требования immutability неизбежно.
ГВ>>Как минимум, узлы должны хранить индекс начального элемента собственной подстроки. Могут, конечно, не хранить, но тогда поиск фрагментов очень не кисло усложнится. WH>Нет. Им достаточно хранить количество символов в собственной подстроке.
Нет, этого мало.
ГВ>>Подстроки тоже никогда не выделяешь? WH>А вот на этой задачке ропы порвут всех на мелкие кровавые ошметки. WH>Более жестокий разрыв на куски будет только при конкатенации.
Ты говорил, что где-то давал ссылку? Можно повторить?
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>Так собственно, речь-то о чём была? О том, что дублирование узлов при соблюдении требования immutability неизбежно.
И в чем проблема?
Ибо даже с учетом этого все работает быстрее.
WH>>Нет. Им достаточно хранить количество символов в собственной подстроке. ГВ>Нет, этого мало.
Для чего конкретно этого не хватает?
ГВ>Ты говорил, что где-то давал ссылку? Можно повторить? http://www.ibm.com/developerworks/java/library/j-ropes/index.html
Там есть места где ропы тормознее но это исключительно из-за ущербности самой жабы.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, Serginio1, Вы писали:
S>> В случае если веревки это дерево, то мы теряем да чтении DDR памяти непоследовательного участка памяти. S>>Правда зависит от размера непрерывной памяти WH>Это все шито по вроде белыми вилами. WH>Реально я приводил ссылку где ропы рвали на кровавые ошметки и String и StringBuilder.
За счет чего можно рвать непрерывную неизменяемую память?
Что касается изменяемой то очень сильно зависит как от размера так и действий.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, WolfHound, Вы писали:
ГВ>>Так собственно, речь-то о чём была? О том, что дублирование узлов при соблюдении требования immutability неизбежно. WH>И в чем проблема? WH>Ибо даже с учетом этого все работает быстрее.
Просто такой подход сработает только на длинных строках и только для модификаций. На коротких дешевле будет обычный буфер (в который, в общем-то и должен бы превратиться rope). Ну и иммутабельность должна ещё повлиять: модификации иммутабельного rope будут, конечно, быстрее, чем модификации длинных иммутабельных буферов, но прилично медленнее, чем мутабельных rope-ов.
WH>>>Нет. Им достаточно хранить количество символов в собственной подстроке. ГВ>>Нет, этого мало. WH>Для чего конкретно этого не хватает?
Для доступа по индексу, очевидно. rope тут всегда проиграет буферу, опять таки, за исключением коротких строк или случая с небольшой глубиной дерева — здесь они будут практически равны.
P.S.: Ссылку посмотрел, спасибо. Причины заморочек, ИМХО, понятны — похоже, как раз из-за индексного доступа или требования преобразования к линейному буферу.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, WolfHound, Вы писали:
ГВ>>Вот-вот. Возвращаемся к тому, с чего начали: к внутренней структуре строки. WH>И как грамотная реализация строки относится к тому что строк должно быть много?
Нуу... Для редактора текстов представление строк (буфферов) будет отличаться от обычных коротких строк.
Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>Просто такой подход сработает только на длинных строках и только для модификаций. На коротких дешевле будет обычный буфер (в который, в общем-то и должен бы превратиться rope). Ну и иммутабельность должна ещё повлиять: модификации иммутабельного rope будут, конечно, быстрее, чем модификации длинных иммутабельных буферов, но прилично медленнее, чем мутабельных rope-ов.
С какой стати?
Создание узлов операция очень дешевая.
WH>>>>Нет. Им достаточно хранить количество символов в собственной подстроке. ГВ>>>Нет, этого мало. WH>>Для чего конкретно этого не хватает? ГВ>Для доступа по индексу, очевидно.
Те по твоему нельзя реализовать доступ по индексу если каждый узел знает только размер своей подстроки?
Я правильно тебя понял?
ГВ>rope тут всегда проиграет буферу, опять таки, за исключением коротких строк или случая с небольшой глубиной дерева — здесь они будут практически равны.
Опять таки зачем конкретно нужен доступ по индексу к одиночному элементу?
ГВ>P.S.: Ссылку посмотрел, спасибо. Причины заморочек, ИМХО, понятны — похоже, как раз из-за индексного доступа или требования преобразования к линейному буферу.
Нет.
Там заморочки из серии:
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.
.NET 2.0 и старше конкретно этой заморочкой не страдает.
Хотя и он весьма ущербен.
Короче тут нужно делать нормальную ВМ с нормальным оптимизатором.
Тогда ропы или пальчиковые деревья (надо смотреть что лучше) будут рулить со страшной силой.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Serginio1, Вы писали:
S> За счет чего можно рвать непрерывную неизменяемую память? S>Что касается изменяемой то очень сильно зависит как от размера так и действий.
RTFM
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Cyberax, Вы писали:
C>Нуу... Для редактора текстов представление строк (буфферов) будет отличаться от обычных коротких строк.
И чем конкретно ропы не подходят для редактора текста?
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
C>>Нуу... Для редактора текстов представление строк (буфферов) будет отличаться от обычных коротких строк. WH>И чем конкретно ропы не подходят для редактора текста?
Для редактора текстов заметно лучше подходят строки с gap-буффером.
Не будь требования immutability — можно было бы просто добавить узел. Это оптимистичный случай. Если узлы хранят индексы элементов, и мы вставляем новый узел в начало, то дублировать придётся всё.
