2017年08月21日 に投稿

PHPでマージソートしてみる

PHP
アルゴリズム

はじめに

Java で書かれたマージソートを PHP で書き換えてみたら思ったより時間がかかったのでメモ。 できたコードはこんな感じ

MergeSort.php
class MergeSort
{
    public $array;

    function __construct($ary)
    {
        $this->array = $ary;
    }
    function run()
    {
        $this->mergeSort(0, count($this->array));
    }

    function mergeSort($low, $high)
    {
        if ($high - $low <= 1) return;
        $middle = (int)($low + ($high - $low) / 2);
        $this->mergeSort($low, $middle);
        $this->mergeSort($middle, $high);
        $this->merge($low, $middle, $high);
        echo "<pre>";
        print_r($this->array);
        echo "</pre>";
    }

    function merge($low, $middle, $high)
    {
        $helper = array();
        $helperLeft = $low;
        $helperRight = $middle;

        while ($helperLeft < $middle && $helperRight < $high) {
            if ($this->array[$helperLeft] <= $this->array[$helperRight]) {
                $result[] = $this->array[$helperLeft];
                $helperLeft++;
            } else {
                $result[] = $this->array[$helperRight];
                $helperRight++;
            }
        }
        while ($helperLeft < $middle) {
            $result[] = $this->array[$helperLeft];
            $helperLeft++;
        }
        while ($helperRight < $high) {
            $result[] = $this->array[$helperRight];
            $helperRight++;
        }
        $this->arrayCopy($result, $low, $high);
    }

    function arrayCopy($resource, $start, $end)
    {
        $resIndex = 0;
        for ($i = $start; $i < $end; $i++) {
            $this->array[$i] = $resource[$resIndex];
            $resIndex++;
        }
    }
}

$ary = range(1, 10, 1);
shuffle($ary);

$mergeSort = new MergeSort($ary);
$mergeSort->run();

つまずいたポイント

1 PHP では引数に配列を渡すと参照渡しではなくとしてコピーされる

  1. 参照渡しはパフォーマンス的にも宜しくない -> 配列を操作するアルゴリズムを関数にしてはいけない?
  2. 整数同士の割り算でも実数値になる

解決1

配列が参照渡しされるように引数の前に&をつけて見たものの下の記事を拝見するといいやり方ではないよう、、 たいてい配列は参照渡しだろーと思っていたので思わぬところでつまずいた汗  PHP の変数は最初からすべてポインタであるため参照渡しを明示してやる必要はない。よって関数に配列が渡されたときに値がまるまるコピーされるわけではないので、&をつける必要がない。むしろパフォーマンスが悪くなる。

解決2

参照渡しをしないで配列を操作するアルゴリズムをどう書けばいいのか悩んだ結果、同じ方のとても参考になる記事を見つけた。配列の中身を変更するのであれば関数ではなく、クラス化して状態をもたせるのがいいみたい。

解決3

C や Java では整数同士の割り算は整数値になるが、PHP では実数値になるためキャストする必要がある。 PHP7 のintdiv関数でもいけると思ったが、Fatal error: Allowed memory size of ~とエラーがでて動かなかった...