進・日進月歩

IT, Jazz, study, engineering, すべての真実とクリエイティビティのために

Archive for October, 2009

o(np)のdiffアルゴリズム（貼っただけ

  • Author: harajune
  • Filed under: 雑記
Monday
Oct 12,2009

o(np)のdiffアルゴリズムを作りました。
元ネタはこの辺。
An O(NP) sequence comparison algorithm

なんで車輪の再発明したかというと、既存のライブラリだと挙動がわからない上に、使い勝手がいまいちだからです。
自分で全部書けば、自由自在（ぉ
とりあえずリファクタリングの余地は多々ある感じですが。

一般的な意味でのdiffと違うところと言えば、追加／削除のみしか考えておらず、「置換」がありません。
けど、アルゴリズム上「置換」に当たる場合は「追加→削除」または「削除→追加」のいずれかの順番でSESの中に現れるので、その場合を「置換」と処理すればよいかと思います。

使い方とかは暇があったら書く。

このあたりを参考にさせてもらいました。日本語の解説ではこれが一番わかりがよく正確だと思います。
diff(1)

PLAIN TEXT
CODE:
  1. <?php
  2. class DiffModel{
  3.     private $flip = false;
  4.     private $arr1 = null;
  5.     private $arr2 = null;
  6.     private $size1 = null;
  7.     private $size2 = null;
  8.     private $ses = null;
  9.  
  10.     private $patharr=null;
  11.     const SAME=0;
  12.     const ADD=1;
  13.     const DEL=2;
  14.  
  15.     public function __construct($article1="", $article2=""){
  16.         if(is_array($article1) and is_array($article2)){
  17.             $this->setArray($article1, $article2);
  18.         }else{
  19.             $this->setArticles($article1, $article2);
  20.         }
  21.     }
  22.  
  23.     public function setArticles($article1, $article2){
  24.         if(strlen($article1)> strlen($article2)){
  25.             $this->arr1 = empty($article1) ? array() : mb_str_split($article1);
  26.             $this->arr2 = empty($article2) ? array() : mb_str_split($article2);
  27.  
  28.             $this->size1 = count($this->arr1);
  29.             $this->size2 = count($this->arr2);
  30.             $this->flip = true;
  31.         }else{
  32.             $this->arr1 = empty($article2) ? array() : mb_str_split($article2);
  33.             $this->arr2 = empty($article1) ? array() : mb_str_split($article1);
  34.  
  35.             $this->size1 = count($this->arr1);
  36.             $this->size2 = count($this->arr2);
  37.             $this->flip = false;
  38.         }
  39.     }
  40.  
  41.     public function setArray($arr1, $arr2){
  42.         if(count($arr1)> count($arr2)){
  43.             $this->arr1 = $arr1;
  44.             $this->arr2 = $arr2;
  45.  
  46.             $this->size1 = count($this->arr1);
  47.             $this->size2 = count($this->arr2);
  48.             $this->flip = true;
  49.         }else{
  50.             $this->arr1 = $arr2;
  51.             $this->arr2 = $arr1;
  52.  
  53.             $this->size1 = count($this->arr1);
  54.             $this->size2 = count($this->arr2);
  55.             $this->flip = false;
  56.         }
  57.  
  58.     }
  59.  
  60.     public function diff(){
  61.  
  62.         $offset = $this->size2 + 1;
  63.  
  64.         $this->patharr = array();
  65.  
  66.         $fp = array_fill(0, $this->size1 + $this->size2 + 3, -1);
  67.         $delta = $this->size1 - $this->size2;
  68.  
  69.         $p=0;
  70.         for(; $fp[$delta + $offset] <$this->size1; $p++){
  71.             for($k = -$p; $k <$delta; $k++){
  72.                 $fp[$k + $offset] = $this->snake($k, $offset, $fp);
  73.             }
  74.  
  75.             for($k = $delta + $p; $k>= $delta; $k--){
  76.                 $fp[$k + $offset] = $this->snake($k, $offset, $fp);
  77.             }
  78.  
  79.         }
  80.  
  81.         return $delta + 2*($p - 1);
  82.     }
  83.  
  84.     public function getDiff(){
  85.         $ind = $this->size2 + $this->size1*($this->size2+1);
  86.         $item = array(-1, $this->size2, $this->size1);
  87.         $this->ses = array();
  88.         do{
  89.             switch($this->patharr[$ind][0]){
  90.             case (self::ADD):
  91.                 if($item[0] != $this->patharr[$ind][0]){
  92.                     $this->ses[] = array($this->flip ? self::ADD : self::DEL, $this->patharr[$ind][1], $item[1] - $this->patharr[$ind][1]);
  93.                 }else{
  94.                     $this->ses[count($this->ses)-1][1] = $this->patharr[$ind][1];
  95.                     $this->ses[count($this->ses)-1][2] += $item[1] - $this->patharr[$ind][1];
  96.                 }
  97.                 //echo sprintf("add %3d-%3d %s\n", $this->patharr[$ind][1], $item[1], mb_substr($this->article2, $this->patharr[$ind][1], $item[1] - $this->patharr[$ind][1], "utf-8"));
  98.                 break;
  99.             case (self::DEL):
  100.                 if($item[0] != $this->patharr[$ind][0]){
  101.                     $this->ses[] = array($this->flip ? self::DEL : self::ADD, $this->patharr[$ind][2], $item[2] - $this->patharr[$ind][2]);
  102.                 }else{
  103.                     $this->ses[count($this->ses)-1][1] = $this->patharr[$ind][2];
  104.                     $this->ses[count($this->ses)-1][2] += $item[2] - $this->patharr[$ind][2];
  105.                 }
  106.                 //echo sprintf("del %3d-%3d %s\n", $this->patharr[$ind][2], $item[2], mb_substr($this->article1, $this->patharr[$ind][2], $item[2] - $this->patharr[$ind][2], "utf-8"));
  107.                 break;
  108.             case (self::SAME):
  109.                 if($item[0] != $this->patharr[$ind][0]){
  110.                     $this->ses[] = array(self::SAME, $this->patharr[$ind][1], $item[1] - $this->patharr[$ind][1]);
  111.                 }else{
  112.                     $this->ses[count($this->ses)-1][1] = $this->patharr[$ind][1];
  113.                     $this->ses[count($this->ses)-1][2] += $item[1] - $this->patharr[$ind][1];
  114.                 }
  115.                 //echo sprintf("sam %3d-%3d %s\n", $this->patharr[$ind][1], $item[1], mb_substr($this->article2, $this->patharr[$ind][1], $item[1] - $this->patharr[$ind][1], "utf-8"));
  116.                 break;
  117.             }
  118.  
  119.             $item = $this->patharr[$ind];
  120.             $ind = $this->patharr[$ind][1] + $this->patharr[$ind][2]*($this->size2+1);
  121.  
  122.         }while($ind> 0);
  123.  
  124.         $this->ses = array_reverse($this->ses);
  125.         return $this->ses;
  126.  
  127.     }
  128.  
  129.     private function snake($k, $offset, &$fp){
  130.         $y=0;
  131.         if($fp[$k-1 + $offset] + 1> $fp[$k+1+$offset]){
  132.             $y = $fp[$k-1 + $offset] + 1;
  133.             //$this->patharr[($y-$k) + $y*($this->size2+1)] = array($y-$k,$y-1);
  134.             $this->patharr[($y-$k) + $y*($this->size2+1)] = array(self::DEL, $y-$k,$y-1);
  135.         }else{
  136.             $y = $fp[$k+1 + $offset];
  137.             $this->patharr[($y-$k) + $y*($this->size2+1)] = array(self::ADD, $y-$k-1, $y);
  138.         }
  139.  
  140.         $x = $y-$k;
  141.         $sx = $x;
  142.         $sy = $y;
  143.  
  144.         while($x <$this->size2 and $y <$this->size1 and $this->arr2[$x] == $this->arr1[$y]){
  145.             $x++;
  146.             $y++;
  147.         }
  148.  
  149.         if(!($x == $sx and $y == $sy) )$this->patharr[$x+$y*($this->size2+1)] = array(self::SAME, $sx,$sy);
  150.  
  151.         return $y;
  152.     }
  153.  
  154. }
  155. ?>

  • 1 Comment

    • JavaScriptで文字列型から整数型への変換速度比較(追試

    • Author: harajune
    • Filed under: 雑記
    Wednesday
    Oct 7,2009

    JavaScriptで文字列型から整数型への変換速度比較
    http://kur.jp/2009/10/06/stringtoint-by-javascript/
    というのがあって、なんかコードを見てたらなんか思うところがあったので追試してみた。
    結果から言うと、だいたい傾向は一緒だった。IE用の回避コードを入れてみて気づいたけど、実行順序によって速さが変わるかもしれない。(一度読み込んだ関数は二回目は若干速い？

    PLAIN TEXT
    CODE:
    1. <script type="text/javascript">
    2.     var randomnums = new Array(1000000);
    3.     for(i=0; i<1000000; i++){
    4.         randomnums[i] = String(Math.round(Math.random() * 100));
    5.     }
    6.  
    7. function warmup(){
    8.     for(i=0; i<1000000; i++){
    9.         randomnums[i];
    10.     }
    11. }
    12. function useSub(){
    13.     var startTime = new Date();
    14.     for(var i = 0; i <1000000;i++){
    15.         randomnums[i] - 0;
    16.     }
    17.     document.write(new Date() - startTime);
    18. }
    19. function useDiv(){
    20.     var startTime = new Date();
    21.  
    22.     for(var i = 0; i <1000000;i++){
    23.         randomnums[i] / 1;
    24.     }
    25.     document.write(new Date() - startTime);
    26. }
    27. function useparseInt(){
    28.     var startTime = new Date();
    29.  
    30.     for(var i = 0; i <1000000;i++){
    31.         parseInt(randomnums[i],10);
    32.     }
    33.     document.write(new Date() - startTime);
    34. }
    35. function useNumber(){
    36.     var startTime = new Date();
    37.  
    38.     for(var i = 0; i <1000000;i++){
    39.         Number(randomnums[i]);
    40.     }
    41.     document.write(new Date() - startTime);
    42. }
    43. //IEがおそすぎて変なalertを出すので１回分はダミー
    44. warmup();
    45. useSub();
    46. document.write("<br />");
    47. warmup();
    48. useSub();
    49. document.write("<br />");
    50. warmup();
    51. useDiv();
    52. document.write("<br />");
    53. warmup();
    54. useparseInt();
    55. document.write("<br />");
    56. warmup();
    57. useNumber();
    58. </script>

    結果はこちら

    firefox
6
6
6
119
274 

IE
801
781
851
2003
1553 

chrome
311
292
299
135
234
  • 2 Comments

    • about me

    原田　惇

    応用数学や統計、ITなどを利用していろんなことをしています。
    自己紹介はこちら

    adsense

    amazonお勧め

    Tags

    ともだち達

    リンク

    Categories

    Recent Posts


    Recent Comments


    Twitter



    Archives


    Meta


    Copyright © 2007 - 進・日進月歩 - is proudly powered by WordPress
    Smashing Theme is created by: Design Disease brought to you by Smashingmagazine.com