使用向量在 C++ 中声明 3D 数组结构 [英] Declaring 3D array structure in c++ using vector

问题描述

您好，我是一名使用 C++ 学习科学计算的研究生.我们的一些研究集中在算法的速度上，因此构造足够快的数组结构很重要.

Hi I am a graduate student studying scientific computing using c++. Some of our research focus on speed of an algorithm, therefore it is important to construct array structure that is fast enough.

我见过两种构造 3D 数组的方法.第一个是使用矢量库.

I've seen two ways of constructing 3D Arrays. First one is to use vector liblary.

vector<vector<vector<double>>> a (isize,vector<double>(jsize,vector<double>(ksize,0)))

这给出了大小为 isize x jsize x ksize 的 3D 数组结构.

This gives 3D array structure of size isize x jsize x ksize.

另一种是使用

new double[isize*jsize*ksize].为了方便地访问 (i,j,k) 的具体位置，运算符重载是必要的(对吗?).

new double[isize*jsize*ksize]. To access the specific location of (i,j,k) easily, operator overloading is necessary(am I right?).

根据我的经验，第一个要快得多，因为它可以轻松访问位置 (i,j,k)，而后一个必须计算位置并返回值.但是我看到有些人更喜欢后一个而不是第一个.为什么他们更喜欢后一种设置?使用第一个有什么缺点吗?

And from what I have experienced, first one is much faster since it can access to location (i,j,k) easily while latter one has to compute location and return the value. But I have seen some people preferring latter one over the first one. Why do they prefer the latter setting? and is there any disadvantage of using the first one?

提前致谢.

推荐答案

它们之间的主要区别在于布局:

Main difference between those will be the layout:

vector<vector<vector<T>>>

这将为您提供 vector> 的一维数组.
每个项目将是 vector 的一维数组.
而这些一维数组的每一项都将是一个一维数组 T.

This will get you a 1D array of vector<vector<T>>.
Each item will be a 1D array of vector<T>.
And each item of those 1D array will be a 1D array of T.

重点是，vector 本身并不存储其内容.它管理一块内存，并将内容存储在那里.这会产生许多不良后果:

The point is, vector itself does not store its content. It manages a chunk of memory, and stores the content there. This has a number of bad consequences:

1. 对于维度为 X·Y·Z 的矩阵，您最终将分配 1 + X + X·Y 个内存块.这是非常缓慢的，并且会破坏堆.想象一下:一个大小为 20 的立方体矩阵会触发 421 次对 new 的调用！
2. 要访问单元格，您有 3 个间接级别:
   • 您必须访问 vector>> 对象以获取指向顶级内存块的指针.
   • 然后您必须访问 vector> 对象以获取指向二级内存块的指针.
   • 然后您必须访问 vector 对象以获取指向叶内存块的指针.
   • 只有这样您才能访问T 数据.

1. For a matrix of dimension X·Y·Z, you will end up allocating 1 + X + X·Y memory chunks. That's horribly slow, and will trash the heap. Imagine: a cube matrix of size 20 would trigger 421 calls to new!
2. To access a cell, you have 3 levels of indirection:
   • You must access the vector<vector<vector<T>>> object to get pointer to top-level memory chunk.
   • You must then access the vector<vector<T>> object to get pointer to second-level memory chunk.
   • You must then access the vector<T> object to get pointer to the leaf memory chunk.
   • Only then you can access the T data.

另一方面，有一个连续的内存块(如new T[X * Y * Z]):

Having a contiguous memory block (like new T[X * Y * Z]) on the other hand gives:

1. 您分配了 1 个内存块.没有堆垃圾，O(1).
2. 您只需要访问指向内存块的指针，然后就可以直接访问所需的元素.
3. 所有矩阵在内存中都是连续的，这对缓存友好.

在那个年代，一次缓存未命中意味着数十或数百个计算周期丢失，不要低估缓存友好性方面.

Those days, a single cache miss means dozens or hundreds lost computing cycles, do not underestimate the cache-friendliness aspect.

顺便说一句，您可能没有提到一种更好的方法:使用众多矩阵库中的一个，它会自动为您处理此问题并提供很好的支持工具(如 SSE 加速矩阵运算).一个这样的库是Eigen，但还有很多其他的.

By the way, there is a probably better way you didn't mention: using one of the numerous matrix libraries that will handle this for you automatically and provide nice support tools (like SSE-accelerated matrix operations). One such library is Eigen, but there are plenty others.

→ 你想做科学计算?让一个库来处理样板和基础知识，这样您就可以专注于科学计算部分.

→ You want to do scientific computing? Let a lib handle the boilerplate and the basics so you can focus on the scientific computing part.

这篇关于使用向量在 C++ 中声明 3D 数组结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！