Most efficient way in C++ to strip strings

Question

If I want to strip a string completely of its whitespaces, punctuation and numbers (i.e. anything that is not A-Z, a-z), what is the most efficient way of doing it in C++?

I tried this:

string strip(string in) {
    string final;
    for(int i = 0; i < in.length(); i++) {
        if(isalpha(in[i])) final += in[i];
    }
    return final;
}

It works as expected, but is too slow on strings with ~2000 characters. I figured out that the code causing this slowness is the isalpha() call.

So does anyone know of a better, more efficient way of stripping a string of everything except [A-Z][a-z] in C++?

At most, the string will be 20000 characters long and I need to strip it in <1 second.

Thanks in advance.

EDIT:

If I remove the if condition, the output will display instantly. But with the if condition, it will take about 1.6 seconds to display the output.

For trying out the code, use this: http://pastebin.com/g3NtBFaD and a normal 20k char string. Then try comparing.

Answer 1

A few thoughts which come to my mind, without having actually profiled your code:

1. Try passing std::string as reference-to-const to avoid a copy (in case your std::string implementation is not Copy-On-Write).
2. Reserve space in the std::string by calling reserve.
3. Avoid calling std::string::length repeatedly, memorize the value.
4. Avoid indexing the string repeatedly, use an iterator instead.

For what it's worth, you could try a different (more functional) way to implement this function. Some may consider this idiomatic, other will find it harder to read. Your call -maybe just for the fun of it, to see how it performs (remember to enable optimizations!):

#include <algorithm>
#include <functional>
#include <locale>
#include <string>

std::string strip( const std::string &s ) {
    std::string result;
    result.reserve( s.length() );

    std::remove_copy_if( s.begin(),
                         s.end(),
                         std::back_inserter( result ),
                         std::not1( std::ptr_fun( isalpha ) ) );

    return result;
}

Answer 2

I would add a:

final.reserve(in.length());

to avoid allocations when doing the +=.

You could try this code, but I doubt it will be much faster:

string strip(const string& in) {
    char final[2000];
    char* cursor = final;
    for(string::const_iterator c = in.begin(), end = in.end(); c != end; ++c) {
        char cc = *c;
        if ((cc >= 'a' && cc <= 'z') || (cc >= 'A' && cc <= 'Z'))
        {
            *cursor = cc;
            ++cursor;
        }
    }
    *cursor = 0;
    return final;
}

Notice that the in parameter is now passed by reference. One possible, though unlikely, improvement would be to create a 256 bool lookup table that stores if a given char is alpha:

string strip(const string& in) {
    bool lut[256];
    for (int i = 0; i < 256; ++i)
    {
        lut[i] = (i >= 'a' && i <= 'z') || (i >= 'A' && i <= 'Z');
    }
    string final;
    final.reserve(in.length());
    for(int i = 0; i < in.length(); i++) {
        if (lut[in[i]]) final += in[i];
    }
    return final;
}

Note that the LUT is populated everytime this code is called, if the string is > 20.000 this time should be insignificant though.

Answer 3

You may try following C++11 code which allocates memory and changes the final string size only once

std::string strip(std::string in) 
  {
  in.erase(std::remove_if(in.begin(), in.end(), [] (std::string::value_type ch)
      { return !isalpha(ch); }
    ), in.end());
  return in;
  }

Answer 4

Here's another benchmark, showing yet another possibility that may be worth considering, if you can:

#include <algorithm>
#include <string>
#include <iterator>
#include <iostream>
#include <vector>
#include <functional>
#include <ctype.h>
#include <time.h>
#include <limits.h>

class not_isalpha {
    bool table[UCHAR_MAX];
public:
    not_isalpha() {
        for (int i=0; i<UCHAR_MAX; i++)
            table[i] = !isalpha(i);
    }

    bool operator()(char input){
        return table[(unsigned char)input];
    }
};

template <class T>
T gen_random(size_t len) {
    T x;
    x.reserve(len);

    std::generate_n(std::back_inserter(x), len, rand);
    return x;
}

