c++ std::string - find and replace all

[Shadow2531]

I often need a find and replace function that finds all instances of a string in a string and replaces each instance with some other string.

I can use regex_replace() from the boost library ( http://www.boost.org/ )

e.g.

string x = "1a2a3a4a5";
string n = regex_replace( x, regex("a"), "b");

However, the find string and the relpacement string are not treated as literals so you have to escape lots of things.
You can make the replacement a literal by doing:

regex_replace( x, regex("a"), "b", format_literal);

However, sometimes I get crashes with the format_literal flag.
Also, in situations where the regex() could be anything, certain strings cause crashes too, because it's an expression and not a literal.

regex_replace is a pain in many cases and is overkill, when all I want to do is find and replace all. Plus, I don't like having the boost library as a dependency for something like this, but regex_replace performs replacement pretty fast, which is a pro.

Anyway, I decided to make my own find and replace function using an ostringsream object for building the new string. I used a copy of the source string that I could modify. Each time through the loop, I'd find the first instance, get the substring before it and write that substring and the replacement to the ostringstream object. I'd then resize the copy of the source string to a substr() of itself; representing everything after the instance found.

Basically, that worked fine and was even fast, but then, I decided to test it on a 1MB text file where every char was the same. I then tried to replace each character with another and then write it to a file. That's where I hit the speed problem.

The replacement on 1M characters was taking about 1 hour 30 minutes or more to complete, which is just insane. I then changed the function to just iterate if the find string was just one character. I thought that fixed the speed problem, but if I searched every 2 or more characters and replaced them, it was still insanely slow.

Here's the function I was using:

string replaceAll( const string& content, const string& instance, const string& replacement ) {
    if ( instance.empty() || content.empty() || content.find(instance) == string::npos || instance == replacement ) {
        return content;
    }
    ostringstream new_content;
    if (instance.size() == 1) {
        for (string::const_iterator i = content.begin(); i != content.end(); ++i) {
            if ( *i == instance[0] ) {
                new_content << replacement;
            } else {
                new_content << *i;
            }
        }
    } else {
        string remaining( content );
        const size_t instance_size( instance.size() );
        for ( size_t start_pos_of_instance; ( start_pos_of_instance = remaining.find(instance) ) != string::npos; ) {
            new_content.write( &remaining[0], start_pos_of_instance); // was using remaining.substr()
            new_content << replacement;
            //remaining.erase(0, start_pos_of_instance + instance_size);
            ostringstream temp;
            temp.write(&remaining[ start_pos_of_instance + instance_size], remaining.size() - (start_pos_of_instance + instance_size) );
            remaining = temp.str();
            temp.clear();
        }
        new_content << remaining;
    }
    return new_content.str();
}

As you can see in last loop, I was trying to make resizing the copy of the source string faster and was trying to avoid using substr() or methods like erase(). However, none of that helped.


I figured the best way to speed things up was to not modify a string at all and to just read a range of characters from the source string right into the stringstream object.
I decided to use write() for that part, but I was still having problems trying to keep track of and find the position of each instance using find(). Well, I decided to use the find() that allows you to specifiy a start position.

Here's the new version and a few tests. This version is fast. It's faster than regex_replace (in my testing). In fact, these same tests with the above code took over 3 hours to complete, but with this version, it's virtually instant.

#include <iostream>
#include <string>
#include <sstream>
#include <fstream>

using namespace std;

inline string replaceAll( const string& s, const string& f, const string& r ) {
    if ( s.empty() || f.empty() || f == r || s.find(f) == string::npos ) {
        return s;
    }
    ostringstream build_it;
    size_t i = 0;
    for ( size_t pos; ( pos = s.find( f, i ) ) != string::npos; ) {
        build_it.write( &s[i], pos - i );
        build_it << r;
        i = pos + f.size();
    }
    if ( i != s.size() ) {
        build_it.write( &s[i], s.size() - i );
    }
    return build_it.str();
}

int main() {
    string example;
    for (size_t i = 0; i < 1048576; ++i) {
        example += "a";
    }
    
    cout << replaceAll( "one two one two one cbhg", "one ", "d") << endl; // example
    cout << replaceAll( "aaaaaaaaaa", "aa","44") << endl; // example
    cout << replaceAll( "aaaaaaaaaa", "a","4") << endl; // example
    cout << replaceAll( "1a2a3a4a5", "a", "") << endl;
    
    const string s( replaceAll( example, "aa", "44") );
    ofstream out("checkoutput.txt");
    if (!out) {
        return 1;
    }
    out << s; // file should consist of 1048576 4s 
    
    const string s2( replaceAll( example, "a", "4") );
    ofstream out2("checkoutput2.txt");
    if (!out2) {
        return 1;
    }
    out2 << s2; // file should consist of 1048576 4s 
}

Now that the function is fast and passes the few tests I've given it, do you see any problems with it? ( like replacements that it fails to do right or segfaults, memory leaking etc). If so, can you help fix them.

How can I make that even better? I definitely want it to be 100% accurate, 100% of the time.

I didn't test with files larger than 1MB yet.

Thanks

 

[bassman]

boost::string_algo has a bunch of replace functions. Try replace_all().

If you don't want the dependency on boost, you can just link to string_algo. If you don't want that dependency, use your own function. Check it out by writing a unit test program for it.

The unit test program could generate strings of random length and content and pass them to your function over and over again. You could have the test run in an endless loop or have it run pre-set number of times. This would test the robustness of the function pretty quickly. You could test the correctness by comparing the output to boost::string_algo::replace_all().

 

[Shadow2531]

Thanks.

I didn't think to look in the other parts of boost. I will indeed use the boost replace_all to check my function.

Edit:

replace_all_copy() is the boost function I was looking for. It works great.

Doing testing on a 20MB string of all A's and replacing each A with a 4, my function is 2 times faster than the boost function.

 

[mikeblas]

Using regex is overkill -- your target string isn't a regular expression, so you're paying for a ton of overhead that you're not using.

Can you think of any ways to make it faster? Have you measured where it is spending its time? Or are you satisfied with the perf it has now? If you're not, I think you have a great opportunity to learn why std::string's performance isn't always a good tradeoff for its perceived safety.

    string example;
    for (size_t i = 0; i < 1048576; ++i) {
        example += "a";
    }

Yikes!!1! Why wouldn't you code this, instead?

    string example(1048576, 'a');

 

[Shadow2531]

^^

That part was just for testing and didn't consider performance/simplicity for that part.

Anyway, for my replaceAll function:

if I change:

build_it << r;

to

build_it.write(&r[0], r.size() );

the function peforms faster.

 

[mikeblas]

Here is an allocator that you can use with std::basic_string:

template <class T>
class MeteredAllocator
{
public:
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
	typedef T* pointer;
	typedef const T* const_pointer;
	typedef T& reference;
	typedef const T& const_reference;
	typedef T value_type;

	pointer address(reference value) const
	{
		return &value;
	}

	const_pointer address(const_reference value) const
	{
		return &value;
	}

	template <class U>
	struct rebind {
		typedef MeteredAllocator<U> other;
	};

	size_type max_size() const 
	{
		return 100000000;
		//  return std::numeric_limits<size_t>::max( ) / sizeof(T);
	}

	pointer allocate(size_type num, std::allocator<void>::const_pointer /* hint */ = 0)
	{
		printf("metered allocator: allocating %d\n", num);
		return (pointer) ::operator new(num*sizeof(T));
	}

	void deallocate(pointer p, size_type num)
	{
		printf("metered allocator: deallocating %d\n", num);
		delete( (void*) p );
	}

	void construct(pointer p, const T& value)
	{
		new((void*)p) T(value);
	}

	MeteredAllocator()
	{
	}

};

Instead of declaring

const string s2( replaceAll( example, "a", "4") );

add this typedef to your code in one place

typedef metered_string std::basic_string<char, std::char_traits<char>, MeteredAllocator<char> >;

then fix your definitions to use the metered allocator:

const metered_string s2( replaceAll( example, "a", "4") );

and this will help you gain some insight into how you're beating up the memory allocator. You'll see lots of spew about allocating and freeing memory. Using the memory manager isn't cheap. Is there a way you can reduce or eliminate these allocations?

Unfortunately, you can't supply a custom allocator to ofstream -- but it's doing a bunch of allocations, too.

That helps you gain insight into your implementation. You can also improve your algorithm.

 

[Shadow2531]

Thanks.

typedef metered_string std::basic_string<char, std::char_traits<char>, MeteredAllocator<char> >;

doesn't work till I change it to:

typedef std::basic_string<char, std::char_traits<char>, MeteredAllocator<char> > metered_string;

Then, when I do :

const metered_string s2( replaceAll( example, "a", "4") );

I get a bunch of compilation errors with the first error being that line.

error: no matching function for call to `std::basic_string<char, std::char_traits<char>, MeteredAllocator<char> >::basic_string(std::string)

 

[mikeblas]

Sorry; I always get typedef's the wrong way around.

I can't guess what your other error is about, tho.

LATER: Oh. It looks like you're not converting all the strings. So, if you've only made that one substitution, you're trying to initialize a metered_string from a string, and they don't know eachother. Change all your references to string to metered_string. (Or, make a macro to do it for you so you can switch back and forth.)

In some places, this requires a more changes:

inline metered_string replaceAll( const metered_string& s, const metered_string& f, const metered_string& r ) {
    if ( s.empty() || f.empty() || f == r || s.find(f) == metered_string::npos ) {
        return s;
    }
    ostringstream build_it;
    size_t i = 0;
    for ( size_t pos; ( pos = s.find( f, i ) ) != metered_string::npos; ) {
        build_it.write( &s[i], pos - i );
        build_it << r;
        i = pos + f.size();
    }
    if ( i != s.size() ) {
        build_it.write( &s[i], s.size() - i );
    }

	metered_string strRet(build_it.str().c_str());
    return strRet;
}

I guess you could add a converting constructor to metered_string.

 

[Shadow2531]

Here's what I have:

#include <string>
#include <sstream>
#include <cstdio>

using namespace std;

template <class T>
class MeteredAllocator
{
public:
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef T value_type;

pointer address(reference value) const
{
return &value;
}

const_pointer address(const_reference value) const
{
return &value;
}

template <class U>
struct rebind {
typedef MeteredAllocator<U> other;
};

size_type max_size() const 
{
return 100000000;
//  return std::numeric_limits<size_t>::max( ) / sizeof(T);
}

pointer allocate(size_type num, std::allocator<void>::const_pointer /* hint */ = 0)
{
printf("metered allocator: allocating %d\n", num);
return (pointer) ::operator new(num*sizeof(T));
}

void deallocate(pointer p, size_type num)
{
printf("metered allocator: deallocating %d\n", num);
delete( (void*) p );
}

void construct(pointer p, const T& value)
{
new((void*)p) T(value);
}

MeteredAllocator()
{
}

};

inline string replaceAll( const string& s, const string& f, const string& r ) {
    if ( s.empty() || f.empty() || f == r || s.find(f) == string::npos ) {
        return s;
    }
    ostringstream build_it;
    size_t i = 0;
    const size_t r_size( r.size() );
    const size_t f_size( f.size() );
    for ( size_t pos; ( pos = s.find( f, i ) ) != string::npos; ) {
        build_it.write( &s[i], pos - i );
        build_it.write( &r[0], r_size );
        i = pos + f_size;
    }
    if ( i != s.size() ) {
        build_it.write( &s[i], s.size() - i );
    }
    return build_it.str();
}

int main() {
    typedef std::basic_string<char, std::char_traits<char>, MeteredAllocator<char> > metered_string;
    const string source( 20971520, 'a' );
    const metered_string s( replaceAll( source, "a", "4" ) );
}

and here are the errors ( from the vc++ 2003 toolkit, so the error format would be more familiar)

 error C2664: 'std::basic_string<_Elem,_Traits,_Ax>::basic
_string(const std::basic_string<_Elem,_Traits,_Ax>::_Alloc &)' : cannot convert
parameter 1 from 'std::string' to 'const std::basic_string<_Elem,_Traits,_Ax>::_
Alloc &'
        with
        [
            _Elem=char,
            _Traits=std::char_traits<char>,
            _Ax=MeteredAllocator<char>
        ]
        and
        [
            _Elem=char,
            _Traits=std::char_traits<char>,
            _Ax=MeteredAllocator<char>
        ]
        Reason: cannot convert from 'std::string' to 'const std::basic_string<_E
lem,_Traits,_Ax>::_Alloc'
        with
        [
            _Elem=char,
            _Traits=std::char_traits<char>,
            _Ax=MeteredAllocator<char>
        ]
        No constructor could take the source type, or constructor overload resol
ution was ambiguous

 

[mikeblas]

Using the complete code below, which does the repalcement, gets the types right, and also adds the allocator to ostringstream, I get this total allocation pattern. -1 is reattach allocations. 2 is ostringstream, 1 is string.

-1: 0 allocations for 0 total bytes
-1: 0 allocations for 0 total bytes
-1: 1 allocations for 1048592 total bytes
-1: 1 allocations for 1048592 total bytes
-1: 0 allocations for 0 total bytes
-1: 0 allocations for 0 total bytes
-1: 2 allocations for 2097184 total bytes
-1: 1 allocations for 1048592 total bytes
-1: 1 allocations for 1048592 total bytes
2: 26 allocations for 3228417 total bytes
-1: 0 allocations for 0 total bytes
-1: 0 allocations for 0 total bytes

That's a lot of allocation and copying and freeing when you could be doing the replacement with just one copy.

#include <iostream>
#include <tchar.h>

#include <string>
#include <stdio.h>
#include <sstream>
#include <fstream>

#include <limits>

using namespace std;

template <class T, int n>
class MeteredAllocator
{
public:
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
	typedef T* pointer;
	typedef const T* const_pointer;
	typedef T& reference;
	typedef const T& const_reference;
	typedef T value_type;

	pointer address(reference value) const
	{
		return &value;
	}

	const_pointer address(const_reference value) const
	{
		return &value;
	}

	template <class U>
	struct rebind {
		typedef MeteredAllocator<U, -1> other;
	};

	size_type max_size() const 
	{
//		return 100000000;
		return std::numeric_limits<size_t>::max( ) / sizeof(T);
	}

	pointer allocate(size_type num, std::allocator<void>::const_pointer /* hint */ = 0)
	{
		printf("%d: metered allocator: allocating %d\n", m_n, num *sizeof(T));

		m_nHits++;
		m_nVolume += num * sizeof(T);

		return (pointer) ::operator new(num*sizeof(T));
	}

	void deallocate(pointer p, size_type num)
	{
		printf("%d: metered allocator: deallocating %d\n", m_n, num);
		delete( (void*) p );
	}

	void construct(pointer p, const T& value)
	{
		new((void*)p) T(value);
	}

	MeteredAllocator()
		: m_n(n), m_nHits(0), m_nVolume(0)
	{
	}

	~MeteredAllocator()
	{
		printf("%d: %d allocations for %d total bytes\n",
			m_n, m_nHits, m_nVolume);

	}

private:
	int m_n;
	size_t m_nVolume;
	size_t m_nHits;
};

typedef std::basic_string<char, std::char_traits<char>, MeteredAllocator<char, 1> > metered_string;



inline metered_string replaceAll( const metered_string& s, const metered_string& f, const metered_string& r ) {
    if ( s.empty() || f.empty() || f == r || s.find(f) == metered_string::npos ) {
        return s;
    }
//    ostringstream build_it;
	basic_stringstream<char, std::char_traits<char>, MeteredAllocator<char, 2> > build_it;
    size_t i = 0;
    for ( size_t pos; ( pos = s.find( f, i ) ) != metered_string::npos; ) {
        build_it.write( &s[i], pos - i );
        build_it << r;
        i = pos + f.size();
    }
    if ( i != s.size() ) {
        build_it.write( &s[i], s.size() - i );
    }

	metered_string strRet(build_it.str().c_str());
    return strRet;
}

int main() {
    metered_string example;
    for (size_t i = 0; i < 1048576; ++i) {
        example += "a";
    }
    
    cout << replaceAll( "one two one two one cbhg", "one ", "d") << endl; // example
    cout << replaceAll( "aaaaaaaaaa", "aa","44") << endl; // example
    cout << replaceAll( "aaaaaaaaaa", "a","4") << endl; // example
    cout << replaceAll( "1a2a3a4a5", "a", "") << endl;
    
    const metered_string s( replaceAll( example, "aa", "44") );
    ofstream out("checkoutput.txt");
    if (!out) {
        return 1;
    }
    out << s; // file should consist of 1048576 4s 
    
    const metered_string s2( replaceAll( example, "a", "4") );
    ofstream out2("checkoutput2.txt");
    if (!out2) {
        return 1;
    }
    out2 << s2; // file should consist of 1048576 4s 
}

 

[Shadow2531]

That won't compile on Mingw, but does on vc++ 2003 tookit. (glad I have it around )

I ran it and it shows a boatload of delocating and allocating. I see it's doing a lot of work, but how can I do it in all one copy as you suggest?

Thanks

 

[mikeblas]

1) avoid ostringstream
2) avoid string

And you'll also want to consider a better algorithm. What if your replacement function sees "abbadabbab" and wants to replace "abbab" with "bar"? Aren't you doing too many comparisons?

 

[mikeblas]

Looks like MingW probably wants specialized operator== and operator!= to test that one allocator instance is equal to antoher. Since that code isn't actually used, VC++ doesn't care. (VC++ doesn't expand template functions unless they're actually invoked. Most other compilers expand everything in the template.)

Since you've got it working with VC++ and see the point, I won't bother fixing the example.

 

[MonkeyShave]

3) The C++ Standard Library contains many useful algorithms (in <algorithm>) from which you can compose more useful algorithms.

std::search and std::copy do the vast majority of what you want. Your desired find-and-replace algorithm is properly an algorithm and the iterator abstraction often proves useful in this domain (as opposed to the string abstraction which your current algorithm uses).

Recognizing this, I present an algorithm that is both correct and operates in linear time.

#include <string>
#include <algorithm>
#include <iostream>
#include <iterator>

template<typename FwdIt1, typename FwdIt2, typename FwdIt3, typename OutIt >
void search_and_replace( FwdIt1 const begin_source,
                         FwdIt1 const end_source,
                         FwdIt2 const begin_find,
                         FwdIt2 const end_find,
                         FwdIt3 const begin_replace,
                         FwdIt3 const end_replace,
                         OutIt destination )
{
    FwdIt1 curr_source_begin = begin_source;
    std::iterator_traits<FwdIt2>::distance_type const find_length = std::distance( begin_find, end_find );
    while( true )
    {
        FwdIt1 curr_source_end = std::search( curr_source_begin, end_source, begin_find, end_find );
        std::copy( curr_source_begin, curr_source_end, destination );   //copy the source elements between
                                                                        // the end of the previous find
                                                                        // position and the beginning of the
                                                                        // subsequent one
        curr_source_begin = curr_source_end;
        if( curr_source_begin == end_source )
        {
            return;             //the find sequence did not occur in the source during this iteration
                                // so we have copied the remainder of the source string to the
                                // destination
        }
        std::copy( begin_replace, end_replace, destination ); //copy the replacement sequence
        std::advance( curr_source_begin, find_length );       //skip the remainder of the find sequence
    }
}

int main()
{
    std::string source( 1000000, 'a' );
    std::string findtext( "a" );
    std::string replacetext( "b" );
    std::string destination;
    search_and_replace( source.begin(), source.end(),
                        findtext.begin(), findtext.end(),
                        replacetext.begin(), replacetext.end(),
                        std::back_inserter( destination ) );
    //std::cout << destination << std::endl;
}

 

[Shadow2531]

(thoughts before reading MonkeyShave's post)

1) avoid ostringstream
2) avoid string

Are you saying to use something else to copy to the new string or are you saying that if speed and resource management is that much of a concern, I should use my own data type and my own functions etc. to deal with the data and make it as fast as I code it?

And you'll also want to consider a better algorithm. What if your replacement function sees "abbadabbab" and wants to replace "abbab" with "bar"? Aren't you doing too many comparisons?

Not sure, but I think find() is doing a lot of comparing when it tries to find a position of something.

 

[Shadow2531]

Looks like MingW probably wants specialized operator== and operator!= to test that one allocator instance is equal to antoher. Since that code isn't actually used, VC++ doesn't care. (VC++ doesn't expand template functions unless they're actually invoked. Most other compilers expand everything in the template.)

Since you've got it working with VC++ and see the point, I won't bother fixing the example.

Thanks.

 

[Shadow2531]

3) The C++ Standard Library contains many useful algorithms (in <algorithm>) from which you can compose more useful algorithms.

std::search and std::copy do the vast majority of what you want. Your desired find-and-replace algorithm is properly an algorithm and the iterator abstraction often proves useful in this domain (as opposed to the string abstraction which your current algorithm uses).

The code doesn't work in mingw, but does in vc++. It's twice as fast as my function. I just need to detemplatize it and make it simpler and more basic so I can see what's going on.

For my function, I wanted to use an iterator to sift through the string, but write() needed an int for the second argument and write() was saving time, but I'm still thinking find() is a little inefficient.

Thanks.

I'll follow up on your code.

 

[MonkeyShave]

If you want to adapt my approach, I would recommend reading the documentation for the C++ Standard Library functions that I used.

std::advance
std::copy
std::distance
std::search

std::search apparently has a worst-case time complexity of O(length( source_range ) * length( find_range )) but the average-case complexity is O( length( source_range ) ). The worst-case complexity will occur when your searched-for string has a large amount of redundancy (i.e. "aaaaaaaaaaa") and your searched-in string has many false-positivies (i.e. "aaaaaaaaaabaaaaaaaaaabaaaaaaaaaab"). If your strings are of this type (and this contributes to a real problem in running time) then you'll want to look at more sophisticated string-searching algorithms with different tradeoffs (i.e. suffix-trees, which are a the far opposite end of the spectrum in worst-case complexity, code complexity, setup time, and memory use).

The mingw incompatibility is likely the line:

std::iterator_traits<FwdIt2>::distance_type const find_length = std::distance( begin_find, end_find );

which should be

std::iterator_traits<FwdIt2>::difference_type const find_length = std::distance( begin_find, end_find );

distance_type must be a Visual C++ library extension, difference_type is a standard member of std::iterator_traits and the documented return-type of std::distance().

 

[mikeblas]

Man, I love this stuff.

Recognizing this, I present an algorithm that is both correct and operates in linear time.

That's pretty neat; nice work!

I could use a little convincing about it running in linear time. As characters are added to the output string, the string will have to grow. The grow operation on the string allocates, copies, and frees as it goes. IIRC, the VC++ implementation of the STL ends up growing 50% each time a reallocation is necessary.

For every n characters you add, you'll reallocate log times, then copy all n characters, then free. Isn't your runtime then O(n*log)? If I'm wrong about the growth pattern, I think it just effects base of the log.

Memory size is pretty cheap compared to reallocating and copying memory. With this kind of grow-copy-free pattern, you're in jeopardy of fragmneting memory, and it's hard to measure or predict the aftereffecs this kind of routine leaves the memory manager. I think you can get a win by either pre-allocating a worst case memory size with string.reserve(), or by using a better search algorithm to learn the size of the resulting string, then do another walk to actually do the replacement work.

Are you saying to use something else to copy to the new string or are you saying that if speed and resource management is that much of a concern, I should use my own data type and my own functions etc. to deal with the data and make it as fast as I code it?

I'm not sure what you mean by "as fast as I code it".

What I'm saying is that the classes you're using have lots of side effects. Those side effects certainly aren't free; in a few cases, they're not even trivial. You're exercising those side-effects in very expensive ways; the side-effects cost O or O(log), and you're doing them in O loops.

The same caveat I mentioned in the other thread applies: if you are convinced you want to use the STL (or any other library!) for the benefits you believe you get in stability or productivity, by all means do so. Those issues are not insignificant, and can be overriding factors.

The code I've come up with, along with the Shadow's original routine and Monkey's code and a main() that tests two cases and prints timing, is at http://www.blaszczak.com/posts/StringReplace.ZIP in a VC++ .NET project. Though my code searches twice, it's actually faster than the STL implemnetation (with those scenarios, on my system with my tools, and so on).

For my solution the search time could be mitigated, particularly for the pedantic strings that Monkey and I were talking about by using something like Boyer-Moore or Knuth-Morris-Pratt. Since I search twice but only build the skip table once, I think the benefit would be particularly interesting.

But like Monkey mentioned, Shadow, I wouldn't "detemplatize it" so that you can learn what it is doing. Learn what it is doing as-is, so you can add something about the STL to your toolbox.

 

[MonkeyShave]

Regarding my claim on linear time:
I don't have my copy of the standard in front of me, so I may be incorrect with regards to the standard's requirements on std::string:ush_back().

std::vector<T>:ush_back(), on the other hand, is required to have amortized constant time complexity.

In general, if a contiguous container (std::vector and MSFT's std::string) grows exponentially when a push_back() forces reallocation, then the average number of element copies required during all reallocations will always fall below some constant. A brief web search, unfortunately, did not turn up any proofs of this, though a newsgroup search on the terms exponential growth amortized constant turned up discussions on the comp.lang.c++.moderated group.

This does assume that allocation and deallocation time is no worse than O(N) in allocation size, but that's relatively safe to assume as long as the system has suficcient free memory.

std::search is another case that should have a better-documented complexity bound. The documentation describes its time complexity (worst-case) as O( length( searched_sequence ) * length( searched_for_sequence ) ) and its average complexity as O( length( searched_sequence ) ).

In a practical implementation, the average case for each execution will actually be linear in the number of elements searched before producing the first result (it terminates its scan once it finds a result).

The result has a size linearly related to the searched_text size, as you replace X strings of length Y each with a string of length Z. Treat Y and Z as constant (invariant during execution) and the final length is length( searched_sequence ) - X*Y + X*Z, where X <= length( searched_sequence ).

Clearly, this does not constitute a formal proof, but I hope it provides enough insight into my line of reasoning to either explain it or reveal its faults.

 

[mikeblas]

In general, if a contiguous container (std::vector and MSFT's std::string) grows exponentially when a push_back() forces reallocation, then the average number of element copies required during all reallocations will always fall below some constant. A brief web search, unfortunately, did not turn up any proofs of this, though a newsgroup search on the terms exponential growth amortized constant turned up discussions on the comp.lang.c++.moderated group.

I think you've misstated something; the element copies don't fall under a constant. The number of element copies is determined by the log of the number of inserts.

But, yeah -- that's amortization, and the STL relies heavily on it for its performance guarantees. Thing is, I think that you don't realize the amoritization benefit when you grow the container from length zero to its final length incrementally.

I believe that my STL-avoiding code is faster is simply because you end up paying for the amoritization over the loops. That, and there are a few silly abstractions left over even after the compiler does its work.

The way the VC++ implementation works for your routine might be part of the problem. When you're copying a range with known length:

std::copy( begin_replace, end_replace, destination );

for example, the implementation is copying from begin_replace to end_replace element by element. It could, instead, guarantee that (end_replace - begin_replace) more elements are available in one call, then do the work it needs.

The ultimate form of such an optimization is what I suggested above; preallocate with string.reserve() in the output object.

This does assume that allocation and deallocation time is no worse than O(N) in allocation size, but that's relatively safe to assume as long as the system has suficcient free memory.

Well, in a multi-threaded application, it's certainly not safe to make such an assumption. If all the threads are using the default allocator, then they're all blocking on eachother to get singular access. It brings complicated systems to its knees. It can be annoying to hook the STL containers to a better, thread-aware allocator.

By the way, it's interesting to talk about orders of performance complexity. But in the final analysis, we have to look at the clock. Say it takes c time to search one character. Maybe a perfectly linear algorithm takes O(n*c) to search n characters. The algorithms we've been talking about need some time measure, t, per each character (count of m) in the matching string. So we're really O(n*c + m*t).

The times to compare a single character or even rewind the characters is very small. At most a dozen instructions, maybe; a few tens of millionths of seconds, at worst. But what if you think of the time to allocate and copy? Say you do that log times, and it costs R.

We arrive at O(n*c + m*t + R*log), then. Even if log is small, ten or twenty times, say, it blasts the heck out of R. Maybe I'm wrong, though -- and it really is a linear cost. So let's call that O(n*c + m*t + R*n/100), or something.

R still appears, and has a big coefficient. Because of the wegith it puts on the performance, finding an algorithm with a higher order of complexity might end up being faster because we've eliminated the dominant R constant.

 

[MonkeyShave]

I struggled for a time to assemble a formal proof of amortized constant time (a sum total of steps which grows in linear relation ot the number of operations) and I think I can adequately describe the inductive step in such a proof.

First, however, I'll approach that problem from two other angles.

1. Assume that your structure doubles its buffer size whenever it runs out.
The first element has been copied log2(size) times,
the second has been copied log2(size) - 1 times,
the third and fourth have been copied log2(size) - 2 times,
the following 4 elements have been copied log2(size) - 3 times,
the following 8 elements have been copied log2(size) - 4 times,
...

The size of each "generation" is larger than the previous and has experienced one less copy. In this case, doubling the size of the structure (from N elements to N*2 elements) will require roughly N*2 copies (N from moving the existing elements + N from inserting the new elements). The ratio of moves to elements will range between around 1 to 3

2. Using concrete numbers, here is an example of the number of moves for each element of a container which doubles its size whenever it exceeds its capacity.

1|                                   1 position,   1 copy,      1 element, ratio   1/1
21|                                  2 positions,  3 copies,    2 elements, ratio  3/2
321 |                                4 positions,  6 copies,    3 elements, ratio  6/3
3211|                                4 positions,  7 copies,    4 elements, ratio  7/4
43221   |                            8 positions, 12 copies,    5 elements, ratio 12/5
432211  |                            8 positions, 13 copies,    6 elements, ratio 13/6
.
.
.
5433222211111111|                   16 positions, 31 copies,   16 elements, ratio 31/16

Finally, the inductive step of a formal-enough-for-the-[H]ard|Forum.

1. Assume you have a container which you grow by the ratio 1/X each time you must add elements.
2. The most recent allocation increased the size by N elements.
3. The previous insertion caused the container to expand.
4. Given 1, 2, and 3, prior to the previous insertion (and subsequent allocation), the container's capacity was X*N elements,
following the previous insertion, the container has a capacity of X*N+N elements and contains X*N+1 elements.
5. Perform N-1 more insertions: This requires N-1 copy operations and no reallocation. The container now contains X*N+N elements.
6. Perform 1 more insertion: This requires reallocation and moving every earlier element to the new space, i.e. X*N+N copies.
It also requires one copy for the new element.
7. We have returned the container to the state described in step 3.
8 We have performed N insertions. These required N-1 + X*N + N + 1 copies. Simplified, this is (2+X)*N copies for N insertions.

Therefore, exponential growth, implemented by reallocating into a container with a new size that is some multiple (greater than 1) of the previous size can perform back-insertion operations in amortized-constant time (N back-insert operations require (2+X)*N copies). This result is consistent with the sequence between 3 and 5 elements above (where X == 1).

The OP mentioned a 90 minute running time for 1 million elements, which indicates an problem of bad asymptotic complexity.

It is true that dynamic allocation can require unpredictable amounts of time, however expanding a container from 1 to 3,000,000 elements requires only 37 reallocations (log1.5(3,000,000)).

Ultimately, algorithm choice depends on a variety of practical matters. If profiling does not demonstrate that a code creates a meaningful bottleneck, I tend to prefer a simpler, more consise solution. I have generally found iterator and algorithm-based approaches easier to debug, demonstrate correct, and adapt to different purposes.

(edit) I have just now reviewed your code and I see why you account for R as the dominant factor. Your MeteredAllocator performs console output (a nororiously slow operation) during each allocation and deallocation. If you rerun the tests with std::allocator, I expect that the time difference would nearly vanish (my version performs 74 memory operations within the timed region, yours performs 1 which performs no output). I don't have Visual Studio installed on this computer, so I am unable to perform this test myself at the moment.

Also, my iterator approach provides the basic exception-safety guarantee and permits automatic memory management (the string referred to by destination iterator will be destroyed). A solution that requires manual deallocation runs the risk of leaking memory due to either exceptions or user error.

 

[mikeblas]

(edit) I have just now reviewed your code and I see why you account for R as the dominant factor. Your MeteredAllocator performs console output (a nororiously slow operation) during each allocation and deallocation. If you rerun the tests with std::allocator, I expect that the time difference would nearly vanish (my version performs 74 memory operations within the timed region, yours performs 1 which performs no output). I don't have Visual Studio installed on this computer, so I am unable to perform this test myself at the moment.

Check the code again; MeteredAllocator isn't in play, because the typedef for metered_string is set to std::string.

// typedef std::basic_string<char, std::char_traits<char>, MeteredAllocator<char> > metered_string;
typedef std::string metered_string;

Also, my iterator approach provides the basic exception-safety guarantee and permits automatic memory management (the string referred to by destination iterator will be destroyed). A solution that requires manual deallocation runs the risk of leaking memory due to either exceptions or user error.

Yep. But there's no chance of a leak in my function, since I only allocate once. If I can't allocate what's known to be needed, I fail -- there's no recovery necessary. Outside of the function, the user can use an auto pointer if exception safety is a concern -- or convert the code to pretty easily (and without additional allocations, I think -- but I haven't tried it) to return the result in std::string.

Ultimately, algorithm choice depends on a variety of practical matters. If profiling does not demonstrate that a code creates a meaningful bottleneck, I tend to prefer a simpler, more consise solution. I have generally found iterator and algorithm-based approaches easier to debug, demonstrate correct, and adapt to different purposes.

As do implementation choices. Shadow didn't make any terrible algorithmic choices -- he was bit by implementation factors that he wasn't aware of. He's not about to do any profiling, and is a little too inexperienced to forsee the problems he might create for himself with a library that he's not expertly familiar with, like you are with the STL. So either he jumps in the deep end and learns the STL and hopes he can track down any implementation issues he didn't expect, or he stays away from it until he learns to anticipate or research what to expect, and is probably more productive with less glossy techniques.

 

[Shadow2531]

I'm not sure what you mean by "as fast as I code it".

Basically, I was thinking that if I coded my own string class, search and copy functions etc., then I wouldn't be depending on any stl methods. That way, if something's not fast and efficient enough, I'd have more control over making it better. In other words, I believe you were saying that no matter much I tweak things, stringstream and string are going to be bottlenecks.

What I'm saying is that the classes you're using have lots of side effects. Those side effects certainly aren't free; in a few cases, they're not even trivial. You're exercising those side-effects in very expensive ways; the side-effects cost O or O(log), and you're doing them in O loops.

The same caveat I mentioned in the other thread applies: if you are convinced you want to use the STL (or any other library!) for the benefits you believe you get in stability or productivity, by all means do so. Those issues are not insignificant, and can be overriding factors.

My function is fast enough for what I need it and it's comfortable using string and stringstream, but since there are more efficient ways, I'm happy to give them a shot.

But like Monkey mentioned, Shadow, I wouldn't "detemplatize it" so that you can learn what it is doing. Learn what it is doing as-is, so you can add something about the STL to your toolbox.

What I had in mind was to detemplatize it at first and then once I see what's it's doing, I'll retemplatize it myself and learn something extra in the process. I've used templates a little for things like coverting int to string and vice versa with stringstream, but not much else.

I haven't messed with MonkeyShave's code yet, but I'll questions soon enough.

Thanks

 

[mikeblas]

Basically, I was thinking that if I coded my own string class, search and copy functions etc., then I wouldn't be depending on any stl methods. That way, if something's not fast and efficient enough, I'd have more control over making it better. In other words, I believe you were saying that no matter much I tweak things, stringstream and string are going to be bottlenecks.

Well, that's the rub, isn't it?

Maybe you don't need your own string class; maybe you just use pointers and arrays like I did. If you do, you have to worry about your own bugs.

There's lots of questions to ask: Is working through the code for the last bit of performance worth it to you? Does the code need to change lots during development? Does the STL bring things you can't tolerate (like exceptions, or memory usage)? Which do you think is more debuggable? Does your compiler work well with the STL? Is the STL well documented for your installation?

If you're on a team instead of workin' by yourself, then there's even more issues -- does the team even know STL and templates? Well enough to support your work if you were hit by a truck?

And so on. I used to think there were lots of arbitrary and stupid decisions about choosing technologies, or programming styles, and so on. But experience has tought me that some of these reasons are actually the most important -- not the least.

 

[Shadow2531]

O.K.

As a start, here's my interpretation of the MonkeyShave code. ( Using my stringstream version as a basis)

#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>

using namespace std;

inline void replaceAll( const string& s, const string& f, const string& r, string& build_it ) {
    if ( s.empty() || f.empty() || f == r || f.size() > s.size() || s.find(f) == string::npos ) {
        return;
    }
    build_it.clear();
    typedef string::const_iterator iter;
    iter i( s.begin() );
    const iter::difference_type f_size( distance( f.begin(), f.end() ) );
    for ( iter pos; ( pos = search( i , s.end(), f.begin(), f.end() ) ) != s.end(); ) {
        copy( i, pos, back_inserter( build_it )  );
        copy( r.begin(), r.end(), back_inserter( build_it ) );
        advance( pos, f_size);
        i = pos;
    }
    copy( i, s.end(), back_inserter( build_it ) );
}

int main() {
    const string source( 20971520, 'a');
    string test;
    replaceAll( source, "a", "4", test );
}

^^ That's kind of what I had in mind when I said I wanted to use an iterator.

That and the original template version are fast (with mingw), if I compile with -O3. (They complete in ~7 seconds for me. If I don't, they take ~22 seconds. My stringstream version completes in ~15 with mingw and ~9 with vc++. With my stringstream version, optimization for mingw doesn't make things faster. With these 2 I'm see an average of 30MB memory usage while one is running.( just looking at the task manager though ).

For the template version, in addition to changing distance_type to difference_type, I had to add 'typename' at the beginning to get it to compile under mingw.

typename std::iterator_traits<FwdIt2>::difference_type const find_length = std::distance( begin_find, end_find );

I'll still have to check out the zip file.

Edit:

I'm seeing ~6 second completion for the c string method with an average of 75MB memory usage while it's running.

 

[MonkeyShave]

Shadow, is your current program (end-to-end) fast and frugal enough for your users (and your boss, if applicable)?

If so, then it's probably time to move on to another program or another part of the same program.

If not, find out how fast the program or operation needs to be, then profile your program. Find the bottleneck and work on that.

If your search-and-replace operation is too slow as is, then you'll probably need to start looking at special cases (i.e. restricted alphabet, common sizes for find text, common sizes for replace text, pathalogical combinations of find pattern and source text) and work on those.

It's more likely that either a) your program is fast enough for the people who care, or b) the bottleneck is elsewhere.

There are a couple of ways to improve on my algorithm (using different sorts of iterators than back_insert_iterator) and if special cases are very important, you'l need to adapt any algorithm.

 

[mikeblas]

I'm seeing ~6 second completion for the c string method with an average of 75MB memory usage while it's running.

Memory usage should be static while it's running. Did you do a retail build?

If so, then it's probably time to move on to another program or another part of the same program.

Unless he wants to keep learning, of course.

 

[Shadow2531]

Shadow, is your current program (end-to-end) fast and frugal enough for your users (and your boss, if applicable)?

One of my uses for search and replace is for finding a string and replacing it with a path where each instance is spread out in small files like say, ~64KB with may a total of 60 instances. In that situation, my original substr() version (the one that takes like 3.5 hours to do the same that yours does in 7 seconds) still performs the task virtually instantly. It's only when I do large things like 20MB of As that it chokes. Basically, 7 seconds to replace every character in a 20MB file is fine. More or less tweaking for learning purposes.

Thanks

 

[Shadow2531]

Memory usage should be static while it's running. Did you do a retail build?Unless he wants to keep learning, of course.

Not until now. I tested yours straight up with just a std::string and your function, with optimizations and no generating code for debugging.

That takes yours down to ~5 seconds.

Memory usages stays at ~22MB for a second or two. Then, it jumps up to ~40mb and then ~80MB before completing.

With the copy() method, things stick ~22MB for a second, then jump up to ~40MB before completing.

(Not that it means anything; just happened to notice)

 

[Shadow2531]

Just for kicks, I tried using copy() with ostringstream via ostream_iterator<char>( build_it ).

~12 completion.

I then tried osteambuf_iterator<char>( build_it ) and I'm getting around 4 - 5 second completion, which is an improvement in completion time compared to using copy() to a string.

#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
#include <sstream>

using namespace std;

inline string replaceAll( const string& s, const string& f, const string& r ) {
    if ( s.empty() || f.empty() || f == r || f.size() > s.size() || s.find(f) == string::npos ) {
        return s;
    }
    ostringstream build_it;
    typedef string::const_iterator iter;
    iter i( s.begin() );
    const iter::difference_type f_size( distance( f.begin(), f.end() ) );
    for ( iter pos; ( pos = search( i , s.end(), f.begin(), f.end() ) ) != s.end(); ) {
        copy( i, pos,  ostreambuf_iterator<char>( build_it ) );
        copy( r.begin(), r.end(), ostreambuf_iterator<char>( build_it ) );
        advance( pos, f_size);
        i = pos;
    }
    copy( i, s.end(), ostreambuf_iterator<char>( build_it ) );
    return build_it.str();
}

int main() {
    const string source( 20971520, 'a');
    const string test( replaceAll(source, "a", "4") );
}

Over in the Ars forums, they often stress that if you are building a string (especially a large one), then it'll be faster with stringstream. I often test that to see if it's true.

I have a question though.

r.begin(), r.end(), f.begin(), f.end() and s.end() are all constant. Should I be storing those in iterater variables first and calling the variables in the loop instead of calling the functions each time through the loop. Basically, is calling s.end() to return the end any more expensive than grabbing it from a variable.

I tested it to see and don't see any difference, but that doesn't necessarily mean that there isn't a difference.

#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
#include <sstream>

using namespace std;

inline string replaceAll( const string& s, const string& f, const string& r ) {
    if ( s.empty() || f.empty() || f == r || f.size() > s.size() || s.find(f) == string::npos ) {
        return s;
    }
    ostringstream build_it;
    typedef string::const_iterator iter;
    const iter f_begin( f.begin() );
    const iter f_end( f.end() );
    const iter r_begin( r.begin() );
    const iter r_end( r.end() );
    const iter s_end( s.end() );
    iter i( s.begin() );
    const iter::difference_type f_size( distance( f_begin, f_end ) );
    for ( iter pos; ( pos = search( i , s_end, f_begin, f_end ) ) != s_end; ) {
        copy( i, pos,  ostreambuf_iterator<char>( build_it ) );
        copy( r_begin, r_end, ostreambuf_iterator<char>( build_it ) );
        advance( pos, f_size);
        i = pos;
    }
    copy( i, s_end, ostreambuf_iterator<char>( build_it ) );
    return build_it.str();
}

int main() {
    const string source( 20971520, 'a');
    const string test( replaceAll(source, "a", "4") );
}

thanks

 

[mikeblas]

With the copy() method, things stick ~22MB for a second, then jump up to ~40MB before completing.

I thought those were high, but then you posted your code. It makes sense, since you're allocating that memory for your strings. The code I posted wouldn't allocate more than a meg.

 

[majikman]

why not use strstr()??

http://www.cplusplus.com/ref/cstring/strstr.html

 

[mikeblas]

Over in the Ars forums, they often stress that if you are building a string (especially a large one), then it'll be faster with stringstream.

Faster than what? Very certainly, it's not the fastest way to build a string.

 

[Shadow2531]

^^

I assume at the least, << with a stream is faster than += with a string, but that goes back to what you previously said where I should step through to see what's actually going on. Plus .str() has to do its stuff for the stream.

But, yeh, I have no reason not to believe that there are faster ways.