下記スクリプトの関数distanceSquaredPointsの実行速度を上げる方法はあるでしょうか。

2つの1次元配列の距離を求める関数です。
入力される配列は、少なくても一つの要素が入っています。
(コメントに配列初期化用のスクリプトを書いておきます)

私のPCでは、
finished in 0.17376899719238sec.
でした。

ポイントの指摘のみでも歓迎ですが、可能なら、変更前のスクリプトの時間と変更後の時間を計測して答えに記述していただけると嬉しいです。

(インデントするために空白を全角スペースに変換しています)
<?php
function distanceSquaredPoints($lhs, $rhs) {
 $result = 0;
 foreach($lhs as $i => $lv){
  $rv = 0;
  if(isset($rhs[$i])){
   $rv = $rhs[$i];
  }
  $result +=
   ($lv - $rv) *
   ($lv - $rv);
 }
 foreach($rhs as $i => $rv){
  if(isset($lhs[$i]) && $rv == 0){
   continue;
  }
  $lv = 0;
  $result +=
   ($lv - $rv) *
   ($lv - $rv);
 }
 return $result;
}
?>

回答の条件
  • 1人5回まで
  • 登録:2009/04/21 09:58:26
  • 終了:2009/04/22 00:05:22

ベストアンサー

id:kn1967 No.1

kn1967回答回数2915ベストアンサー獲得回数3012009/04/21 15:23:35

ポイント100pt
function distanceSquaredPoints($lhs, $rhs) {
    $result = 0;
    foreach($lhs as $i => $lv){
        if(isset($rhs[$i])){
            $result += ($lv - $rhs[$i]) ^ 2;
        } else {
            $result += $lv ^ 2;
        }
    }
    foreach($rhs as $i => $rv){
        if(!isset($lhs[$i])){
            $result += ($lv - $rv) ^ 2;
        }
    }
    return $result;
}

サーバ負荷をあまりかけられないので

600-1000 ではなく 60-100 という非常に小さな値で数回ではありますが

テストしたところ平均で 0.049 → 0.042 と差が出ましたのでお試しあれ。

id:kent013

kn1967さん、ありがとうございます。

こちらで、600-1000でテストしたところ

前 0.081698894500732sec

後 0.064887809753418sec

と速度が変わりました。

この関数はプロファイラで見てクリティカルなところでした。

少なくても66万回呼ばれますので、20%の速度アップはかなり嬉しいです!

2009/04/21 15:56:57
  • id:kent013
    (インデントするために空白を全角スペースに変換しています)
    <?php
    $m = 600;
    $n = 1000;
    $a = createRandomArray($m, $n);
    $b = createRandomArray($m, $n);

    $start = microtime(true);
    for($i = 0; $i < $m; $i++){
      distanceSquaredPoints($a[$i], $b[$i]);
    }
    echo "finished in " . (microtime(true) - $start) . "sec.\n";

    function createRandomArray($m, $n){
      $result = array();
      for($i = 0; $i < $m; $i++){
        if(isset($result[$i]) == false){
          $result[$i] = array();
        }
        for($j = 0; $j < $n; $j++){
          $v = rand(0, $n);
          if($v > (double)$n * 0.95){
            $result[$i][$j] = $n;
          }
        }
        if(empty($result[$i])){
          $result[$i][$j] = $i + 1;
        }
      }
      return $result;
    }

    function distanceSquaredPoints($lhs, $rhs) {
      $result = 0;
      foreach($lhs as $i => $lv){
        $rv = 0;
        if(isset($rhs[$i])){
          $rv = $rhs[$i];
        }
        $result +=
          ($lv - $rv) *
          ($lv - $rv);
      }
      foreach($rhs as $i => $rv){
        if(isset($lhs[$i]) && $rv == 0){
          continue;
        }
        $lv = 0;
        $result +=
          ($lv - $rv) *
          ($lv - $rv);
      }
      return $result;
    }
    ?>
  • id:kent013
    distanceSquaredPointsの二つ目のforeachのif文、
    誤:if(isset($lhs[$i]) && $rv == 0){
    正:if(isset($lhs[$i]) || $rv == 0){
    ですね・・・
  • id:kn1967
    コピペミスってるかもしれないので・・・
    誤 $result += ($lv - $rv) ^ 2;
    正 $result += (0 - $rv) ^ 2;
  • id:kn1967
    $result += (0 - $rv) ^ 2;
      ↓
    $result += $rv ^ 2;
    マイナスxマイナスですから省略すれば・・・もう、ミスって無いだろうか・・・。

  • id:Mook
    アルゴリズムの妥当性の検証はしていませんが、単純に処理のカスタマイズであれば、
    後半の処理の

      foreach($rhs as $i => $rv){
        if(isset($lhs[$i]) || $rv == 0){
          continue;
        }
        $lv = 0;
        $result +=
          ($lv - $rv) *
          ($lv - $rv);
      }

    は冗長に見えても If 文のコストの方が高いので

      foreach($rhs as $i => $rv){
        if(isset($lhs[$i]) ) continue;
        $result += $rv^2;
      }

    の方がもう少し速くなるかと思います。
    こちらでの計測結果は
     オリジナル:0.038291597366333sec
     kn1967さん:0.029101037979126sec
     後半修正 :0.026879000663757sec
    でした。


    これ以上は、データの持ち方やアルゴリズム自身に手を入れないと難しいでしょうか。
  • id:kent013
    kn1967さん、Mookさん、ありがとうございます。
    こちらでテストしたところ600-1000で
    オリジナル:0.080933499336243sec
    kn1967さん:0.060842180252075sec
    Mookさん:0.057339668273926sec

    となりました。
    上記プログラムを変更して、実行したところ全体として30%程度の速度向上をすることができました。

    if文の書き方などで、速度が大幅に改善することを知り、とても勉強になりました。
    Mookさんのおっしゃるとおり、これ以上の高速化はアルゴリズム自体を変えないとならないと思いますので、本質問を終了いたします。

    お二方、どうもありがとうございました。

この質問への反応(ブックマークコメント)

トラックバック

  • 趣味プログラミング 最近、忙しかったけど少しだけ余裕が見えてきました。 ので久しぶりに記事を書こうかなと思ったけど、気合を入れちゃいそうなのでガス抜きに適当なエントリを書こ
「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません