2025-03-06

PHPで無限ストリームの直積(番外編)

そこで、下図に示すように、対角線上に組を生成していくことにします。
お気楽 Haskell プログラミング入門

リスト : 組の生成 (2)

pair_stream' :: [a] -> [b] -> [(a, b)]
pair_stream' xs ys = makePair 1 xs ys where
  makePair n xs ys = zip (take n xs) (reverse (take n ys)) ++ makePair (n + 1) xs ys

これ3個以上に拡張するの難しいかなと思ってたけど思ったほどでもなかった。
対角線じゃなくて対角面？になるけど、考え方としては「要素のインデックス値の合計が一定になるように次の要素を取得するストリームを選んでいく」という考え方にすれば良い。

図で書くとこんな感じ

次に進む方向で分岐すればよい。

実際には重複を避けるために逆流不可の条件を入れる。

「次にどのストリームを選ぶかで分岐する」はツリーイテレータで書ける。

// 対角線上の要素を取得
function diagonal(array $dims): Iterator
{
    if (array_any($dims, fn($a)=>count($a) == 0)) {
        return;
    }
    // 数値インデックスを使うので念のためリスト化
    if (!array_is_list($dims)) {
        $dims = array_values($dims);
    }
    // 先頭の配列を逆順にする
    $dims[0] = array_reverse($dims[0]);

    // 最初のノードをスタックに追加
    $stack = [[$dims, 1]];

    // スタックが空になるまで処理
    while (!empty($stack)) {
        // 現在のノードをスタックから取り出す
        [$dims, $latest_key] = array_pop($stack);
        // 各配列の先頭の値を出力
        yield array_map(fn($a) => $a[array_key_first($a)], $dims);

        // 次の候補ノードをスタックに積む
        // 配列を取り尽していたら終了
        if (count($dims[0]) == 1 || array_all($dims, fn($a) => count($a) == 1)) {
            continue;
        }
        // 次にどの配列を消費するかで分岐
        for ($i = $latest_key; $i < count($dims); $i++) {
            if (count($dims[$i]) == 1) {
                continue; // この列は終了
            }
            $next = $dims;
            array_shift($next[0]);
            array_shift($next[$i]);

            $stack[] = [$next, $i];
        }
    }
}

これを列を増やしながらループする

function iterator_cartesian_product(iterable ...$iterators): Iterator
{
    foreach (iterator_zip(...array_map(gradual_iterator(...), $iterators)) as $dims) {
        yield from diagonal($dims);
    }
}

iterator_zipとgradual_iteratorは最初に作ったやつです

function gradual_iterator(iterable $iter): Iterator
{
    $cached = [];
    foreach ($iter as $val) {
        $cached[] = $val;
        yield $cached;
    }
}
function iterator_zip(iterable ...$iterators): Iterator
{
    while (array_reduce($iterators, fn($acc, $iter) => $acc && $iter->valid(), true)) {
        yield array_map(fn($iter) => $iter->current(), $iterators);
        array_walk($iterators, fn($iter) => $iter->next());
    }
}

実際に動かすとこういう感じ。スタックを増やしたくないので縦探索してるせいで出力はあんまり整列してないね。

test('test iterator_cartesian_product with 2 infinite iterators', function () {
    $iter1 = sequence(0);
    $iter2 = sequence(0);
    $iterator = iterator_cartesian_product($iter1, $iter2);
    $result = iterator_take($iterator, 55);
    $expected = [
        [0, 0],
        [1, 0], [0, 1],
        [2, 0], [1, 1], [0, 2],
        [3, 0], [2, 1], [1, 2], [0, 3],
        [4, 0], [3, 1], [2, 2], [1, 3], [0, 4],
        [5, 0], [4, 1], [3, 2], [2, 3], [1, 4], [0, 5],
        [6, 0], [5, 1], [4, 2], [3, 3], [2, 4], [1, 5], [0, 6],
        [7, 0], [6, 1], [5, 2], [4, 3], [3, 4], [2, 5], [1, 6], [0, 7],
        [8, 0], [7, 1], [6, 2], [5, 3], [4, 4], [3, 5], [2, 6], [1, 7], [0, 8],
        [9, 0], [8, 1], [7, 2], [6, 3], [5, 4], [4, 5], [3, 6], [2, 7], [1, 8], [0, 9]
    ];
    expect($result)->toBe($expected);
});
test('test iterator_cartesian_product with 4 args', function () {
    $iterator = iterator_cartesian_product(
        sequence(0),
        sequence(0),
        sequence(0),
        sequence(0)
    );
    $result = iterator_take($iterator, 10);
    $result = array_map(fn($v) => implode('', $v), $result);
    $this->assertEquals(
        ['0000', '1000', '0001', '0010', '0100', '2000', '1001', '0002', '1010', '0011'],
        $result
    );
});

