• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 2004
  • Last Modified:

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

0
kuntilanak
Asked:
kuntilanak
  • 11
  • 11
1 Solution
 
_Katka_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
 
Sathish David Kumar NArchitectCommented:
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

0
 
kuntilanakAuthor Commented:
what do you mean that it goes both direction at the same time?
0
Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
_Katka_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
 
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.
0
 
_Katka_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
 
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?
0
 
_Katka_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
 
_Katka_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
 
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?
0
 
_Katka_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>

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

0
 
kuntilanakAuthor 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)

Open in new window

0
 
_Katka_Commented:
i = row
j = column
0
 
kuntilanakAuthor 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)

Open in new window

0
 
_Katka_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
 
_Katka_Commented:
Please, post here your Java implementation of that C# algorithm.
0
 
kuntilanakAuthor Commented:
I think I am printing it wrong... where would you print it so you got 256?
0
 
kuntilanakAuthor Commented:
oh nevermind I got it
0
 
_Katka_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;
}

Open in new window

0
 
kuntilanakAuthor 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;
    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

0
 
_Katka_Commented:
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

0
 
kuntilanakAuthor Commented:
and indeed that is true
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Get expert help—faster!

Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.

  • 11
  • 11
Tackle projects and never again get stuck behind a technical roadblock.
Join Now