I have the code below, which is taken from http://rosettacode.org/wiki/Zig_Zag. My question would be, is there a way to make the code to perform similar function in a faster/efficient way than the code below?? If there is then how?

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Hi, I'd go (from the same page) with the C# one, it seems to go from both directions at the same time (potentially twice as fast, and no modulo operation)
I guess a conversion hint is [,] = [][], otherwise it should be the same. It's worth the try.

public static int[,] ZigZag(int n)
{
int[,] result = new int[n, n];
int i = 0, j = 0;
int d = -1; // -1 for top-right move, +1 for bottom-left move
int start = 0, end = n * n - 1;

do
{
result[i, j] = start++;
result[n - i - 1, n - j - 1] = end--;

i += d; j -= d;

if (i < 0)
{
i++; d = -d; // top reached, reverse
}
else if (j < 0)
{
j++; d = -d; // left reached, reverse
}

what do you mean that it goes both direction at the same time?

0

The most successful MSPs rely on metrics â€“ known as key performance indicators (KPIs) â€“ for making informed decisions that help their businesses thrive, rather than just survive. This eBook provides an overview of the most important KPIs used by top MSPs.

I guess it calculates the step index on the specific coordinates, both from start and from the end - because this pattern is easily reversible - too speed it up. Like:

step 1)

0 x x
x x x
x x 8

step 2)

0 1 x
x x x
x 7 8

step 3)

0 1 x
2 x 6
x 7 8

step 4)

0 1 5
2 x 6
3 7 8

step 5)

0 1 5
2 4 6
3 7 8

So 5 instead of 9 steps in this case.

regards,
Kate

0

kuntilanakAuthor Commented:

let me explicityly say what I am trying to do here... I am trying to find the minimum of sum of absolute difference between two array size, one is called the frame and the other called the window. The window array is smaller than the frame. So I am doing a zig-zig scan on the frame and then for each point, which will be the starting position of the frame to compare I will find the sum of absolute difference between that and the window I have.

Well ok, this algorithm just does what yours does - returns the indexed 2D array in a zig-zag manner - only it does it twice as fast at least (it's from the same page as you took the Java example). I was just answering your original question. Just to explain why I sent, what I sent.

Now, if you don't want to use this array, why generate one in the first place ?
Are you trying to do adaptive search window, or something like that ?

I'm confused a bit.

regards,
Kate

0

kuntilanakAuthor Commented:

can you explain why it's twice as fast as I still don't get it

0

kuntilanakAuthor Commented:

wait are you saying that we're zig zagging from top left and bottom right at the same time and we meet at the midle?

The algorithm is only going while (start < end) thus when it arrives at 4 it will "meet" in the middle. It works for the arbitrary array size of course. Check this even grid size:

0 1 5 6
2 4 7 c
3 8 b d
9 a e f

is done by (a-f replaces 10-15) done by these two halves, from the beginning:

0 1 5 6
2 4 7 x
3 x x x
x x x x

and this part is done simultaneously from the end

x x x x
x x x c
x 8 b d
9 a e f

They'll meet when start is about to be start = 8 and end = 7 thus violating start < end, thus method is done. So only 8 steps instead of 16. It's always twice as fast for even sized grids (2x2, 4x4,..) [steps = n / 2] and almost as twice fast for odd sized grids (3x3, 5x5,..) [steps = (n / 2) + 1].

regards,
Kate

0

kuntilanakAuthor Commented:

okay I get all that, now what if I want to call a method called sad for a point that is traced by the zig zag... is i the row here and j is the column?

Another way to look at it is, that the Java algo is doing only:

data[i - 1][j - 1]= element; // per cycle

while the one I posted is doing:

result[i, j] = start++; // one point from the beginning
result[n - i - 1, n - j - 1] = end--; // second from the end

so two points per cycle, thus the speed, in Java it should look like something like <see code>

For your last comment:

i should be y
j should be x

If Java's [][] stands for [x][y] then you should switch it from result[i][j] to result[j][i].

regards,
Kate

public static int[][] ZigZag(int n){ int[][] result = new int[n][n]; int i = 0, j = 0; int d = -1; int start = 0, int end = n * n - 1; do { result[i][j] = start++; result[n - i - 1][n - j - 1] = end--; i += d; j -= d; if (i < 0) { i++; d = -d; // top reached, reverse } else if (j < 0) { j++; d = -d; // left reached, reverse } } while (start < end); if (start == end) { result[i][j] = start; } return result;}

Is it working, is the count 256 now ? if it returns the result reversed then just read it instead of [x][y] by [y][x]. I've checked it and it performs about 15% better in test (1,000,000 calls ~4.9s against the original ~5.6s). I also made some further slight improvements to the algorithm and it should now go as far as 22% better (~4.45s).

regards,
Kate

public static int[,] ZigZagImproved(int n){ int[,] result = new int[n, n]; int x = 0, y = 0, d = -1, m = n - 1; int start = 0, end = n * n - 1; do { result[y, x] = start++; result[m - y, m - x] = end--; x -= d; y += d; if (y < 0) { y = 0; d = 1; } else if (x < 0) { x = 0; d = -1; } } while (start < end); if (start == end) { result[y, x] = start; } return result;}

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

thank you so much for the change! so now below is the change for my sum of absolute difference code.. I just had an extra variable called sad which holds the current lowest minimal sad

public int ZigZagImproved(int n){ int[][] result = new int[n][n]; int x = 0, y = 0, d = -1, m = n - 1; int start = 0, end = n * n - 1; int sad = 100000000000000; do { //result[y, x] = start++; //result[m - y, m - x] = end--; if (sad(x,y) < sad) sad = sad(x,y); if(sad(m-y, m-x) < sad) sad = sad(m-x, m-y) start++; end--; x -= d; y += d; if (y < 0) { y = 0; d = 1; } else if (x < 0) { x = 0; d = -1; } } while (start < end); if (start == end) { //result[y, x] = start; if (sad(x,y) < sad) sad = sad(x,y); } return sad;}

Hi, I'm glad it finally works, but I recommend you to precalculate the sad(x,y) like

if (sad(x,y) < sad) sad = sad(x,y); // <- sad(x,y) is called twice

but that's not needed, just precalculate it

<see code>

regards,
Kate

int startSad = sad(x,y); // calculated only once (speed-up)if (startSad < sad) sad = startSad; // here you're comparing just values (quick)int endSad = sad(m-x, m-y); // I've noticed you got switched m-y and m-xif (endSad < sad) sad = endSad;

It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for freeEdge Out The Competitionfor your dream job with proven skills and certifications.Get started todayStand Outas the employee with proven skills.Start learning today for freeMove Your Career Forwardwith certification training in the latest technologies.Start your trial today

I guess a conversion hint is [,] = [][], otherwise it should be the same. It's worth the try.

public static int[,] ZigZag(int n)

{

int[,] result = new int[n, n];

int i = 0, j = 0;

int d = -1; // -1 for top-right move, +1 for bottom-left move

int start = 0, end = n * n - 1;

do

{

result[i, j] = start++;

result[n - i - 1, n - j - 1] = end--;

i += d; j -= d;

if (i < 0)

{

i++; d = -d; // top reached, reverse

}

else if (j < 0)

{

j++; d = -d; // left reached, reverse

}

} while (start < end);

if (start == end)

{

result[i, j] = start;

}

return result;

}

regards,

Kate