C++工程实践(9):数据抽象 (三)

2014-11-24 12:50:46 · 作者: · 浏览: 7
ct-based.

struct Vector3
{
Vector3(double x, double y, double z)
: x(x), y(y), z(z)
{
}

double x;
double y;
double z;
};

struct Planet
{
Planet(const Vector3& position, const Vector3& velocity, double mass)
: position(position), velocity(velocity), mass(mass)
{
}

Vector3 position;
Vector3 velocity;
const double mass;
};

相同功能的 advance() 代码简短得多,而且更容易验证其正确性。(想想如果把 C 语言版的 advance() 中的 vx、vy、vz、dx、dy、dz 写错位了,这种错误较难发现。)

void advance(int nbodies, Planet* bodies, double delta_time)
{
for (Planet* p1 = bodies; p1 != bodies + nbodies; ++p1)
{
for (Planet* p2 = p1 + 1; p2 != bodies + nbodies; ++p2)
{
Vector3 difference = p1->position - p2->position;
double distance_squared = magnitude_squared(difference);
double distance = std::sqrt(distance_squared);
double magnitude = delta_time / (distance * distance_squared);
p1->velocity -= difference * p2->mass * magnitude;
p2->velocity += difference * p1->mass * magnitude;
}
}
for (Planet* p = bodies; p != bodies + nbodies; ++p)
{
p->position += delta_time * p->velocity;
}
}

性能上,尽管 C++ 使用了更高层的抽象 Vector3,但它的性能和 C 语言一样快。看看 memory layout 就会明白:

C struct 的成员是连续存储的,struct 数组也是连续的。

value3

C++ 尽管定义了了 Vector3 这个抽象,它的内存布局并没有改变,Planet 的布局和 C planet 一模一样,Planet[] 的布局也和 C 数组一样。

另一方面,C++ 的 inline 函数在这里也起了巨大作用,我们可以放心地调用 Vector3::operator+=() 等操作符,编译器会生成和 C 一样高效的代码。

不是每个编程语言都能做到在提升抽象的时候不影响性能,来看看 Java 的内存布局。

如果我们用 class Vector3、class Planet、Planet[] 的方式写一个 Java 版的 N-body 程序,内存布局将会是:

value4

这样大大降低了 memory locality,有兴趣的读者可以对比 Java 和 C++ 的实现效率。

注:这里的 N-body 算法只为比较语言之间的性能与编程的便利性,真正科研中用到的 N-body 算法会使用更高级和底层的优化,复杂度是O(N log N),在大规模模拟时其运行速度也比本 naive 算法快得多。

更多的例子
Date 与 Timestamp,这两个 class 的“数据”都是整数,各定义了一套操作,用于表达日期与时间这两个概念。
BigInteger,它本身就是一个“数”。如果用 C++ 实现 BigInteger,那么阶乘函数写出来十分自然,下面第二个函数是 Java 语言的版本。
BigInteger factorial(int n)
{
BigInteger result(1);
for (int i = 1; i <= n; ++i) {
result *= i;
}
return result;
}

public static BigInteger factorial(int n) {
BigInteger result = BigInteger.ONE;
for (int i = 1; i <= n; ++i) {
result = result.multiply(BigInteger.valueOf(i));
}
return result;
}
图形学中的三维齐次坐标 Vector4 和对应的 4x4 变换矩阵 Matrix4

金融领域中经常成对出现的“买入价/卖出价”,可以封装为 BidOffer struct,这个 struct 的成员可以有 mid() “中间价”,spread() “买卖差价”,加减操作符,等等。
小结
数据抽象是C++的重要抽象手段,适合封装“数据”,它的语义简单,容易使用。数据抽象能简化代码书写,减少偶然错误。