迭代大小为 100000 的 C char 数组需要大量时间

Question

尝试迭代大小为 100000 的字符数组，但需要 8-9 秒。但是对于 int 它需要几毫秒。

    int i;
    char str[100005];
    str[0] = '[=10=]';
    for(i=1;i<10000;i++){
        strcat(str, "HelloWorld");
    }
    for(i=1;i<strlen(str);i++){
        str[i]=str[i-1];
    }

Answer 1

让我们看看这段代码：

for(i = 1; i < 10000; i++){
    strcat(str, "HelloWorld");
}

想想对 strcat 的调用是如何工作的。 strcat 函数通过在字符串中向前扫描直到找到空终止符，然后在那里写入第二个参数来工作。如果你的字符串很短——比如说，它大约有 10-20 个字符长——那是相当快的——但是如果你附加到的字符串很长（比如，10,000 个字符），那么 strcat 会花费很多时间只需扫描到字符串的末尾即可找到要追加字符串的位置。这意味着在此函数中对 strcat 的每次调用都将比前一次调用花费更长的时间，最终最后一次调用相当慢。

那么如何加快速度呢？一种选择是在 str 数组中存储一个指向空终止符的指针，这样您就可以告诉 strcat 从哪里开始查找。这可能是这样的：

size_t length = strlen("HelloWorld");
char* nextSpot = str;
for(i = 1; i < 10000; i++){
    strcat(nextSpot, "HelloWorld");
    nextSpot += length;
}

这意味着 strcat 调用总是会在上一个中断的地方继续，从而加快速度。

希望对您有所帮助！

Answer 2

您的代码存在一些问题。首先是您在尚未初始化的目标数组上调用 strcat 。您需要先设置str[0] = '[=14=]';。

其他的都是算法题。要知道在何处插入目标字符串，每次调用 strcat 时都必须执行 strlen 或等效操作。这意味着它每次都会通过 O(n) 个字符。这使得你的算法 ~O(n^2)。然后你去对每个字符再次调用 strlen ，惩罚相同。请记住，第二个循环只是将整个数组设置为 'H'.

如果你想复制一个字符串 10000 次，你最好预先计算它的长度并沿着缓冲区步进:

char str[100005];
const char *template = "HelloWorld";
int n = strlen(template);
char *p = str;
for(int i = 0; i < 10000; i++) {
    strncpy(p, template, n);
    p += n;
}
*p = '[=10=]';

我在这里使用 strncpy 是因为它避免了为您制作的每个副本复制 template 的终止 '[=23=]'。

另一种方法是使用模除法（这可能会更慢）来放置字符：

char str[100005];
const char *template = "HelloWorld";
int n = strlen(template);
int end = n * 10000;
for(int i = i; i < end; i++) {
    str[i] = template[i % n];
}

这两种方法在我的机器上花费的时间比你原来的循环少几个数量级，因为它们只遍历数组一次。

最后一个循环将前一个字符一遍又一遍地复制到缓冲区的其余部分。由于您的缓冲区充满 HelloWorld，因此循环将 'H' 复制到每个位置。您可以使用 memset 为您做同样的事情：

memset(str, 'H', 10000 * n);

这个故事的寓意是避免重新计算您可以使用简单的计数器或指针跟踪的事情。如果你想让事情进展得快，就尽量少做。

迭代大小为 100000 的 C char 数组需要大量时间

Iterate C char array of size 100000 takes huge time

c

string

performance

strcat