From: Steinar H. Gunderson <sgunderson@bigfoot.com>
Date: Sun, 18 Mar 2012 21:20:54 +0000 (+0100)
Subject: Store a vector of all matches; 90% of the time was spent in map lookup.
X-Git-Url: https://git.sesse.net/?p=wloh;a=commitdiff_plain;h=85c15ca0ba6e416371abb36b0c1c63a4a02e64fd

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

diff --git a/bayeswf.cpp b/bayeswf.cpp
index 62fc9c8..9365a10 100644
--- 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];