カテゴリー: php

「もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら」を解いてみた
の続きです

動的計画法のコードをPHPで書いてみました
（Rubyのコードとロジックは同じです）

<?php
$M = trim(fgets(STDIN)); // 人員
$N = trim(fgets(STDIN)); // 会社数

$minCost = 0;
$num = array();
$cost = array();

for($i = 0; $i < $N; $i++) {
    fscanf(STDIN, '%d %d', $num[$i], $cost[$i]);
    $minCost += $cost[$i];
}

$dp[0] = 0;
for($n = 0; $n < $N; $n++) {
    foreach ($dp as $key => $value) {
        $totalNum = $key + $num[$n];
        $totalCost = $value + $cost[$n];
        if (isset($dp[$totalNum]) == false) {
            $dp[$totalNum] = $totalCost;
        } else {
            if ($dp[$totalNum] > $totalCost) {
                $dp[$totalNum] = $totalCost;
            }
        }
        if ($totalNum >= $M && $minCost > $totalCost) {
            $minCost = $totalCost;
        }
    }
}

//ksort($dp);
//var_dump($dp);
echo $minCost;

人数ごとの結果を残して、再利用しています（わかりにくい..）
一番低いコストの値だけを残しています
まだ無駄のあるコードで、改良の余地ありです

paizaでコードを提出すると採点してくれます
結果はこんな感じです
http://paiza.jp/poh/kirishima/result/fb88794dc2e25c011a242f318744ccc9

最速コードを目指したりするとまだ遊べるようです

paizaの
もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら
という解説が公開されました

アルゴリズムのプログラムをあまりやったことがなかったの考えてみました
解説記事の全文探索をphpで書くとこんな感じ

<?php
function calc($cost, $staff, $idx) {
    global $n, $m, $result, $company;
    if ($n <= $idx) {
        return;
    }   
    if ($m <= $staff + $company[$idx]['num']) {
        $result[] = $cost + $company[$idx]['cost'];
    } else {
        calc($company[$idx]['cost'], $company[$idx]['num'], $idx + 1); 
    }
    calc($cost, $staff, $idx + 1);
}

$m = trim(fgets(STDIN)); // 人員
$n = trim(fgets(STDIN)); // 会社数

$company = array();
for ($i=0; $i < $n; $i++) {
    $t = trim(fgets(STDIN));
    $t = str_replace(
        array("\r\n", "\r", "\n"), '', $t
    );      
    $e = explode(" ", $t);
    $company[$i]['num'] = $e[0];
    $company[$i]['cost'] = $e[1];
}

$result = array();
calc(0, 0, 0);
arsort($result);
echo (array_shift($result));

これだと、会社数が増えたときに組み合わせが多すぎて、テストが通らないみたいです
ビットを使えば再帰関数が不要になります（記事参照）が、同じく全文探索です

計算結果を再利用する動的計画法を使えば、組み合わせが会社数×人数の組み合わせとなるので処理数が減らせテストがすべてクリアできたようです
（解答例 http://paiza.jp/poh/code_index はpaizaに会員登録するとみれます）

xdebugでphpをプロファイリングしてみます

インストールはこちらを参考に
Ubuntuにxdebugをいれてみる

php.iniに設定を追記します

# sudo vi /etc/php5/apache2/php.ini
(追記)xdebug.profiler_enable_trigger=1

Apacheをreload
# sudo service apache2 reload

試しにブラウザでWEBサーバーにアクセス
今回はphpinfoのページを表示させてみました
http://localhost/phpinfo.php?XDEBUG_PROFILE

?XDEBUG_PROFILEをつけるとプロファイリング結果がでます
（つけないと出ない）

すると
# ls /tmp
cachegrind.out.13739
…

とcachegrind.out.13739のファイルができます

結果を見やすくするためkcachegrindというものを入れます

# sudo apt-get install kcachegrind

ダッシュメニューとかから起動します
openで先ほどのファイルを選ぶと

結果が表示されます
負荷高いところやボトルネックを直していきましょう

常にプロファイリング結果を出力したいなら
# sudo vi /etc/php5/apache2/php.ini
(追記)xdebug.profiler_enable=1

とするといいです

Ubuntu12.04(VirtualBox上の）へ
php用のプロファイリング（負荷みたり）、リモートデバッグできたりするxdebugを入れてみます

Apacheとphpがインストール済み、Apache＋phpの例です

pear(pecl)も入ってなかったのでpearインストール
# sudo apt-get install php-pear

# pear version
PEAR Version: 1.9.5
PHP Version: 5.5.15-1+deb.sury.org~precise+1
Zend Engine Version: 2.5.0
Running on: Linux user-vb 3.2.0-67-generic-pae #101-Ubuntu SMP Tue Jul 15 18:04:54 UTC 2014 i686

pear 入りました
peclでxdebugをインストールします

# sudo pecl install xdebug
downloading xdebug-2.2.5.tgz …
Starting to download xdebug-2.2.5.tgz (255,840 bytes)
………done: 255,840 bytes
66 source files, building
running: phpize
sh: 1: phpize: not found
If the command failed with ‘phpize: not found’ then you need to install php5-dev packageYou can do it by running ‘apt-get install php5-dev’ as a root userERROR: `phpize’ failed

コケた..足りないものをいれて、再度実行
# sudo apt-get install php5-dev
# sudo pecl install xdebug

php.iniでxdebugを有効にします
xdebug.soの場所を見つけてから
# vi /etc/php5/apache2/php.ini
(追記)zend_extension=/usr/lib/php5/20121212/xdebug.so

apacheをreloadして
# sudo service apache2 reload

phpinfoを用意して確認します
# vi /var/www/html/phpinfo.php

<?php
phpinfo();

ブラウザでアクセス
http://localhost/phpinfo.php

xdebugが表示されました