use Array.indexOf for relatively big arrays

Question

Is there a way to achieve indexOf functionality, to find out if a string is on an array, for very big arrays relatively fast? When my array grows beyond 40,000 values, my app freezes for a few seconds.

Consider the following code:

var arr = [];

function makeWord()
{
    var text = "";
    var possible = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

    for( var i=0; i < 5; i++ )
        text += possible.charAt(Math.floor(Math.random() * possible.length));
    return text;
}
function populateArr(){
  for (var i=0;i<40000;i++){
    arr[i] = makeWord();
  }
  console.log("finished populateArr");
}
function checkAgainst(){
  for (var i=0;i<40000;i++){
    var wordToSearch = makeWord();
    if (isFound(wordToSearch)){
      console.log("found "+wordToSearch);
    }
  }
  console.log("finished checkAgainst");
}

function isFound(wordToSearch){
  //return $.inArray(wordToSearch,arr) > -1;
  return arr.indexOf(wordToSearch) > -1;
}

populateArr();
checkAgainst();

FIDDLE here

In this code I'm populating an array arr with 40k random strings. Than, in checkAgainst I'm creating 40,000 other random strings, and than each one is checked if it is found on arr. This makes chrome freeze for about 2 seconds. Opening the profiler on Chrome DevTools, I see that isFound is obviously expensive in terms of CPU. even if I lower the for loop iterations number to just 4000 in checkAgainst , it still freezes for about a second or so.

In reality, I have a chrome extension and an array of keywords that grows to about 10k strings. Than, I have to use Array.indexOf to see if chucks of 200 other keywords are in that array. This makes my page freeze every once in a while, and from this example I suspect this is the cause. Ideas?

Niet the Dark Absol · Accepted Answer · 2014-06-30 12:36:16Z

2

Try using keys in an object instead:

var arr = {};

function makeWord() // unchanged
function populateArr(){
  for (var i=0;i<40000;i++){
    arr[makeWord()] = true;
  }
  console.log("finished populateArr");
}
function checkAgainst() // unchanged

function isFound(wordToSearch){
  return arr[wordToSearch];
}

populateArr();
checkAgainst();

If you then need the array of words, you can use Object.keys(arr)

Alternatively, combine the two: have an array and an object. Use the object to look up if a word is in the array, or the array to get the words themselves. This would be a classic compromise, trading memory usage for time.

answered Jun 30, 2014 at 12:36

Niet the Dark Absol

326k86 gold badges480 silver badges604 bronze badges

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

Collectives™ on Stack Overflow

use Array.indexOf for relatively big arrays

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related