avoid toLower in std.algorithm.sort compare alias

Jay Norwood jayn at prismnet.com
Sat Apr 21 23:20:13 PDT 2012


On Sunday, 22 April 2012 at 02:29:45 UTC, Jonathan M Davis wrote:

> Regardless of whether it's the Big(O) complexity or the 
> constant factor that's
> the problem here, clearly there's enough additional overhead 
> that it's causing
> problems for Jay's particular case. It's also the sort of thing 
> that can be
> easy to miss and then end up wondering why your code is so slow 
> (if it
> actually matters in your particular situation).
>
> - Jonathan M Davis

I haven't looked at strncmpi code, but I suspect it is a lot more 
efficient.  For example, in comparing

AbbbCdddEfffXabcdEfgh
AbbbCdddEfffYabcdEfgh

it is not necessary to do case conversion on anything except X 
and Y, and if isUpper(X)==isUpper(Y) then X and Y can be compared 
without conversion, and since X and Y are not equal the remaining 
characters don't have to be converted.

The comment below worries me a little bit about std.string.icmp.  
What if they are two 1MB strings that differ in he first 
character?  Does it really convert both strings to lower case 
before comparing the first character?

http://dlang.org/phobos/std_string.html#icmp

"Technically, icmp(r1, r2) is equivalent to 
cmp!"std.uni.toLower(a) < std.uni.toLower(b)"(r1, r2). "




More information about the Digitalmars-d-learn mailing list