PHPの勉強はじめました（C++/PHP/Rubyのクイックソートによる速度比較）

tech

今日からPHPの勉強をはじめることにしました。「RoRとiPhoneアプリはどうした！？」という声が聞こえてきそうですが、PHPの優先度があがったのですよ。
というわけで、アマゾンで2冊ほど購入。マンモスのが良いと言う書評も見かけましたが、オライリーを買うことにしました。

環境構築

PHPの環境を入れて動作確認。
当面はコマンドラインを使って勉強していこうかと思うので、コマンドライン用のパッケージも入れます。

sudo apt-get install php5 php5-cli
php -v
PHP 5.3.2-1ubuntu4.2 with Suhosin-Patch (cli) (built: May 13 2010 20:01:00) 
Copyright (c) 1997-2009 The PHP Group
Zend Engine v2.3.0, Copyright (c) 1998-2010 Zend Technologies

クイックソート

とりあえず、少しだけプログラムを書いてみることに。お題はクイックソート。
（最近「Cプログラマのためのアルゴリズムとデータ構造」を読み直す機会があったので）
せっかくなので、C++とRubyでも書いてみて実行時間を比較してみました。


[要素数10の配列をソートする] x 5万回をtimeコマンドを使って計ってみた結果です。

C++(4.4.3) PHP(5.3.2) Ruby(1.8.7)
real 0m0.117s 0m4.486s (38倍) 0m14.053s (120倍)
user 0m0.024s 0m4.308s 0m10.041s
sys 0m0.012s 0m0.052s 0m3.732s


(つд⊂)ｺﾞｼｺﾞｼ
　

(；ﾟдﾟ) ・・・


なんぞこれ！？
スクリプト（インタプリタ）が遅いというのは今まで知識としては知っていましたが、実際に目の当たりにすると凄いな。
処理する内容によって全然違ってくるだろうけど、これぐらい違ってくるということもあるのか。
ソフトウェアの速度が出ないときにボトルネック部分をC/C++で書き直すという対処方法もうなずける。
そしてPHPに比べてもRubyが遅い。1.9系だと速くなってるんだっけ？

ちなみにクイックソートのピボットは右端決め打ちで実装しました。(3点中央値はまた今度）

ソースコード

ソースコードさらしておきます。何かおかしかったら教えてください。
コードが間違ってたら、測定結果まったく意味ない＞＜

  • C++
#include <iostream>
#include <memory.h>

void print_array(int array[] , int num)
{
  std::cout << "[";
  for(int i = 0 ; i < num - 1 ; i++){ std::cout << array[i] << " , "; }
  std::cout << array[num - 1] << "]" << std::endl;
}

int partition(int array[] , int left , int right)
{
  int i = left;
  int j = right - 1;
  int pivot = array[right];
  int temp;

  while(1)
  {
    while(array[i] < pivot){ i++; }
    while(array[j] > pivot && i < j){ j--; }

    if(i >= j){ break; }

    temp = array[i]; 
    array[i] = array[j];
    array[j] = temp;
  }

  temp = array[i]; 
  array[i] = array[right];
  array[right] = temp;

  return i;
}

void quick_real(int array[] , int left , int right)
{
  if(left >= right){return;}

  int vertical = partition(array , left , right);

  quick_real(array , left , vertical - 1);
  quick_real(array , vertical + 1 , right);
}

void quick(int array[] , int num)
{
  quick_real(array , 0 , num - 1);
}

int main()
{
  int array_template[10] = {55 , 3 , 74 , 20 , 13 , 87 , 46 , 30 , 12 , 65};
  int array[10];
  int num = sizeof(array) / sizeof(array[0]);
  
  for(int i = 0 ; i < 50000 ; i++)
  {
    memcpy(array , array_template , sizeof(array));
    //print_array(array , num);
    quick(array , num);
    //print_array(array , num);
  }
  
  return 0;
}
  • PHP
#!/usr/bin/php
<?php
function quick(&$array , $left = 0 , $right = -1)
{
  if($right == -1){ $right = count($array) - 1; }

  if($left >= $right){ return; }

  $vertical = partition($array , $left , $right);

  quick($array , $left , $vertical - 1);
  quick($array , $vertical + 1 , $right);

  return;
}

function partition(&$array , $left , $right)
{
  $i = $left;
  $j = $right - 1;
  $pivot = $array[$right];

  while(true)
  {
    while($array[$i] < $pivot){ $i++; }
    while($array[$j] > $pivot && $i < $j){ $j--; }

    if($i >= $j){ break; }

    $temp = $array[$i];
    $array[$i] = $array[$j];
    $array[$j] = $temp;
  }

  $temp = $array[$i];
  $array[$i] = $array[$right];
  $array[$right] = $temp;
  
  return $i;
}

$array_template = array(55 , 3 , 74 , 20 , 13 , 87 , 46 , 30 , 12 , 65);

for($i = 0 ; $i < 50000 ; $i++)
{
  $array = $array_template;

  #print implode("," , $array)."\n";
  quick($array);
  #print implode("," , $array)."\n";
}

?>
  • Ruby
#!/usr/bin/ruby

def quick(array , left = 0 , right = array.size - 1)
  return if left >= right

  vertical = partition(array , left , right)

  quick(array , left , vertical - 1)
  quick(array , vertical + 1 , right)
end

def partition(array , left , right)
  i = left
  j = right - 1
  pivot = array[right]

  while true
    i += 1 while array[i] < pivot
    j -= 1 while array[j] > pivot and i < j

    break if i >= j

    array[i] , array[j] = array[j] , array[i]
  end

  array[i] , array[right] = array[right] , array[i]


  return right
end

array_template = [55 , 3 , 74 , 20 , 13 , 87 , 46 , 30 , 12 , 65]
array = []
50000.times do
  array = array_template.dup
  #p array
  quick(array)
  #p array
end



PHPはよくdisられてるので実はあまり良いイメージは無いんだけども、使ったことも無いのにそんなこと言う資格ないですからね。ある程度つかるようになるぞ！