Too much time consuming when using 3 nested loops to calculate a simple 255 X 255 matrix

This is a simple program to make a 255 X 255 matrix. The logic inside is simple but while executing this in c#, it is taking a lot of time (around 25 minutes). I am not able to figure out the problem. Please help.

int height = croppedArray.GetLength(1);
int width = croppedArray.GetLength(0);
for (int i = 0; i <= 255; i++)
{
    for (int j = 0; j <= 255; j++)
    {
        A = 0;
        for (int n = 0; n < height ; n++)
        {
            for (int m = 0; m <width-1; m++)
            {
                int fmn = croppedArray[m, n];

                int fmxn = croppedArray[m+1,n];

                if (fmn == i && fmxn == j)
                    A++;


            }
        }

        q_zero[i, j] = A;

    }
} 
return q_zero;

Answers


The "complexity" of the logic is rarely what takes CPU time. It is extraordinarily difficult to write logic complex enough to use measurable CPU time. What really makes code go slowly is loops. The complexity of the logic in the inner loop in this case is irrelevant because for each element of a 256x256 matrix (i.e. 65,536 times) you are looking at every single element of croppedArray. Even though it is fairly simple to look at each element, you are doing it 64k times!

Fortunately, it looks like you have 4 nested loops when you only need 2. Rather than iterating over the whole 2D matrix once for each element of q_zero, you can use q_zero as a whole bunch of accumulators. Just iterate over the 2D matrix once, incrementing the appropriate element in q_zero when you see it.

How about this instead:

int height = croppedArray.GetLength(1);
int width = croppedArray.GetLength(0);

for (int n = 0; n < height; n++)
{
    for (int m = 0; m < width - 1; m++)
    {
        int fmn = croppedArray[m, n];
        int fmxn = croppedArray[m+1,n];

        if (fmn >= 0 && fmn <= 255 && fmxn >= 0 && fmxn <= 255)
            q_zero[fmn, fmxn]++;
    }
}

return q_zero;

If I've understood you program correctly the i, j loops are unnecessary. The following code should be equivalent and perform much better:

        int height = croppedArray.GetLength(1); 
        int width = croppedArray.GetLength(0); 
        for (int n = 0; n < height ; n++) 
        { 
             for (int m = 0; m <width-1; m++) 
             { 
                int i= croppedArray[m, n]; 
                int j = croppedArray[m+1,n]; 

                if (i >= 0 && i <=255 && j >=0 && j <= 255) 
                {
                    q_zero[i, j]++; 
                } 
            } 
        }  
        return q_zero; 

Need Your Help

Android - iphone style tabhost

android tabs android-tabhost android-style-tabhost

Is it possible to style the Android Tabhost to look like that of the iPhone?

Ember error while loading asynchronous routes

javascript ember.js

I'm loading data from a JSON API. My routes almost always need to fetch new data from the server. I don't have control over the API format.