Здравствуйте, criosray, Вы писали:
C>Аппелировать к этому маразму? Ну давайте, удачи. Только, боюсь, что любой вменяемый программист Вас просто высмеит, если Вы покажете тот пост. Так что на Вашем месте я бы скромно попалкивал, а не орал на всю деревню: я только что обгадился!111аааа
По существу упомянутых мифов тебе, разумеется, сказать нечего. Почему я не удивлён?
Ладно, ладно, я тоже хорошо знаю, что 2x2=5 при очень больших значениях 2.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Serginio1, Вы писали:
S>Если мы хотим иметь поиск по индексу, то нужно иметь дерево
Дерево, естественно, нужно. Но не обязательно 2-3.
S> Для имутабельного обязательно нужно балансированное дерево, т.к. при модификации строки, мы должны скопировать ветку от корня до узла с модифицированной строкой. Балансированное что бы доступ к узлу от корня был Log(N), в том числе и для закладок, содержащий путь до строкию
Если структура нужна нам в первую очередь для конкатенации — балансировать можно редко.
А так да, если у нас 2-3 дерево, то сложность конкатенации будет логарифмом от длинны меньшей строки.
Но непонятно, откуда Геннадий Васильев вывел необходимость или пересоздавать все узлы (это понадобится только если мы не балансировали дерево и всегда добавляли по дному блоку с одной и той же стороны и дерево выродилось в однонаправленный список) или перебирать все узлы при доступе по индексу.
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>Здравствуйте, Serginio1, Вы писали:
S>>Технология сравнительно молодая, но очень бурно развивающаяся. Как тут в одной ветке аж удивиль когда они нововведения вводить успевают. Все идет своим чередом. Правда для кого то медлено, а для кого то и очень быстро.
ГВ>Трудно сказать. Больше похоже на то, что отставание в производительности у C# будет всегда, если не прибегнуть к мерам типа прямой работы с памятью, от чего пытаются шугаться. Ну не бывает чудес, кроме алгоритмической оптимизации.
На данный момент нет особой оптимзации JIT ом, хотя какую то часть кода можно за счет суперкомпиляции в мсил код оптимизировать.
Вторая это NGen оптимизировать уже под процессор, если JIT этим заниматься не хочет. S>>Главное вектор развития выбран верно. А С++ с C# будут ещё долго существовать вместе.
ГВ>"Верно" — это что означает?
Это развитие как манагед сред так и нативных, во многих случаях сближаясь. В многих случаях не нужна супер пупер скорость, нужны удобные средства разработки с минимальным затратами, с приемлемой скоростью работы. Поверь мне 1С ку.
Вот тут насчет веревок диспут шел, да эффективны,можно и другие структуры более эффективные создать, а будут пользоваться стрингбуилдером. Потому, что для большинства задач его хватает за глаза. Процессор в основном то простаивает.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Klapaucius, Вы писали:
K>Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>>Вспомни, чем было спровоцировано моё непонимание. Здесь же все ходы записаны. K>
ГВ>>>Если узлы хранят индексы элементов, и мы вставляем новый узел в начало, то дублировать придётся всё.
WH>>Какие индексы? Зачем все?
K>Как минимум, узлы должны хранить индекс начального элемента собственной подстроки. Могут, конечно, не хранить, но тогда поиск фрагментов очень не кисло усложнится.
K>Ну и чем может быть спровоцировано такое непонимание? Для добавления последовательности в начало нужно заменить 0 узлов. И создать 1 новый узел. Сложность O(1). При этом доступ по индексу будет с логарифмическим.
ГВ>>Как минимум, узлы должны хранить индекс начального элемента собственной подстроки. Могут, конечно, не хранить, но тогда поиск фрагментов очень не кисло усложнится.
WH>Нет. Им достаточно хранить количество символов в собственной подстроке.
ГВ>В прочем, тут есть более оптимальная структура — хранить в узле только длину фрагмента "слева". Так что, на счёт модификации всех элементов дерева при вставке в начало я погорячился (не внимательно прочёл Боэмовскую бумагу).
Я ж говорю, все ходы записаны. Только надо прочитать записанное.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
комментировать собираетесь? Если нужно, могу написать слово "парадигма" в качестве приманки.
Откомментировал. Думал, что ты всё же перечитал дискуссию.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Klapaucius, Вы писали:
K>Но непонятно, откуда Геннадий Васильев вывел необходимость или пересоздавать все узлы (это понадобится только если мы не балансировали дерево и всегда добавляли по дному блоку с одной и той же стороны и дерево выродилось в однонаправленный список) или перебирать все узлы при доступе по индексу.
Это нужно для имутабельной структуры. Ввыделяя новые узлы до модифицированного узла, му оставляем ссылку на "старое" дерево в старом корне, и ссылаясь на новый корень, представляющий собой ссылку на новое дерево, но имеющегл одинаковые ветки со старым. Классика функционального программирования.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>Я ж говорю, все ходы записаны. Только надо прочитать записанное.
Ну так я читал все это — отсюда и ощущение сюрреальности. Ведь вы вроде как обнаружили свою ошибку, а потом спор продолжился.
Расскажите тогда, что вы понимаете под словами "длина собственной подстроки" — наверное все дело в этом.
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Serginio1, Вы писали:
S> Это нужно для имутабельной структуры. Ввыделяя новые узлы до модифицированного узла, му оставляем ссылку на "старое" дерево в старом корне, и ссылаясь на новый корень, представляющий собой ссылку на новое дерево, но имеющегл одинаковые ветки со старым. Классика функционального программирования.
Ну а я о чем? Узлы до модифицированного узла, а не все узлы дерева.
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
K>Ну а я о чем? Узлы до модифицированного узла, а не все узлы дерева.
Все узлы от корня только в вырожденом случае (двухнаправленный список), чего быть не может в сбалансированом дереве.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Klapaucius, Вы писали:
K>Ну так я читал все это — отсюда и ощущение сюрреальности. Ведь вы вроде как обнаружили свою ошибку, а потом спор продолжился. K>Расскажите тогда, что вы понимаете под словами "длина собственной подстроки" — наверное все дело в этом.
А что можно под этим понимать? Это длина только той строки, которая отнесена непосредственно к узлу. Не сумма длин строк, хранящихся в дочерних узлах, плюс собственная строка, а только та, которая сопоставлена с самим узлом.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Serginio1, Вы писали:
S>Все узлы от корня только в вырожденом случае (двухнаправленный список), чего быть не может в сбалансированом дереве.
Именно это я и написал. Только список однонаправленный, а не двунаправленный.
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>А что можно под этим понимать?
Ну я выше написал что я под этим понял.
ГВ>Это длина только той строки, которая отнесена непосредственно к узлу. Не сумма длин строк, хранящихся в дочерних узлах, плюс собственная строка, а только та, которая сопоставлена с самим узлом.
А. Вы имеете в виду длину линейного буфера в листе. Но буфер не сопоставлен с узлом, да и строка в контексте обсуждения — это дерево. Ну а подстрока — поддерево. Строка это абстракция, а дерево реализация.
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Klapaucius, Вы писали:
ГВ>>А что можно под этим понимать? K>Ну я выше написал что я под этим понял.
Меня, кстати, по этому поводу тоже нагнало ощущение сюрреальности. Вроде же термин "собственный" не имеет такого количества разночтений, что сегодня это — собственная подстрока, завтра — сумма подстрок слева, потом — справа, потом все дочерние узлы и т.п.
ГВ>>Это длина только той строки, которая отнесена непосредственно к узлу. Не сумма длин строк, хранящихся в дочерних узлах, плюс собственная строка, а только та, которая сопоставлена с самим узлом.
K>А. Вы имеете в виду длину линейного буфера в листе.
Нет-нет. Если считать, что с каждым узлом дерева сопоставлен некий фрагмент общей строки, то "собственная подстрока" — это только тот фрагмент, который сопоставлен с этим узлом. Буферы тут не при чём.
K>Но буфер не сопоставлен с узлом, да и строка в контексте обсуждения — это дерево. Ну а подстрока — поддерево. Строка это абстракция, а дерево реализация.
То есть каждому символу строки сопоставляется отдельный узел дерева?
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>Меня, кстати, по этому поводу тоже нагнало ощущение сюрреальности. Вроде же термин "собственный" не имеет такого количества разночтений, что сегодня это — собственная подстрока, завтра — сумма подстрок слева, потом — справа, потом все дочерние узлы и т.п.
Семантики заявили, что все зависит от того, как понимать слова
"картофель", "может" и "двигаться". Так как ключом является модальный
глагол "мочь", то его надлежит тщательно исследовать. Затем они
приступили к созданию Энциклопедии Космической Семасиологии, первые
четыре тома которой посвящались модальным значениям глагола "мочь".
K>>А. Вы имеете в виду длину линейного буфера в листе. ГВ>Нет-нет. Если считать, что с каждым узлом дерева сопоставлен некий фрагмент общей строки, то "собственная подстрока" — это только тот фрагмент, который сопоставлен с этим узлом. Буферы тут не при чём.
Узел, он на то и узел, что с ним сопоставлено N подстрок. Так вот, для бинарного дерева достаточно хранить длину левой подстроки. Если вы ее называете собственной подстрокой — тогда мы понимаем под этими словами одно и то же.
ГВ>То есть каждому символу строки сопоставляется отдельный узел дерева?
Сиволы и группы символов — это не узлы, а листья.
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Klapaucius, Вы писали:
K>>>А. Вы имеете в виду длину линейного буфера в листе. ГВ>>Нет-нет. Если считать, что с каждым узлом дерева сопоставлен некий фрагмент общей строки, то "собственная подстрока" — это только тот фрагмент, который сопоставлен с этим узлом. Буферы тут не при чём. K>Узел, он на то и узел, что с ним сопоставлено N подстрок. Так вот, для бинарного дерева достаточно хранить длину левой подстроки. Если вы ее называете собственной подстрокой — тогда мы понимаем под этими словами одно и то же.
Ни в коем случае я этого так не понимаю. Собственная — это собственная. "Слева" — это "слева". Хорош уже передёргивать — если под белым понимать синее, а под синим оранжевое, то и радуги нет.
ГВ>>То есть каждому символу строки сопоставляется отдельный узел дерева? K>Сиволы и группы символов — это не узлы, а листья.
Тоже вариант, не спорю.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Serginio1, Вы писали:
ГВ>>Трудно сказать. Больше похоже на то, что отставание в производительности у C# будет всегда, если не прибегнуть к мерам типа прямой работы с памятью, от чего пытаются шугаться. Ну не бывает чудес, кроме алгоритмической оптимизации.
S> На данный момент нет особой оптимзации JIT ом, хотя какую то часть кода можно за счет суперкомпиляции в мсил код оптимизировать. S>Вторая это NGen оптимизировать уже под процессор, если JIT этим заниматься не хочет.
Так я-то всё это понимаю. Но ты ж послушай наших боевых анти-C++-ников. .Net разве что курицу не жарит за программиста.
S>>>Главное вектор развития выбран верно. А С++ с C# будут ещё долго существовать вместе.
ГВ>>"Верно" — это что означает? S> Это развитие как манагед сред так и нативных, во многих случаях сближаясь. В многих случаях не нужна супер пупер скорость, нужны удобные средства разработки с минимальным затратами, с приемлемой скоростью работы. Поверь мне 1С ку.
Да нет, это всё понятно. Хотя мне кажется, что .Net развивается немного ради других целей. Ну там, у Java кусок отгрызть, индусов привлечь и т.п. Прагматично и объяснимо. Но это "кажется" супротив "кажется" — ни к чему не придём.
S> Вот тут насчет веревок диспут шел, да эффективны,можно и другие структуры более эффективные создать, а будут пользоваться стрингбуилдером. Потому, что для большинства задач его хватает за глаза. Процессор в основном то простаивает.
Вот в том-то и дело, что если процессор простаивает, то без разницы. Но он-то не всегда занят на 5%. Есть и другие задачи, которые не предполагают, что у нас всегда имеется 20-кратный запас производительности. Тут, понимаешь, прикол в другом, в том, что если следовать апологетам... Короче говоря, всё и так понятно.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>Ни в коем случае я этого так не понимаю. Собственная — это собственная. "Слева" — это "слева". Хорош уже передёргивать — если под белым понимать синее, а под синим оранжевое, то и радуги нет.
Ну в каком она еще смысле может быть собственной, при том, что собственные строки есть у всех узлов?
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Klapaucius, Вы писали:
ГВ>>Ни в коем случае я этого так не понимаю. Собственная — это собственная. "Слева" — это "слева". Хорош уже передёргивать — если под белым понимать синее, а под синим оранжевое, то и радуги нет. K>Ну в каком она еще смысле может быть собственной, при том, что собственные строки есть у всех узлов?
[skip the nice picture]
Собственной она может быть только в прямом смысле, то есть принадлежащей только одному узлу, а не как собирательный термин для обозначения всех подстрок его потомков.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