テスト用のヘルパーはいつもの

/**
 * Iteratorから指定した数の値を取り出してarrayで戻す。
 */
function iterator_take(Iterator $iterator, int $num): array
{
    if ($num == 0) {
        return [];
    }
    $taken = [];
    foreach ($iterator as $value) {
        $taken[] = $value;
        if (--$num <= 0) {
            break;
        }
    }
    return $taken;
}
/**
 * 指定した範囲の整数を出力するIteratorを生成する。
 * @param int $min 最小値。
 * @param int|null $max 最大値。省略時は無限に値を出す。
 */
function sequence(int $min, int|null $max = null): Iterator
{
    while (is_null($max) || $min <= $max) {
        yield $min++;
    }
}

要素が有限の場合に対応しようとすると、列の長短に配慮したり残り半分を取ったりするのが面倒くさいです。

2025-02-17

PHPでDbCの真似事

PHPにはAOP(Weaving)を実現するGo! AOP PHPという素敵なライブラリがあるそうなのでこれでDbC(契約プログラミング)的なことをやる。

実行サンプル

例として正の整数しか扱えないスタック、PositiveIntStackというのを用意する。

<?php

namespace Samples\Sample;

use Samples\DbC\Postcondition;
use Samples\DbC\Precondition;

/**
 * 正の整数のみを扱うスタック
 */
class PositiveIntStack
{
    /**
     * @param array $stack
     */
    public function __construct(private array $stack = [])
    {
    }

    /**
     * 渡された整数をスタックに積む
     * @param int $value 整数
     * @return void なし
     */
    #[Precondition('value > 0', '正の整数のみ使用できます。')]
    public function push(int $value): void
    {
        array_push($this->stack, $value);
    }

    /**
     * 整数をスタックから取り出して戻す。
     * @return int 取り出した整数
     */
    #[Precondition('not this.empty()', '空のスタックはpop出来ません。')]
    #[Postcondition('return > 0', '正の整数のみ戻されます。')]
    public function pop(): int
    {
        return array_pop($this->stack);
    }

    /**
     * @return bool スタックが空かどうかを戻す
     */
    public function empty(): bool
    {
        return empty($this->stack);
    }
}

使用例(テスト) PositiveIntStackTest.php

<?php

namespace Samples\Sample;

use Samples\AOP\DbCAspectKernel;
use Samples\DbC\Exception\PostconditionException;
use Samples\DbC\Exception\PreconditionException;

beforeAll(function (): void {
    $kernel = DbCAspectKernel::getInstance();

    $kernel->init([
        'debug' => true,
        'appDir' => __DIR__ . '/..',
        'cacheDir' => __DIR__ . '/cache',
        'includePaths' => []
    ]);
});

test('test PositiveIntStack push normal', function (): void {
    $stack = new PositiveIntStack();
    expect(fn() => $stack->push(1))->not->toThrow(\Throwable::class);
});
test('test PositiveIntStack push with negative number', function (): void {
    $stack = new PositiveIntStack();
    expect(fn() => $stack->push(-1))->toThrow(
        PreconditionException::class,
        '正の整数のみ使用できます。'
    );
});
test('test PositiveIntStack pop with positive number', function (): void {
    $stack = new PositiveIntStack();
    $stack->push(1);
    expect($stack->pop())->toBe(1);
});
test('test PositiveIntStack pop though empty', function (): void {
    $stack = new PositiveIntStack();
    expect(fn() => $stack->pop())->toThrow(
        PreconditionException::class,
        '空のスタックはpop出来ません'
    );
});
test('test PositiveIntStack pop negative value', function (): void {
    $stack = new PositiveIntStack([-1]);
    expect(fn() => $stack->pop())->toThrow(
        PostconditionException::class,
        '正の整数のみ戻されます。'
    );
});

