c++ push_back的更快替代方案(大小已知)

hsvhsicv  于 2023-05-20  发布在  其他
关注(0)|答案(6)|浏览(166)

我有一个浮点向量。当我处理某些数据时,我会将其推回。在声明向量时,我总是知道大小。
最大的情况是172,490,752个浮动。仅push_back所有内容就需要大约11秒。
有没有更快的替代方案,比如不同的数据结构之类的?

kjthegm6

kjthegm61#

如果你知道最终的大小,那么reserve()在你声明vector之后的大小。这样它只需要分配内存一次。
此外,您可以尝试使用emplace_back(),尽管我怀疑它对float向量有任何影响。但是尝试一下并进行基准测试(当然是使用优化的构建-您正在使用优化的构建-对吗?).
如果您事先知道大小,另一个选择是使用std::array

tvokkenx

tvokkenx2#

当您事先知道vector的大小时,通常的加速方法是在使用push_back之前调用reserve。这消除了每次以前的容量被填满时重新分配内存和复制数据的开销。
有时对于要求非常高的应用程序,这是不够的。即使push_back不会重新分配,它仍然需要每次检查容量。没有基准测试就无法知道这有多糟糕,因为当分支总是/从不被采用时,现代处理器的效率惊人。
您可以尝试使用resize而不是reserve并使用数组索引,但resize强制每个元素的默认初始化;这是一种浪费,如果你知道你要设置一个新的值到每个元素无论如何。
另一种方法是使用std::unique_ptr<float[]>并自己分配存储。

92dk7w1h

92dk7w1h3#

::boost::container::stable_vector请注意,分配一个172 *4 MB的连续块可能很容易失败,并且需要相当多的页面抖动。稳定向量本质上是一个较小的向量或合理大小的数组的列表。您可能还希望并行填充它。

izkcnapc

izkcnapc4#

你可以使用一个自定义的分配器来避免所有元素的默认初始化,就像在this answer中讨论的那样,与普通的元素访问一起使用:

const size_t N = 172490752;
std::vector<float, uninitialised_allocator<float> > vec(N);
for(size_t i=0; i!=N; ++i)
    vec[i] = the_value_for(i);

这避免了(i)默认初始化所有元素,(ii)在每次推送时检查容量,以及(iii)重新分配,但同时保留了使用std::vector(而不是std::unique_ptr<float[]>)的所有便利性。但是,allocator模板参数是不寻常的,因此您将需要使用通用代码而不是特定于std::vector的代码。

46scxncf

46scxncf5#

我有两个答案给你:
1.正如前面的答案所指出的,使用reserve预先分配存储可能非常有用,但是:

  1. push_back(或emplace_back)本身具有性能损失,因为在每次调用期间,它们必须检查是否必须重新分配向量。如果您已经知道要插入的元素数量,则可以通过使用访问操作符[]直接设置元素来避免这种损失。
    所以我推荐的最有效的方法是:
    1.使用'fill'构造函数初始化vector:
std::vector<float> values(172490752, 0.0f);

1.直接使用访问运算符设置条目:

values[i] = some_float;
++i;
axzmvihb

axzmvihb6#

push_back速度慢的原因是,随着向量的增长,它需要多次复制所有数据,即使不需要复制数据,它也需要检查。向量增长得足够快,这种情况不经常发生,但它仍然发生。一个粗略的经验法则是每个元素平均需要复制一次或两次;较早的元素将需要复制更多,但几乎一半的元素根本不需要复制。
您可以在创建向量时调用reserve,以确保它有足够的空间,从而避免复制,但不会进行检查。您可以通过从一开始就使用正确的大小创建它来避免复制和检查,方法是向向量构造函数提供元素的数量,然后使用索引Tobias suggested插入;不幸的是,这也需要额外的时间来初始化所有内容。
如果您在编译时而不仅仅是运行时知道浮点数,那么可以使用std::array,这可以避免所有这些问题。如果您只知道运行时的数字,我建议Mark’s suggestion使用std::unique_ptr<float[]>。你可以用

size_t size = /* Number of floats */;
auto floats = unique_ptr<float[]>{new float[size]};

您不需要执行任何特殊操作即可删除此内容;当它超出范围时,它将释放内存。在大多数情况下,您可以像使用矢量一样使用它,但它不会自动调整大小。

相关问题