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

ГВ>>Мы же, вроде, ропы обсуждали. Да ещё и весьма узкие моменты оных.
K>Ну так зиппер имеет точно такое же отношение к деревьям (и, следовательно ропам), какое gap имеет к массивам.
K>Или о нем говорить нельзя потому, что это реальное решение проблемы?

Да нет, это чтобы не распыляться.

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

K>Детский сад — штаны на лямках.

K>дерево:
K>root(N1_6)
K>N1 = 6
K>N2 = 2

Что означают 2 и 6? Длины собственных подстрок узлов? Индексы? Суммарные длины всех подстрок каждого узла?

K>l(N1) -> N2
K>r(N1) -> L3_4
K>l(N2) -> L1_2
K>r(N2) -> L2_4

K>доступ к элементу номер 4:
K>Стоим на N1.
K>4 < 6 -> переходим на N2
K>4 > 2 -> 4-2 = 2 -> переходим на L2
K>Возвращаем второй элемент L2

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

K>>Ну так зиппер имеет точно такое же отношение к деревьям (и, следовательно ропам), какое gap имеет к массивам.
K>>Или о нем говорить нельзя потому, что это реальное решение проблемы?
ГВ>Да нет, это чтобы не распыляться.

Озвучена проблема. В ответ представлено решение. Это теперь распылением называется? Кака раз редкий для этого форума случай ответа по теме обсуждения.

ГВ>Что означают 2 и 6? Длины собственных подстрок узлов? Индексы? Суммарные длины всех подстрок каждого узла?

Это суммарные длины всех подстрок слева.

Это всё — для 32-битной конфигурации. Попозже проверю на 64-битной.

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

ГВ>>Что означают 2 и 6? Длины собственных подстрок узлов? Индексы? Суммарные длины всех подстрок каждого узла?
K>Это суммарные длины всех подстрок слева.

А теперь перечитай внимательно мою с WolfHound дискуссию. WolfHound утверждал, что достаточно положить в узлы длины собственных подстрок.

Здравствуйте, alexey_ma, Вы писали:
_>Зачем? Подобный код в плюсах не имеет смысла.
_>Получится что-то вроде :
_>

_>    int a = 0;
_>    int c = 10;
_>    int b = 0;
_>    (*(&b)) = ( &a == NULL ? *(&a) : c) / 100;
_>

Это не эквивалентный код.

Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Хм... Что такое ссылки наружу — я не знаю, а вот про блоки памяти вроде Рихтер говорит, что он их просматривает, ну и дальше — что именно делает.
Объект может содержать в себе ссылки, а может не содержать. В отличие от С++/native, про все объекты заранее известно, есть ли в них ссылки. В строках — нет. Поэтому "просматривать" их не нужно.

PD>Вот допустим я, отнюдь не гуру в .Net, написал что-то, а быстродействие этого чего-то меня не устраивает. Пустил профайлер — что-то узнал. Как мне это применить для следующей задачи?

PD>Пуд соли я не съел, и не скоро съем. Для C++ все ясно — используешь медленную функцию, поставил не лучший алгоритм N^2 вместо Nlog(N), память выделяешь не оптимально.
Это тебе ясно исключительно потому, что ты провёл сотни экспериментов с С++. Теперь тебе сразу видно — где стоит поменять алгоритм, где заменить аллокатор, а где сразу нужно переходить на MMX и прочую низкоуровневую химию. Для новичка С++ — точно такая же непредсказуемая штука. Типа поставил где-то в неочевидном месте слово const — бах, сразу скорость подпрыгнула на 20%. Почему, отчего — хрен поймешь. Потому что не все могут выполнять в уме частичную специализацию и определять на глаз, где компилятор сможет выкинуть конструктор копирования временного экземпляра.