環境

goaop/frameworkの安定版3.0.0はPHP7でしか使えないのでdevのを使う。お覚悟はよろしくて？
composer.json抜粋

{
  "require": {
    "php": "^8.4.2",
    "goaop/framework": "4.0.x-dev",
    "symfony/expression-language": "^v7.2.0"
  },
  "require-dev": {
    "pestphp/pest": "^3.7"
  },
  "minimum-stability": "dev",
  "prefer-stable": true
}

実装

事前条件と事後条件を記述するためのAttributeを作成する。条件を書く式言語にSymfony ExpressionLanguageを借りました。
例外は適当に定義したもの

<?php

namespace Samples\DbC;

use Samples\DbC\Exception\PreconditionException;
use Symfony\Component\ExpressionLanguage\ExpressionLanguage;

#[\Attribute]
class Precondition
{
    public function __construct(
        private readonly string $condition,
        private readonly string $message = 'Precondition failed.'
    ) {
    }

    public function validate($object, array $args): void
    {
        $language = new ExpressionLanguage();
        $result = $language->evaluate($this->condition, ['this' => $object, ...$args]);
        if (!$result) {
            throw new PreconditionException($this->message);
        }
    }
}

<?php

namespace Samples\DbC;

use Samples\DbC\Exception\PostconditionException;
use Symfony\Component\ExpressionLanguage\ExpressionLanguage;

#[\Attribute]
class Postcondition
{
    public function __construct(
        private readonly string $condition,
        private readonly string $message = 'Precondition failed.'
    ) {
    }

    public function validate($object, $returnValue): void
    {
        $language = new ExpressionLanguage();
        $result = $language->evaluate($this->condition, ['this' => $object, 'return' => $returnValue]);
        if (!$result) {
            throw new PostconditionException($this->message);
        }
    }
}

Aspectを定義する。戻り値を使用したいのでAroundとして定義。
ポイントカットは@executionを使用。これで指定したアトリビュートが付けられたメソッドが対象になる。
(メモ：@が付くポイントカットはアスペクト/アトリビュート用)

<?php

namespace Samples\AOP;

use Go\Aop\Aspect;
use Go\Aop\Intercept\MethodInvocation;
use Go\Lang\Attribute\Around;
use Samples\DbC\Postcondition;
use Samples\DbC\Precondition;

class ContractAspect implements Aspect
{
    #[Around("@execution(Samples\DbC\Precondition) || @execution(Samples\DbC\Postcondition)")]
    public function aroundExecutionForContract(MethodInvocation $invocation)
    {
        $object = $invocation->getThis();
        $reflectionMethod = $invocation->getMethod();
        $args = $invocation->getArguments();

        // 事前条件の検証
        $preconditionAttributes = $reflectionMethod->getAttributes(Precondition::class);
        if (!empty($preconditionAttributes)) {
            // 引数の名前と値を使って連想配列にする
            $names = array_column($reflectionMethod->getParameters(), 'name');
            $namedArgs = array_combine($names, $args);
            // 検証を実行
            foreach ($preconditionAttributes as $attribute) {
                $attributeInstance = $attribute->newInstance();
                $attributeInstance->validate($object, $namedArgs);
            }
        }

        // メソッド実行（戻り値を取得）
        $returnValue = $invocation->proceed();

        // 事後条件の検証
        $postconditionAttributes = $reflectionMethod->getAttributes(Postcondition::class);
        if (!empty($postconditionAttributes)) {
            foreach ($postconditionAttributes as $attribute) {
                $attributeInstance = $attribute->newInstance();
                $attributeInstance->validate($object, $returnValue);
            }
        }

        return $returnValue;
    }
}

これを登録するAspectKernelの実クラスを実装

<?php
<?php

namespace Samples\AOP;

use Go\Core\AspectContainer;
use Go\Core\AspectKernel;

class DbCAspectKernel extends AspectKernel
{
    /**
     * @inheritDoc
     */
    protected function configureAop(AspectContainer $container): void
    {
        $container->registerAspect(new ContractAspect());
    }
}

