什么是跨步阵列？

Question

还有一个称为密​​度阵列的对应物.这是什么意思？我做了一些搜索,但没有得到准确的信息.

Answer 1

假设你有一个结构

struct SomeStruct {
    int someField;
    int someUselessField;
    int anotherUselessField;
};

和一个数组

struct SomeStruct array[10];

然后,如果你查看someField这个数组中的所有s,它们可以被认为是一个数组,但它们不会占用后续的内存单元,所以这个数组是跨越的.这里的步幅是sizeof(SomeStruct),跨步阵列的两个后续元件之间的距离.

这里提到的稀疏数组是一个更通用的概念,实际上是一个不同的概念:跨步数组在跳过的存储单元中不包含零,它们不是数组的一部分.

Strided数组是通常(密集)数组的推广stride != sizeof(element).

Answer 2

要迈出的是"采取长步骤"

thefreedictionary.com/stride

对于数组,这意味着只存在一些元素,就像每10个元素一样.然后,您可以通过不在其间存储空元素来节省空间.

密集阵列将是存在许多(如果不是全部)元素的阵列,因此元素之间没有空白空间.

Answer 3

如果要对2D数组的子集进行操作,则需要知道数组的"步幅".假设你有:

int array[4][5];

并且您希望对从数组[1] [1]开始到数组[2,3]的元素子集进行操作.图示,这是下图的核心:

+-----+-----+-----+-----+-----+
| 0,0 | 0,1 | 0,2 | 0,3 | 0,4 |
+-----+=====+=====+=====+-----+
| 1,0 [ 1,1 | 1,2 | 1,3 ] 1,4 |
+-----+=====+=====+=====+-----+
| 2,0 [ 2,1 | 2,2 | 2,3 ] 2,4 |
+-----+=====+=====+=====+-----+
| 3,0 | 3,1 | 3,2 | 3,3 | 3,4 |
+-----+-----+-----+-----+-----+

要准确地访问函数中数组的子集,您需要告诉被调用函数数组的步幅:

int summer(int *array, int rows, int cols, int stride)
{
    int sum = 0;
    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            sum += array[i * stride + j];
    return(sum);
}

和电话:

int sum = summer(&array[1][1], 2, 3, 5);

Answer 4

我在这里添加了另一个答案,因为我没有找到任何满意的现有答案.

维基百科解释了步幅的概念,并写道"步幅不能小于元素大小(这意味着元素重叠),但可以更大(表示元素之间的额外空间)".

但是,根据我发现的信息,跨步数​​组允许这样:通过允许步幅为零或负值来节省内存.

跨步阵列

将APL编译为JavaScript解释了跨步数组作为一种表示具有数据和步幅的多维数组的方法,这与假定隐含步幅为1的典型"矩形"数组表示不同.它允许正,负和零步幅.为什么？它允许许多操作仅改变步幅和形状,而不是基础数据,从而允许有效操纵大型阵列.

在处理大量数据时,这种跨步表示的优势变得明显.transpose(??),reverse(??)或drop(???)等函数可以重用数据数组,只关心为结果赋予新的形状,步幅和偏移量.重新形成的标量,例如1000000?0,只能占用恒定的内存量,利用步幅可以为0的事实.

我还没有确切地知道如何将这些操作实现为步幅​​和形状上的操作,但是很容易看出只改变这些操作而不是基础数据在计算方面会便宜得多.但是,值得注意的是,跨步表示可能会对缓存局部性产生负面影响,因此根据用例,使用常规矩形阵列可能会更好.

Answer 5

在高度优化的代码中,一种合理的coomon技术是将填充插入到数组中.这意味着第N个逻辑元素不再处于偏移状态N*sizeof(T).这可能是一个优化的原因是一些缓存是相关性限制的.这意味着它们不能为某些对i,j缓存array [i]和array [j].如果在密集阵列上运行的算法会使用许多这样的对,插入一些填充可能会减少这种情况.

发生这种情况的常见情况是图像处理.图像通常具有512字节的线宽或另一个"二进制圆数",并且许多图像处理例程使用像素的3×3邻域.因此,您可以在某些缓存架构上获得相当多的缓存驱逐.通过在每行的末尾插入"奇怪"数量的假像素(例如3),可以更改"步幅",并且相邻行之间的缓存干扰更少.

这是特定于CPU的,因此这里没有一般建议.

Answer 6

可能性1：步幅（Stride）描述了一个缓冲区数组以读取优化的数组

使用线性存储方法 存储多维数组时。步幅描述了缓冲区每个维度的大小，这将帮助您读取该数组。图片取自Nd4j（有关Stride的更多信息）

可能性2（下层）：跨度是数组的相邻成员之间的距离

这意味着索引为0和1的项目的地址在内存中不会连续，除非您使用单位跨度。较大的值将使项目在内存中的距离更远。

这在较低级别（字长优化，重叠数组，缓存优化）很有用。请参阅Wikipedia。