24
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How fast/slow is your computer? Using a normal machine with about 100 mil ops per second, I think 2000 chars should be short enough. \$\endgroup\$ – zw324 Apr 26 '12 at 10:49
  • 2
    \$\begingroup\$ If this code doesn't run in < 1 second for 2000 character long strings you must be sitting on a c64 or something ;) \$\endgroup\$ – Andreas Brinck Apr 26 '12 at 10:49
  • \$\begingroup\$ The testing server is a Pentium III 800MHz computer.. \$\endgroup\$ – Roshnal Apr 26 '12 at 10:50
  • 1
    \$\begingroup\$ Replace isAlpha with your own comparisons perhaps, although I suspect it may be your += on the string that takes a while if you're not reserving capacity in advance. \$\endgroup\$ – Joachim Isaksson Apr 26 '12 at 10:50
  • 7
    \$\begingroup\$ Push the 'Turbo' button :) \$\endgroup\$ – Martin James Apr 26 '12 at 10:50
17
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ "in case your std::string implementation is not Copy-On-Write" -- none that I know of is. "Avoid calling std::string::length repeatedly, memorize the value." -- this is a non-issue, the lookup is constant. "Avoid indexing the string repeatedly, use an iterator instead." -- non-issue aswell, it's a simple read. Iterators and indexing are both equally fast. And if you're going for the functional-y route, please don't use function pointers. They slow down the code considerably as opposed to function objects. \$\endgroup\$ – Xeo Apr 26 '12 at 11:16
  • \$\begingroup\$ @Xeo: According to gcc.gnu.org/onlinedocs/libstdc++/manual/strings.html libstdc++'s string is Copy-On-Write. No idea to which version(s) it applies. Regarding O(1) complexity of std::string::length - that's only what's specified but maybe the OP's implementation is flawed (there seems to be something fishy given how slow it is). Same is true for your other comments, just because most implementations comply to the specifications, this is not true for all of them (and I'm saying this as somebody who hsa to use MSVC6 a lot...). \$\endgroup\$ – Frerich Raabe Apr 26 '12 at 11:30
  • \$\begingroup\$ @Xeo: In general, any sufficiently old compiler will trigger every bug in the standard (template) libraries you can think of. So be careful when taking things for granted. ;-) \$\endgroup\$ – Frerich Raabe Apr 26 '12 at 11:34
  • \$\begingroup\$ @FrerichRaabe: personally, I care little for outdated compilers. Still, your solution is the fastest that I tested (redefining isalpha and using an inline predicate). Which is comforting me that theory does help, since it's perhaps the most conservative with regard to memory allocation and copies. \$\endgroup\$ – Matthieu M. Apr 26 '12 at 11:49
  • \$\begingroup\$ @MatthieuM.: Glad to hear that increasing the level of abstraction actually improves the runtime efficiency of the code for a change. ;-) \$\endgroup\$ – Frerich Raabe Apr 26 '12 at 11:51
10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Tried that, no improvement... \$\endgroup\$ – Roshnal Apr 26 '12 at 10:53
  • \$\begingroup\$ Still takes as much as long. But if I remove the if condition (which checks for A-Z a-z) its really fast.. \$\endgroup\$ – Roshnal Apr 26 '12 at 11:00
  • \$\begingroup\$ @Roshnal Try it with a lookup table, might be faster. \$\endgroup\$ – Andreas Brinck Apr 26 '12 at 11:05
  • \$\begingroup\$ @Clifford No, I suspect it's something else as well. \$\endgroup\$ – Andreas Brinck Apr 26 '12 at 11:06
  • \$\begingroup\$ If the string is indeed Unicode, it would beed either a very large lookup table or some implicit conversions to char. Even if the string is Unicode, 2000 characters is.. not that many. How could it take a human-noticeable time? \$\endgroup\$ – Martin James Apr 26 '12 at 11:10
7
\$\begingroup\$

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;
  }
\$\endgroup\$
  • \$\begingroup\$ You mean except in the unnecessary copy in the argument? \$\endgroup\$ – DeadMG Apr 26 '12 at 11:02
  • 1
    \$\begingroup\$ @DeadMG I can eliminate that copy, taking into account that in is passed by value \$\endgroup\$ – Andrey Apr 26 '12 at 11:03
  • \$\begingroup\$ If the argument is an lvalue, you just unnecessarily copied it. There is no reason to take by vaue here because you do not need to own the argument string. \$\endgroup\$ – DeadMG Apr 26 '12 at 11:04
  • \$\begingroup\$ Gives me an error in the , in.end() part.. \$\endgroup\$ – Roshnal Apr 26 '12 at 11:08
  • \$\begingroup\$ @Roshnal Tested in VC2010. If your compiler doesn't support C++11, you have to replace the lambda with a predicate. \$\endgroup\$ – Andrey Apr 26 '12 at 11:11
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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:

\$\endgroup\$
  • \$\begingroup\$ @Roshnal can you provide any feedback on this? In all fairness I think this was unjustly moved to codereview, and, though interesting, all micro-optimization beyond final.reserve(in.size()) smells like premature optimization. \$\endgroup\$ – sehe Apr 27 '12 at 8:45
3
\$\begingroup\$

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";
}
\$\endgroup\$
  • \$\begingroup\$ Can you post the test result using the worst case string included in the OP? \$\endgroup\$ – Andreas Brinck Apr 26 '12 at 11:55
  • \$\begingroup\$ I guess that, just for the record, you should verify that the solutions you benchmark actually produce the same results. \$\endgroup\$ – Frerich Raabe Apr 26 '12 at 11:55
  • \$\begingroup\$ Furthermore, in benachmark, you call f() up front - why is that? Finally, your program doesn't run my solution at all. Both s2 and s3 use test::strip2. If you actually run my version, you will see that it's much slower. So I'd actually go for Andrey's version. \$\endgroup\$ – Frerich Raabe Apr 26 '12 at 12:05
  • \$\begingroup\$ Andrey’s original code was better than your adaptation because it passes the argument by value to take advantage of move construction from temporaries. Oh, and +1 for ISO 646 keywords. \$\endgroup\$ – Konrad Rudolph Apr 26 '12 at 12:06
  • \$\begingroup\$ @AndreasBrinck: done. It's a alpha string so unsurprisingly Andrey's solution performs very well. \$\endgroup\$ – Matthieu M. Apr 26 '12 at 12:35
2
\$\begingroup\$

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')).

\$\endgroup\$
  • \$\begingroup\$ Nope, no improvement.. \$\endgroup\$ – Roshnal Apr 26 '12 at 10:55
  • \$\begingroup\$ Still its slow (no improvement whatsoever) \$\endgroup\$ – Roshnal Apr 26 '12 at 11:18
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ No, when I only remove the if condition in the shown code, the output is instantly shown, even if the final += in[i] part is still there. \$\endgroup\$ – Roshnal Apr 26 '12 at 10:58
  • \$\begingroup\$ @Roshnal: Possibly because the compiler can optimise it out to a string copy. If the call assigns the string to itself, it might even optimise out the call altogether (if it were very smart). Something is wrong here; isalpha() is a very simple function (in fact it is a macro, so you can see what it does in the ctype.h file). \$\endgroup\$ – Clifford Apr 26 '12 at 11:26
1
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ What are you doing here?! Just use iterators instead of pointers. Why do you pass the argument as a pointer? Unorthodox, error-prone and unnecessary. Why do you declare ch outside of the loop? And while I agree that using iterators is nice, it won’t change the the performance – at least not nearly as drastic as observed by you. That’s probably due to the removal of an unnecessary copy and avoiding isalpha. Oh, and the code is UB if the string is empty. \$\endgroup\$ – Konrad Rudolph Apr 26 '12 at 18:30
  • \$\begingroup\$ You can thank Microsoft for the poor iterator performance on visual studio compiler. the fact of the matter is that the correct way of doing things often isn't optimal. Yes perhaps a check for empty strings is an idea to prevent an exception accessing element zero. I think your point that using iterators won't change performance as much as I have observed by actually profiling the code is a little naive. \$\endgroup\$ – Pete Apr 27 '12 at 6:10
  • \$\begingroup\$ Oh, and passing the output parameter as a pointer makes it more obvious that it is an output parameter in calling code. See the Qt coding guidelines. \$\endgroup\$ – Pete Apr 27 '12 at 6:13
  • \$\begingroup\$ Iterators on strings are just char* when you compile with optimisations enabled. Going to Qt for coding guidelines is like going to the pope for the pill. Don’t use out parameters at all, use return values. VS (and every other modern compiler) optimises this. As for pointer-versus-index, there is virtually no difference. Again, this is optimised anyway. \$\endgroup\$ – Konrad Rudolph Apr 27 '12 at 6:59
  • 1
    \$\begingroup\$ I'd have to agree with you there. Sometimes you have to be pragmatic, especially when optimizing. If you were to manually vectorize this loop, then you would have to use pointers... \$\endgroup\$ – Pete Apr 27 '12 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.