これで冒頭の実行サンプルが動く

解説

Go! AOP PHPのweavingの仕組み

Go! AOP PHPは特定のpointcutに対してAspectを登録することで関数やメソッドの呼び出し前後に処理を追加することができる。
Aspectに指定できる実行タイミングの種類にはBefore(呼び出し前に実行)、After(呼び出し後に実行)、Around(呼び出す代わりに実行)がある。
どうやって実現しているかというと、PHPのautoloadの機構を使ってクラスローディングのタイミングで読み込まれるクラスを解析して処理を追加(weaving)するらしい。(なのでAspectKernelのinitの前に読み込まれたクラスはweavingされない。)
どの関数やどのクラスのメソッドに処理を追加するのかを指定するのがポイントカットで、今回だとContractAspectのAroundアトリビュートに指定した "@execution(Samples\DbC\Precondition)"という文字列がそれにあたる。アトリビュート/アノテーション以外に直接メソッドや関数を対象とすることもできる。
AspectKernelのinit時にconfigureAop()が呼ばれるのでそこでAspectを登録→Aspectに指定されたポイントカットが記録される→クラス読み込み時に該当する関数/メソッドがあれば処理を追加、という流れ。

Precondition/Postconditionに処理を渡す仕組み

Precondition/Postconditionを付けたメソッドが呼ばれると、そのタイミングでContractAspectの該当メソッドが呼ばれるので、実行時の情報(対象オブジェクトや引数の値や戻り値)をPrecondition/Postconditionに渡して検証している。
Preconditionには、対象オブジェクトと引数を渡す。引数は引数名をキーとする連想配列にしている。
Postconditionには、対象オブジェクトと戻り値を渡す。

Precondition/Postcondition内での処理の仕組み

Precondition/Postconditionはコンストラクタで第1引数を条件($condition)、第2引数を違反時のメッセージ($message)としてプロパティに保存している。ここにはPrecondition/Postconditionアトリビュートに定義した値が渡ってくる。(サンプルでいえば'value > 0'と'正の整数のみ使用できます。'など)
実行時はContractAspectからvalidate()が呼び出されるので、$conditionをSymphony ExpressionLanguageの式、thisとパラメータ(PostConditionの場合はreturn)を変数(環境)として渡して評価し、falseだったら条件違反として例外を投げる。
式内では引数名の$を取ったものが変数として使える。
ここの仕組みはextractとevalでも書けるけど何でも出来ると危ないからね。式言語を使います。

2025-01-27

PHPで無限ストリームの直積(まとめ)

配列同士の直積、つまりそれぞれの配列から要素を1つずつ選ぶ全ての組み合わせを取得する処理を、無限ストリームに拡張できないかと考え、PHPで任意個のiterableの直積という形でそれを実装した。

振り返り

検証的にはPHPで無限ストリームの直積(3) - terazzoの日記で一旦完成であとは蛇足ですね。コードもこの段階のものが一番本質的だと思う。

記事一覧

PHPで無限ストリームの直積(1) - terazzoの日記
- 無限ストリームの2個の直積を生成するHaskellのサンプルを参考にPHPで実装した
- その際、生成済みの値を含めて段階的に値を生成するgradual_iteratorの概念を導入した
- また、「対角線」ではなく「L字型」で生成するパターンも検討した
PHPで無限ストリームの直積(2) - terazzoの日記
- 1のコードを元に無限ストリームの3個の直積を実装した
- その際、各Iteratorを「次元」、出力済みの値のリストを「辺」、新規の値を「点」とみなすメタファーを導入した
閑話休題 - terazzoの日記
- 複数配列(つまり有限の)の直積を求めるコードを実装した
PHPで無限ストリームの直積(3) - terazzoの日記
- 2のコードを元に4個以上(個数を制限しない)の無限ストリームの直積を実装した
- 『各「次元」から「辺」もしくは「点を」選択する処理』および『各次元の「辺」「点」から全ての値を生成する処理』がどちらも「複数配列の直積」で表せることが分かった
PHPで無限ストリームの直積(4) - terazzoの日記
- 4のコードを元に有限の配列を混在させても動くようにした
PHPで無限ストリームの直積(5) - terazzoの日記
- 5のコードを最適化し、あまりメモリを消費しないようにした

