Consider this n X n matrix.
I want to visit only the values on the upper triangle (i.e visit only the Pij's where j > i, Pij being the value at line i and column j)
I want to visit k successive values at a time.
(P13 succeeds P12, P14 succeeds P13, and P23 succeeds P1n, meaning you change line after you've hit the end of line)
How do I find, in any vth visit, the first line and column to start my visit from?
I wasnt clever enough to find the function so I pre-calculated all the upper triangle matrix coordinates (the ij's of all successive points in the triangle) and placed them in a two dimension array that I could then visit the way I wanted to retrieve the line and column needed, but thats just not fast enough, as I'm dealing with huge numbers of data to be computed in parallel. I NEED THAT FUNCTION! I'm just too intellectually exhausted right now to try and find it (or its probably that I'm too stupid to find it)
The nerd hero who will find the answer will acquire 10 glory points.
(finishing GOW2 at titan difficulty equals 4 glory points, so its worth it)
5 comments:
You're looking for any and all values above the diagonal of the matrix? And you only want to grab the first k values?
you can calculate this in a straight forward way, you just need the dimensions (in this case it's a square matrix). It's not a formula more than algorithm.
coordinate getNextForItem(int i, int j)
//i = current row
//j = col
int nextrow = (j+1) mod n;
if (nextrow < j){ i = i+1; nextrow = i + 1;}
return new coordinated(i,j);
something like that. this works because the next value in a given row will always be the value to the right of the diagonal (aii is the diagonal value so ai(i+1) is the next value to the right.
You'll have to include a bounds check obviously but that's pretty much it.
the function needs to know which visit it is (nth visit), and it needs to know the size of the block of values to be visited by each visit.
Say I visit 10 values at a time, and I want to know the line and column of the first value of the 25th visit in a 1000 x 1000 matrix, only visiting the upper triangle.
typedef struct Coord2D
{
Coord2D(int x, int y): x(x),y(y){}
int x;
int y;
};
/*
the number of items to the right of the diagonal at row i are n-i (assuming a nxn matrix)
*/
Coord2D function(int visit, int itemsPerVisit, int n)
{
int itemsToSkip = visit*itemsPerVisit;
int row = 0;
int itemsInRow = n-1;
while (itemsToSkip > itemsInRow)
{
itemsToSkip -= itemsInRow;
--itemsInRow;
++row;
}
return Coord2D(row, itemsToSkip);
}
Excellent ideas!
Although plugging in numbers doesnt seem to give the right answer.
Ex: 10x10 matrix, items visited : 3, visit 4 should give me i:1, j:5 (starting from line 0 and visit 0)
but this algorithm is giving me i:1 j:3... because your skipped items are not adding the lower triangle skipped items! adding them should do the trick.
Thanks man. I think I should manage from there on. 7 glory points for giving me the bigger part of the solution. (its still an awful lot of glory points)
and shit... an iterative solution like this is not gonna give me less processing time... what I was looking for was a way to calculate it with one mathematical function. I'm not sure if its even possible.
Oh what the hell. Thanks anyways man.
Post a Comment