Lookup function or for in loop?

Question

Which is better for performance - having a lookup function that finds an object in array with a particular ID or just using for in loop with holes in array?

In my situation I've got players array which is dynamic. Let's say 3 players are connected so my array would look like this:

players = [player1, player2, player3]

It would be easy to keep array key as player ID so I would know that player with ID 2 is 3rd in players array and in order to access him I just need to use: players[2] but as the 2nd player leaves he creates an array hole:

players = [player1,,player3]

And as I understand this hole reduces the performance of using array, since I'm using for-in loop a lot, would it be a better to have an array of player objects and instead of leaving array holes I just splice the hole out? But this way I wouldn't be able to keep array key as player ID so I would have to use ID lookup function. So in the end which one of these 2 choices is better for performance? Or there is even better way to fix this issue?

Thank You!

For an array of 2 (or 200 or 2000) elements it does not really matter. — zerkms, Aug 05 '16 at 01:12
why not use javascript objects {} where the property keys are the player ID's — Jaromanda X, Aug 05 '16 at 01:14
"Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%" Donald Knuth — Dan Walmsley, Aug 05 '16 at 01:17
I think it's a good question. Because it's not only about performance. Sooner or later you have to do a cleanup if implemented like this, delete all holes and reassign IDs, or the array will become too large. — maraca, Aug 05 '16 at 01:44
[Don't use `for…in` enumerations on arrays at all!](https://stackoverflow.com/q/500504/1048572) — Bergi, Aug 05 '16 at 02:41
"*as the 2nd player leaves he creates an array hole:*" - only if you used `delete`, which you hopefully don't. Just assign `players[1] = null` and no hole is created and no performance is reduced. — Bergi, Aug 05 '16 at 02:42
As suggested by @JaromandaX, you should use objects with playerId as key. When player leaves, you can delete that property as `delete player.playerId` — Rajesh, Aug 05 '16 at 07:59

maraca · Accepted Answer · 2016-08-05T02:50:52.780

1

In my opinion the option mentioned by @Jaromanda X in the comments is the best, because the "hole implementation" will become slower and slower, especially when iterating over the players array, because when you keep adding and removing players the arrow grows and becomes very sparse consisting mainly of holes.

var players = {};
players[p.id] = p; // add player p
delete players[p.id]; // remove player p
// player ids have to be unique and should be strings

Here is why the look up is not such a good idea, first I thought this might be easy, but actually this code fails, because you have to update all indexes after the removed player... so better go with the players object.

// ATTENTION: example of FAILING implementation
var players = [];
var map = {};
// add player p
var idx = players.push(p) - 1;
map[p.id] = idx;
// remove player p
players.splice(map[p.id], 1);
delete map[p.id];

edited Aug 05 '16 at 02:50

answered Aug 05 '16 at 02:03

maraca

8,468
3
23
45

Memory leak? How that? – Bergi Aug 05 '16 at 02:43
If he keeps adding and removing players the array keeps growing becoming very sparse. – maraca Aug 05 '16 at 02:45
1

It's not a memory leak (the same way `window.foo = 'bar';` is not a memory leak). You cannot have a memory leak in JS (unless there is a bug in an implementation). What you refer to is just an inefficient memory use. – zerkms Aug 05 '16 at 02:47
It would also make sense to mention that "will become slower and slower" in real life would be negligible (unless OP is doing something crazy, which is unlikely) – zerkms Aug 05 '16 at 03:00
If the game has a main lobby with people coming in and leaving by the second, then it is not crazy. – maraca Aug 05 '16 at 03:03
@maraca did you make any measurements or you just try to predict how an unbelievably complex tool (a js engine) would behave? Really - try to add and immediately remove 10m elements and see if you can spot any difference in "performance". – zerkms Aug 05 '16 at 03:15
Thank you @maraca, I didn't knew this way of dealing with my issue, problem solved :) – Donatas Aug 05 '16 at 11:41

score 0 · Answer 2 · edited May 23 '17 at 12:08

Use

var players = {
    abc1: player1,
    abc2: player2, 
    abc3: player3
}

Instead of var players = [player1, player2, player3]

Now you can access it via players.abc1.name = "Nicholas" no lookup function needed. If you are only using the ID's to look up each player in an organized way, I would recommend an even simpler approach:

var players = {
    player1: player1,
    player2: player2,
    player3: player3
}

This way you could access it even easier, like players.player1[madeUpPropName] = someValue;

Also, you should never ever us for-in loop on an Array. Use forEach or a basic for loop. Why is using "for...in" with array iteration a bad idea?

Get Off My Lawn · Answer 3 · 2016-08-05T02:29:06.453

You can easily check performance yourself using console.time(str) and console.timeEnd(str). Check it using the following examples:

var array = ['player1', 'player2', 'player3'];

// Test using indexOf
console.time('test1');
var val = array.indexOf('player3');
console.timeEnd('test1');

// Test using a for loop
console.time('test2');
for (var i in array) {
    if (i == 'player3') {
        break;
    }
}
console.timeEnd('test2');

Note how the string in time and timeEnd match.

Lookup function or for in loop?

3 Answers3