Fastest way to loop through array with missing indexes

Question

I have an array of arrays for drawing a tilemap on the screen (basically an array of columns, each column is an array of tiles). I have tried to speed up the drawing process by not setting the array indexes that contain empty tiles, but it is not any faster.

var a1 = [];
a1[0] = 1;
a1[100] = 1;
a1[200] = 1;
a1[300] = 1;

var a2 = [];
for( var i = 0; i <= 300; i++ ) {
    a2[i] = 1;
}

When I compared the time taken to loop through these two 100,000 times, a2 was slightly faster. When I tried using ( for var x in y ) instead, both with an array and an object, they were 4 - 12 times slower.

If looping through an object is a lot slower, and removing 99% of the array (not just from the end) is not making it any faster, is there any way one could actually make it faster?

@Pete I could, but it is roughly 10 times slower.

Erik Lumme
– Erik Lumme

2014-06-02 09:11:25 +00:00
Commented Jun 2, 2014 at 9:11 — Erik Lumme
– Erik Lumme, Commented Jun 2, 2014 at 9:11

Esailija · Accepted Answer · 2014-06-02 08:53:12Z

2

Do not have holes in your arrays, just fill it completely (also pre-allocate to avoid dynamic resizing)

var a1 = new Array(301);
for (var i = 0; i < a1.length; ++i) a1[i] = 0;
a1[0] = 1;
a1[100] = 1;
a1[200] = 1;
a1[300] = 1;

Loop normally (never use for.in, use Object.keys if you need to iterate over keys):

for (var i = 0; i < a1.length; ++i) {
    if (a1[i] !== 0) {
        //Non empty
    }
}

answered Jun 2, 2014 at 8:53

Esailija

140k24 gold badges280 silver badges328 bronze badges

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

10 Comments

sabithpocker Over a year ago

why should we avoid dynamic resizing? I usually goes with a=[] as suggesed by jshint.

Esailija Over a year ago

@sabithpocker a resize is very expensive, all the array elements need to be copied to a new backing array. If you know the size before hand and allocate it, there will be no copying. See en.wikipedia.org/wiki/…

sabithpocker Over a year ago

Ok thanks, i never knew about that. You have any link to read about this or jsperf demostrating the same?

Erik Lumme Over a year ago

Seems it is as good as it gets. What I wanted to achieve was looping through a1 being basically as fast as looping through any array of four elements, but it seems impossible. I wonder if changing array[key] = value to array[x] = [key, value] could be faster.

Esailija Over a year ago

@user3358029 Actually not necessarily, CPU cache highly favors a flat array so even if there is like 300 items where 4 are filled, it wouldn't surprise me if it was faster than an array of 4 items where you need extra indirection to see what their coords are. For 10% marked squares it would be even less surprising

|

Collectives™ on Stack Overflow

Fastest way to loop through array with missing indexes

1 Answer 1

10 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

10 Comments

Your Answer

Sign up or log in

Post as a guest

Related