Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.albasani.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: blmblm@myrealbox.com Newsgroups: comp.lang.java.programmer Subject: Re: StringBuilder Difficulties Date: 4 Jul 2011 03:32:50 GMT Organization: None Lines: 37 Message-ID: <97cqj2FbqnU2@mid.individual.net> References: <9796kgFoijU3@mid.individual.net> <979v96F7epU1@mid.individual.net> X-Trace: individual.net 3bV38f8HdaORnQW1gEluvgr+zOmPmckj76SA/9aIBPqClboFby X-Orig-Path: not-for-mail Cancel-Lock: sha1:AvEVbthmf5JC97Jh/Pt60XJMb/I= X-Newsreader: trn 4.0-test76 (Apr 2, 2001) Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:5840 In article , Patricia Shanahan wrote: > On 7/2/2011 6:34 PM, blmblm@myrealbox.com wrote: > ... > > Both programs (yours and mine) now consistently report sequential > > search to be faster than binary search. Weird, but not as weird as > > the two being different in that regard .... > ... > > Binary search can have a much higher constant multiplier on its time > than sequential search. If the searches are long enough, the O(log n) vs > O(n) complexity difference should dominate over the constant multiplier, > but for short searches the constant multiplier can dominate. Of course -- I know better than to think computational complexity is the whole story, especially in dealing with small problem sizes, which I think is what we have here. (Why I notice this kind of "what was I thinking?" only after posting, who knows.) > Binary search is more expensive than it looks because of branch > prediction. Which makes sense .... [ snip ] > The only way to know which way round this will come out is indeed to > measure, making sure the searches are as similar as possible to the real > workload. Which is apparently by no means straightforward in Java! I recently skimmed through the articles by Brian Goetz referenced in one of Stefan Ram's posts from a while back, and -- fascinating stuff. -- B. L. Massingill ObDisclaimer: I don't speak for my employers; they return the favor.