How can I improve my look-up table using std::map if TOLERANCE is introduced

user_6193296 0
Viewed 67

let's say I have a system to let people query their "social points" according to personal annual income, also I have a look-up table implemented with std::map, where <key, value> indicates <annual income, social points> to avoid repeated Points generation, take a look at this:

#include <iostream>
#include <map>

using namespace std;
class SocialSystem {
public:
  int queryMyPoints(int income) {
    if (cache.find(income) != cache.end()) {
      return cache[income];
    } else {
      cache[income] = PointsGenerator(income);
      return cache[income];
    }
  }
private:
  map<int, int> cache;
  int PointsGenerator(int income);
}

OK, very naive and simple, look-up and query are both O(1), very efficiently! But now memory issue has taken place, we can no longer afford so much memory for recording each income, so we introduce "TOLERANCE mechanism", namely, if TOL = 1%, and at the any specific given time, I have

// TOL = 1 %
cache[1000] = 67.3;
cache[1200] = 69.8;

That is to say, from now on, for all the number within 1000+-1% will use 67.3 as their points without calling PointsGenerator(), on the other words, the income range [990, 1010] will now be 67.3 points, while [1188, 1212] will be 69.8 points.

So the problem is, how can I ELEGANTLY and with lowest computing complexity to achieve this new mechanism? The stupidest way I can think of right now is to for-loop every single entry in the cache:

// pseudo code
int queryMyPoints(int income) {
  for (auto& it: cache) {
    int lower_bound = cache.first*0.99;
    int upper_bound = cache.first*1.01;
    if (income >= lower_bound && income <= upper_bound) {
      return cache.second;
    }
  }
  // cache miss handling
}

Oh this is so stupid, any better ideas to help me improve this please? Thanks a lot!

lookup-tables stdmap c++
2 Answers

You can use either the map's lower_bound or upper_bound methods which will work just like find(), if the key exists, or they will give you an iterator to either the previous or the next key in the map (with certain subtle details that I'll leave for you to discover on your own).

You'll just need to add a little bit more logic in order to inspect the iterator's key (or the previous one, or the next one), to see if it falls within your expectation. The end result's complexity would be still the same as find's.

user_39433120

I’d have a look at boost::interval_map, it seems to offer what you’re looking for. Wrapping std::map and fiddling with equal_range (or the binary search function family in general) can give similar effects and slightly more flexibility if that’s needed (aside from being just an interesting data structure to implement from purely educational standpoint). It really depends what you can and want to use in the end.

user_48853210
Related