[php] 配列から Iterator を作る最も効率のいい方法

やりたいこと

• 配列から Iterator を作りたい。
• なるべくはやく動いてほしい。
• ArrayIterator ってあるけど、それってホントに早いの？
• php 5.6.10 と php 7.4.3 で同じコードで確かめました。

準備

まずは準備するためのコード。

配列

てきとーに大きい連想配列を作ります。
楽なので key も value も int にしました。
ところで、 PHP_INT_MIN って、 php 5 にはないんですね。

if (!defined('PHP_INT_MIN')) {
    define('PHP_INT_MIN', -PHP_INT_MAX - 1);
}

function create_array() {
    $array = [];
    while (count($array) < 1000000) {
        $array[mt_rand(PHP_INT_MIN, PHP_INT_MAX)] = mt_rand(PHP_INT_MIN, PHP_INT_MAX);
    }
    return $array;
}

$array = create_array();
echo '$array length: ' . count($array) . PHP_EOL;
echo PHP_EOL;

テスト関数

テスト関数はこんな感じ。
key も value も両方使いたかったのでそれらをひたすら加算するもの。
30 回計測して 10 回ごとに結果を出力します。

function doTest(array $array, callable $iterator_getter) {
    $times = [];
    for ($i = 0; $i < 3; ++$i) {
        $start = microtime(true);
        $sum = 0;
        for ($j = 0; $j < 10; ++$j) {
            foreach ($iterator_getter($array) as $key => $value) {
                $sum += $key;
                $sum += $value;
            }
        }
        $time = microtime(true) - $start;
        $times[] = $time;
        echo 'time: ' . $time . ', sum: ' . $sum . PHP_EOL;
    }
    echo 'avg: ' . (array_sum($times) / count($times)) . PHP_EOL;
    echo PHP_EOL;
}

テストコード

遅かった順に紹介していきます。
結果は後でまとめて。

テスト 1 内部ポインタ

ワースト 1 はこちら！
この次のやつより早いと思ったのに期待外れ。
内部ポインタ関数を使って Iterator を実装してみました。

内部ポインタ関数には、 reset, end, next, prev, current, key, each があります。
そのうち、reset, next, key, current を使います。

コード 1-1

echo 'test 1-1: InternalPointerArrayIterator' . PHP_EOL;
class InternalPointerArrayIterator implements Iterator {
    private $array;
    public function __construct($array) { $this->array = $array; }
    public function rewind()            { reset($this->array); }
    public function next()              { next($this->array); }
    public function valid()             { return key($this->array) !== null; }
    public function current()           { return current($this->array); }
    public function key()               { return key($this->array); }
}

doTest($array, function ($array) { return new InternalPointerArrayIterator($array); });

テスト 2 index

今度は index を使ってみます。
array_values と array_keys を使って連想配列を index - key - value に分けるワザです。

これらを使えば、添え字が 0 から始まる共通の index を持つ配列を得られます。
array_values は index => value となり
array_keys は index => key となります。

index => [ key, value ] ってなる関数はないんですね。。。

ちなみに array_combine は key にしたい配列と value にしたい配列を組み合わせる関数だそうです。

コード 2-1 キーを使う版

echo 'test 2-1: ArrayIndexKeyValueIterator' . PHP_EOL;
class ArrayIndexKeyValueIterator implements Iterator {
    private $index;
    private $keys;
    private $values;
    public function __construct($array) {
        $this->keys = array_keys($array);
        $this->values = array_values($array);
    }
    public function rewind()  { $this->index = 0; }
    public function next()    { ++$this->index; }
    public function valid()   { return $this->index < count($this->keys); }
    public function current() { return $this->values[$this->index]; }
    public function key()     { return $this->keys[$this->index]; }
}

doTest($array, function test2_1($array) { return new ArrayIndexKeyValueIterator($array); });

コード 2-2 キーを使わない版。

array_keys を使わずに key メソッドの実装では index を返すようにします。

echo 'test 2-2 ArrayIndexValueIterator' . PHP_EOL;
class ArrayIndexValueIterator implements Iterator {
    private $index;
    private $values;
    public function __construct($array) {
        $this->values = array_values($array);
    }
    public function rewind()  { $this->index = 0; }
    public function next()    { ++$this->index; }
    public function valid()   { return $this->index < count($this->values); }
    public function current() { return $this->values[$this->index]; }
    public function key()     { return $this->index; }
}

doTest($array, function ($array) { return new ArrayIndexValueIterator($array); });

テスト 3 ArrayIterator

ArrayIterator は配列を抱えて Iterator のように振る舞うクラスです。
stdClass などのオブジェクトも抱えることができます。
ArrayObject の子供です。

