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
