Single vs Double Array in a loop

  • (2 Pages)
  • +
  • 1
  • 2

27 Replies - 1111 Views - Last Post: 08 August 2013 - 02:53 PM Rate Topic: -----

#1 StrongJoshua  Icon User is offline

  • D.I.C Head

Reputation: 43
  • View blog
  • Posts: 136
  • Joined: 19-July 13

Single vs Double Array in a loop

Posted 05 August 2013 - 02:23 PM

A single array stores one giant list of values and can be easily looped through with a single for loop.
A double array stores values in a way that simulates rows and columns in a table and can be traversed with double for loops, one for the outer array and one for the inner arrays.
Now my question is, does it have any impact performance wise to use one over the other? The reason I ask is because to make a level editor for my game I need an array (or double array) of slots to fill the level so I can place "blocks" wherever I need, in an organized manner. These levels may get somewhat big so I would prefer the more optimized method.
Thanks for your help, StrongJoshua :)

Is This A Good Question/Topic? 0
  • +

Replies To: Single vs Double Array in a loop

#2 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2194
  • View blog
  • Posts: 5,222
  • Joined: 10-September 10

Re: Single vs Double Array in a loop

Posted 05 August 2013 - 02:28 PM

A more optimized method would be to use a class that completely defines the "blocks," including their location in the game space. You could then add the Block instances to a collection of some kind that could be iterated as needed during the game's execution.
Was This Post Helpful? 2
  • +
  • -

#3 StrongJoshua  Icon User is offline

  • D.I.C Head

Reputation: 43
  • View blog
  • Posts: 136
  • Joined: 19-July 13

Re: Single vs Double Array in a loop

Posted 05 August 2013 - 02:31 PM

View PostGregBrannon, on 05 August 2013 - 04:28 PM, said:

A more optimized method would be to use a class that completely defines the "blocks," including their location in the game space. You could then add the Block instances to a collection of some kind that could be iterated as needed during the game's execution.

Oh yes, I do have a block class. The slots make sure that blocks aren't placed randomly, but in a grid. Also, these slots would highlight if the mouse is hovering over them.
Was This Post Helpful? 0
  • +
  • -

#4 NeoTifa  Icon User is online

  • Whorediot
  • member icon





Reputation: 2498
  • View blog
  • Posts: 15,471
  • Joined: 24-September 08

Re: Single vs Double Array in a loop

Posted 05 August 2013 - 02:48 PM

A for loop is O(n), where n is the number of times iterated through the loop. When you have a loop within the loop, it's got its own set of iterations(m), and they're looping through the outer n number of times, so it would iterate O(n*m) times. In the most general case, a doubly nested loop is evaluated at O(nx), where x is the number of nested loops, which in this case would be 2, making your loops O(n2). If it's feasible, always go with as small as possible. But with a just O(n2), it wouldn't be a real kicker until you start having humongous sets of data to access/iterate though, then a better data structure would be needed (edit: ... like greg said, further defining a 'block' to access easier).

https://en.wikipedia.../Big_O_notation

This post has been edited by NeoTifa: 05 August 2013 - 02:50 PM

Was This Post Helpful? 1
  • +
  • -

#5 StrongJoshua  Icon User is offline

  • D.I.C Head

Reputation: 43
  • View blog
  • Posts: 136
  • Joined: 19-July 13

Re: Single vs Double Array in a loop

Posted 05 August 2013 - 02:55 PM

Say the level size was constant (i.e 100x100 blocks). Then both loops would loop through 10,000 times, right? Is the one dimensional array more efficient because it might (I'm saying might because I don't know) take less time to access or does it not matter?
Was This Post Helpful? 0
  • +
  • -

#6 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2194
  • View blog
  • Posts: 5,222
  • Joined: 10-September 10

Re: Single vs Double Array in a loop

Posted 05 August 2013 - 03:05 PM

If each block instance is aware of its location in the game space, why do you need two loops?

More to the point, if everything known and needed to be known about a Block is contained in the Block instance, you should only ever need one loop to iterate through all block instances in the game. Why do you think you'd need two or more loops?
Was This Post Helpful? 0
  • +
  • -

#7 NeoTifa  Icon User is online

  • Whorediot
  • member icon





