Sign in to follow this  
Storyyeller

finding the nearest days in a map?

Recommended Posts

I have a map that represents a player's ratings on certain days. I am trying to create a function to get the players rating on a specific day that behaves like this If the map is empty return 0 If the requested day is in the map, return the associated rating Otherwise, Find the two closest days in the map and return a value that is linearly interpolated between the two associated ratings. If the requested day is earlier then all days in the map, return the rating from the earliest day If the requested day is later then all days in the map, return the rating from the latest day However, I'm having trouble creating this function. Here is what I have come up with so far, but I'm not sure how to find the next highest day.
typedef boost::gregorian::date day;
double Player::GetInterpolatedRating( day d)
{
    if (history.size() == 0)
    {
        return 0;
    }

    std::map<day, TimePoint>::iterator lower = lower_bound(history.begin(), history.end(), d);

    if (lower == d)
    {
        return history[d].rating;
    }

    //???????????????

}



history is a member variable of player std::map<day, TimePoint> history; TimePoint is a struct containing the rating

Share this post


Link to post
Share on other sites
To do this computationally efficiently, you may need to use up some extra memory. Namely, an array and a map.

The first map is your standard "Date to Rank" map. The array is just a sorted list of the dates in your map (i.e. the key's of your map sorted in ascending order). First check the map to see if the date is in it. If it isn't, do a binary search of your array. Ultimately, you will land on two days that your date is between, and you can get their values in the map.

This is not a very pretty solution, however, if you will be adding dates willy nilly into the array. I am assuming that you will most likely be pushing new dates onto the end...

Share this post


Link to post
Share on other sites
Is it really worth it to add a sorted array here? How bad can a linear search be?
After all, even if a player plays a game every other day for over five years, that's still only 1000 odd entries.

That's like what? .01 seconds? It doesn't seem like it'd make a noticeable difference either way.

Share this post


Link to post
Share on other sites
Didn't check your code too well. Lower_bound performs a binary search on a sorted container anyway. If lower != d, can't you just increment the iterator to get the next highest element, which should be one above?

The issue is, lower_bound is supposed to take a sorted container anyway -- so you can either get the keys and sort them each time, or keep a pre-sorted vector and use lower_bound...

Share this post


Link to post
Share on other sites
From what I've read,
Maps automatically sort everything anyway.
However, random access is impossible, so binary search takes linear time. Although as I mentioned, I don't think that's a problem.

I just realized that I had been forgetting that iterators can be incremented!

Ok here's my revised code


double Player::GetInterpolatedRating( day d) const
{
if (history.size() == 0)
{
return 0;
}

std::map<day, TimePoint>::const_iterator lower = lower_bound(history.begin(), history.end(), d);

if (lower->first == d)
{
return lower->second.rating;
}

if (d <= history.begin()->first)
{
return history.begin()->second.rating;
}

if (d >= (--history.end())->first)
{
return (--history.end())->second.rating;
}

std::map<day, TimePoint>::const_iterator upper = lower;
upper++;

double r1 = lower->second.rating;
double r2 = upper->second.rating;

int numerator = (d - lower->first).days();
int denominator = (upper->first - lower->first).days();

return r1 + (r2-r1) * (double) (numerator/denominator);
}



It's working except that lower_bound is complaining about some sort of missing operator.

C:\Program Files\CodeBlocks\MinGW\bin\..\lib\gcc\mingw32\3.4.5\..\..\..\..\include\c++\3.4.5\bits\stl_algo.h||In function `_ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = std::_Rb_tree_const_iterator<std::pair<const day, TimePoint> >, _Tp = day]':|
C:\ActiveProjects\Expy\players.cpp|31|instantiated from here|
C:\Program Files\CodeBlocks\MinGW\bin\..\lib\gcc\mingw32\3.4.5\..\..\..\..\include\c++\3.4.5\bits\stl_algo.h|2634|error: no match for 'operator<' in '(&__middle)->std::_Rb_tree_const_iterator<_Tp>::operator* [with _Tp = std::pair<const day, TimePoint>]() < __val'|
K:\CodeBlocksI\Boost\boost\detail\shared_count.hpp|377|note: candidates are: bool boost::detail::operator<(const boost::detail::weak_count&, const boost::detail::weak_count&)|
K:\CodeBlocksI\Boost\boost\detail\shared_count.hpp|275|note: bool boost::detail::operator<(const boost::detail::shared_count&, const boost::detail::shared_count&)|
||=== Build finished: 1 errors, 0 warnings ===|


[Edited by - Storyyeller on June 22, 2009 4:11:09 PM]

Share this post


Link to post
Share on other sites
Why are you using the non-member version of lower_bound() instead of std::map::lower_bound()?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this