I've asked a similar (but not identical) question on SO here https://stackoverflow.com/questions/5984102 but the answers aren't that helpful for I need very fast indexing (and maybe that my question wasn't clear enough).
I precomputed a lot of values that took days to compute (with the load spread on several computers). Now I've got a huge lookup table that I need to frequently access and that access has to be as fast as possible.
Basically, I've got a problem like this: I precomputed C(38,6) values (i.e. 2 760 681 values) that are now store in a big lookup table. Memory ain't an issue. Precomputing ain't an issue. The "order" ain't an issue and I can re-order in any way I like.
Also, C(38,6) is just an example, I could be needing C(42,7) as well, etc.
When I did the precomputing, I basically looped like this (the actual code is more complicated for the load needed to be spread across several machines and for the actual computation aren't here but here's the meat of it):
for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { for (int l = k + 1; l < n; l++) { for (int m = l + 1; m < n; m++) { for (int o = m + 1; o < n; o++) { ... } } } } } }
The only thing that matters is to have the fastest lookup time possible.
I've got i,j,k,l,m and n all in [0..37] (or [1..38], doesn't matter) and I need to access the corresponding precomputed element in my huge lookup array as fast as possible.
Is there a closed formula for this that is fast to compute?
What I've got now is a binary search: my i shall always be lower than j, j lower than k etc. I then created an arbitrary index doing:
(i + 1) * (n exp 5) + (j + 1) * (n exp 4) + (k + 1) * (n exp 3) + (l + 1) * (n exp 2) + (m + 1) * n + o
This is probably overkill but guarantees no collisions. I then do a binary search on that index and find where the precomputed value is stored.
This is kinda fast but I was wondering if there was a faster way to "reach" my precomputed index?
Basically because I don't know enumerative combinatorics well enough I'm precomputing my own index and using that index to do a binary search. This is fast but I'm looking for something faster, like a closed formula (I doubt anything doing "enumerations" and i++ or things like that would be faster than those few multiplication to compute that index + the binary search).
I think the complexity of my method is log(n) but I'm just not sure.