Reputation: 2498
  • View blog
  • Posts: 15,471
  • Joined: 24-September 08

Re: Single vs Double Array in a loop

Posted 05 August 2013 - 03:11 PM

Depends on what you're trying to do. Yes, in terms of number of calculations, it would be. If the code inside a nested 100x100 for loop was only 1 statement, then yes, about 10,000 "calculations" (in Java, there is encapsulation, so it's rarely just 1 statement, which is evaluated at O(1), and what that translates to in machine code is even more code. One "statement" such as 'var++' is really more like "GET R0; STR R0, R1; ADD R1, 1; STR R1, R0;" or something suchlike in a more "machine code", which is obviously more than 1 statement). If performance is essential, go lower level, like C or even Assembly. But to answer your question, it depends on what your doing and the structure you're trying to achieve. If you're jumping through more hoops to keep it a single dimension array, then no, it might very well not be. But in terms of Big O, yes O(n) is better than O(n2).
Was This Post Helpful? 1
  • +
  • -

#8 StrongJoshua  Icon User is offline

  • D.I.C Head

Reputation: 43
  • View blog
  • Posts: 136
  • Joined: 19-July 13

Re: Single vs Double Array in a loop

Posted 05 August 2013 - 03:13 PM

View PostGregBrannon, on 05 August 2013 - 05:05 PM, said:

If each block instance is aware of its location in the game space, why do you need two loops?

More to the point, if everything known and needed to be known about a Block is contained in the Block instance, you should only ever need one loop to iterate through all block instances in the game. Why do you think you'd need two or more loops?

Maybe I didn't explain myself correctly, though I would need 2 loops one for drawing the blocks in the block array and one for finding the highlighted slot, these are not related. What my question was if a 2 dimensional array (a[100][100]) would take as long to loop through as a 1 dimensional array (a[10,000]) or would one be faster.
Was This Post Helpful? 0
  • +
  • -

#9 NeoTifa  Icon User is online

  • Whorediot
  • member icon





Reputation: 2498
  • View blog
  • Posts: 15,471
  • Joined: 24-September 08

Re: Single vs Double Array in a loop

Posted 05 August 2013 - 03:14 PM

Well, 100x100 == 10,000, so they would probably be similar in performance. In this day and age, 10,000 is just chump change to a computer.

This post has been edited by NeoTifa: 05 August 2013 - 03:14 PM

Was This Post Helpful? 2
  • +
  • -

#10 StrongJoshua  Icon User is offline

  • D.I.C Head

Reputation: 43
  • View blog
  • Posts: 136
  • Joined: 19-July 13

Re: Single vs Double Array in a loop

Posted 05 August 2013 - 03:20 PM

View PostNeoTifa, on 05 August 2013 - 05:11 PM, said:

Depends on what you're trying to do. Yes, in terms of number of calculations, it would be. If the code inside a nested 100x100 for loop was only 1 statement, then yes, about 10,000 "calculations" (in Java, there is encapsulation, so it's rarely just 1 statement, which is evaluated at O(1), and what that translates to in machine code is even more code. One "statement" such as 'var++' is really more like "GET R0; STR R0, R1; ADD R1, 1; STR R1, R0;" or something suchlike in a more "machine code", which is obviously more than 1 statement). If performance is essential, go lower level, like C or even Assembly. But to answer your question, it depends on what your doing and the structure you're trying to achieve. If you're jumping through more hoops to keep it a single dimension array, then no, it might very well not be. But in terms of Big O, yes O(n) is better than O(n2).

