# fastest zig zag scan

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?
``````public static int[][] Zig_Zag(int size){
int[][] data= new int[size][size];
int i= 1;
int j= 1;
for(int element= 0;element < size * size;element++){
data[i - 1][j - 1]= element;
if((i + j) % 2 == 0){
// Even stripes
if(j < size){
j++;
}else{
i+= 2;
}
if(i > 1){
i--;
}
}else{
// Odd stripes
if(i < size){
i++;
}else{
j+= 2;
}
if(j > 1){
j--;
}
}
}
return data;
}
``````
###### Who is Participating?

x
I wear a lot of hats...

"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.

Commented:
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
}

} while (start < end);

if (start == end)
{
result[i, j] = start;
}

return result;
}

regards,
Kate
0
ArchitectCommented:
write seprate method for this if else loop

because u have do same condition check in both if,else loop

that is code reusalbity .... then it much faster

``````if(j < size){
j++;
}else{
i+= 2;
}
if(i > 1){
i--;
}
``````
0
Author Commented:
what do you mean that it goes both direction at the same time?
0
Commented:
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
Author 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.
0
Commented:
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
Author Commented:
can you explain why it's twice as fast as I still don't get it
0
Author 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?
0
Commented:
Yes, thus half of the steps -> twice the speed. The algo you posted is doing this:

step 1)

0 x x
x x x
x x x

step 2)

0 1 x
x x x
x x x

step 3)

0 1 x
2 x x
x x x

..

step 9)

0 1 5
2 4 6
3 7 8
0
Commented:
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
Author 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?
0
Commented:
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>

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;
}
``````
0
Author Commented:
okay, running both using the parameter as 16... I got the algorithm from C-- as
``````(0,0)
(0,1)
(1,0)
(2,0)
(1,1)
(0,2)
(0,3)
(1,2)
(2,1)
(3,0)
(4,0)
(3,1)
(2,2)
(1,3)
(0,4)
(0,5)
(1,4)
(2,3)
(3,2)
(4,1)
(5,0)
(6,0)
(5,1)
(4,2)
(3,3)
(2,4)
(1,5)
(0,6)
(0,7)
(1,6)
(2,5)
(3,4)
(4,3)
(5,2)
(6,1)
(7,0)
(8,0)
(7,1)
(6,2)
(5,3)
(4,4)
(3,5)
(2,6)
(1,7)
(0,8)
(0,9)
(1,8)
(2,7)
(3,6)
(4,5)
(5,4)
(6,3)
(7,2)
(8,1)
(9,0)
(10,0)
(9,1)
(8,2)
(7,3)
(6,4)
(5,5)
(4,6)
(3,7)
(2,8)
(1,9)
(0,10)
(0,11)
(1,10)
(2,9)
(3,8)
(4,7)
(5,6)
(6,5)
(7,4)
(8,3)
(9,2)
(10,1)
(11,0)
(12,0)
(11,1)
(10,2)
(9,3)
(8,4)
(7,5)
(6,6)
(5,7)
(4,8)
(3,9)
(2,10)
(1,11)
(0,12)
(0,13)
(1,12)
(2,11)
(3,10)
(4,9)
(5,8)
(6,7)
(7,6)
(8,5)
(9,4)
(10,3)
(11,2)
(12,1)
(13,0)
(14,0)
(13,1)
(12,2)
(11,3)
(10,4)
(9,5)
(8,6)
(7,7)
(6,8)
(5,9)
(4,10)
(3,11)
(2,12)
(1,13)
(0,14)
(0,15)
(1,14)
(2,13)
(3,12)
(4,11)
(5,10)
(6,9)
(7,8)
``````
0
Commented:
i = row
j = column
0
Author Commented:
and the original java that I had as:

