2

我正在开发一个 C/C++ 函数来修剪额外的空白，除了非常大的数据集的 1 个空白。这是我的功能：

       void  iterative_trim_whitespace(const char* src, char* target){


             bool hitspace(*src = ' ');
             while (*src != '\x0'){
                if (!hitspace){
                    *target++ = *src++;
                } 
                else{
                    src++;
                }
                if (isspace(*src)){
                    hitspace = true;
                }  
                else{

                    hitspace = false;
                }
             }

         }

我写了一个递归函数来做同样的事情。如果你愿意，我可以提供。但是，对于具有大字符串的非常大的数据，递归函数调用堆栈开销可能会令人望而却步。有谁知道在 C/C++ 中最快的方法？我熟悉标准模板库和 Boost 模板库。但是我认为本机 C/C++ 会比 C++ 模板更快。

4

6 回答 6

5

我将假设您的意图与“修剪”通常暗示的有点不同。“修剪”通常用于表示从字符串的开头和/或结尾删除额外的空格，但您似乎意味着输入中每个地方都有一系列空格，您希望输出中有一个空格。

我还假设您设置在处理 C 样式字符串的类 C 实现上。如果这不是给定的，那么仅使用迭代器和标准算法将变得更加简单和清晰。

假设是这种情况，我想我会做更多这样的事情：

bool copy_word(char *&dest, char const *&src) { 
    while (isspace(*(unsigned char *)src))
        ++src;

    while (*src && *src != ' ') {
        *dest = *src;
        ++dest;
        ++src;
    }
    return *src != '\0';
}

void trim_whitespace(char *dest, char const *src) { 
    while (copy_word(dest, src))
        *dest++ = ' ';
    *dest = '\0';
}

这里有两点需要牢记：首先，当您要执行一系列操作时（例如，跳过空白，然后复制非空白），将其编码为序列可能更简洁，而不是编码为通过单个循环的不同路线。其次，当您使用 时isspace，您必须1将操作数强制转换为某种无符号类型以避免 UB。

编辑：为了它的价值，我整理了一个小测试/基准程序，以查看我的代码与 OP 答案中的代码相比如何。

#include <ctype.h>
#include <time.h>
#include <vector>
#include <set>
#include <deque>
#include <iostream>
#include <string>
#include <algorithm>

void  iterative_trim_whitespace(const char* src, char* target){
    bool firstspace(true);
    while (*src != '\x0'){
        if (firstspace){
            *target++ = *src++;
        } 
        else{
            src++;
        }
        if (firstspace && isspace(*(src - 1))){
            firstspace    = false;
        }  
        else{
            firstspace = true;
        }
    }
    *target = '\x0';
}

struct my_isspace {
    bool operator()(char ch) {
        return ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r' || ch == '\v';
    }
};

bool copy_word(char *&dest, char const *&src) { 
    my_isspace check;
    while (check((*src)))
        ++src;

    while (*src && !check(*src))
        *dest++ = *src++;   
    return *src != '\0';
}

void trim_whitespace(char *dest, char const *src) { 
    while (copy_word(dest, src))
        *dest++ = ' ';
    *dest = '\0';
}

void show(std::string const &label, double t) { 
    std::cout << "Time for " << label << " " << t << " seconds\n";
}

template <class test, class T>
double timer(test t, T a, T b) {
    clock_t start = clock();
    t(a, b);
    clock_t stop = clock();
    return double(stop-start)/CLOCKS_PER_SEC;
}

void generate_string(std::vector<char> &dest, size_t size) { 
    for (int i=0; i<size; i++) {
        if (rand() % 5 == 0)
            dest.push_back(' ');
        else
            dest.push_back(rand() % 26 + 'A');
    }
    dest.push_back('\0');
}

int main() {
    static const int size = 1024 * 1024 * 100;

    std::vector<char> src, dest;

    generate_string(src, size-2);

    dest.resize(size);

    show("Original", timer(iterative_trim_whitespace, &src[0], &dest[0]));    
    show("Jerry's", timer(trim_whitespace, &dest[0], &src[0]));

    return 0;
}

至少当我运行它时，我得到：

Time for Original 0.749 seconds
Time for Jerry's 0.468 seconds

我可能应该补充一下：正如我在评论中提到的那样，isspace我使用的编译器的实现相当慢，至少与我在这里抛出的简单编译器相比。然而，公平地说，如果这样做的部分好处只是被简单地实现为函数对象，我不会感到惊讶（无论如何），这通常使编译器更容易为其生成内联代码。