I didn't mean to make this question as elaborate as your answers imply, but I could write a small example of the two different situations:
int w = 100;
int h = 100;
Slot [] slots = new Slot[w * h]; //pretend these are all initialized
for(int x = 0; x < w; x++)
{
   for(int y = 0; y < h; y++
   {
       if(slots[x + y * w].getIfHighlighted)
          //draw the slot overlay/highlight
   }
}
//or
Slot [][] slots = new Slot[w][h];
for(int j = 0; j < slots.length; j++)
{
    for(int k = 0; k < slots[j].length; k++)
    {
       if(slots[j][k].getIfHighlighted)
          //draw the slot overlay/highlight
    }
}


Which of these 2 code examples would run faster (this would be implemented better in my actual program)?
Was This Post Helpful? 0
  • +
  • -

#11 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8316
  • View blog
  • Posts: 31,836
  • Joined: 06-March 08

Re: Single vs Double Array in a loop

Posted 05 August 2013 - 03:25 PM

View PostNeoTifa, on 05 August 2013 - 06:14 PM, said:

Well, 100x100 == 10,000, so they would probably be similar in performance. In this day and age, 10,000 is just chump change to a computer.

100% true :^:

If you had an array with a few millions elements it would have make a difference
but a little array of 10,000 elements does not even worth the discussion for the few nanoseconds more the 2D array will require to access one of its components compared to the single dimension array
Was This Post Helpful? 2
  • +
  • -

#12 NeoTifa  Icon User is online

  • Whorediot
  • member icon





Reputation: 2498
  • View blog
  • Posts: 15,471
  • Joined: 24-September 08

Re: Single vs Double Array in a loop

Posted 05 August 2013 - 03:26 PM

They'll both be O(n2). :P There's still 2 for loops within each other.

If you're doing a 2d grid, like a tile map or such, a 2d array might make more sense as a coder because it's easier to read and see the logic behind it. And also, don't worry about it, this is bringing back memories from my old data structures class, which is good because I'm starting school again in 2 weeks after a hiatus. :x I had to write an essay about the performance of some data structure I programmed. I think it was some sort of hash map. *shudder* Finding efficient hash keys, what a nightmare.

(ninjaedit: *squeeeeeee* peebles! <3)

This post has been edited by NeoTifa: 05 August 2013 - 03:28 PM

Was This Post Helpful? 0
  • +
  • -

#13 StrongJoshua  Icon User is offline

  • D.I.C Head

Reputation: 43
  • View blog
  • Posts: 136
  • Joined: 19-July 13

Re: Single vs Double Array in a loop

Posted 05 August 2013 - 03:29 PM

Thanks for all your input guys. I think I learned quite a bit from this topic :)
Was This Post Helpful? 0
  • +
  • -

#14 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8316
  • View blog
  • Posts: 31,836
  • Joined: 06-March 08

Re: Single vs Double Array in a loop

Posted 05 August 2013 - 03:29 PM

for(int x = 0; x < w; x++)
{
   for(int y = 0; y < h; y++
   {
       if(slots[x + y * w].getIfHighlighted)
          //draw the slot overlay/highlight
   }
}
//or

for(int j = 0; j < slots.length; j++)
{
    for(int k = 0; k < slots[j].length; k++)
    {
       if(slots[j][k].getIfHighlighted)
          //draw the slot overlay/highlight
    }
}



no differences at all this line

slots[x + y * w]

simply does what the compiler will do for you if you use a 2D array
Was This Post Helpful? 2
  • +
  • -

#15 CasiOo  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 1278
  • View blog
  • Posts: 2,848
  • Joined: 05-April 11

Re: Single vs Double Array in a loop

Posted 05 August 2013 - 03:58 PM

View PostNeoTifa, on 05 August 2013 - 10:26 PM, said:

They'll both be O(n2). :P/> There's still 2 for loops within each other.

If you're doing a 2d grid, like a tile map or such, a 2d array might make more sense as a coder because it's easier to read and see the logic behind it. And also, don't worry about it, this is bringing back memories from my old data structures class, which is good because I'm starting school again in 2 weeks after a hiatus. :x I had to write an essay about the performance of some data structure I programmed. I think it was some sort of hash map. *shudder* Finding efficient hash keys, what a nightmare.

(ninjaedit: *squeeeeeee* peebles! <3)


Not O(n2)

Having a one dimensional array which you iterate from start to end should be faster than iterating a two dimensional
But as already told, the difference is tiny, and you should use two dimensional array if it's easier to work with in your head. It all comes down to what you find easier

And change your loop really.... what is up with nested loops when iterating a one dimensional array?!
int w = 100;
int h = 100;
Slot [] slots = new Slot[w * h]; //pretend these are all initialized
for(int x = 0; x < slots.length; x++)
{
   if(slots[x].getIfHighlighted)
	  //draw the slot overlay/highlight
}


Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2