asked on

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

Open in new window

_Katka_

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

Sathish David Kumar N

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

Open in new window

kuntilanak

ASKER

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

_Katka_

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

kuntilanak

ASKER

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.

_Katka_

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

kuntilanak

ASKER

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

kuntilanak

ASKER

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?

_Katka_

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

_Katka_

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

kuntilanak

ASKER

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?

_Katka_

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

Open in new window

kuntilanak

ASKER

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)

Open in new window

_Katka_

i = row
j = column

kuntilanak

ASKER

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)

Open in new window

_Katka_

I've tried to run that C# for 16 and it returned 256 elements as it should. I'm searching what may be wrong.

_Katka_

Please, post here your Java implementation of that C# algorithm.

kuntilanak

ASKER

I think I am printing it wrong... where would you print it so you got 256?

kuntilanak

ASKER

oh nevermind I got it

ASKER CERTIFIED SOLUTION

_Katka_

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

kuntilanak

ASKER

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

Open in new window

_Katka_

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-x

if (endSad < sad) sad = endSad;

Open in new window

kuntilanak

ASKER

and indeed that is true