DEV Community

Are one-liners always the best solutions?

Kailana Kahawaii on December 24, 2020

Whenever I solved an algorithm on leetcode or codesignal, I liked to look at others solutions. For Codesignal in particular, a lot of the top voted...
Read full post
Collapse
 
harrisgca profile image
Glenn Harris • • Edited

Thanks for posting this.

Without getting into filter vs for loop, part of the reason the filter ran so long was because Math.apply is being rerun for every element in the array. It is more performant to run it once and assign the value to a variable and then run the comparison against the variable.

jsben.ch/IOkIn

Collapse
 
aminmansuri profile image
hidden_dude • • Edited

Filter is just the wrong tool for the job. Use a reduce() instead.

Map: convert one elements of an array to an array of something else
Filter: create a new array with certain items removed
Reduce: compute something with the elements of an array

In Smalltalk these were called: collect, select/reject, inject:into: (I like those names better).

martinfowler.com/articles/collecti...

Collapse
 
javila35 profile image
Joe Avila •

nice catch

Collapse
 
slnsrn profile image
Selin Serin • • Edited

this can be an alternative one line solution.
here

Alt text of image

Collapse
 
aminmansuri profile image
hidden_dude •

I don't get it.
I tried with:

const arr = [100, 22, 22, 44, 44, 44,44];
Enter fullscreen mode Exit fullscreen mode

It doesn't seem to work.

Collapse
 
slnsrn profile image
Selin Serin •

sorry, i forgot to mention.
You need to write the sort function explicitly. Otherwise sorts as a string and 4 > 1 :)

   arr.sort((a, b) => a - b)
Enter fullscreen mode Exit fullscreen mode
Collapse
 
jcubic profile image
Jakub T. Jankiewicz •

Clever.

Collapse
 
aminmansuri profile image
hidden_dude • • Edited

The one liner solution here would be to use reduce.
Or map and reduce.

It's important to use the right tool for the job.

For example:

  1. Map the array to the tuple: (num, occ). Ie. number and occurrences, where it would be mapped to 1 initially.
    For example:
    [1,2,3,2,3] => [(1,1),(2,1),(3,1),(2,1),(3,1)]

  2. Reduce to find the max and sum occurrences:
    [(1,1),(2,1),(3,1),(2,1),(3,1)] => (3,2)

Then you basically have your solution that is O(N) so it's faster than solutions based on sort.

Reduce is what you need to convert a list of values into a single solution. But sometimes you need to convert the list into something else to be able to reduce it.

The code would be something like:

arr.map( n => [n,1]).reduce( (result, tuple) =>  
     (result[0] > tuple[0]) ? result :
          (result[0] == tuple[0]) ? [result[0], result[1]+1] :
               tuple)
Enter fullscreen mode Exit fullscreen mode

The lambda can probably be written clearer.

Collapse
 
aminmansuri profile image
hidden_dude •

If you hate the double loop you can avoid the map like this:


arr.reduce( (result, num) =>  
     (result[0] > num) ? result :
          (result[0] ==num) ? [result[0], result[1]+1] :
               [num,1],  (arr[0],0))
Enter fullscreen mode Exit fullscreen mode

This does it all in one pass.

Collapse
 
aminmansuri profile image
hidden_dude • • Edited

In some languages map/reduce are lazy so it's super efficient to do this (ie. it only goes through the array once). Not sure about Javascript though.

Still, going through the array twice is still more efficient than sorting. Though it's a pity the array has to be copied (in Java or .Net the array wouldn't need to be copied for example, so in theory it's as efficient as the raw for loop, but more readable).

Collapse
 
kahawaiikailana profile image
Kailana Kahawaii •

Awesome! I love seeing solutions like these.

Collapse
 
mafflerbach profile image
mafflerbach •

I prefer in general the "long" version. It's about readability. I may have to read more, but it is more clear what happens, especially when I have to switch between multible languages. The general structure from an if/else or a loop are very similar in all languages, but comes to syntactic sugar it becomes difficult.

Collapse
 
noclat profile image
Nicolas Torres • • Edited

Indeed! For loop is a core syntax element of JavaScript so, if written decently, will always be faster than iterator methods and while loops etc.
To dive further into performance:

  • .sort() alters the original array, no need to reassign it, to save a bit of memory :);
  • your snippet computes sort.length on each iteration, better store it into a variable;
  • count and i have the same value, so you can remove one of them.

Note that for loop first instruction can actually be any set of declarations. So You could directly optimize the code like that:

arr.sort((a,b) => b - a);
let count = 0; // declared outside so it remains in the scope after for loop
for(const n = arr.length; count < n; count++) {
  if (arr[0] !== arr[count]) {
    return count;
  } 
}
return count;
Enter fullscreen mode Exit fullscreen mode

But anyway, .sort() on large arrays will still iterate over all elements. Put like this, it'll be more elegant and should have more or less the same perfs:

const target = Math.max(...arr); // compute once, expensive
return arr.filter(v => v === target).length; // iterate once, cheap
Enter fullscreen mode Exit fullscreen mode
Collapse
 
noclat profile image
Nicolas Torres • • Edited

And if you really want the best possible perfs, the best option is to iterate once.

It could go like that:

let count = 0;
for (let i = 0, max = 0, n = arr.length; i<n; i++) {
  if (arr[i] > max) {
    max = arr[i];
    count = 1;
  } else if (arr[i] === max) {
    count++;
  }
}
return count;
Enter fullscreen mode Exit fullscreen mode
Collapse
 
javila35 profile image
Joe Avila •

Great article Kailana.

Collapse
 
ridoansaleh profile image
Ridoan •

This is interesting, less code not always means better performance

Collapse
 
rsa profile image
Ranieri Althoff •

That is never implied, and the problem of this post is not even related to that. It's an inefficient algorithm vs an efficient one problem.