SplDoublyLinkedList を利用したリスト操作

このエントリの内容が興味深かったので、PHP で SplDoublyLinkedList を使って書いてみました。
Python - すごく簡単なアルゴリズムがphpで書けなくてつらい - Qiita [キータ]
PHPでは配列ではなくオブジェクトに状態を持たせよ - なんたらノート第三期ベータ

<?php

function match($seq, $r) {
    $res = array();
    while ($seq->count() >= 2) {
        $a = $seq->shift();
        $i = mt_rand(0, min($r, $seq->count()) - 1);
        $b = $seq[$i];
        unset($seq[$i]);
        $res[$a] = $b;
    }
    return $res;
}

function test($n, $r) {
    $seq = new SplDoublyLinkedList();
    foreach (range(0, $n - 1) as $i) {
        $seq->push($i);
    }
    foreach (match($seq, $r) as $a => $b) {
        print "$a $b\n";
        if ($a - $b >= $r * 2) {
            error_log("XXX");
        }
    }
}

test($argv[1], $argv[2]);

配列ではなく連結リストを使っているので、元プログラムのように末尾から取り出す工夫は不要です。このプログラムでは、先頭から順に取り出すようにしました。

実行結果はこのようになります。

$ php matching.php 10 5
0 5
1 3
2 8
4 6
7 9
$ time php matching.php 10000 10 >/dev/null
real    0m0.086s
user    0m0.043s
sys     0m0.019s
$ time php matching.php 100000 10 >/dev/null
real    0m0.283s
user    0m0.213s
sys     0m0.046s
$ time php matching.php 1000000 10 >/dev/null
real    0m2.252s
user    0m1.897s
sys     0m0.315s

実際に書いてみることで気付いたのですが、SplDoublyLinkedList はイテレータを介した要素の追加、削除といった操作を提供していません。そのため、このプログラムには非効率があります。コード中、$b = $seq[$i] のアクセスでは offsetGet メソッドが、unset($seq[$i]) では offsetUnset メソッドが利用されますが、それぞれのメソッドでリストを先頭から辿ることになり、二度手間です。連結リストなのにイテレータを用いた要素の操作ができないのは、ちょっと不便な気がします。

元プログラムのように末尾の方から取り出すには、このように変更するだけです。

$ diff -C1 matching.php matching_lifo.php
*** matching.php        2013-12-25 22:26:13.456022873 +0900
--- matching_lifo.php   2013-12-25 22:29:26.906024403 +0900
***************
*** 5,7 ****
      while ($seq->count() >= 2) {
!         $a = $seq->shift();
          $i = mt_rand(0, min($r, $seq->count()) - 1);
--- 5,7 ----
      while ($seq->count() >= 2) {
!         $a = $seq->pop();
          $i = mt_rand(0, min($r, $seq->count()) - 1);
***************
*** 16,17 ****
--- 16,18 ----
      $seq = new SplDoublyLinkedList();
+     $seq->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);
      foreach (range(0, $n - 1) as $i) {

setIteratorMode メソッドに SplDoublyLinkedList::IT_MODE_LIFO を指定すると、$seq[0] が末尾要素を指すようになります。一方、shift() や pop() は setIteratorMode の指定による影響を受けないので、上記の diff のように書き換える必要があります。

実行結果はこのようになります。ちゃんと末尾から取られていることが確認できました。

$ php matching_lifo.php 10 5
9 5
8 7
6 2
4 0
3 1

さて、この二つはちょうどキューとスタックに相当します。SPL には SplQueue, SplStack というクラスが用意されているので、それを使って書くこともできます。先頭から取り出すコードは、SplQueue を使って書くと以下のようになります。

$ diff matching.php matching_queue.php
6c6
<         $a = $seq->shift();
---
>         $a = $seq->dequeue();
16c16
<     $seq = new SplDoublyLinkedList();
---
>     $seq = new SplQueue();
18c18
<         $seq->push($i);
---
>         $seq->enqueue($i);

push($i) で追加し、shift() で取り出すという操作は、SplQueue を使えば enqueue($i), dequeue() と書けます。実はこれは単なるエイリアスで、ext/spl/spl_dllist.c で以下のように定義されています。

static const zend_function_entry spl_funcs_SplQueue[] = {
        SPL_MA(SplQueue, enqueue, SplDoublyLinkedList, push,  arginfo_dllist_push, ZEND_ACC_PUBLIC)
        SPL_MA(SplQueue, dequeue, SplDoublyLinkedList, shift, arginfo_dllist_void, ZEND_ACC_PUBLIC)
        PHP_FE_END
};

末尾から取り出すコードも同様に、SplStack を使って以下のように書けます。

$ diff matching_lifo.php matching_stack.php
16,17c16
<     $seq = new SplDoublyLinkedList();
<     $seq->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);
---
>     $seq = new SplStack();

こちらは、SplDoublyLinkedList に元々 push($value), pop() というメソッドが定義されているので、コンストラクタを変更するだけです。

さて、このように限られた使い方をしているうちは便利に見える SplDoublyLinkedList ですが、実は IT_MODE_LIFO にした場合の挙動はなかなか厄介です。このことについては、次の記事にまとめたいと思います。