Effective ways of finding an element in a Javascript array

Question

I am using an array with titles. Each titles index corresponds to an id in a database which contains html for that given title.

Lets say I have a string which contains one of the titles.

title = "why-birds-fly";
titles[] // an array which contains all the titles

To use the string "title" to get the corresponding id I could do:

for (i = 0; i < titles.length-1; i++) {
  if (titles[i] == title)
    return i+1;
}

Another method I could use is to create an associative array together with the titles array which is the exact opposite of titles. That is, it uses the string as an index and returns the number.

titles_id {blah:0,why-birds-fly:1,blah2:2}

I could then access the ID by:

return titles_id[title]+1;

What would be most effective considering CPU, Memory, etc?

Also, please let me know if my logic is all wrong.

Thanks Willem

Answer 1

The linear search approach has a complexity of O(n), and I think the worst case for the associative array approach is probably O(log n), (the best case maybe O(1) if the JS engine is using hashes and getting no collisions). It will depend on how a JS engine typically implements associative arrays/objects, but you can be sure it will beat O(n).

So, the second approach will be faster, but will of course use more memory. This is a very typical trade off, gaining more speed, but using more memory, and only you can decide whether you want to make that trade.

Answer 2

Javascript arrays can use a value such as the title "why-birds-fly" for the index.

Exmaple: var title = "why-birds-fly";

var TitleArray[] = new Array();

TitleArray[title] = id;

Then you have direct access to the id by title:

return TitleArray[title];

Answer 3

It is also important to consider the number of key value pairs you will need to store. If its less than ~50 (depending on implementation) then doing a linear search will be as efficient as doing a hash table lookup, because of the cost of calculating the hash value and resolving collisions. An exception is the Google chrome v8 JavaScript engine keeps a sort of cached version of all objects that allow it to perform a direct lookup of a property on an object, therefore the use of the Object class as a hash table may be faster, though I'm not sure if the cost of creating this cached version will outweigh the benefit for smaller lists.

Answer 4

You can use the indexOf function of Array in your first method.

Below is the information from Mozilla Developer: https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference:Objects:Array:indexOf

indexOf is a JavaScript extension to the ECMA-262 standard; as such it may not be present in other implementations of the standard. You can work around this by inserting the following code at the beginning of your scripts, allowing use of indexOf in ECMA-262 implementations which do not natively support it. This algorithm is exactly the one used in Firefox and SpiderMonkey.

if (!Array.prototype.indexOf)
{
  Array.prototype.indexOf = function(elt /*, from*/)
  {
    var len = this.length >>> 0;

    var from = Number(arguments[1]) || 0;
    from = (from < 0)
         ? Math.ceil(from)
         : Math.floor(from);
    if (from < 0)
      from += len;

    for (; from < len; from++)
    {
      if (from in this &&
          this[from] === elt)
        return from;
    }
    return -1;
   };
}