2
\$\begingroup\$

I've implemented a method to solve the following problem:

Given a dictionary and a text string, find all words from the dictionary that are present in the text. One important point is that if the string is in double quotes, I should treat it a "single" value. If no matches found, the method should return 0.

So for this input:

const text = `Hi. I am a developer. A "Hello world" program was my first code.`;
const dictionary = "hi developer world";

I should get this:

hi
developer
hello
world

This is my current solution:

const fn = (text, dictionary) => {
    const knownWords = dictionary.toLowerCase().split(' ');
    const words = text.toLowerCase().match(/\w+|"[^"]+"/gi);

    const result = words.reduce((acc, word) => {
        if (word[0] == '"') {
            const wordsNoQuotes = word.replace(/"/g, "").split(' ');
            const shouldInclude = wordsNoQuotes.find(word => knownWords.includes(word));
            if (shouldInclude) {
                return acc.concat(wordsNoQuotes);
            }
        } else if (knownWords.includes(word)) {
            acc.push(word)
        }

        return acc;
    }, []);

    return result.length === 0 ? 0 : [...new Set(result)].join('\n');
}

It works ok, but I would like to get some performance related improvements. I am happy to change the code (i.e using indexOf over includes) and so on. Any suggestions are welcome! Thanks.

\$\endgroup\$
2
  • \$\begingroup\$ if the string is in double quotes, I should treat it a "single" value This is a bit unclear to me, given the expected output example. Do you mean that if a matching word is included in double quotes, every word inside those double quotes should be matched as well? \$\endgroup\$ – CertainPerformance Apr 14 '20 at 0:20
  • \$\begingroup\$ @CertainPerformance, yes, if at least one of the words in quotes is in dictionary, all the of the words should be included in the returned result. \$\endgroup\$ – Dan Cantir Apr 14 '20 at 6:39
1
\$\begingroup\$

The main potential performance improvement I can see is turning the array of words into a Set of words instead. For every match in the string, you're doing:

const shouldInclude = wordsNoQuotes.find(word => knownWords.includes(word));

The .find is O(n) (it iterates over all words in the array, worst-case), and the .includes is O(n) (it also iterates through all words in its array, worst-case). So this is an O(n ^ 2) operation which is already inside a loop. That could be a bit expensive when either or both arrays are large. Using a Set for one of the arrays instead will allow you to use Set.prototype.has, which is an O(1) operation. The else part also uses .includes, which can be changed to .has:

const knownWordsSet = new Set(dictionary.toLowerCase().split(' '));
const words = text.toLowerCase().match(/\w+|"[^"]+"/gi);
const result = words.reduce((acc, word) => {
  if (word[0] == '"') {
    const wordsNoQuotes = word.replace(/"/g, "").split(' ');
    const shouldInclude = wordsNoQuotes.find(word => knownWordsSet.has(word));
    if (shouldInclude) {
      return acc.concat(wordsNoQuotes);
    }
  } else if (knownWordsSet.has(word)) {

const fn = (text, dictionary) => {
  const knownWordsSet = new Set(dictionary.toLowerCase().split(' '));
  const words = text.toLowerCase().match(/\w+|"[^"]+"/gi);
  const result = words.reduce((acc, word) => {
    if (word[0] == '"') {
      const wordsNoQuotes = word.replace(/"/g, "").split(' ');
      const shouldInclude = wordsNoQuotes.find(word => knownWordsSet.has(word));
      if (shouldInclude) {
        return acc.concat(wordsNoQuotes);
      }
    } else if (knownWordsSet.has(word)) {
      acc.push(word)
    }

    return acc;
  }, []);

  return result.length === 0 ? 0 : [...new Set(result)].join('\n');
}
console.log(fn(
  `Hi. I am a developer. A "Hello world" program was my first code.`,
  "hi developer world"
));

But Sets have a small overhead as well, so while this will definitely be the best strategy for large inputs, it might do slightly worse for tiny inputs when there are only one or a couple of words. (But for such tiny inputs, performance is not an issue to worry about anyway)

You're currently pushing to an array inside the loop, then the array only gets used to create a Set to deduplicate at the end of the function. It would be more efficient to use a Set of the result words from the beginning, instead of using an array and converting to one after the fact (converting an array to a Set and the other way around is an O(n) process). At this point, since the accumulator would be the same Set every time, .reduce would arguably not be appropriate, so use a plain loop instead.

A potential issue in your current code is that if the global .match has no matches, it will return null, not an empty array (unfortunately). So, to avoid occasionally throwing errors, you have to check to see if the match exists first before iterating over it.

You're using .find to check if there are any elements in the wordsNoQuotes array which fulfill the condition. But you don't care about which element fulfills the condition - you just want to see if any element does. So, rather than using .find (which returns the matching element), it would be more semantically appropriate to use .some (which returns true if any elements pass a callback test, and false otherwise)

When the match is a quote string, your

word.replace(/"/g, "").split(' ');

iterates over and checks every character of the string twice - once to check for "s to remove, and again to identify the positions of spaces. Since you already know the positions of the "s are the first and last character, you could use slice instead:

word.slice(1, word.length - 1).split(' ');

But your word variable isn't necessarily a word - it may well be a quoted string which contains multiple words. To improve clarity, maybe call it match instead.

Edited version in full:

const fn = (text, dictionary) => {
  const knownWordsSet = new Set(dictionary.toLowerCase().split(' '));
  const matches = text.toLowerCase().match(/\w+|"[^"]+"/gi);
  if (!matches) return 0;
  const resultSet = new Set();
  for (const match of matches) {
    if (match[0] == '"') {
      const wordsNoQuotes = match.slice(1, match.length - 1).split(' ');
      const shouldInclude = wordsNoQuotes.some(word => knownWordsSet.has(word));
      if (shouldInclude) {
        for (const word of wordsNoQuotes) {
          resultSet.add(word);
        }
      }
    } else if (knownWordsSet.has(match)) {
      resultSet.add(match);
    }
  }
  return resultSet.size === 0 ? 0 : [...resultSet].join('\n');
}
console.log(fn(
  `Hi. I am a developer. A "Hello world" program was my first code.`,
  "hi developer world"
));

\$\endgroup\$
1
  • \$\begingroup\$ Perfect! Thank you very much! \$\endgroup\$ – Dan Cantir Apr 14 '20 at 8:52

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.