Disclaimer:这个问题更多是理论上的,而不是实际上的。我想找出各种不同的方式来做到这一点,并以速度为新年蛋糕锦上添花。
我希望能够存储字符串列表,并能够根据需要将它们快速组合为1。简而言之,我想压缩一个看起来像
的结构(当前为std::vector<std::string>
)["Hello, ", "good ", "day ", " to", " you!"]
to
["Hello, good day to you!"]
[ ''.join(list_of_strings) ]
?我首先想到的是
We will be concatenating with +=
and reserve()
。我认为+=
。
方法1(贪婪方法)
之所以这样称呼,是因为它忽略了约定并就地运行。
reserve()
现在我知道,您会说这是冒险且不好的。因此:
max_size()
will not be reached,方法2(“避风港”)
之所以这样称呼,是因为它在迭代容器时不会修改容器。
max_size()
但是,也许我们可以使用另一个容器而不是
// Save as greedy_approach.cpp #include <iostream> #include <vector> int main() { // Our test object, with 5 strings std::vector< std::string > my_strings = { "Hello, ", "good ", "day ", "to ", "you!" }; // Suppose already calculated / known int total_characters_in_list = 7 + 5 + 4 + 3 + 4; // Reserve the size for all characters, less than max_size() my_strings[0].reserve(total_characters_in_list); // There are strings left, ... for(auto itr = my_strings.begin()+1; itr != my_strings.end();) { // append, and... my_strings[0] += *itr; // delete, until... my_strings.erase(itr); } // Just to check it's success. std::cout << my_strings[0]; return 0; }
?
在那种情况下,还有什么?
(可能)方法3(伟大的印度“绳子”把戏)
我听说过
std::string
,但不知道是否可以(以及如何)在这里使用它。
按其时间效率(当前和令人惊讶的顺序)是:
// Save as safe_haven.cpp
#include <iostream>
#include <vector>
int main()
{
// Our test object, with 5 strings
std::vector< std::string > my_strings = { "Hello, ", "good ", "day ", "to ", "you!" };
// Suppose already calculated / known
int total_characters_in_list = 7 + 5 + 4 + 3 + 4;
// Store the whole vector here
std::string condensed_string;
condensed_string.reserve(total_characters_in_list);
// There are strings left...
for(auto itr = my_strings.begin(); itr != my_strings.end(); ++itr)
{
// append, until...
condensed_string += *itr;
}
// remove all elements except the first
my_strings.resize(1);
// and set it to condensed_string
my_strings[0] = condensed_string;
// Just to check it's success.
std::cout << my_strings[0];
return 0;
}
定时:
std::vector
我们能做得更好吗?
默认情况下,我会使用rope data structure。只需构造蒸汽,从向量中的所有字符串中输入流,然后返回输出字符串即可。它不是很有效,但是很清楚它的作用。
[在大多数情况下,在处理字符串和打印时不需要快速方法-因此,“易于理解和安全”的方法更好。另外,当今的编译器擅长在简单情况下优化效率低下的问题。
最有效的方法...这是一个很难的问题。一些应用需要多方面的效率。在这些情况下,您可能需要利用多线程。
使用safe_haven: 0.13684312179998959
greedy_approach: 0.1369105681000074
(很快使用NUM_OF_ITERATIONS = 100
test_cases = [ 'greedy_approach', 'safe_haven' ]
for approach in test_cases:
time_taken = timeit.timeit(
f'system("{approach + ".exe"}")',
'from os import system',
number = NUM_OF_ITERATIONS
)
print(approach + ": ", time_taken / NUM_OF_ITERATIONS)
),您可以这样做:
std::stringstream
就我个人而言,我将构造第二个向量以容纳单个“压缩”字符串,构造该压缩字符串,然后在完成后交换向量。
C++20 ranges
[如果由于某种原因引发了异常,则原始向量将保持不变,并进行清除-即,此函数提供了强大的异常保证。
可选地,为减小“压缩的”字符串的大小,在上面初始化std::vector<std::string> v{"Hello, ", "good ", "day ", " to", " you!"};
std::string s = v | ranges::view::join;
后,可以这样做
Demo
关于将其与替代方法进行比较的效率,这取决于。我也不确定它是否相关-如果将字符串继续添加到向量中并需要添加,则很有可能从某个地方获取字符串(并将它们附加到向量中)的代码中都有一个对程序性能的影响大于将其压缩的行为。
您也可以尝试 void Condense(std::vector<std::string> &strings)
{
std::vector<std::string> condensed(1); // one default constructed std::string
std::string &constr = &condensed.begin(); // reference to first element of condensed
for (const auto &str : strings)
constr.append(str);
std::swap(strings, condensed); // swap newly constructed vector into original
}
:
constr
不会更快,但是至少它更紧凑。