実装

なんでこんなコードになってるのっていうのは過去のエントリを読めば理解できると思う。

/** 複数のiterableの直積をIteratorで戻す*/
function iterator_cartesian_product(iterable ...$iterators): \Iterator
{
    foreach (gradual_iterator_zip(...$iterators) as $dimensions) {
        foreach (configure($dimensions) as [$edge_only, $configuration]) {
            if (!$edge_only) {
                yield from array_cartesian_product_iterator(...$configuration);
            }
        }
    }
}

/** 配列の直積を生成するIteratorを戻す */
function array_cartesian_product_iterator(array ...$arrs): \Iterator
{
    if (empty($arrs)) {
        yield [];
        return;
    }
    $array = array_shift($arrs);
    if (!empty($array)) {
        foreach (array_cartesian_product_iterator(...$arrs) as $values) {
            foreach ($array as $value) {
                yield [$value, ...$values];
            }
        }
    }
}
/**
 * 複数のiterableをgradual_iterator化した上でzipする。
 * 全てのiterableの値が尽きたら終了する。
 */
function gradual_iterator_zip(iterable ...$iters): \Iterator
{
    $gradual_iterators = array_map(gradual_iterator(...), $iters);
    while (true) {
        $any_valid = false;
        $values = [];
        foreach ($gradual_iterators as $iter) {
            [$cached, $last, $valid] = $iter->current();
            $iter->next();
            $any_valid = $any_valid || $valid;
            $values[] = [$cached, $last];
        }
        if (!$any_valid) {
            return;
        }
        yield $values;
    }
}
/**
 * iterableから段階的に値を出すIteratorを作る。
 * Iteratorは[生成済みの値の配列, [新規に生成した値], 新規の値の有無]を生成する。
 * 元のiterableの値が尽きても値を生成し続ける。
 */
function gradual_iterator(iterable $iter): \Iterator
{
    $cached = [];
    foreach ($iter as $last) {
        yield [$cached, [$last], true];
        $cached[] = $last;
    }
    // 値が尽きても出し続ける(validかどうかは戻り値で渡す)
    while (true) {
        yield [$cached, [], false];
    }
}
/**
 * それぞれが配列である2要素の配列の配列から、
 * どちらかの要素を取った組み合わせを生成するIteratorを戻す。
 * 但し、要素が空配列の場合はスキップする。
 * 戻されたIteratorは[全てが1要素目かどうか, 組み合わせの配列]を生成する。
 */
function configure(array $dims): \Iterator
{
    if (empty($dims)) {
        yield [true, []];
        return;
    }
    [$edge, $point] = array_shift($dims);

    foreach (configure($dims) as [$edge_only, $confs]) {
        if (!empty($edge)) {
            yield [$edge_only, [$edge, ...$confs]];
        }
        if (!empty($point)) {
            yield [false, [$point, ...$confs]];
        }
    }
}

使用例

test(
    'yields cartesian product of 4 itarables',
    function () {
        $iterator = iterator_cartesian_product(
            sequence(0),
            range('a', 'z'),
            range('A', 'Z'),
            range('!', '/'),
        );
        $result = iterator_take($iterator, 10);
        $result = array_map(fn($v) => implode('', $v), $result);
        expect($result)->toBe(['0aA!', '1aA!', '0bA!', '1bA!', '0aB!', '1aB!', '0bB!', '1bB!', '0aA"', '1aA"']);
    }
);
/**
 * 指定した範囲の整数を出力するIteratorを生成する。
 * @param int $min 最小値。
 * @param int|null $max 最大値。省略時は無限に値を出す。
 */
function sequence(int $min, int|null $max = null): \Iterator
{
    while (is_null($max) || $min <= $max) {
        yield $min++;
    }
}

/**
 * Iteratorから指定した数の値を取り出してarrayで戻す。
 */
function iterator_take(\Iterator $iterator, int $num): array
{
    if ($num == 0) {
        return [];
    }
    $taken = [];
    foreach ($iterator as $value) {
        $taken[] = $value;
        if (--$num <= 0) {
            break;
        }
    }
    return $taken;
}