对于它的价值，还有两点：

  1. 微软的链接时代码生成大大减慢了这两者
  2. 无论哪种方式，修剪都比最初生成输入要快得多

1嗯，从技术上讲，它可能是char一个无符号类型开始 - 但它是不寻常的，你不应该指望它。您的所有输入也可能属于您char可能持有的 ASCII 字符子集，在这种情况下，它似乎工作得很好——但这就是有害的：您可以测试它（尽可能多）但是，除非您使用包含编码为负数的字符的文本执行此操作char，否则它看起来很好。然后，当您的法语/西班牙语/挪威语/等等，客户对其进行测试时，它会掉下来。

于 2012-11-29T15:17:05.877 回答
2

如果您需要真正快速的解决方案，请不要这样做。而是在输入字符串上有一个迭代器，它会跳过空格。任何需要操作“修剪”字符串的地方都可以通过这个迭代器。

这可能会也可能不会，这取决于目前的发展程度。

于 2012-11-29T15:12:11.597 回答
2

这当然看起来很合理，递归版本会很糟糕。如果这些是大字符串，我会考虑修改它们而不是复制它们，但这是一个更高级别的设计决策。它不影响速度，但可以减少内存消耗。

于 2012-11-29T15:07:13.123 回答
1

Jerry Coffin，我刚从列克星敦约会回来。此版本已经过测试。我为我匆忙写的第一个版本道歉，因为我急于去看我在列克星敦的牙医。

void  iterative_trim_whitespace(const char* src, char* target){

         bool firstspace(true);
         while (*src != '\x0'){
            if (firstspace){
                *target++ = *src++;
            } 
            else{
                src++;
            }
            if (firstspace && isspace(*(src - 1))){
      firstspace    = false;
            }  
            else{
      firstspace = true;
            }
         }
    *target = '\x0';
}

void iterative_trim_whitespace_revised(const char* src, char* target){
    bool firstspace(true);
    int ct(0);
    while (*src != '\x0'){
        if (firstspace){
            *target++ = *src++;
        } 
        else{
            src += ct - 2; 
        }
        if (firstspace){ 
            char *x = (char *)src - 1;
            ct = 1;
            bool sentinel(false);
            while(isspace(*(x + (ct - 1)))){
                ct += 1;
                sentinel = true;

            }
            if (sentinel){
                firstspace = false;
            }
        }
        else{
            ct = 1;
            firstspace = true;
        }
    }
    *target = '\x0';
}

void iterative_trim_whitespace_friday_5Timesfaster(const char* src, char* target){ bool firstspace(true); 整数 ct(0); while (*src != '\x0'){ if (firstspace){ *target++ = *src++; } 其他{ src += ct - 2; }

       if (firstspace){ 
     char *x = (char *)src - 1;
     ct = 1;
     bool sentinel(false);
     while(*(x + (ct - 1)) == ' '){ 
         ct += 1;
         sentinel = true;

     }
     if (sentinel){
         firstspace    = false;
     }
            }
            else{
     ct = 1;
     firstspace = true;
            }
         }
    *target = '\x0';

}

// 这是我们今天早上的 ProjectDirector 版本 // TrimLeading() 和 TrimTrailing 是附加的内联函数

void iterative_trim_whitespace_ProjectDirector(const char* src, char* target){

int out=0;

for (int i=0;src[i]!= '\x0';i++) {

    if (src[i] != ' ' || src[i+1] != ' '){

        target[out++]=src[i];
    }

}

target[out]= '\x0';

}

于 2012-11-29T22:29:58.343 回答
1

你的代码不会像写的那样工作。如果第一个字符是空格，则不会复制空格，也不会复制空格之后的字符。这样的事情更合理：

bool hitSpace = false;
while (*src != '\x0')
{
    if (isspace(*src))
    {
        if (hitSpace)
        {
            src++;
        }
        else
        {
            *target++ = *src++;
            hitSpace = true;
        }
    }
    else
    {
        *target++ = *src++;
        hitSpace = false;
    }
}
于 2012-11-29T15:12:21.570 回答
1

首先，我会选择迭代（在 C 或 C++ 中）而不是递归。无论如何，编译器可能会将递归算法转换为循环，但如果它没有（或者您在调试模式下构建），那么您肯定会溢出堆栈。此外，调用函数是有代价的，你想避免这种情况。

您的基本算法看起来不错（一旦吉姆发现的错误被修复）。我会检查isspace是否被内联。如果不是，则将其替换为*str == ' '.

涉及模板的解决方案肯定只是将一个简单的问题复杂化而没有任何优势。

于 2012-11-29T15:14:12.630 回答