1

摘自 O'Reilly 的书：

在此处输入图像描述

从上面的摘录中，作者用性能术语解释了为什么在 big oh 或其他术语中应该存在性能差异，以及公式在 c 维数组中找到 n 中的任何元素的基础。

附加：为什么在三维示例中使用不同的数据类型？你为什么还要费心用不同的方式来表示这一点？

4

1 回答 1

1

该文章似乎指出了表示矩阵数据结构的不同方法以及单个数组表示的性能增益，尽管它并没有真正解释为什么您会获得性能增益。

例如，要表示一个 NxNxN 矩阵：

以对象形式：

Cell {
   int x,y,z;
}
Matrix {
   int size = 10;
   Cell[] cells = new Cell[size];
}

三数组形式：

Matrix {
    int size = 10;
    int[][][] data = new int[size][size][size];
}

在单个数组中：

Matrx {
    int size = 10;
    int[] data = new int[size*size*size];
}

对于您的问题，通过将 NxN 矩阵表示为 N*N 长度的单个数组可以提高性能，因为缓存可以提高性能（假设您不能将整个矩阵放在一个块中）；单个数组表示保证整个矩阵将位于连续的内存块中。当数据从内存移动到缓存（或磁盘到内存）时，它是以块的形式移动的，你有时会抓取比你需要的更多的数据。您抓取的额外数据包含您需要的数据周围的区域。

说，您正在逐行处理矩阵。当获取新数据时，操作系统可以每块抓取 N+10 个项目。在 NxN 的情况下，额外的数据（+10）可能是不相关的数据。在 N*N 长度数组的情况下，额外数据 (+10) 很可能来自矩阵。

SGI 的这篇文章似乎提供了更多细节，特别是良好缓存使用的原则：http: //techpubs.sgi.com/library/dynaweb_docs/0640/SGI_Developer/books/OrOn2_PfTune/sgi_html/ch06.html

于 2013-09-17T15:36:36.987 回答