2025-01-27

PHPで無限ストリームの直積(5)

前回
terazzo.hatenadiary.org

折角Generatorを使った遅延評価なのにarray_cartesian_productがばかでかい配列を作るのでメモリが足りなくなるのがイマイチですね。

array_cartesian_product()の方もGenerator化していく。
再帰でGeneratorのチェーンにするとメモリ効率良そう。

/**
 * 配列の直積を生成するIteratorを戻す
 */
function array_cartesian_product_iterator(array ...$arrs): \Iterator
{
    if (empty($arrs)) {
        yield [];
        return;
    }
    $array = array_shift($arrs);
    if (!empty($array)) {
        foreach (array_cartesian_product_iterator(...$arrs) as $values) {
            foreach ($array as $value) {
                yield [$value, ...$values];
            }
        }
    }
}

本体の方は、2箇所の呼び出し部分を直すのと、array_shiftで出力済みをスキップしていたところをフラグで制御に直す。

function iterator_cartesian_product(iterable ...$iterators): \Iterator
{
    foreach (gradual_iterator_zip(...$iterators) as $dimensions) {
        $at_first = true;
        foreach (array_cartesian_product_iterator($dimensions) as $configuration) {
            if ($at_first) {
                $at_first = false;
                continue;
            }
            yield from array_cartesian_product_iterator($configuration);
        }
    }
}

configurationを作ってるところは専用関数にしてもいいですね。
「すべて辺」をスキップするのを明確化したうえで空リストをスキップする効率化もする。

// 各次元から辺と線のどちらかを選ぶすべての組み合わせを生成する。
function configure(array $dims): \Iterator
{
    if (empty($dims)) {
        yield [true, []];
        return;
    }
    [$edge, $point] = array_shift($dims);

    foreach (configure($dims) as [$edge_only, $confs]) {
        if (!empty($edge)) {
            yield [$edge_only, [$edge, ...$confs]];
        }
        if (!empty($point)) {
            yield [false, [$point, ...$confs]];
        }
    }
}

function iterator_cartesian_product(iterable ...$iterators): \Iterator
{
    foreach (gradual_iterator_zip(...$iterators) as $dimensions) {
        foreach (configure($dimensions) as [$edge_only, $configuration]) {
            if (!$edge_only) {
                yield from array_cartesian_product_iterator(...$configuration);
            }
        }
    }
}

Iterator8個の直積の先頭1億件取ってもメモリ破綻しない。

    public function test_iterator_product10()
    {
        $iterator = iterator_cartesian_product(
            sequence(0), sequence(0), sequence(0), sequence(0),
            sequence(0), sequence(0), sequence(0), sequence(0)
        );
        for ($i = 0; $i < 99999990; $i++) {
            $iterator->next();
        }
        $result = [];
        for ($i = 0; $i < 10 && $iterator->valid(); $i++, $iterator->next()) {
            $result[] = $iterator->current();
        }

        $result = array_map(fn($v) => implode('', $v), $result);
        $this->assertEquals(
            ['09999999', '19999999', '29999999', '39999999', '49999999', '59999999', '69999999', '79999999', '89999999', '99999999'],
            $result
        );
    }

2025-01-15

PHPで無限ストリームの直積(4)

前回→
terazzo.hatenadiary.org
まあここからはほぼ蛇足だけど、前回のものをIteratorに有限のものが混ざっていても大丈夫なように修正する。

初回の時の図を思い出しながら、これの片方が有限の場合で考えてみる。
両方が増えていく場合
↓↓↓↓↓

増えたaに対して過去のbの全値を掛け合わせていけばいいですね。

プログラムを見直すと、まずIteratorを同時に回しているところを修正し「どれか一つでも次の値がある場合にループを続けるようにする」のと、「次の値がない場合は出力済みの値を出し続ける」ように直せば良そう。

function gradual_iterator(iterable $iter): \Iterator
{
    $cached = [];
    foreach ($iter as $last) {
        yield [$cached, [$last], true];
        $cached[] = $last;
    }
    // 値が尽きても出し続ける(validかどうかは戻り値で渡す)
    while (true) {
        yield [$cached, [], false];
    }
}

