3

语境

我正在实现一个接缝雕刻算法。

我将图片中的像素表示为一维数组

private int[] picture;

每个int代表像素的RGB。

要访问像素，我使用辅助方法，例如：

private int pixelToIndex(int x, int y) {return (y * width()) + x;}

另一种方法是存储在二维数组中：

private int[][] picture;

接缝雕刻算法有两个部分。

首先，它进行一些图像处理，找到能量最低的水平或垂直连接接缝。在这里，像素访问在行之间跳跃了一下。

其次，它去除了这个连接的接缝。

对于垂直接缝，我标记要删除的像素-1并创建一个新的图片数组，跳过删除的像素，如下所示：

int i = 0, j = 0;
while (i < temp.length) {
    if (picture[j] != -1) {
        temp[i++] = picture[j];
    }
    j++;
}
picture = temp;

对于水平接缝，给定特定列，我将该列的已删除像素之后的所有像素向上移动一行，如下所示：

for (int i = 0; i < temp.length; i++) {
    int row = indexToY(i);
    int col = indexToX(i);
    int deletedCell = seam[col];

    if (row >= deletedCell) temp[i] = picture[i + width()];
    else temp[i] = picture[i];
}
picture = temp;

问题

显然，由于每个子数组的开销，一维数组使用较少的物理内存，但考虑到我迭代矩阵的方式，二维数组是否会更有效地被 CPU 缓存，从而更高效？

这些阵列在加载到 CPU 缓存和 RAM 中的方式有​​何不同？一维数组的一部分会进入一级缓存吗？一维和二维数组如何加载到内存中？它会取决于数组的大小吗？

4

2 回答 2

2

一个 int 数组就是这样表示的：一个 int 值数组。数组数组...增加了一定的开销。所以，简短的回答：在处理大量数据时；普通的一维数组是你的朋友。

另一方面：只有在了解瓶颈后才开始优化。您知道，优化内存中的数据结构并没有多大帮助……例如，当您的应用程序花费大部分时间等待 IO 时。如果您编写“高性能”代码的尝试产生“复杂、难以阅读、因此难以维护”的代码……您可能专注于错误的领域。

此外：具体性能数字受许多不同变量的影响。所以你想先做分析；看看不同的硬件、不同的数据集等会发生什么。

另一个旁注：有时，对于实数运算；在 C++ 中实现某些东西也可以是一个可行的选择，可以通过 JNI 进行调用。这实际上取决于您的问题的性质；使用的频率是多少；用户期望的响应时间；等等。

于 2016-04-05T14:00:21.650 回答
1

Java具有用于多维数组的数组数组。在您的情况下int[][]是一个数组int[]（当然int[]是一个数组int）。因此，矩阵表示为一组行和每行的指针。在这种情况下，这意味着 NxM 矩阵正在为数据和指针数组占用 NxM。

由于您可以将任何矩阵表示为数组，因此以这种方式存储它会减少内存消耗。

另一方面，将二维矩阵表示为数组的情况下的地址操作并不复杂。

如果我们假设您有一个 NxM 访问的矩阵和一个大小为 NxM 的数组表示该矩阵，则您可以访问Matrix[x,y]as的元素Array[x*n+y]。

Array[i]是紧凑的，它很有可能在 L1 缓存中，甚至在寄存器缓存中。

Matrix[x,y]需要一次内存读取，加法 Array[x*n+y]需要一次乘法和一次加法。

所以，我会花上两分钱Array，但无论如何它必须经过测试（不要忘记等待 JIT 编译器的预热时间）

于 2016-04-05T14:12:55.877 回答