avoid toLower in std.algorithm.sort compare alias

Jonathan M Davis jmdavisProg at gmx.com
Sat Apr 21 19:22:16 PDT 2012


On Sunday, April 22, 2012 03:47:30 Jay Norwood wrote:
> On Saturday, 21 April 2012 at 23:54:26 UTC, Jonathan M Davis
> 
> wrote:
> > 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
> 
> use of toLower in the sort expression adds around 11.2 secs
> overhead to a 0.3 sec operation which reads and sorts the 34k
> directory entries in this 2GB layout on the ssd drive, so it
> isn't an option for me.
> 
> finished! time:312 ms
> 
> finished! time:11598 ms
> 
> std.algorithm.sort!("toLower(a) <
> toLower(b)",std.algorithm.SwapStrategy.stable)(dirs);
> //std.algorithm.sort!("a < b",
> std.algorithm.SwapStrategy.stable)(dirs);

It wasn't saying that it _was_ an option. I was just trying to point out the 
likely reason why it's so bad with toLower - algorithmically-speaking. This 
definitely appears to be a case where doing some extra computation ahead of 
time will save you a lot later.

- Jonathan M Davis


More information about the Digitalmars-d-learn mailing list