JAVA : time factor regarding Array Dimension

Question

i have a coding experience in C++. Recently, i've been trying to learn Java.

I was practicing a simple problem at an Online Judge. the problem required an array of 2x1000000 dimension. i declared an array:

int ara[][]=new int[1000000][2]

but the code could not fit within 3 second time limit and got Time Limit Exceeded verdict in the very first test case.

then i just switched the dimension like this :

int ara[][]=new int[2][1000000]

and altered the code accordingly and the code got accepted.

after some experiment i figured that was the only reason my first code got Time Limit Exceeded.

What is the difference between int ara[][]=new int[1000000][2] and int ara[][]=new int[2][1000000] ? Why is there such a huge significant time difference between those array declaration ?

What do you think is faster? Allocating 1000000 arrays with 2 values each or allocating 2 arrays with 1000000 values each? Why do you think so? — Sotirios Delimanolis
– Sotirios Delimanolis, Commented May 5, 2016 at 15:35
Coming from C++, you probably think that int[3][5] is a 2-dimensional array. It is not. It is an array of arrays. Big difference internally, though functionally it can behave like a 2D array. But being an array of arrays, each secondary array can actually be a different size, which a pure 2D array can't do. See JLS 15.10.2 and look at example 15.10.2-2 to see what's going on behind the scene. — Andreas
– Andreas, Commented May 5, 2016 at 15:45

nhouser9 · Accepted Answer · 2016-05-05 15:40:03Z

1

Allocating memory takes time. Allocating one array of 5 elements does not take the same amount of time as allocating 5 arrays of one element. For each allocation, the OS has to look in the page table for a free block, assign it, etc.

So in one example you declare only 2 arrays, in the other you declare 1000000. That is why one is faster than the other.

answered May 5, 2016 at 15:40

nhouser9

6,7803 gold badges23 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

JAVA : time factor regarding Array Dimension

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related