时间戳

首页 > 解决方案 > 循环操作中的向量重新声明与插入 - C++

c++ - 循环操作中的向量重新声明与插入 - C++

问题描述

我可以选择在每次调用时创建和销毁向量func()并在每次迭代中推送元素，如示例 A 所示，或者修复初始化并仅在每次迭代中覆盖旧值，如示例 B 所示。

示例 A：

void func () 
{
    std::vector<double> my_vec(5, 0.0);
    for ( int i = 0; i < my_vec.size(); i++) {
        my_vec.push_back(i);
        // do something
    }
}

while (condition) {
    func();
}

示例 B：

void func (std::vector<double>& my_vec) 
{
    for ( int i = 0; i < my_vec.size(); i++) {
        my_vec[i] = i;
        // do something
    }
}

while (condition) {
    std::vector<double> my_vec(5, 0.0);
    func(myVec);
}

两者中的哪一个在计算上是便宜的。数组的大小不会超过 10。

标签： c++vectortime-complexity

解决方案

我仍然怀疑被问到的问题不是预期的问题，但我想到我回答的要点可能不会改变。如果问题得到更新，我可以随时编辑此答案以匹配（或删除它，如果结果不适用）。

取消优先级优化

有多种因素会影响您编写代码的方式。理想的目标包括空间优化、时间优化、数据封装、逻辑封装、可读性、鲁棒性和正确的功能。理想情况下，所有这些目标都可以在每一段代码中实现，但这并不是特别现实。更有可能的情况是必须牺牲其中一个或多个目标以支持其他目标。发生这种情况时，优化通常应该屈服于其他一切。

这并不是说应该忽略优化。有很多优化很少会阻碍更高优先级的目标。这些范围从小的（例如通过 const 引用而不是按值传递）到大的（例如选择对数算法而不是指数算法）。但是，确实会干扰其他目标的优化应该推迟到您的代码合理完成并正常运行之后。此时，应该使用分析器来确定瓶颈的实际位置。这些瓶颈是其他目标应该屈服于优化的唯一地方，并且只有在分析器确认优化实现了他们的目标时。

对于提出的问题，这意味着主要关注的不应该是计算费用，而是封装。为什么调用者func()需要分配空间供func()使用？它不应该，除非分析器将此识别为性能瓶颈。如果分析器这样做了，那么询问分析器是否有帮助会比询问 Stack Overflow 更容易（也更可靠！）。

为什么？

我可以想到降低优化优先级的两个主要原因。首先，“嗅探测试”是不可靠的。虽然可能有少数人可以通过查看代码来识别瓶颈，但还有很多很多人只是认为他们可以。其次，这就是我们优化编译器的原因。有人想出这个超级聪明的优化技巧，却发现编译器已经在这样做，这并非闻所未闻。保持代码干净，让编译器处理例程优化。只有当任务明显超出编译器的能力时才介入。

另请参阅：

选择优化

好的，假设分析器确实将这个小型 10 元素数组的构造确定为瓶颈。下一步是测试替代方案，对吗？几乎。首先，您需要一个替代方案，我会考虑对各种替代方案的理论优势进行审查，这很有用。请记住，这是理论上的，分析器拥有最终决定权。因此，我将从问题中探讨替代方案的优缺点，以及可能需要考虑的其他一些替代方案。让我们从最坏的选择开始，朝着更好的方向努力。

示例 A

在示例 A 中，创建了一个包含 5 个元素的向量，然后将元素推送到向量上，直到i达到或超过向量的大小。看到i向量的大小在每次迭代时都增加一（并且i开始时小于大小），这个循环将一直运行，直到向量增长到足以使程序崩溃。这意味着可能有数十亿次迭代（尽管问题声称大小不会超过 10）。

很容易成为计算成本最高的选项。不要这样做。

示例 B

在示例 B 中，为外while循环的每次迭代创建一个向量，然后从内部通过引用访问该向量func()。这里的性能缺点包括将参数传递给向量func()并func()通过引用间接访问向量。没有性能专家，因为它完成了基线（见下文）会做的所有事情，加上一些额外的步骤。

即使编译器可能能够弥补缺点，我认为没有理由尝试这种方法。

基线

我使用的基线是对示例 A 的无限循环的修复。具体来说，将“ my_vec.push_back(i);”替换为示例 B 的“ my_vec[i] = i;”。这种简单的方法符合我对分析器初始评估的期望。如果你不能打败简单，坚持下去。

示例 B*

问题的文本对示例 B 的评估不准确。有趣的是，评估描述了一种有可能在基线上改进的方法。要获得与文本描述匹配的代码，请将示例 B 的“ ”移动到语句std::vector<double> my_vec(5, 0.0);之前的行。while这具有仅构造一次向量的效果，而不是每次迭代都构造它。

这种方法的缺点与最初编码的示例 B 的缺点相同。但是，我们现在获得了一个好处，即向量的构造函数只被调用一次。如果构造比间接成本更昂贵，那么一旦while循环迭代得足够频繁，结果应该是净改进。（请注意这些条件：这是一个重要的“如果”，并且没有先验猜测多少次迭代“足够”。）尝试这个并查看分析器所说的内容是合理的。

获取一些静电

Example B* 上有助于保持封装的变体是使用基线（固定的 Example A），但在向量声明之前使用关键字static. 这带来了只构造一次向量的好处，但没有与使向量成为参数相关的开销。事实上，好处可能比示例 B* 中的更大，因为每次程序执行只发生一次构造，而不是每次while启动循环时。循环启动的次数越多while，这种好处就越大。

这里的主要缺点是向量将在整个程序执行过程中占用内存。与示例 B* 不同，它不会在包含while循环的块结束时释放其内存。在太多地方使用这种方法会导致内存膨胀。因此，虽然分析此方法是合理的，但您可能需要考虑其他选项。（当然，如果分析器将此称为瓶颈，使所有其他瓶颈相形见绌，则成本小到足以支付。）

固定大小

我个人选择在这里尝试的优化是从基线开始并将向量切换到std::array<10,double>. 我的主要动机是所需的大小不会超过 10。同样相关的是 a 的构造double是微不足道的。数组的构造应该与声明 10 个类型的变量相当double，我希望可以忽略不计。所以不需要花哨的优化技巧。让编译器做它的事情。

这种方法的预期可能好处是 avector在堆上为其存储分配空间，这会产生开销。当地人array不会有这个成本。然而，这只是一个可能的好处。向量实现可能已经利用了小向量的这种性能考虑。（也许在容量需要超过某个幻数（可能超过 10 个）之前它不会使用堆。）当我提到“超级聪明”和“编译器已经在做”时，我会向您推荐。

我会通过探查器运行它。如果没有好处，那么其他方法可能没有好处。试一试，当然，因为它们很容易，但最好利用您的时间来查看其他方面进行优化。

推荐阅读