template <class Container, class stripper>
clock_t test(Container const &input, Container &result, stripper strip) {   
    result.reserve(input.size());
    clock_t start = clock();
    std::remove_copy_if(input.begin(), input.end(), std::back_inserter(result), strip);
    return clock() - start;
}

void show(std::string const &label, clock_t ticks) {
    std::cout << label << ": " << ticks/(double)CLOCKS_PER_SEC << " Seconds\n";
}

int main(){
    typedef std::vector<char> T;
    static const size_t size = 50000000; 

    T x(gen_random<T>(size));
    T result;

    show("not_isalpha, vector", test(x, result, not_isalpha()));
    show("::isalpha, vector", test(x, result, std::not1(std::ptr_fun(isalpha))));

    std::string input2(x.begin(), x.end());
    std::string result2;

    show("not_isalpha, string", test(input2, result2, not_isalpha()));
    show("::isalpha, string", test(input2, result2, std::not1(std::ptr_fun(isalpha))));

    return 0;
}

At least in my testing, with both VC++ (10), and g++ (4.7.0), std::vector comes out faster than string.

VC++ 10:

not_isalpha, vector: 0.246 Seconds
::isalpha, vector: 0.401 Seconds
not_isalpha, string: 0.473 Seconds
::isalpha, string: 0.631 Seconds

g++ 4.7.0:

not_isalpha, vector: 0.212 Seconds
::isalpha, vector: 0.382 Seconds
not_isalpha, string: 0.285 Seconds
::isalpha, string: 0.413 Seconds

Using our own table-driven version of isalpha helps speed quite a bit compared to using ::isalpha, but using std::vector improves speed even more, especially with VC++ (though the difference is fairly substantial with g++ as well).

For those who like to compare compilers, it's worth noting that g++ is not only faster overall, but also more consistently fast. With g++, the worst case is only about two times slower than the fastest. With VC++, the worst case is about three times slower.

Answer 5

Use the C locale. On some locales, isalpha and friends might be very slow.

E.g. on UNIX

LANG=C
export LANG

or use std::locale to activate the C locale from code

std::locale::global(std::locale::classic); // untested draft

Background

For an example of how locales can slowdown performance of e.g. UNIX sort(1) by a factor of 20x, see this old answer:

• https://stackoverflow.com/questions/7124489/unix-sort-command-takes-much-longer-depending-on-where-it-is-executed-fastest/7150015#7150015

Answer 6

Sometimes, one needs to use benchmarks.

An idiomatic C++ solution is likely to be better optimized, so Andrey's and Frerich's solutions are both strong contenders.

The code exposed below gives the following results with gcc 4.3.2 and -O2:

• Input1: "afoiahge m8hfw fewu8 n hv ghwvoiwbegh2390ty3t80ytgh8ghng8hg24u8b vh2vn289vh2gh28g9jfhfuweghwu2hbvgfw22ghb84ty2bgv2nfbukbvsdbvwuivbnbvbnn hf wgwg gwev wgbv23t4 1sv4gbwer14hh414ernhe 01e4g 1e 1h4ghwerh14re e4hj 14yv y344yjd1vh h 1e6"

• Input2: the string you proposed

• Original: 1: 3268, 2: 138894

• From Andrey's: 1: 1243, 2: 65469

• From Frerich's: 1: 1965, 2: 140818

Therefore, Andrey's solution offers a solid 2x speed up over your proposed solution. Much better.

Their strategy differ though, because Andrey copies the whole string in one swoop and then removes the parts that do not fit, while Frerich only copy the right parts to begin with.

I would select Frerich's approach (despite it being stlightly slower here), just to avoid large unused copies if memory is a concern. Note that if you have an inkling about the distribution, then you can adjust the amount of memory reserved.

Code:

#include <sys/time.h>

#include <algorithm>
#include <iostream>

namespace bench {

  template <typename Func>
  double benchmark(Func f, size_t iterations)
  {
    f();

    timeval a, b;
    gettimeofday(&a, 0);
    for (; iterations --> 0;)
    {
      f();
    }
    gettimeofday(&b, 0);
    return (b.tv_sec * (unsigned int)1e6 + b.tv_usec) -
           (a.tv_sec * (unsigned int)1e6 + a.tv_usec);
  }

}

