5
\$\begingroup\$

I have the following solution but I am trying to optimize it to run in O(n) time, any thoughts?

I first split the string removing any non-alphanumeric characters, then split the words using spaces and then sort the new string. The rest is just looping to get the duplicate words and its count which I sort one last time to have the most frequently used word on top of the list.

This function also takes care of empty spaces, and limits the numofwords parameter to the total number of words, to avoid any unexpected results.

function getFrequency(mystring, numofwords) {
    mystring = mystring.replace(/[\.,-\/#!$%\^&\*;:{}=\-_`~()]/g,"");
    var words = mystring.split(' '),
    sortedWords = words.sort(),
    uniqueWords = [],
    d = {},
    wordcount = 1,
    result = [];

    for (var i=0; i<sortedWords.length; i++) {

        var currentword = sortedWords[i];

        if(sortedWords[i+1] === currentword) {
            wordcount++;
        }

        if(!d[currentword]) {
            d[currentword] = true;
            uniqueWords.push({word:currentword, count:wordcount});
        }   
    }

uniqueWords = uniqueWords.slice(0,numofwords).sort(function (a,b) { return b.count-a.count;});  

for(i=0; i<uniqueWords.length; i++) {

    result.push(uniqueWords[i].word);
}

return result.toString();
}
\$\endgroup\$
  • 2
    \$\begingroup\$ For linear complexity, you would need to get rid of the sorting. For comparison-based sort algorithms, it is proveable they need at least O(n*log(n)) in the average case (planetmath.org/LowerBoundForSorting). \$\endgroup\$ – Abrixas2 Sep 26 '14 at 14:07
5
\$\begingroup\$

From a once over:

  • It seems your code is giving the words with fewest occurrences, consider switching b.count and a.count
  • I am not vehemently against regexes, but if you use them, I would advise 2 lines of comments, one with the intent of the regex, and one with an example of from -> to
  • Naming, numofwords -> should be numOfWords or since you only use it once you might as well go for numberOfWords and personally I called it cutOff
  • Not sure why you named the string myString, I would just call it string or s
  • It seems that sorting the words in advance will require more code to process the words and it is not guaranteed to be faster, I would not do that
  • From a data structure perspective, I would go for an object, where each word is a property of the object, and the value is the count, this way you can skip the build
  • If you are going to sort and slice, then perhaps you should FIRST sort and SECOND slice ;)

This would be my approach:

function getFrequency2(string, cutOff) {
  var cleanString = string.replace(/[\.,-\/#!$%\^&\*;:{}=\-_`~()]/g,""),
      words = cleanString.split(' '),
      frequencies = {},
      word, frequency, i;

  for( i=0; i<words.length; i++ ) {
    word = words[i];
    frequencies[word] = frequencies[word] || 0;
    frequencies[word]++;
  }
  
  words = Object.keys( frequencies );

  return words.sort(function (a,b) { return frequencies[b] -frequencies[a];}).slice(0,cutOff).toString();
}

document.write( getFrequency2( "1 2 1 2 3 1 2 3 1 1 4 test", 3  ) ); 

\$\endgroup\$
  • \$\begingroup\$ Are the and The considered "Unique Words"? A case-insensitive comparison might be needed, depending on your use case. Also, a split on whitespace instead of space will handle newlines and non-breaking spaces as well, i.e. words = cleanString.split(/\s/). \$\endgroup\$ – Mogsdad May 25 '15 at 0:16
  • \$\begingroup\$ How many words this have for you? " ".split(' '); (note that code formatting is not allowing me to show the bunch of spaces the string has) \$\endgroup\$ – Sebastian Aug 1 '16 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.