From: Elliotte Rusty Harold (elharo@metalab.unc.edu)
Date: Tue Oct 08 2002 - 09:25:06 EDT
At 8:44 AM -0400 10/8/02, John Cowan wrote:
>The underlying data structure here is called a "range table", and is
>a list of ranges in codepoint order, expressed thus:
>
> start of first range
> end of first range + 1
> start of second range
> end of second range + 1
>
>etc. etc. What you are doing is equivalent to a linear search over
>this range followed by loop unrolling. However, you can do better,
>especially in complex cases, with a *binary* search over the range
>followed by loop unrolling. The trick here is that if the binary
>search returns an even value, it succeeds; an odd value fails.
>
Interesting. Do you have any references on that I can explore
further? A quick google search didn't turn up anything relevant. I'm
curious to see how the algorithm actually works.
-- +-----------------------+------------------------+-------------------+ | Elliotte Rusty Harold | elharo@metalab.unc.edu | Writer/Programmer | +-----------------------+------------------------+-------------------+ | XML in a Nutshell, 2nd Edition (O'Reilly, 2002) | | http://www.cafeconleche.org/books/xian2/ | | http://www.amazon.com/exec/obidos/ISBN%3D0596002920/cafeaulaitA/ | +----------------------------------+---------------------------------+ | Read Cafe au Lait for Java news: http://www.cafeaulait.org/ | | Read Cafe con Leche for XML news: http://www.cafeconleche.org/ | +----------------------------------+---------------------------------+
This archive was generated by hypermail 2.1.5 : Tue Oct 08 2002 - 10:15:06 EDT