[erlang-questions] How would you do 100 ifs?

Jesper Louis Andersen jesper.louis.andersen@REDACTED
Tue Nov 15 16:16:27 CET 2011

On Tue, Nov 15, 2011 at 16:03, Sverker Eriksson
<sverker@REDACTED> wrote:

> Or do binary search in a tuple:

I'd also contemplate a digital method. Note that if we restrict
ourselves to numbers less than 16bit in size, we can inspect the most
significant bit and then split on that one. If it is set, we know the
number falls into the group of numbers above 32767, if not below. This
allows us a fast indexing which can let us pick a candidate interval
quickly. There are now two methods which are applicable:

Path compression. Skip bits which do not "make any significant
impact". This is essentially the idea of a RADIX/Patricia tree.

Level compression. We could inspect 4 bits at the first level and take
one of the 16 branches. The interesting thing here is that binary
pattern matches allows us to do this, and it may be fairly fast.
Further, it allows us to begin with a great stride.

Another worthy idea is to play with the concept where you coalesce a
number of small intervals into a list and then just pick general
intervals. Linear search in a small list may be faster.


More information about the erlang-questions mailing list