在三维矩阵中寻找最大值

本文关键字：寻找 最大值 三维 | 更新日期: 2023-09-27 18:20:11

我有一个三维矩阵（n*m*k）。我试图通过在k维中搜索来定义每个n和m的最大数量。（（我试图找到每个n和m在k维中的最大数）），最后我得到了一个2d矩阵（n*m）。我有以下代码，但它太慢了。是否有任何新代码或对当前代码的任何更改可以更快地执行此操作。

谢谢。

我的c#代码：注意：li是三维矩阵，它们更大或等于零。

int[,] array2 = new int[n, m];   
int[,] array = new int[n, m];
 List<Array> li = new List<Array>();             
for(int k = 0; k <'not a specific value, change each time' ; k++)
   { 
     li.Add(array);
     %% changing array
   } %% so li will became a (n*m*k) matrix   
for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                {
                    int ma = -2;
                    int d = 0;
                    while (d <= k)
                    {
                        ma = Math.Max(ma, Convert.ToInt32(li[d].GetValue(i, j)));
                        d++;
                    }
                    array2[i, j] = ma;
                }

在三维矩阵中寻找最大值

最大的性能问题是使用Array对象作为列表的元素。这使得使用GetValue访问的每个元素都将值框起来，即分配一个新的小对象来保存元素值。

如果你更换，你的代码会运行得更快

List<Array> li = new List<Array>();

带有

List<int[,]> li = new List<int[,]>();

和

ma = Math.Max(ma, Convert.ToInt32(li[d].GetValue(i, j)));

带有

ma = Math.Max(ma, li[d][i, j];

由于您事先不知道三维，因此使用三维阵列会更加困难。

一种完全不同的方法是在构建列表li时计算最大值。这将在两个方面有所帮助：1。您可以避免索引到数组和2的列表中。只要m和n不太大，就可以提高局部性。也就是说：您正在处理的值在内存中更接近，更有可能在处理器缓存中。

这应该能奏效（尽管它可能比你的方法慢一点）：

// put this at the top of your source file
using System.Linq;
// put this where you calculate the maxima
for(int i = 0; i < array2.GetLength(0); ++i)
for(int j = 0; j < array2.GetLength(1); ++j)
{
    array2[i, j] = Convert.ToInt32(li.Max(x => x.GetValue(i, j)));
}

您可以使用这样的三维数组：

int xRange = 10;
int yRange = 10;
int zRange = 10;
int[, ,] matrix = new int[xRange, yRange, zRange];
// set up some dummy values
for (int x = 0; x < xRange; x++)
    for (int y = 0; y < yRange; y++)
        for (int z = 0; z < zRange; z++)
            matrix[x, y, z] = x * y * z;
// calculate maximum values
int[,] maxValues = new int[xRange, yRange];
/* LINQ version of maximum calculation
for (int x = 0; x < xRange; x++)
    for (int y = 0; y < yRange; y++)
        maxValues[x, y] = Enumerable.Range(0, zRange).Select(z => matrix[x, y, z]).Max();
*/
// longhand version of maximum calculation
for (int x = 0; x < xRange; x++)
    for (int y = 0; y < yRange; y++)
        for (int z = 0; z < zRange; z++)
            maxValues[x, y] = Math.Max(maxValues[x, y], matrix[x, y, z]);
// display results
for (int x = 0; x < xRange; x++)
{
    for (int y = 0; y < yRange; y++)
        Console.Write("{0}'t", maxValues[x, y]);
    Console.WriteLine();
}

从算法的角度来看，没有更有效的方法来评估所有k的固定n，m的最大值。这将需要O（n*m*k）个运算。

现在，提高性能的唯一方法是在实现中找到改进，特别是在3D矩阵的存储中。

使用List<Array>是一个需要改进的主要领域。您很容易出现装箱问题（将基元类型转换为对象），并进行超出必要数量的函数调用。

将您的3D矩阵简化为基元数组：

int[] my3DArray = new int[n * m * l]; // Note I'm using l where you use k

现在使用以下偏移量在[i，j，k]处对数组进行索引：

int elementAtIJK = my3DArray[i + (n * j) + (m * n * k)];

如果您只使用基元数组，您应该看到一个明确的改进。

编辑：

事实上，在C#（和其他几种语言）中，直接实现3D阵列非常容易，例如：

   int[,,] my3DArray = new int[n,m,l];
   int elementAtIJK = my3DArray[i,j,k];

这比我最初描述的要简单得多（但最终会以1D形式进行内部翻译）。

如果第三个维度的大小不同该怎么办

现在，如果第三维度的大小变化很大，就会变得更有趣。如果它有一个已知的最大值，并且不太大，您可以简单地将其设置为最大值，并用零填充空值。这很简单，可以满足您的需求。

然而，如果第三维度可能非常大，那么所有这些额外存储的零可能会浪费大量宝贵的空间，而您需要的是稀疏矩阵表示。

稀疏矩阵有不同的存储机制。出于您的目的，您可以将您的3D阵列视为具有（n*m）行和最大（k）列的2D矩阵。由于第三个维度的长度各不相同，所以列中有很多空白。这被称为稀疏行，其标准数据存储为"压缩稀疏行"。同样，为了提高性能，这可以仅由三个基元数组表示，一个数据数组、一个行索引数组和一个列指针数组。网络上其他地方的资源比我更好地描述了CSR的实现，但希望这能为您指明正确的方向。

相关文章：