ardggy's blog

Esc - Meta - Alt - Ctrl - Shift

複数のイテレータを合流させる(承前)

前は2つのイテレータを合流させるパターンを書いたが、3つ以上のイテレータも混ぜられないだろうか。 confluence(confluence($it1, $it2, $compare), $it3, $compare) とやれば複数混ぜられそうな気がする。

つまり畳み込みの計算で、array_reduce をつかえばいい。

<?php
declare(strict_types=1);

// x=0: 0, 3, 6, 9, ...
// x=1: 1, 4, 7, 10, ...
// x=2: 2, 5, 8, 11, ...
function mod3($x = 0): Iterator {
  for ($y = $x; 1; $y += 3) { yield $y; }
}

$compare = fn($x, $y) => $x <=> $y;
$iter3 = array_reduce([mod3(0), mod3(1), mod3(2)],
                      fn($acc, $it) => confluence($acc, $it, $compare),
                      $initial = new EmptyIterator);

assert([0,1,2,3,4,5,6,7,8,9] === iterator_to_array(new LimitIterator($iter, 0, 10)));

array_reduce は左からの畳込みだけど、右から畳み込んでも動くんじゃないかと思う。

イテレータを合流させる

ソート済みの2つのイテレータを混ぜ合わせて直列にできないだろうか、という動機

<?php
declare(strict_types=1);

$iter = confluence(odds(), evens(), fn($x, $y) => $x <=> $y);
assert([0,1,2,3,4,5,6,7,8,9] === iterator_to_array(new LimitIterator($iter, 0, 10), $use_keys = false));

function confluence(Iterator $it1, Iterator $it2, Callable $compare): Iterator {
  while ($it1->valid() && $it2->valid()) {
    $v1 = $v1 ?? $it1->current();
    $v2 = $v2 ?? $it2->current();

    // どちらのイテレータからもらうかの選択
    // 改善の余地あり
    if ($compare($v1, $v2) < 0) {
      yield $v1;
      $it1->next();
      $v1 = $it1->current();
    } else {
      yield $v2;
      $it2->next();
      $v2 = $it2->current();
  }
  for ( ; $it1->valid(); $it1->next()) {
    yield $it1->current();
  }
  for ( ; $it2->valid(); $it2->next()) {
    yield $it2->current();
  }
}

function odds(): Iterator {
  for ($x = 1; 1; $x += 2) {
    yield $x;
  }
}

function evens(): Iterator {
  for ($x = 0; 1; $x += 2) {
    yield $x;
  }
}

ジェネレータとSQL

SQL の結果をなめたいがメモリにぜんぶ展開すると out of memory になりがちなところ、 チャンクを次々とジェネレータで供給するというパターンを思いついた。これならほぼ定数メモリで大量のデータを処理できる。

ジェネレータは Iterator を実装しているので、SPL のイテレータにわたすこともできる。

function chunk(SQL $query, int $size) : Iterator {
  $offset = 0;
  $query->limit($size);
  while ($result = fetch_all($query)) {
    yield from $result;

    $query->offset($offset += $size);
  }
}

$query = sql("SELECT * FROM sakila.film"); // SQL を表すナニカ
foreach (chunk($query, $size = 1000) as $film) {
  # do useful stuff
}

実際は offset ではなく、id ベースでたどるのがよさそうではある。