Changeset 1021

Timestamp:

03/01/09 17:42:38 (3 years ago)

Author:

gcosmin

Message:

Optimized longest common subsequence algorithm with O(N + M) memory and wrote it in C++
​http://reviewboard.infoarena.ro/r/70/

Location:

trunk

Files:

• common/diff.php (modified) (1 diff)
• common/lcs.cpp (added)
• scripts/setup (modified) (3 diffs)

trunk/common/diff.php

@@ -88 +88 @@
 
 // compute longest common subsequence using dynamic programming
-// FIXME: both time and memory complexity can be reduced
 function lcs($a, $b) {
-    $N = mb_strlen($a);
-    $M = mb_strlen($b);
-    $C = array(array(2), array($M+1));
+    $descriptorspec = array(
+        0 => array("pipe", "r"),
+        1 => array("pipe", "w"),
+        2 => array("pipe", "w"),
+    );
 
-    for ($i = 0; $i < 2; ++$i)
-        for ($j = 0; $j <= $M; ++$j)
-            $C[$i][$j] = "";
-    
-    for ($i = 1; $i <= $N; ++$i) {
-        for ($j = 1; $j <= $M; ++$j) {
-            if (mb_substr($a, $i-1, 1) == mb_substr($b, $j-1, 1)) {
-                $C[$i%2][$j] = $C[($i-1)%2][$j-1].mb_substr($a, $i-1, 1);
-            } else if (mb_strlen($C[($i-1)%2][$j]) > mb_strlen($C[$i%2][$j-1])) {
-                $C[$i%2][$j] = $C[($i-1)%2][$j];
-            } else {
-                $C[$i%2][$j] = $C[$i%2][$j-1];
-            }
-        }
+    // run lcs process
+    $process = proc_open("iconv -f utf8 -t utf32 | " . IA_ROOT_DIR.
+        "/common/lcs" . " | iconv -f utf32 -t utf8", $descriptorspec, $pipes);
+    log_assert(is_resource($process), "Could not create process.");
+
+    // feed script to pipe
+    list($lcs_in, $lcs_out, $lcs_err) = $pipes;
+
+    fwrite($lcs_in, $a."\n");
+    fwrite($lcs_in, $b."\n");
+    fclose($lcs_in);
+
+    $result = fread($lcs_out, 10000);
+    fclose($lcs_out);
+
+    // check for errors
+    $errors = fread($lcs_err, 1000);
+    if ($errors) {
+        log_error($errors);
     }
-    return $C[$N%2][$M];
+    fclose($lcs_err);
+
+    // clean-up
+    proc_close($process);
+
+    $result = trim($result, "\n");
+
+    return $result;
 }
 

trunk/scripts/setup

@@ -83 +83 @@
         chgrp($dstfile, getmygid());
     }
+}
+
+// Compiles longest common substrig written in c++
+function compile_lcs($IA_ROOT_DIR)
+{
+    $command = "g++ " . $IA_ROOT_DIR . "common/lcs.cpp -O2 -static -o " .
+        $IA_ROOT_DIR . "common/lcs";
+
+    $last_line = system($command, $ret_val);
+
+    if ($ret_val) { // check for errors
+        print("\nWARNING!!! There has been a problem when trying to compile a " .
+            "cpp source! Check your gcc/g++ installation then rerun " .
+            "the script.\nThis will not affect the setup except for " .
+            "comparing revisons, but you should take a look at this!\n\n");
+        return 0;
+    }
+
+    return 1;
 }
 
@@ -128 +147 @@
         $config_vars['IA_URL_PREFIX'], true, true);
 
+// Compile needed files
+compile_lcs($config_vars['IA_ROOT_DIR']);
+
 // Database configuration here.
 while (true) {
@@ -246 +268 @@
 print("FIXME: forum is not completely functional\n");
 print("FIXME: eval won't work, but it doesn't matter.\n");
+
+?>