PD>Все так или иначе документировано и от наличия или отсутствия опыта у меня не очень зависит.
Это неправда.
PD>Нашел bottleneck — определи суть — больше так не делай.
Это неправда.
PD>Не потому, что профайлер показал его, а по определенной сути.
Это неправда.
PD>В принципе я мог бы и без профалера эту суть найти, просто анализом, медленнее, конечно, будет.
Анализом? Это каким? Ну-ка, ну-ка, покажи мне способ при помощи "анализа" за конечное время выяснить, где порылась собака в быстродействии программы на основе того же boost::lambda?

PD>А ты сам говоришь — попробуешь улучшить — чего доброго ухудшишь, пока пуд соли не съешь и эмпирические правила не освоишь. Вот так не делай, не потому что суть этого плохая, а потому что прошлый раз плохо получилось
Я говорю, что суть показывает только профайлер. В современном программировании это именно так уже лет двадцать как. Тот же SQL Server — есть масса факторов, влияющих на производительность запросов. Неопытный DBA может, конечно, на основе прочитанных книжек попытаться угадать план исполнения по запросу, а также прикинуть, какие факторы определяют быстродействие. Опытный DBA сделает это гораздо быстрее — и не потому, что он читал больше книжек, а потому, что наблюдал глазами результат применения различных сочетаний этих факторов на реальных условиях. Этого ни в каких книжках не пишут. Разве что в блогах иногда. Но опытный DBA всё равно не станет пренебрегать профайлером, несмотря на то, что суть вроде как всегда одна. Потому, что слишком много есть "факторов" в этой сути, и какой именно перевесит можно сказать априори исключительно в самых простых случаях.

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

ГВ>А теперь перечитай внимательно мою с WolfHound дискуссию. WolfHound утверждал, что достаточно положить в узлы длины собственных подстрок.

Это они и есть. Смысл дискуссии был в том нужно ли обходить все узлы для доступа по индексу — правильный ответ — нет.

Я объясняю как работают бинарные деревья поиска пользователю из ТОП100 rsdn. Сюрреализм происходящего поражает мое воображение.

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

S>Здравствуйте, alexey_ma, Вы писали:
_>>Зачем? Подобный код в плюсах не имеет смысла.
_>>Получится что-то вроде :
_>>

_>>    int a = 0;
_>>    int c = 10;
_>>    int b = 0;
_>>    (*(&b)) = ( &a == NULL ? *(&a) : c) / 100;
_>>

S>Это не эквивалентный код.
Хорошо. Измените сами по вкусу .
Зачем мне такой код ? Какой нибудь толковый пример есть?

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

ГВ>>А теперь перечитай внимательно мою с WolfHound дискуссию. WolfHound утверждал, что достаточно положить в узлы длины собственных подстрок.
K>Это они и есть.

Кто????? Длины собственных подстрок узлов — это теперь то же самое, что длина слева? У тебя там улыбка Чеширского кота рядом не летает?

K>Смысл дискуссии был в том нужно ли обходить все узлы для доступа по индексу — правильный ответ — нет.

Спасибо, это мне известно почему-то. Я пытался уяснить магию с длинами собственных подстрок.

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

ГВ>Кто????? Длины собственных подстрок узлов — это теперь то же самое, что длина слева?

Да не длина слева, а суммарная длина собственных (те, что в левом поддереве узла) подстрок узла.
Дерево — рекурсивная структура.
Без картинки не понятно что-ли?

ГВ>Я пытался уяснить магию с длинами собственных подстрок.

Эта магия называется аккумулятор. Проходят в первом классе, когда складывают (мысленно) яблоки из маленьких корзин в большую.

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


C>>>>Небольшой тест производительности std::wstring в сравнении со StringBuilder.
Х>>>чем больше я вижу твоего С++ кода, тем больше понимаю почему тебе было мучительно больно на нём писать и ты перелез на C#
G>>Чего словами кидаться. Давай соптимизируй плюсовый код criosray, чтобы он был быстрее, так чтобы там stl остался.

ГВ>Лучше чуточку к реальности приблизить. Скопируем полученные строки в массив:

