Optimal way to implement this specific lookup table in C#?

Question

I want to create a lookup table for this data:

The "input variables" (what is used to "lookup") are 4 different doubles that can each take on 1 of 200 numbers (the numbers range from 1-1000 but there are only 200 possible numbers that each can be (these 200 possible numbers that each of them can be are known to me)) the doubles are all 2 decimal places. If any one of the four were changed it would slightly change the output variables. There is also 1 integer (enum really) that can take on a value from 1-5.

There is a condition on 3 of the input variables that (1/x + 1/y + 1/z must be less than 1.02). Could this be used in a hashing algorithm?

The "output variables" (what is returned) are ~30 doubles (mostly 2 decimal places but one has 10 decimal places). (will be packaged in an object) ranging from 1 to 1000 (2 decimal places).

I expect there to be ~150 million records.

Should I use a big dictionary and load it into memory then I start the program?

Would a Database and LINQ be best?

Can I use Trees or Hashing in some way to speed it up?

I've never had to make a LUT this big before, where speed is a major factor.

Clarification: Because of the condition that (1/x + 1/y + 1/z must be less than 1.02, see above) there is only ~150 million combinations of input variables. Not ~(200)^4.

Update:

I have looked at some stats (min and max observed values and discovered some relationships) for my input variables and have found that if we call the 4 input doubles A, B, C, D: A and B have ~200 possible values each,
C has ~50 possible values, and
D has ~120 possible values

Of these, there are several relationships that mean that there are only ~27 million combinations of these rather than the ~150 million I originally thought. So there will be ~27 million records in the LUT. There is also definitely a relationship that I haven't been able to figure out between (A, B, C) and D which will also bring down the number of combinations.

Would it be optimal to run the LUT from RAM now that I have reduced the entries from 150 to 27 million (and probably lower)?

Now that it's down to 27 million would storing them as ints by multiplying them by 100 (2 decimal places) still be optimal?

As DocBrown suggested, I should store the doubles as ints (multiply by 100 because they have 2 decimal places) and then combine the 5 different ints (4 doubles (see above) and 1 enum (value:1-5)) into a key for the LUT.

How to do this such that I will have a unique value for each combination of my 5 input variables (the 5 ints) AND this method is open to expansion of each of the input variables, i.e. should I need to expand the double C's combinations to 70 instead of 50 I will need unique key values for the new entries that are result of the expanded number of total combinations of the input variables.

Answer 1

Doubles with 2 decimal places can easily be stored in an integer (just multiply each one by 100). If you map your 5 input variables to an index from 0 to 200 (or 1-5 for the fifth), you will need at most 5 bytes to store them all. For your output records, from what you write I estimate you will need around 4 bytes per value, maybe 8 for the last one, giving you a total of 29*4+8=124 bytes. Add the former 5 bytes, and add some internal overhead, you will need roundabout 150 bytes per record in total. Multiply this with 150 million records shows that you will need at least 22GB to hold the full data in memory. And that won't differ if you are using a hash structure or a tree structure.

If you have a 64 bit machine for your processing at hand with so much main memory, you can try to handle this without a database, but if you are using a typical standard PC, I would tend to use a database for that (at least, nowadays, in 5 or ten years when the "standard PC" comes with >64GB RAM the situation may be different). And don't use the doubles directly for indexing, map them first to integers in the 0,...,200 interval, combine them into a 5 byte integer and use that value as an indexed key.

Answer 2

Ideally a LUT should be quick to reference but can be slow to generate. Unfortunately I don't think your scenario is going to be quick to reference. Given five different input variables, this would require some sort of hash mechanism that guarantees a unique value for every possible combination. This is not going to be very quick to generate.

I think looking into tree based structures will be your best bet.

Perhaps a "tree" where each of your input elements is used as a index into a smaller LUT which then references another LUT....etc, until you reach the final LUT giving you your output data.

From your inputs description it looks like you could have as many as 8 billion records (200^4)*5.

Answer 3

I'm assuming here that the problem is read-only and that if something changes you can stop and programmatically rebuild your index. First, I would look at coding your input space as a series of permutations, just like Doc Brown is talking about. However, I would look at changing the output to be an address. This has a few advantages. If the output length varies, this makes for fixed widths on lookups because address width doesn't vary. It also allows the output to be pushed to secondary storage like disk etc. so that the OS can handle caching for lookups. It does add a layer of indirection, which is not so good in some ways but if your output is ever repeated it can also allow you to point at the same answer. So let's look at some numbers. First, your input space has something like 200*200*50*120 = 240,000,000 entries in the full space, not just the used space. Second, your output space is roughly 27,000,000 * 30 * 8 (for a full double - but this could maybe get better), which gives us 6.48 GB of data. This can be addressed with room to spare by 5 bytes. So now we come to a sticking point: trees? arrays? Trees are great for many things and depending on your usage pattern may be great. But it's really hard to beat arrays if they fit in memory. If we use trees, we only need to store entries for the actually used 27 million inputs. However, the hidden cost of trees is the multiple lookups for layers of indirection. (But B-Trees may be a good option if you don't like what I say next...) But if we use arrays for speed, we need to store pointers to our data for all 240 million entries. BUT to be fair, 5 bytes * 240 million gives ~1.2GB which can fit into memory on even a modest machine for your main lookup to secondary storage.

So the full system would look like this.

To build the lookup table, do the following:

1) Scan all your data and create lists of each unique input for each variable, say maybe 200 for A, 198 for B, etc.

2) For each input variable, build a dictionary that takes the input to an increasing int. These dictionaries should be the fastest data structures you can come up with for small lookups. Given the small number of values, a sorted array using binary search may not be a bad choice. Using this versus a tree may allow for better cache locality, but you may want to conduct some experiments on this.

3) Create your lookup array and output file. For each input, drop in the current output file offset (5 bytes) and append your output to the output file. The key is just created by doing something like this (A value)*(number of B's*number of C's*number of D's) + (B value)*(number of C's * number of D's) + (C value)(number of D's) + (D value)

To do a lookup:

1) Calculate the key from the inputs as explained above by using the small dictionaries for each individual input variable and then computing the key through math.

2) Index into the array.

3) Load object from disk/secondary storage. If you can fit it into RAM, good for you. If not, we'll just have to trust the OS disk cache.

I'm sure there's a more clever answer out there for sure. But what I like about this approach is that I could code it up quickly and get it to run on my box at home without a server. That secondary storage can be whatever is available to you, and that's worth a lot.

Also, given the type of work being done here, I would definitely recommend an unmanaged language over a managed language for allowing fast unsafe memory access - unmanaged languages are not the answer for all problems but it seems like a good fit here. Similarly, the problem seems specialized and constrained enough that a database is probably not the best fit, since with a little tweaking we can more or less guarantee that at least the primary lookup can fit in RAM.