function gradual_iterator_zip(iterable ...$iters): \Iterator
{
    $gradual_iterators = array_map(gradual_iterator(...), $iters);
    while (true) {
        $any_valid = false;
        $values = [];
        foreach ($gradual_iterators as $iter) {
            [$cached, $last, $valid] = $iter->current();
            $iter->next();
            $any_valid = $any_valid || $valid;
            $values[] = [$cached, $last];
        }
        if (!$any_valid) {
            return;
        }
        yield $values;
    }
}

ついでに配列も渡せるように引数をiterableにしている。
新規の値があるかをvalid()じゃなくて値で判定するのはIteratorとしては行儀が悪い気はしますね。判定と過去の値を保持するのを同時にやりたいのでこうなってる。

function iterator_cartesian_product(iterable ...$iterators): \Iterator
{
    foreach (gradual_iterator_zip(...$iterators) as $dimensions) {
        $configurations = array_cartesian_product(...$dimensions);
        array_shift($configurations); // 出力済みの値をスキップ
        foreach ($configurations as $configuration) {
            yield from array_cartesian_product(...$configuration);
        }
    }
}

テスト

    public function test_iterator_product2_finite()
    {
        $iterator = iterator_cartesian_product(sequence(0), sequence(0, 2));
        $result = iterator_take($iterator, 15);
        $expected = [[0, 0], [1, 0], [0, 1], [1, 1], [2, 0], [2, 1], [0, 2], [1, 2], [2, 2], [3, 0], [3, 1], [3, 2], [4, 0], [4, 1], [4, 2]];
        $this->assertEquals($expected, $result);
    }

折角Generatorを使った遅延評価なのにarray_cartesian_productがばかでかい配列を作るのでメモリが足りなくなるのがイマイチですね。

2025-01-07

PHPで無限ストリームの直積(3)

前回→
terazzo.hatenadiary.org
無限ストリーム(Iterator)の直積を4個以上にも対応していきたい。
方針を立てるために前回のストリーム3個の場合のコードを見ながら、引き続き各Iteratorを「次元」、値のリストを「辺」、値を「点」とみなすメタファーを使って疑似コードを書いてみる。

function iterator_cartesian_product(\Iterator ...$iters): \Iterator
{
    // ①引数を生成済みの値を段階的に出力するIteratorに変換
    $gradual_iters = array_map(gradual_iterator(...), $iterators):
    // ②それを同時に進行するIteratorを作ってforeachで回す
    foreach(iterator_zip(...$gradual_iters) as $dimensions) {
        ③各次元の値を「辺(出力済みの値のリスト)」と「点(新たに出力された値)」に分解
        ④各次元から辺または点のどちらかを選んだすべての組み合わせのリストを作成
        foreach(④ as 各次元から辺または点のどちらかを選んだリスト) {
            if (すべてが辺) continue; // 出力済み
            ⑤ yield from [点,点,点...]のリスト
        }
    }
}

⑤の部分が有限リストの直積で出せそうだが、④の各次元から辺or点を選ぶ部分ももよく見たら直積(2×2×...)になってる。これを「閑話休題 - terazzoの日記」の配列の直積で書いてみる。

その前に準備としてgradual_iterator()を直して[出力済みの値のリスト,[新たな値]]を出すようにする。あとから分解するの面倒だからね。

function gradual_iterator(\Iterator $iter): \Iterator
{
    $cached = [];
    foreach ($iter as $last) {
        yield [$cached, [$last]];
        $cached[] = $last;
    }
}
// こっちは変更なし
function iterator_zip(\Iterator ...$iterators): \Iterator
{
    while (array_reduce($iterators, fn($acc, $iter) => $acc && $iter->valid(), true)) {
        yield array_map(fn($iter) => $iter->current(), $iterators);
        array_walk($iterators, fn($iter) => $iter->next());
    }
}

これとこの前作った配列の直積を出す関数を使って

function array_cartesian_product(array ...$arrs): array
{
    return array_reduce($arrs, fn($acc, $arr) => array_reduce(array_map(fn($v) => array_map(fn($r) => [...$r, $v], $acc), $arr), array_merge(...), []),[[]]);
}

すると無限ストリーム(Iterator)の直積は以下のように書ける