So why is there C-- no iterating through 15,15?
``````(0,0)
(0,1)
(1,0)
(2,0)
(1,1)
(0,2)
(0,3)
(1,2)
(2,1)
(3,0)
(4,0)
(3,1)
(2,2)
(1,3)
(0,4)
(0,5)
(1,4)
(2,3)
(3,2)
(4,1)
(5,0)
(6,0)
(5,1)
(4,2)
(3,3)
(2,4)
(1,5)
(0,6)
(0,7)
(1,6)
(2,5)
(3,4)
(4,3)
(5,2)
(6,1)
(7,0)
(8,0)
(7,1)
(6,2)
(5,3)
(4,4)
(3,5)
(2,6)
(1,7)
(0,8)
(0,9)
(1,8)
(2,7)
(3,6)
(4,5)
(5,4)
(6,3)
(7,2)
(8,1)
(9,0)
(10,0)
(9,1)
(8,2)
(7,3)
(6,4)
(5,5)
(4,6)
(3,7)
(2,8)
(1,9)
(0,10)
(0,11)
(1,10)
(2,9)
(3,8)
(4,7)
(5,6)
(6,5)
(7,4)
(8,3)
(9,2)
(10,1)
(11,0)
(12,0)
(11,1)
(10,2)
(9,3)
(8,4)
(7,5)
(6,6)
(5,7)
(4,8)
(3,9)
(2,10)
(1,11)
(0,12)
(0,13)
(1,12)
(2,11)
(3,10)
(4,9)
(5,8)
(6,7)
(7,6)
(8,5)
(9,4)
(10,3)
(11,2)
(12,1)
(13,0)
(14,0)
(13,1)
(12,2)
(11,3)
(10,4)
(9,5)
(8,6)
(7,7)
(6,8)
(5,9)
(4,10)
(3,11)
(2,12)
(1,13)
(0,14)
(0,15)
(1,14)
(2,13)
(3,12)
(4,11)
(5,10)
(6,9)
(7,8)
(8,7)
(9,6)
(10,5)
(11,4)
(12,3)
(13,2)
(14,1)
(15,0)
(15,1)
(14,2)
(13,3)
(12,4)
(11,5)
(10,6)
(9,7)
(8,8)
(7,9)
(6,10)
(5,11)
(4,12)
(3,13)
(2,14)
(1,15)
(2,15)
(3,14)
(4,13)
(5,12)
(6,11)
(7,10)
(8,9)
(9,8)
(10,7)
(11,6)
(12,5)
(13,4)
(14,3)
(15,2)
(15,3)
(14,4)
(13,5)
(12,6)
(11,7)
(10,8)
(9,9)
(8,10)
(7,11)
(6,12)
(5,13)
(4,14)
(3,15)
(4,15)
(5,14)
(6,13)
(7,12)
(8,11)
(9,10)
(10,9)
(11,8)
(12,7)
(13,6)
(14,5)
(15,4)
(15,5)
(14,6)
(13,7)
(12,8)
(11,9)
(10,10)
(9,11)
(8,12)
(7,13)
(6,14)
(5,15)
(6,15)
(7,14)
(8,13)
(9,12)
(10,11)
(11,10)
(12,9)
(13,8)
(14,7)
(15,6)
(15,7)
(14,8)
(13,9)
(12,10)
(11,11)
(10,12)
(9,13)
(8,14)
(7,15)
(8,15)
(9,14)
(10,13)
(11,12)
(12,11)
(13,10)
(14,9)
(15,8)
(15,9)
(14,10)
(13,11)
(12,12)
(11,13)
(10,14)
(9,15)
(10,15)
(11,14)
(12,13)
(13,12)
(14,11)
(15,10)
(15,11)
(14,12)
(13,13)
(12,14)
(11,15)
(12,15)
(13,14)
(14,13)
(15,12)
(15,13)
(14,14)
(13,15)
(14,15)
(15,14)
(15,15)
``````
0
Commented:
I've tried to run that C# for 16 and it returned 256 elements as it should. I'm searching what may be wrong.
0
Commented:
0
Author Commented:
I think I am printing it wrong... where would you print it so you got 256?
0
Author Commented:
oh nevermind I got it
0
Commented:
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;
}
``````
0

Experts Exchange Solution brought to you by

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

Author Commented:
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;
do
{
//result[y, x] = start++;
//result[m - y, m - x] = end--;

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

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

but that's not needed, just precalculate it

<see code>

regards,
Kate
``````int startSad = sad(x,y); // calculated only once (speed-up)