Let’s have a look at arrays vs. linked lists, and for what use.
Here, the assumption is that we need to access a property and/or call a function from a lot of objects in a list at the highest speed possible. Let’s say we are making a game and we want to go through all of our animated sprite objects.
Basically, we have two options:
- Linked lists
Commonly used, arrays are easy to manipulate. You just need to iterate through it and access each object via its index in the list. For a loop performance test refer to this article. In AS3, object access is supposedly faster than array access, which we will verify later.
In a linked list, objects are linked together. Basically, there is no index to access data (even if that can be implemented) but each object in the list has a reference to the next object (single) or to the previous one as well (double). Well this is just the idea behind linked lists. You can have as many references as you want depending on the use of the objects.
Linked lists also allow us to add and remove objects from the list in a fast and easy way.
But let’s have a look at the results I got with an iteration of 1000000 :
|inserting new element (class instance, string passed to constructor) into array||969 ms|
|inserting new element (string passed to constructor) into linked list||645 ms|
|inserting new element (string passed to property) into linked list||757 ms|
|accessing text (string, property) from array element (class instance)||32 ms|
|accessing text (string, property) from linked list||28 ms|
|accessing text (string, function) from linked list||97 ms|
|writing into 4 properties (string) from array element (class instance)||55 ms|
|reading from 4 properties (string) from array element (class instance)||56 ms|
|writing into 4 properties in linked list||51 ms|
|reading from 4 properties in linked list||52 ms|
My configuration is:
Intel Core2 6400 @ 2.13GHz, 3Go Ram, WinXP.
I ran the test multiple times. It is weird because sometimes, arrays are like 3 times faster than linked lists… but the results are too high compared to what I have “normally”. The results in the table above reflect what I get most of the time.
Well, linked lists seem to be slightly faster but no big difference here… and there are 1.000.000 objects, which is pretty big. So with less objects in the list, the difference would be even smaller.
The tool I used is right here for you to test. Keep in mind that the results might change from time to time and from computer to computer.