c - 在 C 中获取多维数组列的最有效方法

Question

我试图在 C 中创建一个矩阵数据结构。我有一个结构，并且有一个二维空指针数组(大小在堆中动态定义)用于该结构中的 cargo 部分(数据)。

给定一个列索引，我想在一维数组中获取该列的值。使用一个 for 或 while 循环很容易做到这一点。但是如果这个矩阵的行数是N，那么得到一个列 vector 需要O(N)的时间。我可以使用像 memcpy 这样的内存操作更有效地做到这一点吗？否则我该如何提高性能(我的数据非常结构化，我需要将其存储在某种矩阵中)。

Answer 1

如果列中的行数为 N，则您无法在少于 O(N) 的时间内复制、读取或以其他方式操作整个列。这是一个坚定的下限；每个元素都必须考虑，并且有 N 个。

所以不，你不能让它比 O(N) 更快。

请注意，x[3][5] 被编译器翻译为 x+((3*num_cols)+5)*size_of_element 用于已知大小二维数组。因此，使您的数组更快的一种方法是删除其动态大小调整。

另一个重要的一点是，顺序访问内存并不总是最快的——所以仅仅将数组旋转 90 度不一定会给你最好的结果。将阻塞 视为一种优化技术。底线:哪种内存布局最好取决于您的访问模式和硬件参数，例如缓存行长度和缓存大小。