Tuesday, January 20, 2009

O(log(N)) or O(1)?

I use a binary search on types and methods to find the corresponding function. This has O(log(N)).

It is possible to compile to O(1) lookup, assuming that the source is type-checked. A select term can be written in compiled down lambda terms as ((select "a_method") a_value). The term (select "a_method") can be translated to a combinator "F_a_method". If the value holds an integer of a fixed range, the number of types, O(1) is possible.

I am sticking with the first scheme for now.

No comments:

Post a Comment