Faster to get 1 element from larger array or smaller array? C#

Unity Engine
1

Lets say I have two arrays with a bunch of instances of a class in them.

Element 40,000 of array1 points to the same exact instance that element 2,000 in array2 points to.

Is it then faster to do
Array2[2000]

rather than
Array1[40000]

in order to get that instance?

Meaning, does C# have a way of going directly to that element of the array? Or does having more elements in array before the desired index reduce the performance of getting to that index?

More specifically I think I am asking, internally, do C# arrays work like linked lists?

2

Arrays are O(1) lookup.

3

I’m not familiar with this term. I’ve searched google and got a few articles. But nothing to specific or in-depth. Could you further describe what this means?

4

Sure. It’s constant time, so doesn’t matter which element you are accessing; 1 or 1 millionth is the same amount of time

5

Bear in mind that large arrays can suffer from LOH. I.E the garbage collection leaves the memory fragmented. Not sure if this is true of fixed array size or specifically List<> or Dictionary<,>.

Found out its on array’s where the array is over 85kb, .NET shove it on the large object heap (LOH). This is what can cause it

6

Arrays are contiguous in memory.

7

I would say yes they are O(1) not O(n) as you are suggesting.

You did not mention if you are talking about buitin arrays or java arrays.

see http://docs.unity3d.com/Documentation/ScriptReference/Array.html

But both would be O(1) look up.

buitin arrays ( ie var arr : int[ ] = new int[100] ) would be a standard c style array

java arrays ( ie var arr = new Array () ) would be something like a STL vector style array

The document do not say how java arrays are implemented but I think they would be a STL vector style array.

8

just standard c# array

int[ ] myint = new int[100];

although its an array of classes