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

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

第二个函数比第一个函数做更多的工作，所以当然需要更长的时间。分析代码应该会准确地显示代码花费时间的位置。 例如，第一个函数最多循环遍历str1 次，但第二个函数可能会循环遍历同一个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;
}

Answer 2

33 个内存分配与~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. 如果计数等于 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 作为COMPRESS_COUNT_SEPARATOR因为 C 字符串不能包含空终止符，但 std：：string 可以。