个人中心
gpt4 book ai didi

c++ - std::vector::reserve( unknown m )，我知道 m<
转载 作者：行者123 更新时间：2023-11-30 03:34:17 24 4
gpt4 key购买 nike

我有适用于 N 的代码对象，然后只返回 some m 的结果指数，基于一些自定义条件。

这是一个可靠的例子(查询字符串 ' ' 上的所有 str 字符):-

 std::vector<int> reports; //will keep index of ' ' in "str"
 for(int i=0;i<N;i++){  // str.size() = "N"
     bool condition = str.at(i)==' ';  //"str" is string   #B
     if(condition){ //rarely true
         reports.push_back(i); 
     }
 }
 //now reports.size() = m

在那些 block 中，我知道 m总是小于或等于 N和通常 m << N .

在现实生活中， block 更复杂，但共享相似的算法:-

 //int "N" is a local variable, it is not a constant. 
 std::vector<Input> inputs; 
 std::vector<Report> reports;  //"Report" is any type of result, actually
 int outOfLoopVariable=0; 
 for(int i=0;i<N;i++){
     bool condition = some logic #B about "inputs[i]" and "outOfLoopVariable";
     outOfLoopVariable= ....; //some complex logic #B
     int var1 = ....; //some complex logic #B
     //var2, var3, etc.
     if(condition){ //rarely true
         reports.push_back(Report(i,var1,var2,...)); 
     }
 }

原始问题

算法#B总复杂度 = O(N) ,
但是std::vector::push_back的总复杂度 =

  • O(m*log(m))在大多数情况下(当 m<<N 时)
  • O(N*log(N))在最坏的情况下(当 m~N 时)

正如 oLen 所指出的，这是完全错误的。不过，我还是决定留作引用。

问题

(编辑) 算法 #B需要重新分配 vector多次。

问题

如何使上述 block 的复杂度为O(N)？
(编辑，感谢oLen)如何避免vector不必要的内部保留(1->2->4->...)?

我糟糕的解决方案

多年来，我一直通过以下方法之一解决这个问题:-

  1. reports.reserve(N) at first statement - 在大多数情况下这是一个过度保留。
    当report时真的很糟糕是一个大物体并且N非常大(异形，10000+)。
  2. 循环 2 次。
    • 第一个循环确定m .
    • 然后 reserve(m) .
    • 最后，第二个循环执行实际的 reports.push_back(i);
    • 不方便。代码重复往往会导致轻微的可维护性问题。
      (可以通过 lambda[&] 部分解决，稍微牺牲了可读性)
    • 此外，粗略地说，#B 的复杂性现在是O(2*n)
    • ... 或 O(1.x*n)如果我可以省略第一个循环的一些计算。

我希望会有更好的方法。

最佳答案

回答:只是不要改变你的代码，不要使用reserve。

std::vector::push_back 的复杂度是恒定的(考虑到 amortized time )所以你只要使用它就可以了。

关于c++ - std::vector::reserve( unknown m )，我知道 m<<N (通常)并且知道 N，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42185176/

24 4 0

文章推荐： java - 从 Ebean 中排除字段以将其保存在 DB 中
文章推荐： java - Selenium - NoSuchElementException 错误检查
文章推荐： java - 带有 Class 参数的 ObjectFactory
文章推荐： java - WildFly 8.2 为远程服务器配置JMS Bridge
行者123
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com