Storing up-to-date array index in a separate array with JavaScript

Question

I have an array of objects. Key of the array is generated automatically with .push(). Some objects might be removed from the array with delete array[index];. Array might contain anything from 0 to 10K+ entries.

Here is the declaration and some of the logic:

var allClients = [];

someFunction(client) {
    allClients.push(client);

    var callbackFunction = function() {
        var index = allClients.indexOf(client);
        try {
            delete allClients[index];
        } catch (err) {
            console.error(err);
        }
    }
}

function getClientsMeetingCriteria(some_unique_id) {
    var filteredClients = allClients.filter(function(client) {
        return client.id_list.indexOf(some_unique_id) > -1;
    });
    return filteredClients;
}

Now above code (very simplified version of what it is IRL) works well with 100-300 clients, but it becomes too slow for it's purpose with 500+. Problem is that getClientsMeetingCriteria() might be called 10 times per second asynchronously. I need to set up caching with some_unique_id as the key. I have cache code, but I don't know how to store this data in it.. Imagine this:

client = {id:1, id_list='123;124;'} is added to clients[]
getClientsMeetingCriteria('123') returns [client {id:1...}] and caches the response
delete client[0] is called and client is removed from the clients[]
getClientsMeetingCriteria('123') is called again and returns cached [client {id:1...}], but that entry is no longer in the clients[]

I know that JS passes by value in this case (return filteredClients). So far I came up with this: I can actually loop through the array in getClientsMeetingCriteria() and find indexes of the matching clients. I place an array with them (indexes) in cache under some_unique_id. I also keep an array indexed with client_ids with data being list of cached some_unique_id referencing client ids. Before calling delete allClients[index], I fetch array entry for index and hence get list of cache keys ('some_unique_id') that should be flushed. That seems like a generally big overhead, but it is nothing compared to looping through 1K objects every 100 ms...

Can you think of a better solution? Is there a way to make an object of links to array entries (indexes) which will be up to date - in other words refresh (become null) when index is removed? Something like an iterator.

P.S. I also realize that I can load the list of client ids from the cache and check if the index exists, but that does not solve the problem with adding a new client that has a matching 'some_unique_id'.

Try these suggestions: gamealchemist.wordpress.com/2013/05/01/… (look at suggestion #6) — Don Rhummy
– Don Rhummy, Commented Nov 12, 2013 at 18:03
@DonRhummy unfortunately that will only make native functions work faster and maybe I can include some of the code for solution I came up with, but it will still require me to create a separate array: client_id => {unique_ids}. If there are no solutions, I'll just optimize the code using 6th suggestion :) Thanks. — Xeos
– Xeos, Commented Nov 12, 2013 at 18:15
Why don't you index on client id? An object with clients might be faster than an array, if you're doing lookups and not loops. Or maybe getClientsMeetingCriteria() would be too slow... — Rudie
– Rudie, Commented Nov 12, 2013 at 20:30
@Rudie Thanks. I will try creating two indexes, one for userids and one for uniqueids. — Xeos
– Xeos, Commented Nov 12, 2013 at 21:05
That's not what I meant, but it's a good idea. Forget what I said. You need the fast loops. — Rudie
– Rudie, Commented Nov 12, 2013 at 21:12

Michael Geary · Accepted Answer · 2013-11-13 00:35:28Z

An array is the wrong data structure for this. Use some objects and set up the indexes up front, and you won't need to search at all.

I'm going to assume the id property of each client is unique. Let me know if that's not the case.

And I'm going to take one liberty with getClientsMeetingCriteria() (the find method in the code below). Instead of returning an array of clients, I'm going to return an object containing those clients. That's mostly to demonstrate an important point: you can actually write this code so this retrieval is instantaneous. The entire function body is simply:

        return criteria[criterion] || {};

If you need an array that's easy too (and will still be very fast), so we'll come back to that.

Paste this code into your Chrome or Firebug console and execute it:

// Return a boolean telling if an object is empty (has no properties)
function isEmpty( object ) {
    for( var name in object ) {
        return false;
    }
    return true;
}

// An object that keeps track of clients and criteria (id_list)
function Clients() {

    // An object containing all of the clients that have been added
    // using clients.add(client). The client.id is the property name,
    // and the client object is the property value. So:
    // clients[clientID] is a client object with the given client.id
    var clients = {};

    // An object containing every unique criterion ID. The criterion ID
    // is the property name, and the property value is an object
    // containing every client that has this criterion ID in its id_list
    // property. So:
    // criteria[criterionID] is an object containing clients
    // criteria[criterionID][clientID] is a client with that criterion
    var criteria = {};

    // Internal function to split an id_list and iterate over it
    function eachCriterion( client, callback ) {
        var ids = client.id_list.split(';');
        for( var i = 0, n = ids.length;  i < n;  ++i ) {
            callback( ids[i] );
        }
    }

    // Add a client
    this.add = function( client ) {
        if( clients[client.id] ) {
            // already exists, return or error?
        }
        clients[client.id] = client;
        eachCriterion( client, function( id ) {
            if( ! criteria[id] ) {
                criteria[id] = {}
            }
            criteria[id][client.id] = client;
        });
    };

    // Remove a client
    this.remove = function( client ) {
        delete clients[client.id];
        eachCriterion( client, function( id ) {
            delete criteria[id][client.id];
            if( isEmpty(criteria[id]) ) {
                delete criteria[id];
            }
        });
    };

    // Return an object containing all the clients that have the given
    // criterion in their id_list property
    this.find = function( criterion ) {
        return criteria[criterion] || {};
    };
}

var clients = new Clients;

var client3 = { id:3, id_list:'10;20' };
var client1 = { id:1, id_list:'30;40;10' };
var client4 = { id:4, id_list:'40;20' };
var client5 = { id:5, id_list:'50;70' };
var client9 = { id:9, id_list:'10;70' };
var client2 = { id:2, id_list:'50;' };
var client7 = { id:7, id_list:'40;70;90' };

clients.add( client3 );
clients.add( client1 );
clients.add( client4 );
clients.add( client5 );
clients.add( client9 );
clients.add( client2 );
clients.add( client7 );

function find( id ) {
    console.log( 'Finding', id );
    console.log( JSON.stringify( clients.find(id), null, 4 ) );
}

find( '10' );
clients.remove( client3 );
find( '10' );
clients.remove( client1 );
find( '10' );
clients.remove( client9 );
find( '10' );

It will log:

Finding 10
{
    "1": {
        "id": 1,
        "id_list": "30;40;10"
    },
    "3": {
        "id": 3,
        "id_list": "10;20"
    },
    "9": {
        "id": 9,
        "id_list": "10;70"
    }
}
Finding 10
{
    "1": {
        "id": 1,
        "id_list": "30;40;10"
    },
    "9": {
        "id": 9,
        "id_list": "10;70"
    }
}
Finding 10
{
    "9": {
        "id": 9,
        "id_list": "10;70"
    }
}
Finding 10
{}

If you really need an array instead of an object for the .find() return, you could use this version of the find method instead (or any similar code):

    this.find = function( criterion ) {
        var result = [];
        for( var id in criteria[criterion] ) {
            result.push( clients[id] );
        }
        return result;
    };

Might be even faster if criteria is 1 level deep, with concated index id + '_' + client.id. Maybe not. I like it.
Interesting idea, but would it work? The only parameter to the find method is the criterion ID (id). We don't know the client ID at this point. find is supposed to take a criterion ID and return all the clients that have that ID in their id_list.

Collectives™ on Stack Overflow

Storing up-to-date array index in a separate array with JavaScript

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related