mm.c (rate): Simplify the algorithm.

Now we don't need to take a copy of the code histogram, and there's less
conditional stuff to do in the loop.  This gives an overall 25%
performance improvement, as measured by running `time mm -a 4 8'.

diff --git a/mm.c b/mm.c
index 16f635bc61caca8491ce1f3720379b5c68383dd0..2176e338e722361e826542d6abf44a4e8ac7e6cf 100644 (file)
--- a/mm.c
+++ b/mm.c
@@ -70,12 +70,10 @@ typedef struct mm {
  *   * %$t$% is temporary work space for the rating function.
  *
  * The rating function works by taking a pass over the guess, computing a
- * count table %$v'$%; but for each guess symbol which matches the
- * corresponding code symbol, decrementing the count %$v_i$% for that symbol
- * (in a temporary copy of the table %$v$%).  The black count is then the
- * number of such matches, and the white count is given by
+ * count table %$v'$%.  The black count %$b$% is then the number of such
+ * matches, and the white count is given by
  *
- *   %$w = \displaystyle \sum_{0<i\le n} \min(v_i, v'_i).$%
+ *   %$w = \displaystyle \sum_{0<i\le n} \min(v_i, v'_i) - b.$%
  *
  * Thus, the work is %$O(k + n)$%, rather than the %$O(k^2)$% for a
  * %%na\"\i{}ve%% implementation.
@@ -94,7 +92,7 @@ static ratectx *rate_alloc(const mm *m)
   dig *v;
 
   r = CREATE(ratectx);
-  v = xmalloc((3 * m->n + m->k) * sizeof(dig));
+  v = xmalloc((2 * m->n + m->k) * sizeof(dig));
   r->m = *m;
   r->v = v;
   r->s = r->v + m->n;
@@ -125,24 +123,18 @@ static void rate(const ratectx *r, const dig *g, unsigned  *b, unsigned *w)
   unsigned i;
   unsigned k = r->m.k, n = r->m.n;
   dig *v = r->t;
-  dig *vv = v + n;
   const dig *s = r->s;
   unsigned bb = 0, ww = 0;
 
   memset(v, 0, n * sizeof(dig));
-  memcpy(vv, r->v, n * sizeof(dig));
   for (i = 0; i < k; i++) {
-    if (g[i] != s[i])
-      v[g[i]]++;
-    else {
-      vv[g[i]]--;
-      bb++;
-    }
+    if (g[i] == s[i]) bb++;
+    v[g[i]]++;
   }
   for (i = 0; i < n; i++)
-    ww += v[i] < vv[i] ? v[i] : vv[i];
+    ww += v[i] < r->v[i] ? v[i] : r->v[i];
   *b = bb;
-  *w = ww;
+  *w = ww - bb;
 }
 
 static void rate_free(ratectx *r) { xfree(r->v); DESTROY(r); }