常见操作的复数数组格式效率
我和我办公室的另一个人讨论了哪种复数矩阵数组格式更有效：交错存储实部和虚部，如
struct {
double real;
double imag;
} Complex foo[m][n];
单独存储矩阵的实部和虚部：
struct {
double rarray[m][n];
double iarray[m][n];
} CArray foo;
一方面， Complex[][] 更简单地表示复数数组，并且可能更容易按元素进行处理；另一方面，总体而言，CArray 似乎更高效。例如，矩阵乘法可以使用 CArray 格式对组件数组进行 4 次矩阵乘法来完成，而 Complex[][] 格式似乎可能会因使用元素之间交错（因为 (a+bi)*(c+di) = (ad - bc) + (ac + bd)i）。显然，MATLAB 使用后一种格式：在此处输入链接描述。
还有其他来源可以解决这个问题吗？
Another person in my office and I got into a discussion about which complex number matrix array format is more efficient: storing the real and imaginary parts interleaved, as in
struct {
double real;
double imag;
} Complex foo[m][n];
or by storing the real and imaginary parts of the matrix separately:
struct {
double rarray[m][n];
double iarray[m][n];
} CArray foo;
On the one hand, Complex[][] is more of a straightforward representation of an array of complex numbers, and might be easier to work on elementwise; on the other hand, it seems that CArray could be more efficient in general. For example, matrix multiplication can be done using 4 matrix multiplications of the component arrays using the CArray format, while the Complex[][] format seems as though it might suffer due to interleaving between the elements (since (a+bi)*(c+di) = (ad - bc) + (ac + bd)i). Apparently, MATLAB uses the latter format: enter link description here.
Are there any other sources that treat this question?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是适用于复数的古老的“结构数组与数组结构”问题。像大多数性能问题一样，一般来说答案是“这取决于”，但在这种情况下，我会把钱花在结构数组版本上。
为数值计算选择高效数据结构的关键是将通常同时需要的数据在内存中保持在彼此靠近的位置。到主内存获取数据很慢；您希望一次将一大块数据放入缓存并尽可能多地使用所有该缓存行。由于您几乎总是需要复数的实部和虚部来进行最有意义的计算，因此将它们存储为（实部，虚部）对的数组意味着如果您正在处理实部，则虚部几乎总是已经在缓存中等待计算。
但这取决于访问模式。仅仅因为我想象的操作将从复数数组中受益，并不意味着您正在想象相同的操作；其他人可以从双阵列方法中受益。如果你对矩阵 A 和 B 进行大量操作，例如 Re(A)*Im(B) - 这意味着什么，我不知道，但仍然 - 那么我认为 CArray 方法可能会明显更快，因为您不必通过加载不需要的数据（例如 Im(A) 和 Re(B)）来浪费内存带宽。
最终，这是一个经验问题；如果您了解访问模式的组合，那么测试这两种方法就很容易了。但对于我最容易想象的模式，第一种方法会获胜。
事实上，根据你的链接，Matlab 不同意我的观点，这让我感到惊讶，几乎让我怀疑我的答案。我不是 Matlab 的忠实粉丝，但 Matlab 的人很聪明并且关心如何快速进行数值计算。但这是那些一旦做出就很难撤销的决定之一——Matlab 现在无法在不破坏自己和第三方的无数其他东西的情况下改变这样一个基本的数据布局——而且这个决定可能已经做出了几十年前，当缓存性能不太重要时，与某些库的兼容性可能更重要。我注意到像 Lapack 这样的包是基于另一种格式，即结构数组（尽管只是隐式地——在 Fortran 中，complex 至少从 FORTRAN 66 开始就是一种原始数据类型）。
This is the age old "array of structures vs structure of arrays" question applied to complex numbers. Like most performance questions, in general the answer is "it depends", but in this case I would put my money on the array of structures version.
The key to choosing efficient data structures for numerical computing is to keep data you're typically going to need at the same time near each other in memory. Going out to main memory to get data is slow; you want to bring in one chunk of data at a time into cache and use all of that cache line as much as possible. Since you're almost always going to need both the real and imaginary component of a complex number for most meaningful computations, storing them as arrays of (real,imaginary) pairs means that if you're working on the real component, the imaginary component is almost always going to be sitting there already in cache ready to be computed upon.
But it depends on access patterns. Just because the operations I imagine are going to benefit from the array of complex numbers, doesn't mean you're imagining the same ones; others could benefit from the two-array approach. If you had lots of operations on matricies A and B like Re(A)*Im(B) - what that would mean, I don't know, but still - then I think that one would likely be significantly faster in the CArray approach, since you wouldn't have to waste memory bandwidth by loading in data you wouldn't need (eg, Im(A) and Re(B).)
Ultimately, this is an empirical question; if you have an idea of what your mix of access patterns is, it's easy enough to test out the two approaches. But for the patterns I can most easily envision, the first approach would win.
The fact that Matlab disagrees with me, as per your link, surprises me enough to almost make me doubt my answer. I'm not a huge Matlab fan, but the Matlab people are smart and concerned about making numerical computation fast. But this is one of those decisions which, once made, is incredibly hard to undo - Matlab couldn't change such a fundamental data layout now without breaking zillions of other things, of their own and third-party - and the decision was probably made decades ago when cache performance was less crucial and compatability with certain libraries probably mattered more. I note that packages like Lapack are based on the other format, array of structures (although only implicitly -- in Fortran, complex has been a primitive data type since at least FORTRAN 66).