Sparse O(1) array with indices being consecutive products
- by Kos
Hello,
I'd like to pre-calculate an array of values of some unary function f.
I know that I'll only need the values for f(x) where x is of the form of a*b, where both a and b are integers in range 0..N.
The obvious time-optimized choice is just to make an array of size N*N and just pre-calculate just the elements which I'm going to read later. For f(a*b), I'd just check and set tab[a*b]. This is the fastest method possible - however, this is going to take a lot of space as there are lots of indices in this array (starting with N+1) which will never by touched.
Another solution is to make a simple tree map... but this slows down the lookup itself very heavily by introducing lots of branches. No.
I wonder - is there any solution to make such an array less sparse and smaller, but still quick branchless O(1) in lookup?
