But I'm still confused how this reduces the number of iterations of the binary search when the array has no duplicates in it?
Mike McCandless http://blog.mikemccandless.com On Wed, Aug 6, 2014 at 6:49 PM, Fuxiang Chen <[email protected]> wrote: > Dear Michael, > > > Thank you for the prompt reply. We truly appreciate it. > > Yes, there are 4 similar occurrences of this, that's why we only display the > general structure that is being exhibited. > > The potential faster implementation is by fetching the index of a key > immediately lower than the one you were looking for, then do a binary chop > between the two. > > e.g. > > else if (low != mid) //Equal but range is not fully scanned > high = mid; //Set upper bound to current number and rescan > > At this point we do a binary chop and this will save us iterations of > checking. > > This has been suggested by a couple of high reputation open-source users > such as Jon Skeet and Max. > > Reference: http://stackoverflow.com/questions/6676360/. > > We hope you can consider this and let us know of your thoughts. > > Please do not hesitate to contact me @ [email protected] as we truly value > your feedback and comments. > > Thanks and have a great week ahead! > > > > On Wed, Aug 6, 2014 at 9:42 PM, Michael McCandless > <[email protected]> wrote: >> >> Hmm, but in Lucene, a SortedIntDocSet should never contain duplicates? >> >> Also, there are multiple binary searches in that source ... I'm not >> sure which one(s) you're trying to speed up, and I don't see how >> adding more conditionals would make the code faster. >> >> Mike McCandless >> >> http://blog.mikemccandless.com >> >> >> On Wed, Aug 6, 2014 at 12:40 AM, Fuxiang Chen <[email protected]> wrote: >> > Dear Lucene Developers, >> > >> > In the source file "SortedIntDocSet.java", the code fragment that is >> > used >> > for binary search can have its speed improved by adding two more >> > conditions. >> > >> > Original Code >> > -------------------- >> > if (docb < doca) { >> > low = mid+1; >> > } >> > else if (docb > doca) { >> > high = mid-1; >> > } >> > >> > >> > Changed Code >> > ---------------------- >> > if (docb < doca) { >> > low = mid+1; >> > } >> > else if (docb > doca) { >> > high = mid-1; >> > else if (low != mid) //Equal but range is not fully scanned >> > high = mid; //Set upper bound to current number and rescan >> > else //Equal and full range is scanned >> > return mid; >> > >> > Reference: http://stackoverflow.com/questions/6676360/ >> > >> > >> > -- >> > Warmest Regards, >> > Fuxiang >> >> --------------------------------------------------------------------- >> To unsubscribe, e-mail: [email protected] >> For additional commands, e-mail: [email protected] >> > > > > -- > Warmest Regards, > Fuxiang --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
