通过字符串来计算长度需要更长的时间，而不是移动字符串几次？

Question

我写了下面两个函数。在第二个函数中，我使用了 reserve() 这样就没有内存重新分配，但不幸的是第二个函数比第一个慢。

我在 Visual Studio 中使用了释放模式和这个 CPU 分析器来计算时间。在第二个函数中，重新分配发生了 33 次。所以我的问题是：真的吗？将一个长度的字符串计算长度比将此字符串移动 33 次需要更长的时间？

string commpres2(string str)
{
    string strOut;
    int count = 0;
    for (int i = 0; i < str.length(); ++i)
    {
        ++count;
        if (i < str.length() - 1)
        {
            if (str[i + 1] != str[i])
            {
                strOut += str[i];
                strOut += to_string(count);
                count = 0;
            }
        }
        else
        {
            strOut += str[i] + to_string(count);
        }
    }
    return strOut.length() < str.length() ? strOut : str;
}

string commpres3(string str)
{
    int compressedLength = 0;
    int countConsecutive = 0;
    for (int i = 0; i < str.length(); ++i)
    {
        ++countConsecutive;
        if (i + 1 >= str.length() || str[i] != str[i + 1]) 
        {
            compressedLength += 1 + 
                to_string(countConsecutive).length();
            countConsecutive = 0;
        }
    }
    if (compressedLength >= str.length())
        return str;
    string strOut;
    strOut.reserve(compressedLength);
    int count = 0;
    for (int i = 0; i < str.length(); ++i)
    {
        ++count;
        if (i < str.length() - 1)
        {
            if (str[i + 1] != str[i])
            {
                strOut += str[i];
                strOut += to_string(count);
                count = 0;
            }
        }
        else
        {
            strOut += str[i] + to_string(count);
        }
    }
    return strOut;
}

int main()
{
    string str = "aabcccccaaa";

    //str.size ~ 11000000;
    for (int i = 0; i < 20; ++i)
        str += str;
    commpres2(str); //107ms //30,32% CPU
    commpres3(str); //147ms //42,58% CPU
}

Answer 1

第二个函数比第一个函数做更多的工作，所以当然会花费更长的时间。对代码进行概要分析应该可以准确地向您显示代码将时间花在哪里。例如，第一个函数最多循环 str 1 次，但第二个函数可能循环相同的 str 2 次，根据定义，这需要更长的时间。

而且您也没有消除第二个函数的所有内存分配。 to_string()分配内存，你在调用reserve()前后多次调用它。消除所有 to_string() 分配非常简单，使用 std::snprintf() 到本地缓冲区，然后 std::string::append() 将该缓冲区添加到输出 std::string。

您可以放弃所有的预计算，只使用 reserve() 完整的 str 长度，即使您最终没有使用所有的内存。在最坏的情况下（根本无法压缩），您不会用完超过原始 str 的长度：

inline int to_buffer(size_t number, char *buf, size_t bufsize)
{
    return snprintf(buf, bufsize, "%zu", number);
}

string commpres3(const string &str)
{
    string::size_type strLen = str.length();
    string strOut;
    strOut.reserve(strLen);
    size_t count = 0;
    char buf[25];
    for (string::size_type i = 0; i < strLen; ++i)
    {
        ++count;
        if (i < strLen - 1)
        {
            if (str[i + 1] != str[i])
            {
                strOut += str[i];
                strOut.append(buf, to_buffer(count, buf, sizeof(buf)));
                count = 0;
            }
        }
        else
        {
            strOut += str[i];
            strOut.append(buf, to_buffer(count, buf, sizeof(buf)));
        }
        if (strOut.length() >= strLen)
            return str;
    }
    return strOut;
}

或者，如果您必须预先计算，您可以用 returns 所需长度的其他内容替换第一组 to_string() 调用，而无需动态分配内存（see this想法）。在计算要保留的大小时，您不需要实际将整数 123 转换为分配的字符串“123”就知道它会占用 3 个字符。

inline int to_buffer(size_t number, char *buf, size_t bufsize)
{
    return snprintf(buf, bufsize, "%zu", number);
}

inline int to_buffer_length(size_t number)
{
    return to_buffer(number, nullptr, 0);
}

string commpres3(const string &str)
{
    string::size_type strLen = str.length();
    string::size_type compressedLength = 0;
    size_t countConsecutive = 0;
    for (string::size_type i = 0; i < strLen; ++i)
    {
        ++countConsecutive;
        if (i < (strLen - 1))
        {
            if (str[i + 1] != str[i])
            {
                strOut += 1 + to_buffer_length(countConsecutive);
                countConsecutive = 0;
            }
        }
        else
        {
            strOut += 1 + to_buffer_length(countConsecutive);
        }
    }
    if (compressedLength >= strLen)
        return str;
    string strOut;
    strOut.reserve(compressedLength);
    size_t count = 0;
    char buf[25];
    for (string::size_type i = 0; i < strLen; ++i)
    {
        ++count;
        if (i < strLen - 1)
        {
            if (str[i + 1] != str[i])
            {
                strOut += str[i];
                strOut.append(buf, to_buffer(count, buf, sizeof(buf)));
                count = 0;
            }
        }
        else
        {
            strOut += str[i];
            strOut.append(buf, to_buffer(count, buf, sizeof(buf)));
        }
    }
    return strOut;
}

Answer 2

33 内存分配 vs ~11000000 额外的 if 语句.

您正在执行 if (i < str.length() - 1) 每次迭代检查，但您只需执行一次。

考虑以下几点：

   if (str.empty()) return str;
   const auto last = str.length() - 1;
   for (size_t i = 0; i < last; ++i)
   {
       ++count;
       if (str[i + 1] != str[i])
       {
           strOut += str[i];
           strOut += to_string(count);
           count = 0;
       }
   }
   strOut += str[last] + to_string(count);

一些优化提示：

如果计数等于一，您可以避免添加计数。否则，你的算法 "compresses" "abc" 到 "a1b1c1".
添加一个指示符，表示后面的字节是一个计数，而不是一个正则字符，以区分"a5"和"aaaaa"。例如，使用 0xFF。因此，"a5" 被编码为 "a5"，但是 "aaaaa" -> {'a', 0xFF, 5}
以二进制形式存储计数，而不是 ASCII。例如，您可以写 3 (0x03) 而不是 '3' (0x33)。您可以使用一个字节来存储最多 255 个计数。

constexpr char COMPRESS_COUNT_SEPARATOR = 0xFF;

string compress(const string &str)
{
    string strOut;
    if (str.empty()) return strOut;

    unsigned char count = 0;
    const auto last = str.length() - 1;
    for (size_t i = 0; i < last; ++i)
    {
        ++count;
        if (str[i + 1] != str[i] || count == 255)
        {
            strOut += str[i];
            if (count > 1) {
               strOut += COMPRESS_COUNT_SEPARATOR;
               strOut += static_cast<char>(count);
            }
            count = 0;
        }
    }
    strOut += str[last];
    if (count) {
        strOut += COMPRESS_COUNT_SEPARATOR;
        strOut += static_cast<char>(count+1);
    }

    return strOut;
}

或者您甚至可以将 0x00 用作 COMPRESS_COUNT_SEPARATOR，因为 C 字符串不能包含空终止符，但 std::string 可以。

通过字符串来计算长度需要更长的时间，而不是移动字符串几次？

Going ones through string to count length takes longer time, than moving string a couple of times?

c++

string

memory-reallocation