代码之家 › 专栏 › 技术社区 › Sinayra

循环中的strcat()与sprintf()

strcat printf loops performance c

Sinayra · 技术社区 · 8 年前

我有一个程序,可以删除字符串中的所有变量。这些变量以“$”开头。例如,如果我给出一个像[1,2,$1,$2]这样的字符串,它应该只返回[1,2]。

但是,哪个循环对性能更有利?

这是:

while (token != NULL)
{
    if (*token != '$')
    {
        sprintf(dst, "%s,%s", dst, token);
    }
    token = strtok(NULL, "], ");
}

或者这个:

while (token != NULL)
{
    if (*token != '$')
    {
        strcat(dst, token);
        strcat(dst, ",");
    }
    token = strtok(NULL, "], ");
}

3 回复 | 直到 8 年前

Keith Thompson 8 年前

根据 C11 standard 7.21.6.6 p2 ,描述 sprintf :

如果复制发生在重叠的对象之间,则行为是未定义。

因此,您的第一个代码片段在从中复制时调用了一个未定义的行为 dst 到 dst 这个 strcat 这种方法没有这个问题。

rici 8 年前

strtok 是破坏性的,因此执行此代码后,输入字符串将不可用。在这种情况下,您不妨就地进行转换。这有两个优点,其中一个是不需要分配任何内存(因为最后一个字符串不能比原始字符串长)。这也需要一点额外的簿记,但这提供了另一个优势:结果函数的执行时间与输入的大小成线性关系。在每次迭代中从一开始就重新启动输出缓冲区扫描——就像两个解决方案一样——使函数 二次的 在绳子的长度上。[注1]二次算法的使用比替代标准库调用成本的微小差异要严重得多。
正如许多人所提到的,打电话是不明确的行为 sprintf 在输出缓冲区和要打印的一个字符串之间存在重叠。那么你对 把格式数据写成串 是不正确的,尽管它可能在某些实现中起作用。
也不 strcat 也没有 把格式数据写成串 防止缓冲区溢出。你可以用 snprintf (通过将新字符串放在累积缓冲区的末尾,而不是在每次迭代时用其自身覆盖缓冲区的开头)或者您可以使用 strncat ,但在这两种情况下,你都需要额外记账。

下面是第一点中提出的算法的快速实现。请注意,它不调用 malloc() 它也不会在堆栈上分配任何字符串。还请注意,它使用 memmove 而不是 memcpy 在字符串中向前移动新发现的令牌,以避免令牌与其目标重叠时出现问题。( memmove 允许重叠; memcpy , strcpy 和 字符串连接函数 不要这样做。)

/* Compresses the string str in place by removing leading and trailing separator
 * characters (which are the characters in 'fs') and replacing any interior
 * sequence of separator characters with a single instance of 'ofs'.
 * Returns 'str'.
 */
char* compress(char* str, const char* fs, char ofs) {
  char* out = str;
  char* token = strtok(str, fs);
  while (token != NULL) {
    size_t tlen = strlen(token);
    memmove(out, token, tlen);
    out += tlen;
    *out++ = ofs;
    token = strtok(NULL, fs);
  }
  /* Overwrite the last delimiter (if there was one) with a NUL */
  if (out != str) --out;
  *out = 0;
  return str;
}

API注释:

与最初的不同,这不会丢弃以a开头的代币 $ .这是微不足道的补充。
与最初的功能不同,该功能还避免了拖尾 , .同样,如果有充分的理由,这很容易改变。(然而,后面的逗号意味着只有一个标记的字符串最终会长一个字符,因此无法做出就地保证。)
我选择返回压缩字符串的起始地址(与输入缓冲区的地址相同),以与各种标准C接口保持一致。然而,在许多情况下,返回更有用 out (这是尾随NUL的地址),以便在不必计算字符串的新长度的情况下允许进一步连接。或者,可以返回字符串的新长度,如下所示: 把格式数据写成串 是吗( return out - str; )
这个API诚实地告诉我们,它破坏了原始字符串(通过用转换后的字符串覆盖它);只调用 斯特托克 但返回一个单独的输出可能会导致微妙的错误,因为调用者不清楚原始字符串是否已被破坏。而在之后无法恢复字符串 斯特托克 已被调用,只需复制原始字符串,即可轻松将就地算法转换为非破坏性算法:
```
/* Returns freshly allocated memory; caller is responsible for freeing it */
char* compress_and_copy(const char* str, const char* fs, char ofs) {
  return compress(strdup(str), fs, ofs);
}
```
当然,有可能原始的未简化函数没有保证生成较短字符串的功能;例如,从一个片段开始扩展 $ 用变量的值替换它们。在这种情况下,需要生成一个新字符串。

在某些情况下,甚至在大多数情况下,输出仍然比输入短。但是,如果可能的话,我们应该抵制在适当的地方进行转换的诱惑,只有在必要时才分配一个新字符串。虽然它可能更有效,但它使分配所有权的规则复杂化;最后你不得不说“只有当返回的字符串与原始字符串不同时,调用者才拥有它”,这既笨拙又容易发生事故。

因此,如果这是实际的用例,那么(从干净API设计的角度来看)最佳解决方案就是使用 strspn() 和 strcspn() 以非破坏性方式移动原始字符串。这是一个多一点的工作,因为它需要更多的簿记;另一方面,它避免了重新计算的需要 strlen(token) 在识别令牌之后。

笔记:

从技术上讲,时间与字符串长度和令牌数量的乘积成正比,但在最坏的情况下(令牌较短),这实际上是O(n) ^2. ).

chqrlie 8 年前

这两种方法都不可取:

经过 sprintf 与目标和源相同的指针 %s 格式说明符具有未定义的行为。此外 把格式数据写成串 如果目标阵列不够大,则无法防止缓冲区溢出。
第二种方法是几个 strcat 调用可能存在缓冲区溢出问题,而且效率低下,因为目标字符串会被反复扫描以找到副本的位置。

以下是另一种方法:

char src[LINE_SIZE];
char dst[LINE_SIZE + 1];  /* dst is large enough for the copy */
int pos = 0;

token = strtok(src, "], ");
while (token != NULL) {
    if (*token != '$') {
        pos += sprintf(dst + pos, "%s,", token);
    }
    token = strtok(NULL, "], ");
}