CODEWITHSUNDEEP
javascriptarraysperformance
bobo2000
bobo2000

Reputation: 1877

Checking if element exists in array without iterating through it

my array:

tempListArray = "[{"id":"12","value":false},{"id":"10","value":false},{"id":"9","value":false},{"id":"8","value":false}]";

To check if an element exists I would do this:

for (var i in tempListArray) {
    //check flag
    if (tempListArray[i].id == Id) {
        flagExistsLoop = 1;
        break;
    }
}

Is there anyway, I can check if an Id exists without looping through the whole array. Basically I am worried about performance if say I have a 100 elements.

Thanks

Upvotes: 0

Views: 12140

Answers (6)

Taylor Hillegeist
Taylor Hillegeist

Reputation: 1

There is a possible cheat for limited cases :) and it is magic...cough cough (math)

imagine you have 3 elements:

  • 1
  • 2
  • 3

and you want to know if one of these is in an array without iterating it...

we could make a number that contains a numerical flavor of the array. we do this by assigning prime numbers to the elements:

  • 1 - 2
  • 2 - 3
  • 3 - 5

the array so when we add item 2 we check that the array doesn't already contain the prime associated to that item by checking (if Flavor!=0 && (Flavor%3)!=0) then adding the prime Flavor*=3;

now we can tell that the second element is in the array by looking at the number.

if Flavor!=0 && (Flavor%3)==0 // its There!

Of course this is limited to the numerical representation that can be handled by the computer. and for small array sizes (1-3 elements) it might still be faster to scan. but it's just one idea.

but the basis is pretty sound. However, this method becomes unusable if you cannot correlate elements one to one with a set of primes. You'll want to have the primes calculated in advance. and verify that the product of those is less numerical max numerical representation. (also be careful with floating-point. because they might not be able to represent the number at the higher values due to the gaps between representable values.) You probably have the best luck with an unsigned integer type.

This method will probably be too limiting. And there is something else you can do to possibly speed up your system if you don't want to iterate the entire array.

Use different structures: dictionaries/maps/trees etc.

if your attached to the array another method can be a bloom filter. This will let you know if an element is not in your set, which can be just as useful.

Upvotes: 0

Dave
Dave

Reputation: 10924

Depending on your scenario, you may be able to use Array.indexOf() which will return -1 if the item is not present.

Granted it is probably iterating behind the scenes, but the code is much cleaner. Also note how object comparisons are done in javascript, where two objects are not equal even though their values may be equal. See below:

var tempListArray = [{"id":"12","value":false},{"id":"10","value":false},{"id":"9","value":false},{"id":"8","value":false}];

var check1 = tempListArray[2];
var check2 = {"id":"9","value":false};

doCheck(tempListArray, check1);
doCheck(tempListArray, check2);

function doCheck(array, item) {
  var index = array.indexOf(item);
  
  if (index === -1)
    document.write("not in array<br/>");
  else
    document.write("exists at index " + index + "<br/>");
}

Upvotes: 1

Oriol
Oriol

Reputation: 288580

No, you can't know that without iterating the array.

However, note for...in loops are a bad way of iterating arrays:

  • There is no warranty that it will iterate the array with order
  • It will also iterate (enumerable) non-numeric own properties
  • It will also iterate (enumerable) properties that come from the prototype, i.e., defined in Array.prototype and Object.protoype.

I would use one of these:

  • for loop with a numeric index:

    for (var i=0; i<tempListArray.length; ++i) {
    if (tempListArray[i].id == Id) {
        flagExistsLoop = 1;
        break;
    }
}

  • Array.prototype.some (EcmaScript 5):

    var flagExistsLoop = tempListArray.some(function(item) {
    return item.id == Id;
});

    Note it may be slower than the other ones because it calls a function at each step.

  • for...of loop (EcmaScript 6):

    for (var item of tempListArray) {
    if (item.id == Id) {
        flagExistsLoop = 1;
        break;
    }
}

Upvotes: 2

cybersam
cybersam

Reputation: 67019

There is no way without iterating through the elements (that would be magic).

But, you could consider using an object instead of an array. The object would use the (presumably unique) id value as the key, and the value could have the same structure you have now (or without the redundant id property). This way, you can efficiently determine if the id already exists.

Upvotes: 0

Alaa Badran
Alaa Badran

Reputation: 1858

try to use php.js it may help while you can use same php function names and it has some useful functionalities

Upvotes: 0

Niels Keurentjes
Niels Keurentjes

Reputation: 41968

No, without using custom dictionary objects (which you seriously don't want to for this) there's no faster way than doing a 'full scan' of all contained objects.

As a general rule of thumb, don't worry about performance in any language or any situation until the total number of iterations hits 5 digits, most often 6 or 7. Scanning a table of 100 elements should be a few milliseconds at worst. Worrying about performance impact before you have noticed performance impact is one of the worst kinds of premature optimization.

Upvotes: 2

Related Questions