2 criosray: Толку-то в СВ баллы ставить? Если вам этот код по какой-то причине понравится — можете поставить где-нибудь в профильном баллы пользователю Alexey Romanov. Это его проект.
... << 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>2 criosray: Толку-то в СВ баллы ставить? Если вам этот код по какой-то причине понравится — можете поставить где-нибудь в профильном баллы пользователю Alexey Romanov. Это его проект.
Баллы за ссылку, т.к. упорно гуглил, но так и не нашел.
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, Serginio1, Вы писали:
S>>На дефрагментацию кучи время уходит? И это может происходить достаточно часто. Все зависит от емкости, и скорости изменения дерева. WH>Чё? Дефрагментация кучи происходит во время сборки мусора. WH>Причем я тут можно очень серьезно срезать углы по сравнения с изменяемой кучей.
По сравнению с изменяемой кучей, одноразмерных объектов, может даже и сливать. WH>>>2-3 дерево. Частный случай B дерева. Еще вопросы? S>> Прибавляй затраты на балансировку. WH>Какую балансировку? WH>B дерево строится сбалансированным сразу. WH>Ты вообще представляешь как работают B деревья?
Знаю. http://rsdn.ru/article/alg/tlsd.xml
. Я имел ввиду затраты на новые узлы.
Если ссылки на строки лежат в листьях тому, что объект занимает 12 бай + лево + право + сумма итого 28 байт на объект
Плюс листья по 3 ссылки на строки итого 12 байт. При частой сборке мусора они будут вносить свою лепту в фрагмнтацию кучи старших поколений.
Мало того, что ты получаешь дефрагментацию в 0 поколении, так еще получишь и в старших поколениях.
При слиянии строк данные как правило сидят в кэше, так то на копирование другие трудозатраты. S>> Я к тому, что много дополнительных затрат, которые по уму нужно учитывать, при выборе типа инструмента. WH>Каких?
На дефрагментацию старших поколений. Плюс при сканировании строки скачки по уровням, и тормоза к памяти вне кэша, по сравненю с прогоном по непрерывной памяти.
Мало того, в большинсве случаем строки выделяются сразу, не подвергаются изменениям в течении всей своей жизни.
Во всяком случае на 64 элементах Б+ деревьях это заметно. S>>Поэтому и убежден, что 3 на бора строк это лучше чем 1 универсальный, WH>Хуже. Причем сильно хуже.
Ну Б+ деревьев до сих пор в стандартной библиотеке нет, а SortedList сливает также как и стрингБуилдеру веревкам.
Посмотрим когда их в библиотеку. Затраты по сравнению с обычными строками я приводил.
S>>но с реализацией одинаковых интерфейсов. WH>Одинаковые интерфейсы у изменяемых и неизменяемых структур данных просто сюр.
Ну не совсем. Я имел ввиду имутабельные строки один интерфейс для мутабельных другой, но если для первых это функции то для вторых это процедуры.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, criosray, Вы писали:
C>C++ 858 ms C>C# 823 ms
Это называется "равны с точностью до погрешности измерения".
C>Про сложность кода и явную костыльность С++ (обратите внимание как пришлось извратиться, чтоб сконвертировать число в wstring там, где StringBuilder делает конвертацию сам и не парит нам мозги) и говорить не стоит — вся красота перед глазами.
Мне из моего колодца трудно судить о недостаточной эстетике, я, так сказать, привык по-простому, "от сохи":
ws += L"Карл у Клары украл кораллы в количестве ";
ws += _itow(i,buffer,10);
ws += L" штук\n";
И не надо никаких append и преобразований из MBCS.
C>Но самое замечательное, что С++ вариант банально крашился, если Count = 10000 (и возможно меньше... не проверял между 5к и 10к).
У меня было всё ровно наоборот: C++ вариант попыхтел на пару с виндой, но таки 10K строк отработал, тогда как C# пыхтел столько же, а потом сказал OutOfMemoryException.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Klapaucius, Вы писали:
K>Здравствуйте, Serginio1, Вы писали:
K>>>Это для вставки. А не для добавления к началу/концу т.е. конкатенации. S>>Может я чего то не понимаю — В чем разница? Так структура мутабельна мы должны выделить новыю ссылку на корень,и от него добраться либо в конец либо в начало, S>>выделяя новую ветку, с модификациу длины?
K>1) Для конкатенации не нужно добираться в конец или в начало. K>2) Быстрый доступ к концу и началу можно организовать с помощью двух "пальцев" указывающих на самый левый и самый правый узлы (удерживать их всегда в первом уровне дерева). Но для конкатенации это не нужно, это нужно если мы хотим чтобы строки у нас были деком с константным доступом.
эээ WolfHound утверждает что веревки это 2-3 дерево. Так что вставка не зависит от того в какое место вставляется, это не очередь.
S>>По уму нужно еще сложность балансировки добавлять, т.к. деревья могут вырождаться в двухнапрвленный список.
K>Это все учтено. Сложность вставки О(1) — амортизированная.
Наверное я чего то не пониаю. Ну да ладно
и солнце б утром не вставало, когда бы не было меня
C>>C++ 858 ms C>>C# 823 ms
ГВ>Это называется "равны с точностью до погрешности измерения".
Конечно. Но вот чисто append сливает в три раза, а чисто replace так вообще в десятки раз (по крайней мере наколенковая реализация на базе wstring.find/wstring.replace.
C>>Про сложность кода и явную костыльность С++ (обратите внимание как пришлось извратиться, чтоб сконвертировать число в wstring там, где StringBuilder делает конвертацию сам и не парит нам мозги) и говорить не стоит — вся красота перед глазами.
ГВ>Мне из моего колодца трудно судить о недостаточной эстетике, я, так сказать, привык по-простому, "от сохи": ГВ>
ГВ>ws += L"Карл у Клары украл кораллы в количестве ";
ГВ>ws += _itow(i,buffer,10);
ГВ>ws += L" штук\n";
ГВ>
ГВ>И не надо никаких append и преобразований из MBCS.
Принято.
C>>Но самое замечательное, что С++ вариант банально крашился, если Count = 10000 (и возможно меньше... не проверял между 5к и 10к).
ГВ>У меня было всё ровно наоборот: C++ вариант попыхтел на пару с виндой, но таки 10K строк отработал, тогда как C# пыхтел столько же, а потом сказал OutOfMemoryException.
У меня дотнет вариант отработал за примерно 4 секунды, С++ тут же крашнулся без вменяемого сообщения о роде проблемы.
Здравствуйте, criosray, Вы писали:
C>>>C++ 858 ms C>>>C# 823 ms
ГВ>>Это называется "равны с точностью до погрешности измерения".
C>Конечно. Но вот чисто append сливает в три раза, а чисто replace так вообще в десятки раз (по крайней мере наколенковая реализация на базе wstring.find/wstring.replace.
Тут на самом деле не надо путать StringBuilder, специально заточенный на модификации, и std::wstring, которая, по сути, своего рода компромисс между хранилищем строки (добавь требование преобразования к zero-terminated) и StringBuilder. Забавляет другое — что некоторый выигрыш Append/Replace нивелируется медленным ToString.
C>>>Но самое замечательное, что С++ вариант банально крашился, если Count = 10000 (и возможно меньше... не проверял между 5к и 10к). ГВ>>У меня было всё ровно наоборот: C++ вариант попыхтел на пару с виндой, но таки 10K строк отработал, тогда как C# пыхтел столько же, а потом сказал OutOfMemoryException. C>У меня дотнет вариант отработал за примерно 4 секунды, С++ тут же крашнулся без вменяемого сообщения о роде проблемы.
На 10000 строк 4 секунды? Интересно.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
C>>>>C++ 858 ms C>>>>C# 823 ms
ГВ>>>Это называется "равны с точностью до погрешности измерения".
C>>Конечно. Но вот чисто append сливает в три раза, а чисто replace так вообще в десятки раз (по крайней мере наколенковая реализация на базе wstring.find/wstring.replace.
ГВ>Тут на самом деле не надо путать StringBuilder, специально заточенный на модификации, и std::wstring, которая, по сути, своего рода компромисс между хранилищем строки (добавь требование преобразования к zero-terminated) и StringBuilder.
О том и речь. Потому я и утверждал, что разделение на immutable класс строк и mutable класс аккумулятор строк позволяют достич значительно большей эфективности.
ГВ>Забавляет другое — что некоторый выигрыш Append/Replace нивелируется медленным ToString.
Обычно ToString вызывается гораздо реже Append`ов и крайне редко, чтоб он вызывался в цикле, как было предложено.
C>>>>Но самое замечательное, что С++ вариант банально крашился, если Count = 10000 (и возможно меньше... не проверял между 5к и 10к). ГВ>>>У меня было всё ровно наоборот: C++ вариант попыхтел на пару с виндой, но таки 10K строк отработал, тогда как C# пыхтел столько же, а потом сказал OutOfMemoryException. C>>У меня дотнет вариант отработал за примерно 4 секунды, С++ тут же крашнулся без вменяемого сообщения о роде проблемы.
ГВ>На 10000 строк 4 секунды? Интересно.
Да чуть меньше 4х. На 5000 меньше секунды. С2D 3Ghz, 6GB RAM, Win7 64bit.
Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>>>Это называется "равны с точностью до погрешности измерения".
C>>Конечно. Но вот чисто append сливает в три раза, а чисто replace так вообще в десятки раз (по крайней мере наколенковая реализация на базе wstring.find/wstring.replace.
ГВ>Тут на самом деле не надо путать StringBuilder, специально заточенный на модификации, и std::wstring, которая, по сути, своего рода компромисс между хранилищем строки (добавь требование преобразования к zero-terminated) и StringBuilder. Забавляет другое — что некоторый выигрыш Append/Replace нивелируется медленным ToString.
Не флейма ради В Delphi самые православные (и даже zero-terminated совместимые) строки По первому тесту результаты такие (только я количество итераций уменьшил на один нолик, а то у меня памяти не хватает ):
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, Геннадий Васильев, Вы писали:
S>почувсвуйте разницу на коротких строках. Поэтому и пишут свои стрингбуилдеры S>
H>Delphi 2009 (миллисекунды): H>----------- RTL строки H>string.append: elapsed 697 (20000000) H>string.replace: elapsed 0 (20000000) // нет замены в строке, только с созданием копии -- мерять не стал H>string.insert: elapsed 5880 (20000090) H>----------- с использование класса TStringBuilder H>sb.append: elapsed 1063 (20000000) H>sb.replace: elapsed 65 (20000000)
Попробуйте Replace('1','2') заменить на Replace('c1', 'abc4') Будет куда интереснее, чем замена одного символа.
Извини, я не совсем понял — к чему ты это? Сам код понятен, не могу понять твою мысль.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, criosray, Вы писали:
ГВ>>>>Это называется "равны с точностью до погрешности измерения". C>>>Конечно. Но вот чисто append сливает в три раза, а чисто replace так вообще в десятки раз (по крайней мере наколенковая реализация на базе wstring.find/wstring.replace. ГВ>>Тут на самом деле не надо путать StringBuilder, специально заточенный на модификации, и std::wstring, которая, по сути, своего рода компромисс между хранилищем строки (добавь требование преобразования к zero-terminated) и StringBuilder. C>О том и речь. Потому я и утверждал, что разделение на immutable класс строк и mutable класс аккумулятор строк позволяют достич значительно большей эфективности.
Нет, с иммутабельностью это не связано. Здесь главное то, что StringBuilder специально затачивался на модификацию строк, а std::wstring — это так, гора компромиссов между ужами и ежами.
ГВ>>Забавляет другое — что некоторый выигрыш Append/Replace нивелируется медленным ToString. C>Обычно ToString вызывается гораздо реже Append`ов и крайне редко, чтоб он вызывался в цикле, как было предложено.
Цикл нужен только для того, чтобы время операции точней померить.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
ГВ>>>>>Это называется "равны с точностью до погрешности измерения". C>>>>Конечно. Но вот чисто append сливает в три раза, а чисто replace так вообще в десятки раз (по крайней мере наколенковая реализация на базе wstring.find/wstring.replace. ГВ>>>Тут на самом деле не надо путать StringBuilder, специально заточенный на модификации, и std::wstring, которая, по сути, своего рода компромисс между хранилищем строки (добавь требование преобразования к zero-terminated) и StringBuilder. C>>О том и речь. Потому я и утверждал, что разделение на immutable класс строк и mutable класс аккумулятор строк позволяют достич значительно большей эфективности.
ГВ>Нет, с иммутабельностью это не связано. Здесь главное то, что StringBuilder специально затачивался на модификацию строк, а std::wstring — это так, гора компромиссов между ужами и ежами.
Вот именно. Именно такое разделение позволило сделать класс string immutable, а StringBuilder — более эфективным (по производительности, менее эфективным по памяти, очевидно) для операций над строками.
ГВ>>>Забавляет другое — что некоторый выигрыш Append/Replace нивелируется медленным ToString. C>>Обычно ToString вызывается гораздо реже Append`ов и крайне редко, чтоб он вызывался в цикле, как было предложено. ГВ>Цикл нужен только для того, чтобы время операции точней померить.
Так что Вы меряете? Append или ToString? Ведь ToString`ов ровно столько же, сколько и Append`ов, что почти что нонсенс.
Здравствуйте, criosray, Вы писали:
H>>Delphi 2009 (миллисекунды): H>>----------- RTL строки H>>string.append: elapsed 697 (20000000) H>>string.replace: elapsed 0 (20000000) // нет замены в строке, только с созданием копии -- мерять не стал H>>string.insert: elapsed 5880 (20000090) H>>----------- с использование класса TStringBuilder H>>sb.append: elapsed 1063 (20000000) H>>sb.replace: elapsed 65 (20000000)
C>Попробуйте Replace('1','2') заменить на Replace('c1', 'abc4') Будет куда интереснее, чем замена одного символа.
Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>Здравствуйте, Serginio1, Вы писали:
ГВ>Извини, я не совсем понял — к чему ты это? Сам код понятен, не могу понять твою мысль.
В тормознутости StringBuilder a
и солнце б утром не вставало, когда бы не было меня
Я все к чему клоню то. Что если сделать мутабельную структуру,
наподобие Б+ на листовом уровне, и ветки ссумой символов в пддереве как 2-3 дерево, то можно получить
очень быструю структуру. Так в моих Б+ дереве на листовом уровне 64 элемента кей валуе, что для int*int дает отличную скорость,
то для чаров это будет 256. Если вставки и удаления будут такого же порядка, то вполне быстря структура.
Надо будет попробовать на досуге.
и солнце б утром не вставало, когда бы не было меня