How to move fast around a 2D array

[jehugaleahsa@gmail.com]

Hello:

I have a List<T[]where the internal arrays are of a fixed size.

I want to be able to take an index of, say, {1, 3} and quickly move to
the next nth position. So say I have a method that looks like this:

public struct Position
{
Position(int x, int y) { X = x; Y = y; }
int X { get; set; }
int Y { get; set; }
}

private Position Advance(Positio n pos, int distance)
{
// creates new position that is distance positions forward in the
array
}

I am currently implementing this method like this:

private Position Advance(Positio n pos, int distance)
{
int offset = pos.X * FIXED_ARRAY_SIZ E + pos.Y + distance;
return new Position(offset / FIXED_ARRAY_SIZ E, offset %
FIXED_ARRAY_SIZ E);
}

However, my profiler is showing that the majority of the time in my
application is being spent on this method, due to the multiplication
and division. I tried using Math.DivRem, but that didn't help very
much at all.

I am wondering if there is a more efficient manner of getting the
offset. Any help would be greatly appreciated.

Thanks,
Travis

[Alun Harford]

Re: How to move fast around a 2D array

jehugaleahsa@gm ail.com wrote:

Hello:
>
I have a List<T[]where the internal arrays are of a fixed size.
>
I want to be able to take an index of, say, {1, 3} and quickly move to
the next nth position. So say I have a method that looks like this:
>
public struct Position
{
Position(int x, int y) { X = x; Y = y; }
int X { get; set; }
int Y { get; set; }
}
>
private Position Advance(Positio n pos, int distance)
{
// creates new position that is distance positions forward in the
array
}
>
I am currently implementing this method like this:
>
private Position Advance(Positio n pos, int distance)
{
int offset = pos.X * FIXED_ARRAY_SIZ E + pos.Y + distance;
return new Position(offset / FIXED_ARRAY_SIZ E, offset %
FIXED_ARRAY_SIZ E);
}
>
However, my profiler is showing that the majority of the time in my
application is being spent on this method, due to the multiplication
and division. I tried using Math.DivRem, but that didn't help very
much at all.
>
I am wondering if there is a more efficient manner of getting the
offset. Any help would be greatly appreciated.

Well if you *must* keep the same data structure (I would have thought a
List<intwould be more appropriate given what you have to do here...)

If you know that distance will normally be small, you can do

private Position Advance(Positio n pos, int distance)
{
if(pos.X + distance >= 0 && pos.X + distance < FIXED_ARRAY_SIZ E)
{
return new Position(pos.Y, pos.X + distance);
}
else
{
//Your code
}
}

Another option would be (and you could do both if you need it *really*
fast but less readable):

Dictionary<int, Positionlookup = new Dictionary<int, Position>();
private Position Advance(Positio n pos, int distance)
{
int offset = pos.X * FIXED_ARRAY_SIZ E + pos.Y + distance;
Position p;
if(lookup.TryGe tValue(offset, out p))
{
return p;
}
int y = offset / FIXED_ARRAY_SIZ E;
for(int i = 0; i < FIXED_ARRAY_SIZ E; i++)
{
lookup.Add(y + i, new Position(y, i));
}
return new Position(p, offset % FIXED_ARRAY_SIZ E);
}

Or you can bit fiddle, depending on the value of FIXED_ARRAY_SIZ E.

Alun Harford

[jehugaleahsa@gmail.com]

Re: How to move fast around a 2D array

On Feb 17, 5:37 am, Alun Harford <devn...@alunha rford.co.ukwrot e:

jehugalea...@gm ail.com wrote:

Hello:

>

I have a List<T[]where the internal arrays are of a fixed size.

>

I want to be able to take an index of, say, {1, 3} and quickly move to
the next nth position. So say I have a method that looks like this:

>

public struct Position
{
    Position(int x, int y) { X = x; Y = y; }
    int X { get; set; }
    int Y { get; set; }
}

>

private Position Advance(Positio n pos, int distance)
{
    // creates new position that is distance positions forward in the
array
}

>

I am currently implementing this method like this:

>

private Position Advance(Positio n pos, int distance)
{
    int offset = pos.X * FIXED_ARRAY_SIZ E + pos.Y + distance;
    return new Position(offset / FIXED_ARRAY_SIZ E, offset %
FIXED_ARRAY_SIZ E);
}

>

