On Tue, 28 Sep 2010 20:45:27 -0400, bearophile <[email protected]>
wrote:
retard:
Instead of O(n) linear search or O(ln n) binary search, why not use O(1)
jump tables in this case?
I don't exactly know. But you must take into account the constants too,
it's not just a matter of worst-case computational complexity. Probably
when the density of a large jump table becomes too much low, its
experimental performance on modern CPUs gets worse than a binary search
among few entries. But I am not sure, I have not written&run benchmarks
on this.
Bye,
bearophile
Well there are 28 labeled cases and ~16kb of jump table address space.
(32kb on 64-bit platforms)
