C ++ question
I have an integral algorithm based on location. (That is, the output of the algorithm is based on a curvilinear position, and each result is influenced by the values of the previous results).
To avoid recalculating every time, I would like to pre-compute with a given sample rate and then search and either return the pre-computed result (if I land directly on one) or interpolate between two adjacent results.
It would be trivial for me in F # or C #, but my C ++ is very rusty (and wasn't even that good).
Is the card the correct design to use? And could you kindly give me an example of how I would do the search? (I'm thinking of pre-computation in milimetres, which means the key can be int, the value will be double).
UPDATE OK, maybe I need a sorted dictionary. (Rolls with sleeves), pseudocode:
//Initialisation
fun MyFunction(int position, double previousresult) returns double {/*etc*/};
double lastresult = 0.0;
for(int s = startposition to endposition by sampledist)
{
lastresult = MyFunction(s, lastresult);
MapOrWhatever.Add(s, lastresult);
}
//Using for lookup
fun GetValueAtPosition(int position) returns double
{
CheckPositionIsInRangeElseException(position);
if(MapOrWhatever.ContainsKey(position))
return MapOrWhatever[position];
else
{
int i = 0;
//or possibly something clever with position % sampledist...
while(MapOrWhatever.Keys[i] < position) i+=sampledist;
return Interpolate(MapOrWhatever, i, i+sampledist, position);
}
}
Thinks ... maybe if I keep a persistent selector I would just use an array and index it ...
source to share
If you are considering a map, always consider the vector as well. For values that haven't changed much (or even haven't been changed at all) during application startup, pre-sorted std::vector< std::pair<Key,Value> >
(with O(N)
lookup) is more often than never faster to find than std::map<key,Value>
(with O(log N)
lookup) - despite all theory.
You need to try to measure.
source to share
std :: map is probably fine if speed isn't too critical. If the search speed is critical, you can try a vector as above, where you jump straight to the element you want (don't use binary search, as you can calculate the index from position). Something like:
vector<double> stored;
// store the values in the vector
double lastresult = 0.0;
for(int s = startposition, index = 0; s <= endposition; s+=sampledist, ++index)
{
lastresult = MyFunction(s, lastresult);
stored[index] = lastresult;
}
//then to lookup
double GetValueAtPosition(int position) returns double
{
int index = (position - startposition) / sampledist;
lower = stored[index];
upper = stored[index+1];
return interpolate(lower, upper, position);
}
source to share
see my comment but here is the documentation map
http://www.cplusplus.com/reference/stl/map/
and it's important to note that the other poster didn't mention that if you use [] to search for a key that doesn't exist on the map, the map will create an object so there is something in there.
edit: see the docs here for this information http://msdn.microsoft.com/en-us/library/fe72hft9%28VS.80%29.aspx
use find () instead, which returns an iterator. then check that iterator on map.end () and if it is equal then there was no match.
source to share
Refer: http://www.cplusplus.com/reference/stl/map/
You can use Map,
typedef std::map<int,const double> mapType;
Card performance:
map :: find complexity Logarithmic size.
Beware of the operator [] on the map
If x matches the key of an element in the container, the function returns a reference to its display value.
If x does not match the key of any item in the container, the function inserts a new item with that key and returns a reference to its display value. Note that this always increases the size of the map by one, even if no mapped value is assigned to the element (the element is created using its default constructor).
source to share
HASH_MAP is the best STL algoirthim for fast search than any other algorithms. But filling takes a little longer than a map or vector, and it also doesn't sort. Any search for a value requires constant time.
std::hash_map<int, double,> memo;
memo.insert(std::make_pair(5, 0.5));
memo.insert(std::make_pair(7,0.8));
.
.
.
hash_map<int,double>::iterator cur = memo.find(5);
hash_map<int,double>::iterator prev = cur;
hash_map<int,double>::iterator next = cur;
++next;
--prev;
Interpolate the current value with (* next) .second (), (* prev) .second ().
source to share