Есть строка, представляющая алгебраическое выражение. Строка очень большая, в перспективе до сотен мегабайт (возможно это уже не строка а файл на диске, в котором есть выражении и их него происходит считывание данных). Необходимо одно подвыражение в строке разбить и заменить другим.
К примеру 3 + fn(a1, l, c1) + 4 * fn(a1, l, c2) - 5 * fn(a3, l, c3)
Заменить на 3 + f1a1 + 4 * f2a1 - 5 * f3a3
Использовал для строки класс string, а для поиска и операций find, replace, substr.
Профайлер показывает, что на эту замену уходит до 60% времени программы. Хотелось бы оптимизировать операции. Я так понимаю придется работать с char* (C строки).

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

Пока все это так

кто тебе сказал, что с ними будет быстрее работать?

Я предположил. К примеру при конкатенации строк, каждый раз вычисляется длина строки, эта операции чуть ли не самая долгая из всех. Работаю с char* я смогу хранить указатель на конец строки и организовать свой метод конкатенации строк. Подействует?

скорее всего length() \представляет собой end-begin, так что все работает быстро. Я лично не проверял, но не вижу почему std::string может работать медленее. Поимщи, на форуме было сравнение скорости работы, и если мне память не изменяет работа со string получалась быстрее.

Делать замену в строке такого размера - самоубийство. Лучше сразу пиши в файл вывода то, что нужно.

  Операции replace, substr и конкатинация действительно медленные. Было дело, что мне удалось увеличить скорость не менее чем в 4 раза заменив wstring на TCHAR* , но дело было не просто в замене, а в том что при помощи TCHAR* удобно делать низкоуровневые оптимизации. Кроме того можно выиграть если все выделения памяти внутри цикла производить не в куче, а в специальном пуле (как в стеке), т.е. память освободиться только по выходу из цикла целиком.
  Бить нужно в выделения памяти. Оператор "+" это выделение памяти с копированием, replace это выделение памяти с еще большим копированием, substr выделение памяти с небольшим копированием. Компиляторы С++ чаще всего имеют фиговенькие менеджеры куч, потому операция выделения памяти весьма не быстрая.

Попробуйте пользовать два массива/строки исходный и целевой. В целевом заранее зарезервировать память нужного размера,
и организовать туда выборочное копирование по Вашему заданию.

Если говорить об оптимизации то явно STL не оптимизирована. 
Оптимизация работы с памятью это сложный вопрос(как правило включается зависимость железа)
 - разворот циклов на чтение.запись памяти
 - Как читается указатель
Вообщем очень много , советую почитать литературу.

Понравился совет mes. В принципе сам пришел к такому же решению. Попробую, скажу результат.
Если в дальнейшем не будет хватать памяти, организую это все через файлы и потоки.

Второй вариант.



Выигрыша во времени НЕТ! Мои надежды не оправдались.

Добавлено через 29 секунд
Видно нужны другие подходы.

...

Это сообщение отредактировал(а) mes - 18.1.2009, 18:15

Для такой задачи нужно кардинально другой метод обработки - нужно не перепахивать многократно всю строку для каждой fn, а делать все замены на одном проходе (можно даже на лету, не сохраняя собственно строку). Ищи по ключевым словам regex, NFA, DFA

во втором варианте вы делаете проход побайтно!!!  а в первом вы вызываете ОПТИМИЗИРОВАННУЮ функцию поиска подстроки(если ничего не попутал то что видел)...

естественней будет медленней. и странно что то же самое получили  видать тест не длинный...

постарайтесь использовать приведённые тут советы..и помните..
1) функции из библиотек обрабатываемые скопом инфу - оптимизированные на низком уровне...наверняка поиск символа в строке будет в коде звучать типа substr т.е. быстрее вряд ли придумаешь...
2) постарайтесь измерять и проанализировать где ЯВНО у вас встречаються тормоза...и можно ли эти участки сделать паралельно. Т.е. например поиск подстрок выражений - скопом, а вот обработку их отдельно - в потоках. грамотная ось будет давать выигрыш в скорости даже на одном проце с одним конвеером(к сожалению форточки к этим осям не относяться) ...
3) постарайтесь глобально проанализировать задачу...возможно решение в лоб (поиск и замена) - не есть оптимум к результату... может имеет смысл искать начало и конец этих функций на момент создания(вставки) , информацию сохранять и потом именно её и кушать на входе?


удачи Вам
(круглый)

 по моему trim сгодится

если говорить о хорошей оптимизации, то вместо того чтобы искать "хорошую" стандартную функцию для общих задач, лучше грамотно поставить задачу и сделать свою функцию под эту частную задачу.