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
  *   * %$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.
  *
  * 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);
   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;
   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;
   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));
   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++) {
   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++)
   }
   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;
   *b = bb;

-  *w = ww;
+  *w = ww - bb;

 }
 
 static void rate_free(ratectx *r) { xfree(r->v); DESTROY(r); }
 }
 
 static void rate_free(ratectx *r) { xfree(r->v); DESTROY(r); }