ある条件でソートされているIDのリストを与えられて、なんとなく近い範囲でマッチングさせたいという要件があった。配列からの任意の要素の取り出しは O(n) だけど、末尾や末尾から固定した範囲の要素に限って言えば O(1) なので、後ろの方からマッチングさせながら要素を取り出していけば O(n) でマッチングできるはず。

なんにも難しいことは無い話で、 Python で書けばこうなる。 list.pop() が末尾からのインデックス (-1 が最後の要素を表す) を許すのが地味に便利だ。

matching.py

# coding: utf-8

def match(seq, r=100):
    from random import randint
	# 奇数個の時に先頭周辺の要素がボッチになるのが嫌なら、先に後ろの方の
	# 要素を取り除いて偶数にしておくこと.
    while len(seq) >= 2:
        # 引数を省略すると末尾の要素を取り出す.
        a = seq.pop()
        # 配列の後ろから r の範囲内でランダムに選択し取り出す.
        b = seq.pop(-randint(1, min(r, len(seq))))
        yield a, b

def test(n, r):
    for a, b in match(range(n), r):
        #print a, b
        assert a - b < 20

import sys
test(int(sys.argv[1]), 10)

要件を聞いた時にすぐにこのアルゴリズムを思いついて、「簡単簡単」と安請け合いしたのだが、 php に限って言えば全然簡単ではなかった。連想配列から指定したキーの要素を取り除くことができるのに、配列から途中の要素を取り出す（後ろを詰める）関数がいくら探しても見つからない。

数十分 php のリファレンスの array の章を読んだ結果、 list.pop() に相当する操作は存在しなかった。配列を一回切り出して連結すれば一応似たことができるものの、配列の連結コストが O(n) なのでマッチングアルゴリズムが O(n^2) になってしまう。結局自分で取り出した要素よりも後ろの要素を1つずつ前にずらすループを書かないといけなかった。

php だと配列と連想配列がごっちゃになってるせいで、 array 系の関数はキーの扱いが判りにくい。あまりに判りにくすぎてphp開発者もこんなに基本的な処理を提供していないのに気づいていないのではないか。

追記

コメント欄で指摘いただいた通り、 array_splice() で期待する動作を実現できました。ちゃんと負の数による末尾からのインデックスにも対応しています。上記のコードを php で書き換えると次のようになります。

しかし、実行時間がやっぱり O(n) になっていないようですorz
アルゴリズマーの端くれとして、phpを使わない権利を基本的人権として主張します。

matching.php

<?php

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

function test($n, $r) {
    foreach (match(range(0, $n-1), $r) as $a => $b) {
        //printf("%d %d\n", $a, $b);
        if ($a - $b >= $r*2) {
            error_log("XXX");
        }
    }
}

test($argv[1], 10);

# 実行結果
$ time python matching.py 10000

real   0m0.038s
user   0m0.031s
sys    0m0.006s
$ time python matching.py 20000

real   0m0.043s
user   0m0.035s
sys    0m0.007s
$ time php matching.php 10000

real   0m1.821s
user   0m1.806s
sys    0m0.012s
$ time php matching.php 20000

real   0m11.842s
user   0m11.797s
sys    0m0.041s

追記2

さすがに自分で実装したらいけるだろうと考えたんだが、それも難しかった。うろ覚えだけど参照に対して count() するときに CoW が発生した気がするので、そのせいだと思う。

php ではクソな組み込み関数を回避するために自前で array を処理することすらままならないので、配列を操作したかったら php 拡張を作ってC言語で書こう。 php はテンプレート言語であり、プログラムはC言語で書くのが無難。

matching2.php

<?php

function list_pop(&$seq, $index) {
    $n = count($seq);
    if ($index < 0)
        $index += $n;
    $value = $seq[$index];
    for ($i = $index; $i < $n-1; ++$i) {
        $seq[$i] = $seq[$i+1];
    }
    array_pop($seq);
    return $value;
}

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

function test($n, $r) {
    foreach (match(range(0, $n-1), $r) as $a => $b) {
        printf("%d %d\n", $a, $b);
        if ($a - $b >= $r*2) {
            error_log("XXX");
        }
    }
}

test($argv[1], 10);

# 実行結果
$ time php matching2.php 10000

real   0m1.631s
user   0m1.607s
sys    0m0.020s
$ time php matching2.php 20000

real   0m9.160s
user   0m9.105s
sys    0m0.052s

追記3

追記2 で list_pop() にしていた処理をベタ書きしたら、やっと予想通りの性能が出るようになった。 php で配列の参照に対して操作してはいけない。つまり、配列を操作するアルゴリズムを関数にしてはいけない。

matching3.php

<?php

function match($seq, $r=100) {
    $res = array();
    while (count($seq) >= 2) {
        $a = array_pop($seq);
        $n = count($seq);
        $i = $n - mt_rand(1, min($r, $n));
        $b = $seq[$i];
        for (; $i < $n-1; ++$i) {
            $seq[$i] = $seq[$i+1];
        }
        array_pop($seq);
        $res[$a] = $b;
    }
    return $res;
}

function test($n, $r) {
    foreach (match(range(0, $n-1), $r) as $a => $b) {
        //printf("%d %d\n", $a, $b);
        if ($a - $b >= $r*2) {
            error_log("XXX");
        }
    }
}

# 実行結果
$ time php matching2.php 10000

real   0m0.064s
user   0m0.052s
sys    0m0.011s
$ time php matching2.php 20000

real   0m0.076s
user   0m0.064s
sys    0m0.011s