Store a vector of all matches; 90% of the time was spent in map lookup.

diff --git a/bayeswf.cpp b/bayeswf.cpp
index 62fc9c8b2895b42c7df81ea2dd31cf1936e7c2ea..9365a1068ea460efb41e0008ef8543e0e5dd9053 100644 (file)
--- a/bayeswf.cpp
+++ b/bayeswf.cpp
@@ -33,11 +33,12 @@ float prior_sigma = 70.0f;
  */
 
 struct match {
-       int other_player;
+       int player, other_player;
        int margin;
        float weight;
 };
 map<int, vector<match> > matches_for_player;
+vector<match> all_matches;
 
 void dump_scores(const vector<string> &players, const float *mu, const float *sigma, int num_players)
 {
@@ -94,26 +95,19 @@ void update_mu(float *mu, float *sigma, int player_num, const vector<match> &mat
 
 void dump_raw(const float *mu, const float *sigma, int num_players)
 {
-       for (int i = 0; i < num_players; ++i) {
-               for (unsigned j = 0; j < matches_for_player[i].size(); ++j) {
-                       const match& m = matches_for_player[i][j];
-
-                       // Only count each match once.
-                       if (m.other_player <= i) {
-                               continue;
-                       }
-
-                       float mu1 = mu[i];
-                       float mu2 = mu[m.other_player];
-                       float sigma1 = sigma[i];
-                       float sigma2 = sigma[m.other_player];
-                       float sigma = sqrt(sigma1 * sigma1 + sigma2 * sigma2);
-                       float mu = mu1 - mu2;
-                       float x = m.margin;
-                       float w = m.weight;
-
-                       printf("%f %f\n", (x - mu) / sigma, w);
-               }
+       for (unsigned i = 0; i < all_matches.size(); ++i) {
+               const match& m = all_matches[i];
+
+               float mu1 = mu[m.player];
+               float mu2 = mu[m.other_player];
+               float sigma1 = sigma[m.player];
+               float sigma2 = sigma[m.other_player];
+               float sigma = sqrt(sigma1 * sigma1 + sigma2 * sigma2);
+               float mu = mu1 - mu2;
+               float x = m.margin;
+               float w = m.weight;
+
+               printf("%f %f\n", (x - mu) / sigma, w);
        }
 }
 
@@ -159,24 +153,17 @@ void update_sigma(float *mu, float *sigma, int player_num, const vector<match> &
 void update_global_sigma(float *mu, float *sigma, int num_players)
 {
        float nom = 0.0f, denom = 0.0f;
-       for (int i = 0; i < num_players; ++i) {
-               for (unsigned j = 0; j < matches_for_player[i].size(); ++j) {
-                       const match& m = matches_for_player[i][j];
-
-                       // Only count each match once.
-                       if (m.other_player <= i) {
-                               continue;
-                       }
-
-                       float mu1 = mu[i];
-                       float mu2 = mu[m.other_player];
-                       float mu = mu1 - mu2;
-                       float x = m.margin;
-                       float w = m.weight;
-
-                       nom += w * ((x - mu) * (x - mu));
-                       denom += w;
-               }
+       for (unsigned i = 0; i < all_matches.size(); ++i) {
+               const match& m = all_matches[i];
+
+               float mu1 = mu[m.player];
+               float mu2 = mu[m.other_player];
+               float mu = mu1 - mu2;
+               float x = m.margin;
+               float w = m.weight;
+
+               nom += w * ((x - mu) * (x - mu));
+               denom += w;
        }
 
        float best_sigma = sqrt(nom / denom) / sqrt(2.0f);  // Divide evenly between the two players.
@@ -223,26 +210,19 @@ float compute_total_logl(float *mu, float *sigma, int num_players)
        }
 
        // Matches.
-       for (int i = 0; i < num_players; ++i) {
-               for (unsigned j = 0; j < matches_for_player[i].size(); ++j) {
-                       const match& m = matches_for_player[i][j];
-
-                       // Only count each match once.
-                       if (m.other_player <= i) {
-                               continue;
-                       }
-
-                       float mu1 = mu[i];
-                       float mu2 = mu[m.other_player];
-                       float sigma1 = sigma[i];
-                       float sigma2 = sigma[m.other_player];
-                       float sigma = sqrt(sigma1 * sigma1 + sigma2 * sigma2);
-                       float mu = mu1 - mu2;
-                       float x = m.margin;
-                       float w = m.weight;
-
-                       total_logl += w * compute_logl((x - mu) / sigma);
-               }
+       for (unsigned i = 0; i < all_matches.size(); ++i) {
+               const match& m = all_matches[i];
+
+               float mu1 = mu[m.player];
+               float mu2 = mu[m.other_player];
+               float sigma1 = sigma[m.player];
+               float sigma2 = sigma[m.other_player];
+               float sigma = sqrt(sigma1 * sigma1 + sigma2 * sigma2);
+               float mu = mu1 - mu2;
+               float x = m.margin;
+               float w = m.weight;
+
+               total_logl += w * compute_logl((x - mu) / sigma);
        }
 
        return total_logl;
@@ -335,16 +315,20 @@ int main(int argc, char **argv)
                }
 
                match m1;
+               m1.player = player_map[pl1];
                m1.other_player = player_map[pl2];
                m1.margin = score1 - score2;
                m1.weight = weight;
                matches_for_player[player_map[pl1]].push_back(m1);
 
                match m2;
+               m2.player = player_map[pl2];
                m2.other_player = player_map[pl1];
                m2.margin = score2 - score1;
                m2.weight = weight;
                matches_for_player[player_map[pl2]].push_back(m2);
+
+               all_matches.push_back(m1);
        }
 
        float mu[MAX_PLAYERS];