Back to For Beginners

finding the nearest days in a map?

For Beginners

Started by Storyyeller June 22, 2009 03:17 PM

5 comments, last by Storyyeller 14 years, 9 months ago

Storyyeller

215

Author

June 22, 2009 03:17 PM

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

I trust exceptions about as far as I can throw them.

choffstein

1,090

June 22, 2009 03:24 PM

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...

Storyyeller

215

Author

June 22, 2009 03:46 PM

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.

I trust exceptions about as far as I can throw them.

choffstein

1,090

June 22, 2009 03:53 PM

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...

Storyyeller

215

Author

June 22, 2009 04:11 PM

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]

I trust exceptions about as far as I can throw them.