Question

I have matrix with 3 dimension (n*m*k). I am trying to fined the maximum number for each n and m by searching in k dimension.((I try to find the maximum number in k dimension for each n and m)) and at last i have a 2d matrix (n*m). i have the following code but it is so slow. Is there any new code or any changes to the current code that do this more quickly.

thanks.

我的c#代码:注: li是3个层面矩阵,是gra或等于零。

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;
                }

Answer 1

The biggest performance issue is that you use Array objects as elements of your list. This makes it so that every element access using GetValue boxes the value, i.e. allocates a new tiny object to hold the element value.

如果你替代的话,你的法典将大大加快。

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

iii

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

以及

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

iii

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

由于你事先不知道第3个层面,使用3D阵列更为困难。

An entirely different approach would be to compute the maximum as you re building the list li. This will help in two ways: 1. You avoid indexing into the list of arrays 以及 2. as long as m 以及 n aren t too large, you improve locality. That is: the values you re working iiiare closer together in memory, 以及 more likely to be in the processor cache.

Answer 2

This should do the trick (even though it could be kinda slower than your approach):

// 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)));
}

Answer 3

You could use a three-dimensional array like this:

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}	", maxValues[x, y]);
    Console.WriteLine();
}

Answer 4

从算法的角度来看,对于所有k的固定Nm的最高值,没有更有效的评估。它将进行O(n*m*k)业务。

Now, the only way to improve performance is to find improvements in your implementation, particularly in your storage of the 3D matrix.

Using List<Array> is a major area for improvement. You are prone to boxing issues (conversion of primitive types to objects) and making more function calls than are necessary.

1. 将3D矩阵降低到一系列价格:

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

Now index into your array at [i, j, k] using the following offset:

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

如果你只是使用一些原始物品,那么你就应当看到明显的改进。

<><>Edit>:

事实上,在C#(和其他几种语文)中,很容易实施3D阵列 直接<>,例如:

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

这比我首次描述的要简单得多(但当天末用1D表格内部翻译)。

www.un.org/Depts/DGACM/index_spanish.htm 如果第3个层面在规模上有所不同,则需要做什么......。

Now, it gets more interesting if the size of the 3rd dimension varies significantly. If it has a known maximum and isn t too big, you can simply set it to the maximum and fill the empty values with zeroes. This is simple and may meet your needs.

However, if the 3rd dimension can be very big, all these extra stored zeroes could waste a lot of valuable space and what you need is a Sparse Matrix representation.

There are different storage mechanisms for sparse matrices. For your purposes, you could consider your 3D array to be a 2D matrix, with (n*m) rows and max(k) columns. As the 3rd dimension varies in length, there are lots of empty spaces in your columns. This is called a sparse row and the standard data storage for this is "Compressed Sparse Row". Again, for performance this can be represented just by three primitive arrays, a data array, a row index array and a column pointer array. There are resources elsewhere on the web that describe the CSR implementation better than I can, but hopefully this will point you in the right direction.

友情链接