Why is my _.words() implementation sooo slow?

I am currently working on the lodash Project. We are tasked to implement _.words()
One obvious way is to use String.split(), as it does essentially the same. As using split wouldn’t require any arrays, loops, iterators or objects it is against the purpose of the exercise and i tried to implement it by my own. This is what i came up with:

    words(sentence){
        let chars = [];
        let words = [];
        for(let i = 0; i < sentence.length; i++){
            if(sentence[i] != ' ') chars.push(sentence[i]);
            if((sentence[i] === ' ' || i === sentence.length - 1) && chars != []){
                words.push(chars.join(''));
                chars = [];
            }
        }
        return words;
    },

    words2(sentence){
        return sentence.split(' ');
    },

It passes all the tests, but well… it is slow as a snail when compared to String.split(). I have done some measurements and my implementation takes ~4.7 times longer than String.split().

Why is this the case? Is there something fundamentally wrong with my algorithm?

The code i used to test this:

function measureRuntime(func, iterations = 1, ...rest){
    const { performance } = require('perf_hooks');
    if(iterations < 1) return NaN;
    let start = performance.now();
    for(let i = 1; i <= iterations; i++){
        func(...rest);
    }
    return (performance.now()-start)/iterations;
}

let input = 'a ';
for(let i = 0; i<=20; i++) input = input + input;
iterations = 100;

console.log(measureRuntime(_.words, iterations, input));
console.log(measureRuntime(_.words2, iterations, input));
/*
143.64185600001366
30.37421700000763
*/

Hey there Kevin!
Here I’d separate with a else statement:


if(sentence[i] != ' ') chars.push(sentence[i]);
if((sentence[i] === ' ' || i === sentence.length - 1) && chars != []){
  words.push(chars.join(''));
  chars = [];
}

Or you could use continue inside the first condition but after the push.

Also, now that I think about it:
you don’t need to push every character to the char array. You could store temporarily as a string and then push the entire temp variable to words once you hit a blank. Then reset the temp var.

Does this make any sense? Are you also actively learning from this suggestion?

3 Likes

From what I know, for loops are generally slower than iterators (array methods). Even if they perform the same task.
But your alternative solution runs through so many tasks compared to the .split() method, that I wouldn’t be surprised that it is much slower.

  1. Iterate through each character of the string passed in
  2. Check if each character meet one or more of four conditions
  3. Push each letter to an array
  4. Join each letter that is not a space
  5. Create a new array for each word

What part of the instructions make you think that .split() is against the instructions?

1 Like

I think the misunderstanding could come from the fact that loadash is presented as the holy graal of performance. While this could have been true 10 years ago when it was first released, most of its most useful methods have been absorbed into ES6 in 2015 and later.

One very cool thing that JS doesn’t support yet natively, maybe loadash does I don’t know, is an array comparator, so a function/method that is able to compare two arrays.

more info here:

It’s an amazing piece of code, very recommended. :slight_smile:

No part of the instructions, just that the lodash project is within the Practice JavaScript Syntax: Arrays, Loops, Objects, Iterators part of the course. So i shall practice those :slight_smile:

@usernamegiapreso
Your suggestion of using a temporary string was golden. Changed the code to:

words(sentence){
        let chars = '';
        let words = [];
        for(let i = 0; i < sentence.length; i++){
            if(sentence[i] != ' ')chars = chars + sentence[i];
            if((sentence[i] === ' ' || i === sentence.length - 1) && chars != ''){
                words.push(chars);
                chars = '';
            }
        }
        return words;
    },

now it only takes a third of the runtime of the original method. Still ~1.8 times slower than String.split(), but that’s at least close.

btw. is the String.split() method precompiled to assembly (in nodejs) or is it just internal javascript beeing interpreted aswell? May make a difference too.

Edit:
Adding a continue in the first if block made me require to do another push after the for loop (otherwise the last word was skipped). But it improved runtime a little bit, too.

It is perfectly fine to use that method in the lodash project and even intended, as I understood.

I Don’t know much about NodeJS yet, I like that you’re so centered on time complexity. :slight_smile:

1 Like