namespace test {

  bool isalpha(char c) { return (c >= 'a' and c <= 'z') or (c >= 'A' and c <= 'Z'); }
  bool notalpha(char c) { return not isalpha(c); }

  struct NotAlpha {
    bool operator()(char c) { return notalpha(c); }
  };

  // Roshal
  std::string strip1(std::string const& in) {
      std::string final;
      for(size_t i = 0; i < in.length(); i++) {
          if(isalpha(in[i])) final += in[i];
      }
      return final;
  }

  // Andrey
  std::string strip2(std::string const& s) {
    std::string in = s;
    in.erase(std::remove_if(in.begin(), in.end(), NotAlpha()), in.end());
    return in;
  }

  // Frerich Raabe
  std::string strip3( const std::string &s ) {
    std::string result;
    result.reserve( s.length() );

    std::remove_copy_if( s.begin(),
                         s.end(),
                         std::back_inserter( result ),
                         NotAlpha() );

    return result;
  }

} // namespace test

namespace bench {
  struct Stripper {
    typedef std::string (*Func)(std::string const&);

    Stripper(Func f, std::string const& s): _func(f), _s(s) {}

    void operator()() { _func(_s); }

    Func const _func;
    std::string const _s;
  };
}

int main(int argc, char* argv[]) {

  std::string const ref = argc == 1 ? "Let's make an example" : argv[1];

  bench::Stripper s1(test::strip1, ref);
  bench::Stripper s2(test::strip2, ref);
  bench::Stripper s3(test::strip3, ref);

  double const r1 = benchmark(s1, 1000);
  double const r2 = benchmark(s2, 1000);
  double const r3 = benchmark(s3, 1000);

  std::cout << "1: " << r1 << "\n";
  std::cout << "2: " << r2 << "\n";
  std::cout << "3: " << r3 << "\n";
}

Answer 7

Try calling reserve(2000) on your final string before using it. Also take a const ref as argument.

Edit:

I would suspect that on Unix, the isalpha function is performing a lot more work to support Unicode, and you are only interested in the ASCII range. It's still a big leap, but you might try replacing it with a custom comparison, like if ((in[i] <= 'Z' && in[i] >= 'A') || (in[i] >= 'a' && in[i] <= 'z')).

Answer 8

I suggest that it is not the isalpha() call that is taking the time but rather the two std::string::operator[] calls and/or the std::string::operator+= call.

You could probably speed this loop up by using an iterator to reference in, thus avoiding std::string::operator[], and appending the character will be faster using std::string::push_back and if you initially expanding final to have the same initial capacity as in.

Passing the unmodified input string as a const reference may also help but will only be significant if you are calling the function itself iteratively.

string strip( const string& in) 
{
    final.reserve( in.length() ) ;
    string::iterator it;
    for ( it=str.begin() ; it < str.end(); it++ )
    {
        if( isalpha( *it ) )
        {
            final.push_back( *it ) ;
        }
    }

    return final  ;
}

All that said, I strongly suggest that your use the profiler or add timing instrumentation to the code to reveal the true performance hog. The timings you suggest do not seem likely - something else is happening here I think.

Answer 9

This is a quick method. Maybe a bit naughty writing directly into the string contents, but the new c++ standard guarantees that the string will be contiguous (according to another stackoverflow post).

inline bool isAZaz(char ch) {
    return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z');
}

void strip(std::string const& s, std::string* result)
{
    result->clear();
    if (s.empty()) {
        return;
    }
    result->resize(s.size());

    char ch;
    char const* p = s.c_str();
    char const* e = p + s.size();
    char* o = &(*result)[0];
    char const* r = o;
    for (; p < e; ++p) {
        ch = *p;
        if (isAZaz(ch)) {
            *o++ = (ch);
        }
    }
    result->resize(o - r);
}

Executes in 0.000037 seconds on my PC, compared to 0.000759 for your original method, so roughly 20 times faster. using ::isalpha instead of a handwritten check takes 0.000096 seconds (3x slower my version).