As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center提供指导。
7年前关闭。
我正在编写一些需要尽可能快的代码,而又不占用我的所有研究时间(换句话说,就是没有手工优化的汇编程序)。
我的系统主要由一堆3D点(原子系统)组成,因此我编写的代码进行了大量的距离比较,最近邻居搜索以及其他类型的排序和比较。这些是大型的,数百万或十亿的点系统,嵌套在循环中的天真的O(n ^ 2)不会削减它。
对我来说,仅使用
我敢肯定,知道
数组很简单;我确切地知道何时分配内存,我所有算法的顺序如何,等等。没有黑盒未知数,我可能要经历。然而,我经常看到有人批评人们在互联网上对 vector 使用数组,这让我不得不怀疑是否遗漏了更多信息。
编辑:为澄清起见,有人问“为什么要使用数组或 vector 处理如此大的数据集”?好吧,最终,所有内容都存储在内存中,因此您需要选择一些抽象的底层。例如,我使用kd-trees来保存3D点,但是即使这样,kd-tree也需要基于数组或 vector 构建。
另外,我并不是在暗示编译器无法优化(我知道最好的编译器在许多情况下都可以胜过人类),而仅仅是说它们不能优化超出其约束所允许的范围,并且由于我的无知,我可能无意中引入了约束。 vector 的实现。
显然
现在,为Pixel提供空副本Ctor:
因此,总而言之:重新考虑您的算法,否则,也许可以使用围绕New [] / Delete []的自定义包装器。无论如何,由于某种未知的原因,STL的实现不会变慢,它恰好可以满足您的要求。希望你知道更多。
在刚开始使用 vector 的情况下,它们的行为可能令人惊讶,例如以下代码:
7年前关闭。
我正在编写一些需要尽可能快的代码,而又不占用我的所有研究时间(换句话说,就是没有手工优化的汇编程序)。
我的系统主要由一堆3D点(原子系统)组成,因此我编写的代码进行了大量的距离比较,最近邻居搜索以及其他类型的排序和比较。这些是大型的,数百万或十亿的点系统,嵌套在循环中的天真的O(n ^ 2)不会削减它。
对我来说,仅使用
std::vector
来保存点坐标将是最简单的。一开始,我认为阵列的速度可能差不多,所以太好了!但是,这个问题(Is std::vector so much slower than plain arrays?)使我感到非常不安。我没有时间使用数组和 vector 编写所有代码并对它们进行基准测试,因此我现在需要做出一个明智的决定。我敢肯定,知道
std::vector
背后详细实现的人可以在不影响速度的情况下使用这些功能。但是,我主要使用C进行编程,所以我不知道std::vector
在幕后做什么,而且我也不知道push_back
每次调用它都会执行一些新的内存分配,或者我还有其他“陷阱”可能会使我的代码运行缓慢。数组很简单;我确切地知道何时分配内存,我所有算法的顺序如何,等等。没有黑盒未知数,我可能要经历。然而,我经常看到有人批评人们在互联网上对 vector 使用数组,这让我不得不怀疑是否遗漏了更多信息。
编辑:为澄清起见,有人问“为什么要使用数组或 vector 处理如此大的数据集”?好吧,最终,所有内容都存储在内存中,因此您需要选择一些抽象的底层。例如,我使用kd-trees来保存3D点,但是即使这样,kd-tree也需要基于数组或 vector 构建。
另外,我并不是在暗示编译器无法优化(我知道最好的编译器在许多情况下都可以胜过人类),而仅仅是说它们不能优化超出其约束所允许的范围,并且由于我的无知,我可能无意中引入了约束。 vector 的实现。
最佳答案
这一切都取决于您如何实现算法。 std::vector
是这样的通用容器概念,它为我们提供了灵活性,但让我们可以自由地负责设计结构化算法的实现。我们将通过std::vector
观察到的大多数效率开销来自复制。 std::vector
提供了一个构造函数,该构造函数使您可以使用值X初始化N个元素,并且使用它时, vector 的速度与数组一样快。
我做了一个测试std::vector
与描述here的数组的测试,
#include <cstdlib>
#include <vector>
#include <iostream>
#include <string>
#include <boost/date_time/posix_time/ptime.hpp>
#include <boost/date_time/microsec_time_clock.hpp>
class TestTimer
{
public:
TestTimer(const std::string & name) : name(name),
start(boost::date_time::microsec_clock<boost::posix_time::ptime>::local_time())
{
}
~TestTimer()
{
using namespace std;
using namespace boost;
posix_time::ptime now(date_time::microsec_clock<posix_time::ptime>::local_time());
posix_time::time_duration d = now - start;
cout << name << " completed in " << d.total_milliseconds() / 1000.0 <<
" seconds" << endl;
}
private:
std::string name;
boost::posix_time::ptime start;
};
struct Pixel
{
Pixel()
{
}
Pixel(unsigned char r, unsigned char g, unsigned char b) : r(r), g(g), b(b)
{
}
unsigned char r, g, b;
};
void UseVector()
{
TestTimer t("UseVector");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
std::vector<Pixel> pixels;
pixels.resize(dimension * dimension);
for(int i = 0; i < dimension * dimension; ++i)
{
pixels[i].r = 255;
pixels[i].g = 0;
pixels[i].b = 0;
}
}
}
void UseVectorPushBack()
{
TestTimer t("UseVectorPushBack");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
std::vector<Pixel> pixels;
pixels.reserve(dimension * dimension);
for(int i = 0; i < dimension * dimension; ++i)
pixels.push_back(Pixel(255, 0, 0));
}
}
void UseArray()
{
TestTimer t("UseArray");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
Pixel * pixels = (Pixel *)malloc(sizeof(Pixel) * dimension * dimension);
for(int i = 0 ; i < dimension * dimension; ++i)
{
pixels[i].r = 255;
pixels[i].g = 0;
pixels[i].b = 0;
}
free(pixels);
}
}
void UseVectorCtor()
{
TestTimer t("UseConstructor");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));
}
}
int main()
{
TestTimer t1("The whole thing");
UseArray();
UseVector();
UseVectorCtor();
UseVectorPushBack();
return 0;
}
结果如下(在带有g++ -O3的Ubuntu amd64上编译):显然
push_back
在这里不是一个好选择,使用构造函数仍然比数组慢2倍。现在,为Pixel提供空副本Ctor:
Pixel(const Pixel&) {}
给我们以下结果:因此,总而言之:重新考虑您的算法,否则,也许可以使用围绕New [] / Delete []的自定义包装器。无论如何,由于某种未知的原因,STL的实现不会变慢,它恰好可以满足您的要求。希望你知道更多。
在刚开始使用 vector 的情况下,它们的行为可能令人惊讶,例如以下代码:
class U{
int i_;
public:
U(){}
U(int i) : i_(i) {cout << "consting " << i_ << endl;}
U(const U& ot) : i_(ot.i_) {cout << "copying " << i_ << endl;}
};
int main(int argc, char** argv)
{
std::vector<U> arr(2,U(3));
arr.resize(4);
return 0;
}
结果: