Fastest / most efficient way to compare two string arrays Javascript

Question

Hi I was wondering whether anyone could offer some advice on the fastest / most efficient way to compre two arrays of strings in javascript.

I am developing a kind of tag cloud type thing based on a users input - the input being in the form a written piece of text such as a blog article or the likes.

I therefore have an array that I keep of words to not include - is, a, the etc etc.

At the moment i am doing the following:

Remove all punctuation from the input string, tokenize it, compare each word to the exclude array and then remove any duplicates.

The comparisons are preformed by looping over each item in the exclude array for every word in the input text - this seems kind of brute force and is crashing internet explorer on arrays of more than a few hundred words.

i should also mention my exclude list has around 300 items.

Any help would really be appreciated.

Thanks

scunliffe · Accepted Answer · 2010-02-21 22:38:10Z

5

I'm not sure about the whole approach, but rather than building a huge array then iterating over it, why not put the "keys" into a map-"like" object for easier comparison?

e.g.

var excludes = {};//object
//set keys into the "map"
excludes['bad'] = true;
excludes['words'] = true;
excludes['exclude'] = true;
excludes['all'] = true;
excludes['these'] = true;

Then when you want to compare... just do

var wordsToTest = ['these','are','all','my','words','to','check','for'];
var checkWord;
for(var i=0;i<wordsToTest.length;i++){
  checkWord = wordsToTest[i];
  if(excludes[checkword]){
    //bad word, ignore...
  } else {
    //good word... do something with it
  }
}

allows these words through ['are','my','to','check','for']

answered Feb 21, 2010 at 22:38

scunliffe

63.8k26 gold badges133 silver badges168 bronze badges

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

8 Comments

Tim Down Over a year ago

To prevent any chance of this going wrong because of augmentation of Object.prototype (for example, if a library has added an each method to Object.prototype, "each" will be considered a bad word in the example code), you could use jshashtable (timdown.co.uk/jshashtable).

David Over a year ago

this makes sense. I have implemented it and ti works great in firefox but it still crashes ie as it did before. I wonder if ie is known for problems like this or if my code can be improved any.

David Over a year ago

Edit: I have just tested my code in chrome, opera, firefox and safari and it works super fast. In ie it fails miserably and i have to restart the browser :(

Kyle Butt Over a year ago

@Tim Down: That's a very good reason NOT to use frameworks that mash the default namespace until it's unrecognizable.

scunliffe Over a year ago

@David - do you have a url where we can see the whole the thing? There may be something else tripping up IE.

|

Pointy · Accepted Answer · 2010-02-21 23:59:29Z

2

It would be worth a try to combine the words into a single regex, and then compare with that. The regex engine's optimizations might allow the search to skip forward through the search text a lot more efficiently than you could do by iterating yourself over separate strings.

answered Feb 21, 2010 at 23:59

Pointy

415k62 gold badges600 silver badges631 bronze badges

Comments

pablochan · Accepted Answer · 2010-02-21 22:21:39Z

0

You could use a hashing function for strings (I don't know if JS has one but i'm sure uncle Google can help ;] ). Then you would calculate hashes for all the words in your exclude list and create an array af booleans indexed by those hashes. Then just iterate through the text and check the word hashes against that array.

answered Feb 21, 2010 at 22:21

pablochan

5,72530 silver badges42 bronze badges

2 Comments

David Over a year ago

thanks for the reply, I will definately look into that but how much faster can this be since you are still essentially iterating over the same number of elements the same number of times arent you?

pablochan Over a year ago

Nope. The algorithm that you presented has O(nmk) complexity where n is the exclude list size, m - text size and k is the average number of operations in string comparison. The method im proposing has O(n) complexity for the initial hashing and O(m) for every comparison

vsync · Accepted Answer · 2011-05-23 00:22:24Z

0

I have taken scunliffe's answer and modified it as follows:

var excludes = ['bad','words','exclude','all','these']; //array

now lets prototype a function that checks if a value is inside an Array:

Array.prototype.hasValue= function(value) {
  for (var i=0; i<this.length; i++)
      if (this[i] === value) return true; 
  return false;
}

lets test some words:

var wordsToTest = ['these','are','all','my','words','to','check','for'];
var checkWord;
for(var i=0; i< wordsToTest.length; i++){
  checkWord = wordsToTest[i];
  if( excludes.hasValue(checkWord) ){
    //is bad word
  } else {
    //is good word
    console.log( checkWord );
  }
}

output:

['are','my','to','check','for']

answered May 23, 2011 at 0:22

vsync

133k61 gold badges345 silver badges430 bronze badges

Comments

yunzen · Accepted Answer · 2011-10-01 15:56:35Z

0

I'd opt for the regex version

text = 'This is a text that contains the words to delete. It has some <b>HTML</b> code in it, and punctuation!';
deleteWords = ['is', 'a', 'that', 'the', 'to', 'this', 'it', 'in', 'and', 'has'];

// clear punctuation and HTML code
onlyWordsReg = /\<[^>]*\>|\W/g;
onlyWordsText = text.replace(onlyWordsReg, ' ');

reg = new RegExp('\\b' + deleteWords.join('\\b|\\b') + '\\b', 'ig');
cleanText = onlyWordsText .replace(reg, '');

// tokenize after this

answered Oct 1, 2011 at 15:56

yunzen

33.5k13 gold badges79 silver badges114 bronze badges

Collectives™ on Stack Overflow

Fastest / most efficient way to compare two string arrays Javascript

5 Answers 5

8 Comments

Comments

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

8 Comments

Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related