Re: Is there a faster way to fetch data from stl map?

There are a few ways you can optimize this; all depend on what exactly
you're doing with the data:

On Dec 26, 1:09 pm, Steve555 <foursh...@btinternet.com> wrote:

You say you load all data from a text file. What is the format of your
text file? You may consider changing the format a bit to optimize
things. For example, your inner loop above tries to map userID ->
MyUserClass* for 500,000 iterations for every user. This is a
bottleneck. You could save a lookup in a 500,000 entry map by simply
changing SongRating to this:

struct SongRating {
  MyUserClass *user;
  double rating;

};

Now you never have to look up the user ID in the map. However, this
means that when loading the text file, you have to load the user data
first, and then fill these structures as you load the song rating
data, doing the user map lookup there. Depending on how many times you
run through your huge loop below, doing the lookup (for every song and
rating) *once* when you load the file, rather than more than once,
will save you a lot of time.

Then, you can optimize your text file format to eliminate user map
lookups even on load. For example, say your text file is (for
example):

<songid> <song info...>
<songid> <song info...>
<songid> <song info...>
...
begin user <userid> <user info...>
  <songid> <rating>
  <songid> <rating>
  <songid> <rating>
  <songid> <rating>
  ...
end user

You are now explicitly associating SongRatings with users in your text
file. This eliminates any user map lookups on load at all. Loading is
simply this:

  1. Load all song information into songID -> song map.
  2. Load all user information, for each user:
     - Create MyUserClass and load user info into it.
     - Create entry in userID -> user map (if you even need to).
     - Create the SongRatings, and you already know exactly which
MyUserClass they're associated with!

The key there is grouping song ratings by user in the data file means
you always know precisely which user is associated with a song rating,
as you load it, without having to look that user up by ID.

That's the biggest optimization I can think of given how you say you
are using the data. It eliminates all userID -> MyUserClass lookups
entirely.

That is only one suggestion. Read on!

There is another possible optimization you can make. It appears that
you are examining every single rating for every single song, and
counting the total number of ratings made by a given user where
CheckUserSuitable(user) is true.

Well, CheckUserSuitable depends only on the user. It does not depend
on the song or the rating. So why iterate through all the songs and
ratings in an outer loop? You say the data never changes, so simply
count the number of SongRatings each user is associated with on load,
store that count in MyUserClass, and *all* you need to do to compute
'count' is iterate through your users and sum up all the counts for
users where CheckUserSuitable is true:

class MyUserClass {
public:
  int getNumberOfSongRatings () const;

};

You can store the users in a map, or even a vector, if it turns out
you don't need to actually do the userID -> MyUserClass lookups any
more; here I'll use a map:

map<long,MyUserClass *> users;
map<long,MyUserClass *>::const_iterator user;
int count = 0;

for (user = users.begin(); user != users.end(); ++ user)
  if (CheckUserSuitable((*user).second))
    count += (*user).second->getNumberOfSongRatings();

However, note that if you're counting the number of song ratings each
user has on load, you still may have to do some map lookups on load.
Well, if you change your text file format to the example I gave above,
counting song ratings per user becomes trivial -- since song ratings
are grouped per user, you do not need to do any map lookups at all to
count song ratings as you load them and store that count in
MyUserClass.

In general, it sounds like you have a huge amount of data, but you're
not storing it in a way that is optimal for what you're actually doing
with it. You need to look at what operations are the most time
consuming, and the figure out how to get rid of them: Looking up users
in the user map is time consuming, to get rid of it you can store the
MyUserClass* instead of the user ID in SongRating. To optimize that,
you can modify your text data format accordingly. Iterating over every
song and rating when CheckUserSuitable depends on neither is also time
consuming, you can do some "preprocessing" on load by counting the
number of song ratings per user to eliminate those loops from the
picture.

There are plenty of other easy optimizations you can make depending on
how you are accessing the data. For example, if you believe you will
frequently be looking up users with the same ID, then cache, say, the
last 10 userID -> MyUserClass* entries, and search your cache, hitting
the map only if...

read more =BB

struct SongRating {
  MyUserClass *user;
  double rating;

};