[Avida-SVN] r3381 - branches/goings/source/main

[goingssh at myxo.css.msu.edu]

Author: goingssh
Date: 2009-08-24 15:28:21 -0400 (Mon, 24 Aug 2009)
New Revision: 3381

Modified:
   branches/goings/source/main/cGenomeUtil.cc
Log:
Added Charles optimizations to edit distance to my code

Modified: branches/goings/source/main/cGenomeUtil.cc
===================================================================
--- branches/goings/source/main/cGenomeUtil.cc	2009-08-24 17:33:34 UTC (rev 3380)
+++ branches/goings/source/main/cGenomeUtil.cc	2009-08-24 19:28:21 UTC (rev 3381)
@@ -129,22 +129,34 @@
   if (!size1) return size2;
   if (!size2) return size1;
 
-  int * cur_row  = new int[size1];  // The row we are calculating
-  int * prev_row = new int[size1];  // The last row we calculater
+  // Count how many direct matches we have at the front and end.
+  int match_front = 0, match_end = 0;
+  while (gen1[match_front] == gen2[match_front]) match_front++;
+  while (gen1[size1 - match_end - 1] == gen2[size2 - match_end - 1]) match_end++;
 
+  // We can ignore the last match_end sites since we know they have distance zero.
+  const int test_size1 = size1 - match_front - match_end;
+  const int test_size2 = size2 - match_front - match_end;
+
+  if (test_size1 <= 0 || test_size2 <=0) return abs(test_size1 - test_size2);
+
+  // Now match everything else...
+  int * cur_row  = new int[test_size1];  // The row we are calculating
+  int * prev_row = new int[test_size1];  // The last row we calculated
+
   // Initialize the previous row to record the differece from nothing.
-  for (int i = 0; i < size1; i++)  prev_row[i] = i + 1;
+  for (int i = 0; i < test_size1; i++)  prev_row[i] = i + 1;
 
   // Loop through each subsequent character in the test code
-  for (int i = 0; i < size2; i++) {
+  for (int i = 0; i < test_size2; i++) {
     // Initialize the first entry in cur_row.
-    if (gen1[0] == gen2[i]) cur_row[0] = i;
+    if (gen1[match_front] == gen2[match_front + i]) cur_row[0] = i;
     else cur_row[0] = (i < prev_row[0]) ? (i+1) : (prev_row[0] + 1);
 
     // Move down the cur_row and fill it out.
-    for (int j = 1; j < size1; j++) {
+    for (int j = 1; j < test_size1; j++) {
       // If the values are equal, keep the value in the upper left.
-      if (gen1[j] == gen2[i]) {
+      if (gen1[match_front + j] == gen2[match_front + i]) {
 	cur_row[j] = prev_row[j-1];
       }
 
@@ -169,7 +181,7 @@
 
   // Now that we are done, return the bottom-right corner of the chart.
 
-  const int value = prev_row[size1 - 1];
+  const int value = prev_row[test_size1 - 1];
 
   delete [] cur_row;
   delete [] prev_row;