К какой реальности? Никто в здравом уме не станет 25 тыс. раз в цикле вызывать ToString для StringBuilder`а.

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

ГВ>>Лучше чуточку к реальности приблизить. Скопируем полученные строки в массив:

C>К какой реальности?

К повседневной, в которой строки, синтезированные StringBuilder-ом не хранятся в самом StringBuilder-е.

C>Никто в здравом уме не станет 25 тыс. раз в цикле вызывать ToString для StringBuilder`а.

Ну никто в здравом уме не станет и 100000000 раз вызывать в цикле append для std::wstring.

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

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

Ну пусть так — суммарная длина подстрок левого узла. Суть одна и та же — что длина слева, что суммарная длина и т.п.

K>Дерево — рекурсивная структура.
K>Без картинки не понятно что-ли?

WolfHound должен сказать тебе "спасибо" за разъяснения того, что он имел в виду. Осталось дождаться, чтобы он согласился с твоими разъяснениями.

ГВ>>Я пытался уяснить магию с длинами собственных подстрок.
K>Эта магия называется аккумулятор. Проходят в первом классе, когда складывают (мысленно) яблоки из маленьких корзин в большую.

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

ГВ>WolfHound должен сказать тебе "спасибо" за разъяснения того, что он имел в виду. Осталось дождаться, чтобы он согласился с твоими разъяснениями.

Ну так вы не могли понять, как можно одновременно не заменять все узлы при перестроении и не проходить по всем узлам при доступе по индексу. Я показал как. Какая разница теперь что скажет WolfHound — это имеет значение? Думаете, тут многие люди не понимают, как деревья поиска работают?

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

ГВ>>WolfHound должен сказать тебе "спасибо" за разъяснения того, что он имел в виду. Осталось дождаться, чтобы он согласился с твоими разъяснениями.

K>Ну так вы не могли понять, как можно одновременно не заменять все узлы при перестроении и не проходить по всем узлам при доступе по индексу. Я показал как. Какая разница теперь что скажет WolfHound — это имеет значение? Думаете, тут многие люди не понимают, как деревья поиска работают?

Вспомни, чем было спровоцировано моё непонимание. Здесь же все ходы записаны.

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

ГВ>Вспомни, чем было спровоцировано моё непонимание. Здесь же все ходы записаны.

ГВ>>Если узлы хранят индексы элементов, и мы вставляем новый узел в начало, то дублировать придётся всё.
WH>Какие индексы? Зачем все?

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

Ну и чем может быть спровоцировано такое непонимание? Для добавления последовательности в начало нужно заменить 0 узлов. И создать 1 новый узел. Сложность O(1). При этом доступ по индексу будет с логарифмическим.

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

K>Ну и чем может быть спровоцировано такое непонимание? Для добавления последовательности в начало нужно заменить 0 узлов. И создать 1 новый узел. Сложность O(1). При этом доступ по индексу будет с логарифмическим.
Если речь идет об иммутабельной структуре, то придется создать новые узлы от вершины до модифицируемого узла, модифицируя в том числе и суммарные длины в подветках.
Сложность будет равна сложности поиска.

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

C>>>>Небольшой тест производительности std::wstring в сравнении со StringBuilder.
Х>>>чем больше я вижу твоего С++ кода, тем больше понимаю почему тебе было мучительно больно на нём писать и ты перелез на C#
G>>Чего словами кидаться. Давай соптимизируй плюсовый код criosray, чтобы он был быстрее, так чтобы там stl остался.

ГВ>Лучше чуточку к реальности приблизить. Скопируем полученные строки в массив:

ГВ>Это — C#/.Net 2.0 (под рукой другого нет)
ГВ>

ГВ>String[] s = new String[Count];
ГВ>

ГВ>А это — С++:
ГВ>

ГВ>std::vector<std::wstring> wv;
ГВ>

С каких пор вектор стал массивом?

ГВ>Соотношение в пользу C++ примерно 1 : 1.8.

