Performance - should I use both Arrays and Objects for huge list?

Question

Till now, my server has handled huge arrays of entities.

Mainly, it does a for loop x times per second on entities, checking if one entity is in the scope of an other entity (each entity has an array entitiesInScope) by doing entitiesInScope.indexOf(entity), and that's the biggest cost of my program.

for (var i = 0; i < entities.length; i++) {
    var entity = entities[i];
    for (var j = 0; j < entities.length; j++) {
        var checkEntity = entities[j];
        var idx = entity.entitiesInScope.indexOf(checkEntity);
        if (idx >= 0) {
            if (!check(checkEntity.state, entity.state)) {
                entity.removeEntityInScope(idx);
                //... remove: send checkEntity.id
            } 
        } else {
            if (check(checkEntity.state, entity.state)) {
                entity.addEntityInScope(checkEntity);
                //... add: send checkEntity.id, checkEntity.state
            }
        }
    }
}

(I've optimized it by not doing the second loop on all the entities, but that's not the point)

However, I've seen that Object's hasOwnProperty is much faster than indexOf. On the other side, I also do a lot of push and splice. So if I add an Object of entities, I should use delete (perf?) too.

Should I:

-add an object with id entity key, to use hasOwnProperty(entity.id), and then allow to use indexOf if true?

-add an object with entity key, to use hasOwnProperty(entity.id) (memory wasting)?

-continue with arrays

Why don´t you just traverse the entitiesInScope array instead of the second loop? — juvian
– juvian, Commented Jan 26, 2017 at 16:34
Or perhaps a Map? (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… ) — Me.Name
– Me.Name, Commented Jan 26, 2017 at 16:41
@juvian in fact, there is a physics loop that updates the state of the entities (position,...), and there is a broadcast loop (previous code) where the entitiesInScope are updated (add/remove) for each entity, by doing some checks. — zbeyens
– zbeyens, Commented Jan 26, 2017 at 16:45
@Miyud in that case using an object instead of array and using hasOwnProperty + delete would be much more efficient. But just traversing entitiesInScope is even better... (you would need to traverse it backwards to remove without messing up indexes) — juvian
– juvian, Commented Jan 26, 2017 at 17:09

juvian · Accepted Answer · 2017-01-26 18:55:09Z

1

I would recommend to iterate over entitiesInScope to update or remove the entities there, as you already know the indexes that way and if you traverse it backwards you can remove the items without messing up indexes.

As for adding the missing entities, I would mark the ones already on entitiesInScope in an object for fast lookup and then iterate over entities and add the missing ones. The code would be something similar to this :

for (var i = 0; i < entities.length; i++) {
    var entity = entities[i];
    var alreadyInScope = {}

    for (var j = entity.entitiesInScope.length - 1; j >= 0; j--) {
        var checkEntity = entity.entitiesInScope[j];

        if (!check(checkEntity.state, entity.state)) {
           var id = entity.entitiesInScope.splice(j, 1).id
        } else {
            alreadyInScope[checkEntity.id] = true;
        }
    }

    for (var j = 0; j < entities.length; j++) {
        if (alreadyInScope.hasOwnProperty(entities[j].id) == false) {
            entity.entitiesInScope.push(entities[j])
        }
    }

}

edited Jan 26, 2017 at 18:55

answered Jan 26, 2017 at 18:31

juvian

16.1k2 gold badges42 silver badges40 bronze badges

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

3 Comments

zbeyens Over a year ago

Thanks. I think you mean splice(-1,1) to delete last element. Btw, is there a performance difference with forward splice(j,1), or just for user convenience ?

juvian Over a year ago

@Miyud my mistake, splice(j, 1) is the right option

juvian Over a year ago

@Miyud if you have many entities in alreadyInScope and you usually remove more than 10, it would probably be more efficient to add the ones that you will not remove to a temporary array and at the end of the loop replace alreadyInScope with the temporary array

Collectives™ on Stack Overflow

Performance - should I use both Arrays and Objects for huge list?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related