425,763 Members | 1,641 Online Need help? Post your question and get tips & solutions from a community of 425,763 IT Pros & Developers. It's quick & easy.

# Better data structure?

 P: n/a I am in the process of converting some legacy code (written in C) to C++. The original data structure is used to hold a table of data (Gaussian distribution, some of you call it a "normal distribution"). There are two values of relevance: the "z" value (telling how many standard deviations away from the mean), and the "phi" value (cumulative probability). The data we are reading lists "z" values from -4.00 to +4.00, in 0.02 increments. As a result, the old data structure was an array declared as such: double probs; where probs[i] is the "z" value and probs[i] is the "phi" value. Later, we want to look up values in the table, and interpolate if the exact values are not there, as follows: double z, phi, tmp, ratio; int indexL, indexH; /* z is calculated here */ if (z <= -4.0) phi = probs; else if (z >= 4.0) phi = probs; else { tmp = (z + 4.0) / 0.02; indexL = floor(tmp); indexH = ceil(tmp); if (indexL == indexH) phi = probs[indexL]; else { ratio = (z - probs[indexL]) / 0.02; phi = probs[indexL] + ratio * (probs[indexH] - probs[indexL]); } } Pretty ugly! So, I am trying to use better data structures, but it doesn't seem to be a huge improvement: std::vector< std::pair > probs; // z is calculated here if (z <= -4.0) { phi = probs.front().second; } else if (z >= 4.0) { phi = probs.back().second; } else { double tmp = (z + 4.0) / 0.02; int indexL = static_cast(std::floor(tmp)); int indexH = static_cast(std::ceil(tmp)); if (indexL == indexH) { phi = probs[indexL].second; } else { double ratio = (z - probs[indexL].first) / 0.02; phi = probs[indexL].second + ratio * (probs[indexH].second - probs[indexL].second); } } Is there a better way to do this, maybe involving a std::map? However, my issue with the std::map<> is the floating-point inaccuracies when comparing the keys to see if the exact key is in the table. -- Marcus Kwok Oct 10 '05 #1