コード 3-1 キーを使う版

echo 'test 3-1: ArrayIterator' . PHP_EOL;
doTest($array, function ($array) { return new ArrayIterator($array); });

テスト 4 ジェネレーター

これをやりたかったから今までのテストがあるんです。

yield を使う関数は Generator という Iterator を実装したクラスを返します。

コード 4-1 key 使う版

echo 'test 4-1: yield key value' . PHP_EOL;
doTest($array, function ($array) { foreach ($array as $key => $value) { yield $key => $value; } });

コード 4-2 key 使わない版

echo 'test 4-2: yield value' . PHP_EOL;
doTest($array, function ($array) { foreach ($array as $value) { yield $value; } });

テスト結果

php5

$array length: 1000000

test 1-1: InternalPointerArrayIterator
time: 9.3887410163879, sum: -1.6109817797916E+16
time: 9.4301509857178, sum: -1.6109817797916E+16
time: 9.4480760097504, sum: -1.6109817797916E+16
avg: 9.4223226706187

test 2-1: ArrayIndexKeyValueIterator
time: 7.8769841194153, sum: -1.6109817797916E+16
time: 7.2404820919037, sum: -1.6109817797916E+16
time: 7.5442090034485, sum: -1.6109817797916E+16
avg: 7.5538917382558

test 2-2 ArrayIndexValueIterator
time: 6.0075109004974, sum: -5.3709754974784E+15
time: 5.8148491382599, sum: -5.3709754974784E+15
time: 5.8173658847809, sum: -5.3709754974784E+15
avg: 5.8799086411794

test 3-1: ArrayIterator
time: 3.4061341285706, sum: -1.6109817797916E+16
time: 3.4112520217896, sum: -1.6109817797916E+16
time: 3.4074258804321, sum: -1.6109817797916E+16
avg: 3.4082706769307

test 4-1: yield key value
time: 3.8069369792938, sum: -1.6109817797916E+16
time: 3.8960921764374, sum: -1.6109817797916E+16
time: 3.8957939147949, sum: -1.6109817797916E+16
avg: 3.866274356842

test 4-2 yield value
time: 3.8193328380585, sum: -5.3709754974784E+15
time: 3.8335611820221, sum: -5.3709754974784E+15
time: 3.8304271697998, sum: -5.3709754974784E+15
avg: 3.8277737299601

php7

$array length: 1000000

test 1-1: InternalPointerArrayIterator
time: 2.9903738498688, sum: 3.3884535088043E+22
time: 2.9772939682007, sum: 3.3884535088043E+22
time: 2.9829080104828, sum: 3.3884535088043E+22
avg: 2.9835252761841

test 2-1: ArrayIndexKeyValueIterator
time: 2.3398787975311, sum: 3.3884535088043E+22
time: 2.325747013092, sum: 3.3884535088043E+22
time: 2.3066658973694, sum: 3.3884535088043E+22
avg: 2.3240972359975

test 2-2 ArrayIndexValueIterator
time: 2.1043679714203, sum: -6.4247619686786E+21
time: 2.0666069984436, sum: -6.4247619686786E+21
time: 2.0694139003754, sum: -6.4247619686786E+21
avg: 2.0801296234131

test 3-1: ArrayIterator
time: 0.77759599685669, sum: 3.3884535088043E+22
time: 0.7790789604187, sum: 3.3884535088043E+22
time: 0.77693104743958, sum: 3.3884535088043E+22
avg: 0.77786866823832

test 4-1: yield key value
time: 0.61654806137085, sum: 3.3884535088043E+22
time: 0.60638499259949, sum: 3.3884535088043E+22
time: 0.60806393623352, sum: 3.3884535088043E+22
avg: 0.61033233006795

test 4-2: yield value
time: 0.56992816925049, sum: -6.4247619686786E+21
time: 0.5589599609375, sum: -6.4247619686786E+21
time: 0.56230807304382, sum: -6.4247619686786E+21
avg: 0.56373206774394

No	項目	key	php5	php7
1-1	内部ポインタ	あり	9.4223226706187	2.9835252761841
2-1	index	あり	7.5538917382558	2.3240972359975
2-2		なし	5.8799086411794	2.0801296234131
3-1	ArrayIterator	あり	3.4082706769307	0.77786866823832
4-1	ジェネレーター	あり	3.866274356842	0.61033233006795
4-2		なし	3.8277737299601	0.56373206774394

まとめ

• もう php7 優秀すぎ。まったく同じコードなのにこの差。約 3 倍。
• 与えられたものつかっとけ。無理に作るな。
• キーを使わないようにケチってもそれほど差は得られない。
• ほかにもっといい方法、早くなくても面白い方法あれば教えてください。