А теперь приведем к общему знаменателю:

            const int count = 5000;

            var stringBuilder = new StringBuilder();
            var s = new List<string>(count);

            var stopwatch = new Stopwatch();
            stopwatch.Start();

            for (int i = 0; i < count; i++)
            {
                stringBuilder.Append("Карл у Клары украл кораллы в количестве ");
                stringBuilder.Append(i);
                stringBuilder.AppendLine(" штук");
                
                s.Add(stringBuilder.ToString(0, stringBuilder.Length));
            }

            stopwatch.Stop();

            Console.WriteLine("append: elapsed {0}", stopwatch.Elapsed);

inline std::wstring StringToWString(const std::string& s)
{
    std::wstring temp(s.length(),L' ');
    std::copy(s.begin(), s.end(), temp.begin());
    return temp;
}

int _tmain(int argc, _TCHAR* argv[])
{
    static const size_t count = 5000;

    std::vector<std::wstring> wv;
    std::wstring ws;
    std::string temp;
    char buffer[20];
    DWORD dwStart = ::GetTickCount();


    for(int i = 0; i < count; ++i)
    {
      ws.append(L"Карл у Клары украл кораллы в количестве ");
      _itoa_s(i,buffer,10);
      temp = buffer;
      ws.append(StringToWString(temp));
      ws.append(L" штук\n");
      wv.push_back(ws);
    }

    DWORD dwEnd = ::GetTickCount();

    std::cout << (dwEnd - dwStart) << " ms" << std::endl;
}

C++ 858 ms
C# 823 ms

Про сложность кода и явную костыльность С++ (обратите внимание как пришлось извратиться, чтоб сконвертировать число в wstring там, где StringBuilder делает конвертацию сам и не парит нам мозги) и говорить не стоит — вся красота перед глазами.

Но самое замечательное, что С++ вариант банально крашился, если Count = 10000 (и возможно меньше... не проверял между 5к и 10к).

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

Что до дотнет 3.5 и дотнет 2.0 — сколько раз говорить, что рантайм у них ИДЕНТИЧНЫЙ. Не может быть никакой разницы в производительности.

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

K>>Ну и чем может быть спровоцировано такое непонимание? Для добавления последовательности в начало нужно заменить 0 узлов. И создать 1 новый узел. Сложность O(1). При этом доступ по индексу будет с логарифмическим.
S> Если речь идет об иммутабельной структуре, то придется создать новые узлы от вершины до модифицируемого узла, модифицируя в том числе и суммарные длины в подветках.
S>Сложность будет равна сложности поиска.

Это для вставки. А не для добавления к началу/концу т.е. конкатенации.
Преимущество у мутабольного дерева будет не очень существенным (да и то только при однопоточности) — алгоритмическая сложность та же, просто вместо создания нескольких небольших объектов-узлов будет модификация (не атомарная). Ну и с персистентностью придется распрощаться.

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

ГВ>>>Лучше чуточку к реальности приблизить. Скопируем полученные строки в массив:

C>>К какой реальности?

ГВ>К повседневной, в которой строки, синтезированные StringBuilder-ом не хранятся в самом StringBuilder-е.

То есть у Вас среди повседневных задач формирование вектора из десятков тысяч вызовов ToString() StringBuilder`а? Что-то мне не верится в это.

Но даже так, то дотнет значительно выигрывает, как мы видим скорректированном примере.

C>>Никто в здравом уме не станет 25 тыс. раз в цикле вызывать ToString для StringBuilder`а.

ГВ>Ну никто в здравом уме не станет и 100000000 раз вызывать в цикле append для std::wstring.

Естественно. Это синтетика для чистого сравнения методов append. 10 млн только для того, чтоб более явно была видна разница.


Так что там с Replace? Мы увидим тест для replace внутри wstring`а, который бы отрабатывал по времени примерно столько же, сколько отрабатывал тест на append? Слабо?