6 Replies

 P: n/a On Mon, 10 Oct 2005 20:02:10 +0000, Marcus Kwok wrote: double probs; struct Prob { double z; double phi; }; Prob probs; exact values are not there, as follows: double z, phi, tmp, ratio; int indexL, indexH; /* z is calculated here */ if (z <= -4.0) phi = probs; phi = probs.phi; else if (z >= 4.0) phi = probs; phi = probs.phi; else { tmp = (z + 4.0) / 0.02; indexL = floor(tmp); indexH = ceil(tmp); if (indexL == indexH) phi = probs[indexL]; phi = probs[indexL].phi; else { ratio = (z - probs[indexL]) / 0.02; ratio = (z - probs[indexL].z) / 0.02; phi = probs[indexL] + ratio * (probs[indexH] - probs[indexL]); phi = probs[indexL].phi + ratio * (probs[indexH].phi - probs[indexL].phi); } } } } - Jay Oct 10 '05 #2

 P: n/a Jay Nabonne wrote: On Mon, 10 Oct 2005 20:02:10 +0000, Marcus Kwok wrote: double probs; struct Prob { double z; double phi; }; Prob probs; exact values are not there, as follows: double z, phi, tmp, ratio; int indexL, indexH; /* z is calculated here */ if (z <= -4.0) phi = probs; phi = probs.phi; else if (z >= 4.0) phi = probs; phi = probs.phi; else { tmp = (z + 4.0) / 0.02; indexL = floor(tmp); indexH = ceil(tmp); if (indexL == indexH) phi = probs[indexL]; phi = probs[indexL].phi; else { ratio = (z - probs[indexL]) / 0.02; ratio = (z - probs[indexL].z) / 0.02; phi = probs[indexL] + ratio * (probs[indexH] - probs[indexL]); phi = probs[indexL].phi + ratio * (probs[indexH].phi - probs[indexL].phi); } } } } Thanks. However, I was trying to avoid basic arrays and instead use a std::vector<>, though maybe it will be clearer to create a struct (as you did) instead of using a std::pair<>. The main thing I am trying to do is clean up the calculation of the index, and seeing if the exact value is in the table. -- Marcus Kwok Oct 10 '05 #3

 P: n/a Marcus Kwok wrote: Jay Nabonne wrote: On Mon, 10 Oct 2005 20:02:10 +0000, Marcus Kwok wrote: double probs; struct Prob { double z; double phi; }; Prob probs; exact values are not there, as follows: double z, phi, tmp, ratio; int indexL, indexH; /* z is calculated here */ if (z <= -4.0) phi = probs; phi = probs.phi; else if (z >= 4.0) phi = probs; phi = probs.phi; else { tmp = (z + 4.0) / 0.02; indexL = floor(tmp); indexH = ceil(tmp); if (indexL == indexH) phi = probs[indexL]; phi = probs[indexL].phi; else { ratio = (z - probs[indexL]) / 0.02; ratio = (z - probs[indexL].z) / 0.02; phi = probs[indexL] + ratio * (probs[indexH] - probs[indexL]); phi = probs[indexL].phi + ratio * (probs[indexH].phi - probs[indexL].phi); } } } } Thanks. However, I was trying to avoid basic arrays and instead use a std::vector<>, though maybe it will be clearer to create a struct (as you did) instead of using a std::pair<>. The main thing I am trying to do is clean up the calculation of the index, and seeing if the exact value is in the table. I don't think there is much you can do. It already is short, is easy to understand. I really don't see a need to clean it up. The only thing I would do is: I would check if it ever happens that IndexL equals indexH. If it happens, how often does it happen? Due to round-off errors I don't think it is likely that the calculation of ( z + 4.0 ) / 0.02 equals a whole number when using double arithmetic. So there is no point in having an 'if' that is almost never taken. But I may be wrong, only a test could show that. -- Karl Heinz Buchegger kb******@gascad.at Oct 11 '05 #4

 P: n/a Marcus Kwok wrote: I am in the process of converting some legacy code (written in C) to C++. The original data structure is used to hold a table of data [is] Pretty ugly! So, I am trying to use better data structures... In a process of converting legacy code it is nod a good idea to change anything. There's russian saying, the "better" is an enemy of the "good". Oct 11 '05 #5

 P: n/a Marcus Kwok wrote: I am in the process of converting some legacy code (written in C) to C++. The original data structure is used to hold a table of data [is] Pretty ugly! So, I am trying to use better data structures... ma************@gmail.com wrote: In a process of converting legacy code it is nod a good idea to change anything. There's russian saying, the "better" is an enemy of the "good". I am reimplementing the entire program (it's not too terribly big) so I have full control over the entire code base, so it's not too big of a deal. Converting it to C++ has allowed me to not worry as much about resource management (since I use RAII a lot), leaving me more time to spot inefficiencies in the algorithms we're using. -- Marcus Kwok Oct 11 '05 #6

 P: n/a >> Jay Nabonne wrote: > On Mon, 10 Oct 2005 20:02:10 +0000, Marcus Kwok wrote: > >> double probs; > > struct Prob > { > double z; > double phi; > }; > > Prob probs; > >> >> exact values are not there, as follows: >> >> >> double z, phi, tmp, ratio; >> int indexL, indexH; >> >> /* z is calculated here */ >> >> if (z <= -4.0) >> phi = probs; > > phi = probs.phi; > >> else if (z >= 4.0) >> phi = probs; > > phi = probs.phi; > >> else { >> tmp = (z + 4.0) / 0.02; >> indexL = floor(tmp); >> indexH = ceil(tmp); >> if (indexL == indexH) >> phi = probs[indexL]; > > phi = probs[indexL].phi; > >> else { >> ratio = (z - probs[indexL]) / 0.02; > > ratio = (z - probs[indexL].z) / 0.02; > >> phi = probs[indexL] + ratio * (probs[indexH] - probs[indexL]); > > phi = probs[indexL].phi + ratio * (probs[indexH].phi - probs[indexL].phi); > >> } >> } >> } >> } Marcus Kwok wrote: Thanks. However, I was trying to avoid basic arrays and instead use a std::vector<>, though maybe it will be clearer to create a struct (as you did) instead of using a std::pair<>. The main thing I am trying to do is clean up the calculation of the index, and seeing if the exact value is in the table. Karl Heinz Buchegger wrote: I don't think there is much you can do. It already is short, is easy to understand. I really don't see a need to clean it up. The only thing I would do is: I would check if it ever happens that IndexL equals indexH. If it happens, how often does it happen? Due to round-off errors I don't think it is likely that the calculation of ( z + 4.0 ) / 0.02 equals a whole number when using double arithmetic. So there is no point in having an 'if' that is almost never taken. But I may be wrong, only a test could show that. Thanks for your response. I may go back and look at it later, but a separate, more urgent issue (completely unrelated to this) has come up in a different area of the code. Since it works now, I may leave it as is. -- Marcus Kwok Oct 11 '05 #7

### This discussion thread is closed

Replies have been disabled for this discussion. 