function iterator_cartesian_product(\Iterator ...$iterators): \Iterator
{
    foreach (iterator_zip(...array_map(gradual_iterator(...), $iterators)) as $dimensions) {
        $configurations = array_cartesian_product(...$dimensions);
        array_shift($configurations);
        foreach ($configurations as $configuration) {
            yield from array_cartesian_product(...$configuration);
        }
    }
}

$configurations(各次元から辺または点を選んだもの)の一つ目はすべて辺(出力済みの値)なのでarray_shiftで除去しています。手抜きだね。
内側のforeachはarray_mapとarray_mergeでも書けるけどメモリすごく食うのでforeachで十分。

テストとしてシーケンス4個をproductして最初の10個と9991～10000個目をみてみる。

    public function test_iterator_product()
    {
        $iterator = iterator_cartesian_product(sequence(0), sequence(0), sequence(0), sequence(0));
        $result = iterator_take($iterator, 10000);
        $result = array_map(fn($v) => implode('', $v), $result);
        $head10 = array_slice($result, 0, 10);
        $tail10 = array_slice($result, -10);
        $this->assertEquals(['0000', '1000', '0100', '1100', '0010', '1010', '0110', '1110', '0001', '1001'], $head10);
        $this->assertEquals(['0999', '1999', '2999', '3999', '4999', '5999', '6999', '7999', '8999', '9999'], $tail10);
    }

ちゃんと網羅できてるっぽい。
有限のIteratorが混ざってる場合にも対応したいですね。

2024-12-19

閑話休題

PHP

その1. PHPで配列の直積

複数配列の直積、ワンラインで書けますね。

function array_cartesian_product(array ...$arrs): array
{
    return array_reduce($arrs, fn($acc, $arr) => array_reduce(array_map(fn($v) => array_map(fn($r) => [...$r, $v], $acc), $arr), array_merge(...), []),[[]]);
}

可変長引数の代わりに各配列にラベルをつけるために連想配列で渡して結果もラベル付き(連想配列)で受け取れる感じにしたかったらこう↓

/**
 * array_reduce()の連想配列版。$callbackを呼び出す際に第3引数としてキーを渡す。
 */
function assoc_reduce(array $assoc, callable $callback, mixed $acc = null): mixed
{
    foreach ($assoc as $key => $value) {
        $acc = $callback($acc, $value, $key);
    }
    return $acc;
}
/**
 * 配列を値として取る連想配列の直積を取り、各配列のキーを値に付与したものの配列を戻す。
 */
function assoc_cartesian_product(array $assoc): array
{
    return assoc_reduce(
        $assoc,
        fn($acc, $array, $key) => array_reduce(
            array_map(fn($value) => array_map(
                fn($r) => $r + [$key => $value],
                $acc
            ), $array),
            array_merge(...),
            []
        ),
        [[]]
    );
}

流石に見にくいので改行した(IDEさんが)
こんな感じで連想配列の配列で受け取れる

    public function test_assoc_cartesian_product()
    {
        $result = assoc_cartesian_product(
            [
                'digit' => [0, 1],
                'ab'    => ['a', 'b'],
                'sign'  => ['+', '-']
            ]
        );

        $this->assertEquals(
            [
                ['digit' => 0, 'ab' => 'a', 'sign' => '+'],
                ['digit' => 1, 'ab' => 'a', 'sign' => '+'],
                ['digit' => 0, 'ab' => 'b', 'sign' => '+'],
                ['digit' => 1, 'ab' => 'b', 'sign' => '+'],
                ['digit' => 0, 'ab' => 'a', 'sign' => '-'],
                ['digit' => 1, 'ab' => 'a', 'sign' => '-'],
                ['digit' => 0, 'ab' => 'b', 'sign' => '-'],
                ['digit' => 1, 'ab' => 'b', 'sign' => '-']
            ],
            $result
        );
    }

その2. array_all()

array_reduce($iterators, fn($acc, $iter) => $acc && $iter->valid(), true)

こういうの、PHP8.4以降だとarray_allで書けるらしい。

array_all($iterators, fn($iter) => $iter->valid())

簡潔だし、一つでもfalseがあればそこで止まるので経済。
参考: PHP: array_all - Manual