4 ms·

Interestingly, Dick's code is by far the fastest using those implementations. For a sample size of 1,000,000 employees (to highlight the efficiency difference):

by atto 14y ago

Interestingly, Dick's code is by far the fastest using those implementations. For a sample size of 1,000,000 employees (to highlight the efficiency difference): Tom (sorted version): 1510ms Dick (min-linear version): 113ms Harry (monoid version): 995ms

greendestiny 14y ago
I don't think the point is the implementation itself, just what the author finds interesting in a problem. After all the 'plus' operator just does a series of ordered comparisons like the minBy solution does.
- atto 14y ago
  Sure. However, it does represent problems I've seen before with "overly" (subject to the person, I guess) complex solutions that end up being significantly less efficient. In this case, the problem is actually the `.toSet`, which forces a second iteration of the dataset. If the Monoid class was rewritten (yes, to be less mathematically pure) to use Seqs, it's nearly identical performance (as expected) as the linear solution. Fun performance graph: http://i.imgur.com/2rOvb6V.png http://i.imgur.com/2rOvb6V.png
  - greendestiny 14y ago
    That is interesting. Personally I didn't find framing the original problem as monoid enlightening at all, but that's what I thought the author was getting at.
jes5199 14y ago
I find that to be pretty typical - naive solutions are bad for Big-O reasons. If you solve the math on paper and implement a straightforward algorithm, you get the fastest possible solution. If you push some of that math into the type system of your language, you get something that should be Big-O equivalent to the fastest possible solution, but the machinery of the type system never gets fully optimized away. There might be other advantages, though, of having that machinery - your compiler might be able to detect errors in your code, or you might be able to use higher-level constructs to make more concise code. Maybe.
davidroberts 14y ago
So the ultimate point is the futility of spending any time optimizing a solution to a problem that at most requires 2 seconds to run.
graue 14y ago
If it's fair for you to benchmark this, it's surely also fair for me to point out that in a lazily-evaluated language (Haskell!), Tom's approach is O(n) and equivalent to Dick's. :)
- fusiongyro 14y ago
  That's true if you pick the right sort algorithm. I'm not sure if it is true of whatever happens to be in Data.List; I wouldn't be surprised either way.

by atto 14y ago

greendestiny 14y ago

I don't think the point is the implementation itself, just what the author finds interesting in a problem. After all the 'plus' operator just does a series of ordered comparisons like the minBy solution does.

atto 14y ago
Sure. However, it does represent problems I've seen before with "overly" (subject to the person, I guess) complex solutions that end up being significantly less efficient. In this case, the problem is actually the `.toSet`, which forces a second iteration of the dataset. If the Monoid class was rewritten (yes, to be less mathematically pure) to use Seqs, it's nearly identical performance (as expected) as the linear solution. Fun performance graph: http://i.imgur.com/2rOvb6V.png http://i.imgur.com/2rOvb6V.png
- greendestiny 14y ago
  That is interesting. Personally I didn't find framing the original problem as monoid enlightening at all, but that's what I thought the author was getting at.

jes5199 14y ago

I find that to be pretty typical - naive solutions are bad for Big-O reasons. If you solve the math on paper and implement a straightforward algorithm, you get the fastest possible solution. If you push some of that math into the type system of your language, you get something that should be Big-O equivalent to the fastest possible solution, but the machinery of the type system never gets fully optimized away. There might be other advantages, though, of having that machinery - your compiler might be able to detect errors in your code, or you might be able to use higher-level constructs to make more concise code. Maybe.

davidroberts 14y ago

So the ultimate point is the futility of spending any time optimizing a solution to a problem that at most requires 2 seconds to run.

graue 14y ago

If it's fair for you to benchmark this, it's surely also fair for me to point out that in a lazily-evaluated language (Haskell!), Tom's approach is O(n) and equivalent to Dick's. :)

fusiongyro 14y ago
That's true if you pick the right sort algorithm. I'm not sure if it is true of whatever happens to be in Data.List; I wouldn't be surprised either way.