Efficiently evaluate if JavaScript object contains a string

Question

I have the following example client side object:

var obj = {
"locations": [
    [
        37.502917,
        -122.501335
    ],
    [
        37.494473,
        -122.499619
    ],
    [
        37.484394,
        -122.455673
    ]
],
"types": [
    [
        "type1"
    ],
    [
        "type2"
    ],
    [
        "type3"
    ]
    ]
};

Locations could contain up to 50 values. An ajax request returns a set of new locations and I need to evaluate if they are already within obj.locations. Each new returned location is a string e.g:

var test = 37.502917 + ',' + -122.501335;

For each location I can iterate through the current ones and check if it is present:

for(var i = 0; i < obj.locations.length; i++) {
    if(obj.locations[i] == test){
        console.log('Found!');
    }
}

Is there a more efficient way of doing this as iterating through the object for each new location seems inefficient?

EDIT: My Solution:

I decided to take the locations object and turn in to a string, then evaluate each of the incoming strings:

var test = -121.60183 + ',' + 38.025783;
var cords = [].concat([], obj.locations).toString();
if( cords.indexOf(test) !== -1) {
    console.log('found!  ');
}

In your iteration you compare an array with an string. But even arrays you couldn't just compare by "==": [5, 5] == [5, 5] // false! — dsuckau
– dsuckau, Commented Sep 6, 2014 at 18:21
Whats the exact format you get returned by the ajax request? — dsuckau
– dsuckau, Commented Sep 6, 2014 at 18:24
@dsuckau: Actually you can compare arrays with strings, and it might even work: "5,5" == [5,5] // true. Of course you're correct, that's not how it should be done. — Bergi
– Bergi, Commented Sep 6, 2014 at 18:44

score 1 · Accepted Answer · 2014-09-06 18:37:15Z

This is perhaps one of the oldest problems in computer science--looking something up.

You first have to ask yourself if it's worth worrying about. Perhaps it will take 1ms to find the location with a linear search, but 0.5ms with some kind of optimized search. So, is it worth the trouble?

The next approach would be to sort the list of locations, and do a binary search into it.

Another approach is to create some kind of hash table. You could use JavaScript objects for this, with properties as hash keys. The simplest approach would be to use lat+long as the property key, but now you've just shifted the efficiency problem to the efficiency of JS looking up keys in large objects.

You could design your own custom hash-like approach, where all locations with the same integral portion of latitude are stored as an array under a hash of 37. Then the performance is governed by the time taken to find the hash key in the table, and then looking through the smaller number of locations within its array.

Proceeding further, if performance is truly an issue, you could build some kind of tree structure for optimal lookup. At some point, you have to start trading off between the cost of building and updating the tree, and the savings from looking things up using the tree.

Simone Gianni · Accepted Answer · 2014-09-06 18:20:47Z

It is for sure inefficient, but unless you have to deal with thousands of those objects it will not hang your browser.

However, you can index the locations in an associative array and then use that to check for presence or absence of an element.

For example, you could add a locations_index object to your object, like this :

var obj = {
"locations": [
    [
        37.502917,
        -122.501335
    ],
    [
        37.494473,
        -122.499619
    ],
    [
        37.484394,
        -122.455673
    ]
],
"locations_index" : {
    "37.502917,-122.501335" : true,
    "37.494473,-122.499619" : true,
    // ...
},
"types": [
    [

Then you can check if it is or not in the location_index with :

if (obj.locations_index["37.502917,-122.501335"]) {
  // It's already there
} else {

Obviously, you need to take care of adding the new locations (and removing the ones you remove) from both the "real" array and the "index".

Collectives™ on Stack Overflow

Efficiently evaluate if JavaScript object contains a string

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related