avoid toLower in std.algorithm.sort compare alias

[Jonathan M Davis]

On Sunday, April 22, 2012 01:24:56 Jay Norwood wrote:
> While playing with sorting the unzip archive entries I tried use
> of the last example in
> http://dlang.org/phobos/std_algorithm.html#sort
> 
> std.algorithm.sort!("toLower(a.name) <
> toLower(b.name)",std.algorithm.SwapStrategy.stable)(entries);
> 
> It was terribly slow  for sorting the 34k entries in my test
> case.  I'd guess it is doing the toLower call on both strings for
> every compare.
> 
> It was much, much faster to add an entries.lowerCaseName =
> std.string.toLower(entries.name) foreach entry prior to the sort
> execution and then use
> 
> std.algorithm.sort!("a.lowerCaseName < b.lowerCaseName
> ",std.algorithm.SwapStrategy.stable)(entries);
> 
> The difference was on the order of 10 secs vs no noticeable delay
> when executing the sort operation in the debugger.

Yeah. toLower would be called on both strings on _every_ compare. And since 
that involves a loop, that would make the overall call to sort an order of 
magnitude worse than if you didn't call toLower at all. I'm not sure if it's 
an order of magnitude worse than your solution though, since it's been a while 
since I studied Big(O) notation (doing the conversion only once is still more 
expensive than not converting, but I'm not sure how much more expensive - it 
might cost less than sort such that it actually doesn't matter as for as 
Big(O) goes though).

- Jonathan M Davis