我尝试了以下方法：
string strip(string in) {
string final;
for(int i = 0; i < in.length(); i++) {
if(isalpha(in[i])) final += in[i];
}
return final;
}
它可以按预期工作，但是对于带有〜2000个字符的字符串来说太慢了。我发现导致这种缓慢的代码是
isalpha()调用。那么，有人知道一种更好，更有效的方法来剥离C ++中[AZ] [az]以外的所有字符串的方式吗？
最多，该字符串的长度为20000个字符，我需要在<1秒之内将其剥离。
预先感谢。
编辑：
如果取消
if条件，输出将立即显示。但是在if条件下，将显示输出大约需要1.6秒。要尝试代码，请使用以下代码：http://pastebin.com/g3NtBFaD和正常的20k字符字符串。然后尝试比较。
#1 楼
在没有真正分析您的代码的情况下，我想到了一些想法：尝试传递
std::string作为对const的引用以避免复制（以防您复制std::string的实现不是复制-on-Write）。通过调用
std::string来保留reserve中的空间。避免重复调用
std::string::length，记住值。避免重复索引字符串，而应使用迭代器。
>
要了解它的价值，您可以尝试使用其他（功能更强大）的方法来实现此功能。有些人可能认为这很惯用，而另一些人则很难阅读。您的通话-可能只是为了好玩，以了解其性能（请记住启用优化！）：
#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;
}
评论
\ $ \ begingroup \ $
“如果您的std :: string实现不是写时复制”-我所不知道的是。 “避免重复调用std :: string :: length，记住该值。” -这是非问题，查找是恒定的。 “避免重复索引字符串，而应使用迭代器。” -同样不是问题，这很简单。迭代器和索引都同样快。而且，如果您要使用功能Y路线，请不要使用函数指针。与功能对象相反，它们大大降低了代码速度。
\ $ \ endgroup \ $
– Xeo
2012年4月26日上午11:16
\ $ \ begingroup \ $
@Xeo：根据gcc.gnu.org/onlinedocs/libstdc++/manual/strings.html libstdc ++的字符串为“写时复制”。不知道它适用于哪个版本。关于std :: string :: length的O（1）复杂度-仅是指定的内容，但OP的实现可能存在缺陷（考虑到它的执行速度，似乎有些可疑）。您的其他评论也是如此，只是因为大多数实现都符合规范，而并非所有规范都如此（我是说很多人经常使用MSVC6 ...）。
\ $ \ endgroup \ $
–弗里希·拉贝（Frerich Raabe）
2012年4月26日上午11:30
\ $ \ begingroup \ $
@Xeo：通常，任何足够老的编译器都会触发您可以想到的标准（模板）库中的每个错误。因此，在将事情视为理所当然时要小心。 ;-)
\ $ \ endgroup \ $
–弗里希·拉贝（Frerich Raabe）
2012年4月26日上午11:34
\ $ \ begingroup \ $
@FrerichRaabe：就个人而言，我不太关心过时的编译器。不过，您的解决方案是我测试过的最快的方法（重新定义isalpha并使用内联谓词）。令我感到欣慰的是，该理论确实有所帮助，因为它在内存分配和复制方面可能是最保守的。
\ $ \ endgroup \ $
– Matthieu M.
2012年4月26日上午11:49
\ $ \ begingroup \ $
@MatthieuM .：很高兴听到增加抽象级别实际上可以提高更改代码的运行时效率。 ;-)
\ $ \ endgroup \ $
–弗里希·拉贝（Frerich Raabe）
2012年4月26日上午11:51
#2 楼
我会添加一个：final.reserve(in.length());
以避免在进行
+=时分配。您可以尝试使用此代码，但我怀疑会更快：
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;
}
请注意，现在已通过引用传递了
in参数。一种可能（虽然不太可能）的改进方法是创建一个256 bool查找表，该表存储给定的char是否为alpha：代码被调用，如果字符串> 20.000则这次无关紧要。评论
\ $ \ begingroup \ $
尝试过，没有任何改善...
\ $ \ endgroup \ $
– Roshnal
2012年4月26日上午10:53
\ $ \ begingroup \ $
仍然需要尽可能多的时间。但是，如果我删除if条件（检查A-Z a-z），则它的速度非常快。
\ $ \ endgroup \ $
– Roshnal
2012年4月26日上午11:00
\ $ \ begingroup \ $
@Roshnal尝试使用查找表，可能会更快。
\ $ \ endgroup \ $
–安德烈亚斯·布林克（Andreas Brinck）
2012年4月26日上午11:05
\ $ \ begingroup \ $
@Clifford不，我怀疑还有其他问题。
\ $ \ endgroup \ $
–安德烈亚斯·布林克（Andreas Brinck）
2012年4月26日在11:06
\ $ \ begingroup \ $
如果字符串确实是Unicode，则它将成为很大的查找表或对char的一些隐式转换。即使字符串是Unicode，2000个字符也不是很多。怎么会花人类的时间？
\ $ \ endgroup \ $
–马丁·詹姆斯（Martin James）
2012年4月26日上午11:10
#3 楼
您可以尝试遵循C ++ 11代码分配内存并仅更改一次最终字符串大小一次。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;
}
评论
\ $ \ begingroup \ $
你的意思是除了在参数中不必要的副本外？
\ $ \ endgroup \ $
– DeadMG
2012年4月26日上午11:02
\ $ \ begingroup \ $
@DeadMG考虑到in是按值传递的，我可以消除该副本
\ $ \ endgroup \ $
–安德烈
2012年4月26日在11:03
\ $ \ begingroup \ $
如果参数是左值，则只需复制它即可。这里没有理由大惊小怪，因为您不需要拥有参数字符串。
\ $ \ endgroup \ $
– DeadMG
2012年4月26日上午11:04
\ $ \ begingroup \ $
在in.end（）部分给我一个错误。
\ $ \ endgroup \ $
– Roshnal
2012年4月26日上午11:08
\ $ \ begingroup \ $
@Roshnal在VC2010中测试。如果您的编译器不支持C ++ 11，则必须用谓词替换lambda。
\ $ \ endgroup \ $
–安德烈
2012年4月26日上午11:11
#4 楼
这是另一个基准测试，它显示了另一个可能值得考虑的可能性，如果可能的话：#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;
}
至少在我的测试中，同时使用VC ++（10）和g ++ （4.7.0），
std::vector的输出速度比字符串快。 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
与使用
isalpha相比，使用我们自己的表驱动版本的::isalpha可以大大提高速度，但是使用std::vector可以进一步提高速度，尤其是在VC ++上（尽管g ++的差异也相当大）。对于那些喜欢比较编译器的人来说，值得注意的是g ++不仅在整体上更快，而且更加一致。使用g ++，最坏的情况仅比最快的情况慢大约两倍。使用VC ++时，最坏的情况要慢大约三倍。
#5 楼
使用C语言环境。在某些语言环境中，isalpha和朋友可能非常慢。例如在UNIX上
LANG=C
export LANG
或使用std :: locale从代码激活C语言环境
std::locale::global(std::locale::classic); // untested draft
背景
有关语言环境如何降低例如UNIX
sort(1)的20倍，请参见以下旧答案：https://stackoverflow.com/questions/7124489/unix-sort-command-takes-much-longer-depending在执行最快的地方/ 7150015＃7150015
评论
\ $ \ begingroup \ $
@Roshnal您可以对此提供任何反馈吗？公平地说，我认为这是不公正地转移到了codereview上的，尽管有趣，但除final.reserve（in.size（））之外的所有微优化都闻起来像是过早的优化。
\ $ \ endgroup \ $
–sehe
2012年4月27日在8:45
#6 楼
有时，需要使用基准。惯用的C ++解决方案可能会得到更好的优化，因此Andrey和Frerich的解决方案都是强有力的竞争者。使用gcc 4.3.2和-O2的以下结果：
Input1：
"afoiahge m8hfw fewu8 n hv ghwvoiwbegh2390ty3t80ytgh8ghng8hg24u8b vh2vn289vh2gh28g9jfhfuweghwu2hbvgfw22ghb84ty2bgv2nfbukbvsdbvwuivbnbvbnn hf wgwg gwev wgbv23t4 1sv4gbwer14hh414ernhe 01e4g 1e 1h4ghwerh14re e4hj 14yv y344yjd1vh h 1e6" Input2：您建议的字符串
原始值：1：3268，2：138894
来自安德烈（Andrey）：1：1243、2：65469
来自弗雷里希：1：1965、2：140818
因此，安德烈（Andrey）的解决方案提供了比建议的解决方案高2倍的速度。更好。
他们的策略有所不同，因为Andrey一口气复制了整个字符串，然后删除了不合适的部分，而Frerich只复制了正确的部分开始。
我会选择Frerich的方法（尽管这里的速度要慢一些），只是为了避免由于内存问题而导致的大量未使用的副本。请注意，如果您对发行版有所了解，则可以调整保留的内存量。
代码：
#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";
}
评论
\ $ \ begingroup \ $
可以使用OP中包含的最坏情况字符串发布测试结果吗？
\ $ \ endgroup \ $
–安德烈亚斯·布林克（Andreas Brinck）
2012年4月26日上午11:55
\ $ \ begingroup \ $
我想，仅作记录，您应该验证基准测试的解决方案实际上产生了相同的结果。
\ $ \ endgroup \ $
–弗里希·拉贝（Frerich Raabe）
2012年4月26日上午11:55
\ $ \ begingroup \ $
此外，在benachmark中，您预先调用了f（）-为什么呢？最后，您的程序根本无法运行我的解决方案。 s2和s3都使用test :: strip2。如果您实际运行我的版本，您会发现它要慢得多。所以我实际上会选择Andrey的版本。
\ $ \ endgroup \ $
–弗里希·拉贝（Frerich Raabe）
2012年4月26日12:05
\ $ \ begingroup \ $
安德烈（Andrey）的原始代码比您的改编更好，因为它按值传递了参数，以利用临时人员的移动构造。哦，ISO 646关键字为+1。
\ $ \ endgroup \ $
–康拉德·鲁道夫（Konrad Rudolph）
2012年4月26日12:06
\ $ \ begingroup \ $
@AndreasBrinck：完成了。这是一个Alpha字符串，因此毫不奇怪，Andrey的解决方案性能很好。
\ $ \ endgroup \ $
– Matthieu M.
2012年4月26日在12:35
#7 楼
尝试在最终字符串上调用reserve（2000），然后再使用它。还可以将const ref作为参数。编辑：
我怀疑在Unix上，
isalpha函数正在执行更多工作来支持Unicode，而您只是对ASCII范围感兴趣。这仍然是一个很大的飞跃，但是您可以尝试使用自定义比较（例如if ((in[i] <= 'Z' && in[i] >= 'A') || (in[i] >= 'a' && in[i] <= 'z'))）替换它。评论
\ $ \ begingroup \ $
不，没有改善。
\ $ \ endgroup \ $
– Roshnal
2012年4月26日上午10:55
\ $ \ begingroup \ $
仍然很慢（没有任何改善）
\ $ \ endgroup \ $
– Roshnal
2012年4月26日上午11:18
#8 楼
我建议花时间的不是isalpha()调用，而是两个std::string::operator[]调用和/或std::string::operator+=调用。因此，避免使用in，并使用std::string::operator[]附加字符会更快，并且如果您最初将std::string::push_back扩展为具有与final相同的初始容量。仅当您迭代地调用函数本身时才有意义。真正的表演猪。您建议的时机似乎不太可能-我认为这里正在发生其他事情。评论
\ $ \ begingroup \ $
不，当我只删除所示代码中的if条件时，即使最后的+ = in [i]部分仍然存在，输出也会立即显示。
\ $ \ endgroup \ $
– Roshnal
2012年4月26日上午10:58
\ $ \ begingroup \ $
@Roshnal：可能是因为编译器可以将其优化为字符串副本。如果调用将字符串分配给它自己，它甚至可能完全优化调用（如果它非常聪明）。这里不对劲; isalpha（）是一个非常简单的函数（实际上，它是一个宏，因此您可以在ctype.h文件中看到它的作用）。
\ $ \ endgroup \ $
–克利福德
2012年4月26日上午11:26
#9 楼
这是一种快速的方法。直接写入字符串内容可能有点顽皮，但是新的c ++标准保证了该字符串将是连续的（根据另一个stackoverflow文章）。在我的PC上为0.000037秒，而您的原始方法为0.000759秒，因此快了大约20倍。使用:: isalpha代替手写检查需要0.000096秒（我的版本慢3倍）。
评论
\ $ \ begingroup \ $
你在这里做什么？只需使用迭代器而不是指针即可。为什么将参数作为指针传递？非传统的，容易出错的和不必要的。为什么在循环外声明ch？尽管我同意使用迭代器是不错的选择，但它不会改变性能-至少不会像您观察到的那样剧烈。这可能是由于删除了不必要的副本并避免使用isalpha。哦，如果字符串为空，则代码为UB。
\ $ \ endgroup \ $
–康拉德·鲁道夫（Konrad Rudolph）
2012年4月26日18:30
\ $ \ begingroup \ $
您可以感谢Microsoft在Visual Studio编译器上糟糕的迭代器性能。事实是，做事的正确方法通常不是最佳的。是的，也许检查空字符串是一种防止异常访问元素零的想法。我认为您的观点是，使用迭代器不会像我通过实际分析代码所观察到的那样改变性能，这有点天真。
\ $ \ endgroup \ $
– Pete
2012年4月27日在6:10
\ $ \ begingroup \ $
哦，将输出参数作为指针传递时，很明显它是调用代码中的输出参数。请参阅Qt编码准则。
\ $ \ endgroup \ $
– Pete
2012年4月27日在6:13
\ $ \ begingroup \ $
在启用优化的情况下进行编译时，字符串的迭代器只是char *。向Qt寻求编码指南就像去往罗马教皇。完全不用参数，请使用返回值。 VS（以及所有其他现代编译器）对此进行了优化。至于指针对索引，实际上没有区别。同样，无论如何都对它进行了优化。
\ $ \ endgroup \ $
–康拉德·鲁道夫（Konrad Rudolph）
2012年4月27日6:59
\ $ \ begingroup \ $
我必须在那里同意你的看法。有时您必须务实，尤其是在优化时。如果要手动向量化此循环，则必须使用指针。
\ $ \ endgroup \ $
– Pete
2012年4月27日在8:41
评论
您的计算机有多快/慢？使用每秒约1亿次操作的普通机器，我认为2000个字符应该足够短。如果这段代码不能在<1秒内运行2000个字符长的字符串，则您必须坐在c64上；）
测试服务器是奔腾III 800MHz计算机。.
也许用您自己的比较替换isAlpha，尽管我怀疑如果您不提前保留容量，它可能是您在字符串上的+ =会花费一些时间。
按下“涡轮”按钮:)