@methane さんから何度かすごく簡単なアルゴリズムがphpで書けなくてつらいという記事についてメンションもらってた気がするけど、php ってそんなもんでしょって思っているので特に反論するでもなく安寧に過ごしていた訳ですが、少々思うところあってphp で O(n) になるようなコードを書いてみた。という話。

既に @tanakahisateru さんが言及されているとおり、php の場合は組み込み型で頑張るよりもオブジェクトで解決する方が楽。
参照が絡んだ場合の Copy on Write とか予想外の動きしかしないもの。

ただ、せっかく php には SPL (= Standard PHP Library) なるものが用意されているので、使ってみるのも一興。ということで、こんな感じのコードを書いてみました。

<?php

class FixedArray extends SplFixedArray {
  public function pop($index = -1) {
    $n = $this->getSize();
    if ($index < 0) {
      $index += $n;
    }

    $target = $this[$index];
    for ($i = $index; $i < $n-1; ++$i) {
      $this[$i] = $this[$i+1];
    }

    $this->setSize($n-1);
    return $target;
  }

  public static function fromArray(array $array) {
    $self = new self(count($array));
    foreach ($array as $k=>$v) {
      $self[$k] = $v;
    }
    return $self;
  }
}

function match($seq, $r=100) {
  $seq = FixedArray::fromArray($seq);

  while (count($seq) >= 2) {
    $a = $seq->pop();
    $i = mt_rand(1, min($r, count($seq)));
    $b = $seq->pop(-$i);
    yield $a => $b;
  }
}

function test($n, $r) {
  foreach (match(range(0, $n-1), $r) as $a => $b) {
    assert($a - $b < $r*2);
  }
}

test($argv[1], 10);

SplFixedArray 自体は 5.3 からあるのだけど、yield つかってるので 5.5 以降でないと動きませんが、手元で動かしてみた限りでは O(n) っぽい感じになってますね。

$ time php m.php 10000; time php m.php 20000; time php m.php 30000; time php m.php 40000; time php m.php 50000; time php m.php 60000;
php m.php 10000  0.36s user 0.03s system 99% cpu 0.387 total
php m.php 20000  0.58s user 0.05s system 99% cpu 0.637 total
php m.php 30000  0.72s user 0.05s system 99% cpu 0.778 total
php m.php 40000  0.93s user 0.07s system 99% cpu 1.008 total
php m.php 50000  1.06s user 0.09s system 99% cpu 1.153 total
php m.php 60000  1.12s user 0.09s system 99% cpu 1.210 total

SplFixedArray は、zval へのポインタを連続したメモリ上にのみ配置するため、一般的な array よりも軽量かつ高速に扱えるという利点があります。
(php7 においては array の構造が最適化されるので大きな利点にはならないかも知れませんが。)

php がメモリ空間を意識したアルゴリズムに向かないのは事実なので、
そういうところに pure php だけで挑むのは筋違いだよなー。って思うデスよ。

perl の話

~~余談だけど、同じことを perl で書いてみたのだけど、やっぱり CoW 走るのか O(n) にならない。~~
~~上手くチューニングする方法知っている人が居れば教えて欲しい。~~

勘違いでした。自分のコードが間違っていただけなので、
ベンチ結果も差し替えました。

perl 素直！そして早い

use strict;
use warnings;

sub min {
  return $_[0] < $_[1] ? $_[0] : $_[1];
}

sub match {
  my ($seq, $r, $assert) = @_;

  while (@$seq >= 2) {
    my $a = pop @$seq;
    my $i = rand(min($r, scalar(@$seq))) + 1;
    my $b = splice @$seq, -$i, 1;

    #printf "%d, %d\n", $a, $b;
    $a-$b < $r*2 or die;
  }
}

sub test {
  my($n, $r) = @_;
  match([0..$n-1], $r);
}

test($ARGV[0], 10);

$ time perl m.pl 10000; time perl m.pl 20000; time perl m.pl 30000; time perl m.pl 40000; time perl m.pl 50000; time perl m.pl 60000;
perl m.pl 10000  0.05s user 0.01s system 98% cpu 0.057 total
perl m.pl 20000  0.06s user 0.01s system 97% cpu 0.071 total
perl m.pl 30000  0.08s user 0.01s system 98% cpu 0.086 total
perl m.pl 40000  0.09s user 0.01s system 98% cpu 0.103 total
perl m.pl 50000  0.11s user 0.01s system 99% cpu 0.118 total
perl m.pl 60000  0.12s user 0.01s system 98% cpu 0.133 total