However, my profiler is showing that the majority of the time in my
application is being spent on this method, due to the multiplication
and division. I tried using Math.DivRem, but that didn't help very
much at all.

>

I am wondering if there is a more efficient manner of getting the
offset. Any help would be greatly appreciated.

>
Well if you *must* keep the same data structure (I would have thought a
List<intwould be more appropriate given what you have to do here...)
>
If you know that distance will normally be small, you can do
>
private Position Advance(Positio n pos, int distance)
{
    if(pos.X + distance >= 0 && pos.X + distance < FIXED_ARRAY_SIZ E)
    {
       return new Position(pos.Y, pos.X + distance);
    }
    else
    {
       //Your code
    }
>
}
>
Another option would be (and you could do both if you need it *really*
fast but less readable):
>
Dictionary<int, Positionlookup = new Dictionary<int, Position>();
private Position Advance(Positio n pos, int distance)
{
    int offset = pos.X * FIXED_ARRAY_SIZ E + pos.Y + distance;
    Position p;
    if(lookup.TryGe tValue(offset, out p))
    {
       return p;
    }
    int y = offset / FIXED_ARRAY_SIZ E;
    for(int i = 0; i < FIXED_ARRAY_SIZ E; i++)
    {
       lookup.Add(y + i, new Position(y, i));
    }
    return new Position(p, offset % FIXED_ARRAY_SIZ E);
>
}
>
Or you can bit fiddle, depending on the value of FIXED_ARRAY_SIZ E.
>
Alun Harford- Hide quoted text -
>
- Show quoted text -

I could also use a int[][]. If there is a faster way of moving around
it, I would gladly do the additional memory managment.

[Jon Skeet [C# MVP]]

Re: How to move fast around a 2D array

On Feb 17, 10:13 pm, "Steve Gerrard" <mynameh...@com cast.netwrote:

<snip>

If I call each of these 1 million times in a loop, I get the following times:
Advance (creates a new Position each time): 0.469 secs
JustAdvance (does the math and stores result): 0.078 secs
>
It is spending about 16% of the time doing math, and 84% of the time creating a
new Position.

Could you post a short but complete benchmarking program to
demonstrate this? It would be interesting to tweak it.

Jon

[Steve Gerrard]

Re: How to move fast around a 2D array

Jon Skeet [C# MVP] wrote:

On Feb 17, 10:13 pm, "Steve Gerrard" <mynameh...@com cast.netwrote:
>
<snip>
>

>If I call each of these 1 million times in a loop, I get the
> following times: Advance (creates a new Position each time):
> 0.469 secs JustAdvance (does the math and stores result): 0.078
>secs
>>
>It is spending about 16% of the time doing math, and 84% of the time
>creating a new Position.

>
Could you post a short but complete benchmarking program to
demonstrate this? It would be interesting to tweak it.
>
Jon

Sure.

public struct Position
{
public int X , Y ;
public Position(int x, int y) { X = x; Y = y; }
}

const int FIXED_ARRAY_SIZ E = 1000;
const int LOOP_COUNT = 1000000;
Position test = new Position(0,0);

private void button1_Click(o bject sender, System.EventArg s e)
{
int x;
TimeSpan t;
DateTime start, finish;

start = DateTime.Now;
for (x = 0; x < LOOP_COUNT; x++)
{
test=Advance(te st,1);
}
finish = DateTime.Now;
t = finish-start;
System.Diagnost ics.Debug.Write Line(t.TotalSec onds.ToString(" #,0.000"));

start = DateTime.Now;
for (x = 0; x < LOOP_COUNT; x++)
{
JustAdvance(tes t,1);
}
finish = DateTime.Now;
t = finish-start;
System.Diagnost ics.Debug.Write Line(t.TotalSec onds.ToString(" #,0.000"));
}

private Position Advance(Positio n pos, int distance)
{
int offset = pos.X * FIXED_ARRAY_SIZ E + pos.Y + distance;
return new Position(offset / FIXED_ARRAY_SIZ E, offset %
FIXED_ARRAY_SIZ E);
}

private void JustAdvance(Pos ition pos, int distance)
{
int offset = pos.X * FIXED_ARRAY_SIZ E + pos.Y + distance;
pos.X = offset/FIXED_ARRAY_SIZ E;
pos.Y = offset % FIXED_ARRAY_SIZ E;
}