0

我写了以下两个函数。在第二个函数中，我使用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
}
4

2 回答 2

0

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);

一些优化提示：

  1. 如果计数等于一，您可以避免添加计数。否则，您的算法会将“abc”“压缩”为“a1b1c1”。
  2. 添加一个指示符，指示后面的字节是计数而不是常规字符，以区分“a5”和“aaaaa”。例如，使用 0xFF。因此，“a5”被编码为“a5”，但“aaaaa” ->{'a', 0xFF, 5}
  3. 以二进制形式存储计数，而不是 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 asCOMPRESS_COUNT_SEPARATOR因为 C 字符串不能包含空终止符，但 std::string 可以。

于 2020-02-12T08:08:57.820 回答
0

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

而且您也没有从第二个函数中消除所有内存分配。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;
}

或者，如果您必须预先计算，您可以将第一组to_string()调用替换为返回所需长度的其他内容，而无需动态分配内存（有关想法，请参阅此内容）。在计算要保留的大小时，您无需将整数 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;
}
于 2020-02-12T08:05:30.003 回答