c# - 在什么情况下，锯齿状阵列优于普通矩形阵列？

Question

我想弄清楚锯齿状数组的用处是什么？我的意思是锯齿状数组在现实生活中是否有任何应用？任何建议将不胜感激

Answer 1

如果您关心速度，那么您总是更喜欢锯齿状数组而不是多维数组。.NET 运行时支持（抖动和 CLR）对向量和数组有很大的区别。向量是数组的一种特殊情况，一维的起始索引为 0。它在 CLR 内部进行了非常严格的优化，拉动了所有可能的技巧。和抖动，为数组边界检查消除提供了很大的可能性。

锯齿状数组是向量的向量，使用它们时可以获得所有运行时优化。多维数组没有。速度差异大约是两倍。

仅当您喜欢语法便利并已验证数组索引不在程序的关键路径上时，才考虑使用多维数组。

Answer 2

什么算作“现实生活中的情况”？立即想到的一个例子是存储稀疏矩阵。矩阵通常以所谓的“密集”表示形式存储为二维数组。之所以称为密集，是因为它存储了数组的每个元素。但在某些情况下，数组的许多元素都是 0（或者可能是其他值），显式存储它们没有意义。授予大量稀疏矩阵表示使用少量一维数组。

在您不希望每个一维数组具有相同长度的情况下，真正的锯齿状数组绝对有用。锯齿状数组也使得交换整个“行”变得更加容易。

应该注意的是，至少在 .NET 中，锯齿状数组通常比多维数组具有更好的性能。

Answer 3

这是一个简单的例子：

假设由于某种原因您需要对整数进行因式分解。对于小整数，创建查找表以加快处理速度可能是有意义的。那将是一个锯齿状的数组。

int[][] factors = new int[][]
{
    null,                   // 0 doesn't have prime factors
    new int[] { },          // 1 is the trivial case
    new int[] { 2 },
    new int[] { 3 },
    new int[] { 2, 2 },
    new int[] { 5 },
    new int[] { 2, 3},
    new int[] { 7 },
    new int[] { 2, 2, 2 },
    new int[] { 3, 3 },
    new int[] { 2, 5 },
    // ... and so on
};

int[] PrimeFactorsOf(int value)
{
    if (value < factors.Length)
    {
        return factors[value];
    }
    else
    {
        // do the work
    }
}