迭代器和生成器

发表于 更新于 分类于

一道面试题

如果让你用 PHP 生成从 1 到100 万个数值，请问怎么做才能最省内存？

没错，这是一道面试题，如果让你写出答案，你会有什么样的思路呢？请先独自思考几分钟。

可能你想到的会是这种方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<?php
// 我自己本地测试大概用了 34MB 内存
function makeLargeArray($length){
    $dataset = [];
    for ($i = 0; $i < $length; $i++) {
        $dataset[] = $i;
    }
    return $dataset;
}
$customRange = makeLargeArray(1000000);
foreach ($customRange as $i) {
    echo $i, PHP_EOL;
}

// 记录使用的内存
function formatBytes($bytes, $precision = 2) {
    $units = array("b", "kb", "mb", "gb", "tb");

    $bytes = max($bytes, 0);
    $pow = floor(($bytes ? log($bytes) : 0) / log(1024));
    $pow = min($pow, count($units) - 1);

    $bytes /= (1 << (10 * $pow));

    return round($bytes, $precision) . " " . $units[$pow];
}

print formatBytes(memory_get_peak_usage());

你如果给出这种答案的话，肯定不会让面试官满意的。因为这道题的重点是节省内存，如果是如上的程序，虽然能够实现题目的前半部分要求，但实际运行起来却是一个非常吃内存的老虎。因为从 PHP 底层分析， makeLargeArray() 会预先创建一个由一百万个整数组成的数组分配内存！

那么到底要怎么做才能既节省内存，又能实现这道题的目标呢？

正确答案是，使用 PHP生成器 ，代码如下：

1
2
3
4
5
6
7
8
9
10
<?php
// 我本地测试大概用了 718KB 内存
function makeLargeArray($length) {
    for ($i = 0; $i < $length; $i++) {
        yield $i;
    }
}
foreach (makeLargeArray(1000000) as $i) {
    echo $i, PHP_EOL;
}

很少用 PHP 生成器的同学是不是看不太懂？没关系，本文才刚刚开始。

PHP 迭代器

在讲 PHP 生成器之前，我觉得有必要给大家讲一讲迭代器的概念。如果你对 PHP 迭代器的概念很了解，可以直接跳过这个章节，直接前往文中下半部分。

迭代是指反复执行一个过程，每执行一次叫做一次迭代。这么说你可能不是很理解，事实上，我们每天都在和迭代打交道，就比如 PHP 的 foreach() 函数，像这样：

1
2
3
4
5
6
7
8
9
<?php
$home = [
    'bed',
    'television',
    'computer'
];
foreach ($home as $furniture) {
    echo 'There is a '.$furniture.'in my home!';
}

上面一个简单的 foreach() 就是一个迭代器，它将 home 一次又一次的遍历，输出三个家具 furniture。实际上，发生变化的是 home 这个数组，你可以把它当做是一个对象，foreach 在每次遍历它时，都会调用这个对象里的一个方法，让数组在自己内部的指针发生一次变化（迭代）。

所以，我们可以称 home 数组为 迭代器对象，而 foreach 就是一个 迭代器接口（Iterator）。

PHP 生成器

概念

通过上面的例子，想必大家对生成器有一个大概的理解，先来看看官方的解释（慢点儿度读，好好理解）：生成器允许你在 foreach 代码块中写代码来迭代一组数据而不需要在内存中创建一个数组, 那会使你的内存达到上限，或者会占据可观的处理时间。相反，你可以写一个生成器函数，就像一个普通的自定义函数一样, 和普通函数只返回一次不同的是, 生成器可以根据需要 yield 多次，以便生成需要迭代的值。

生成器（Generator）是 PHP5.5 引入的功能，往往没有被大家充分利用。其实这是一个非常有用的功能，我相信大多数开发者和我一样不知道有生成器这种东西，因为平时工作中不常用，其实很简单，生成器就是迭代器，仅此而已。

作用

生成器提供了一种更容易的方法来实现简单的对象迭代，相比较定义类实现 Iterator 接口的方式，性能开销和复杂性大大降低。

生成器的用法

我觉得除了我给的第一个例子，官方给的用例是也能很好的解释生成器的益处。比如 PHP 的一个函数：range ，它可以建立一个包含指定范围单元的数组，标准的 range() 函数需要在内存中生成一个数组包含每一个在它范围内的值，然后返回该数组, 结果就是会产生多个很大的数组。 比如，调用 range(0, 1000000) 将导致内存占用超过 100 MB。

做为一种替代方法, 我们可以实现一个 xrange() 生成器, 只需要足够的内存来创建 Iterator 对象并在内部跟踪生成器的当前状态，这样只需要不到 1K 字节的内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
<?php
function xrange($start, $limit, $step = 1) {
    if ($start < $limit) {
        if ($step <= 0) {
            throw new LogicException('Step must be +ve');
        }

        for ($i = $start; $i <= $limit; $i += $step) {
            yield $i;
        }
    } else {
        if ($step >= 0) {
            throw new LogicException('Step must be -ve');
        }

        for ($i = $start; $i >= $limit; $i += $step) {
            yield $i;
        }
    }
}
/* 注意下面range()和xrange()输出的结果是一样的。 */
echo 'Single digit odd numbers from range():  ';
foreach (range(1, 9, 2) as $number) {
    echo "$number ";
}
echo "\n";
echo 'Single digit odd numbers from xrange(): ';
foreach (xrange(1, 9, 2) as $number) {
    echo "$number ";
}
// 以上例程会输出：
Single digit odd numbers from range():  1 3 5 7 9
Single digit odd numbers from xrange(): 1 3 5 7 9
?>

用法

我们需要注意的关键是 yield，这是生成器的关键。我们通过上面例子，可以看得出，yield 会将当前一个值传递给 foreach，换句话说， foreach 每一次迭代过程都会从 yield 处取一个值，直到整个遍历过程不再存在 yield 为止的时候，遍历结束。

我们也可以发现， yield 和 return 都会返回值，但区别在于一个 return 是返回既定结果，一次返回完毕就不再返回新的结果，而 yield 是 不断产出 直到无法产出为止。

实际上存在 yield 的函数返回值返回的是一个 Generator 对象（这个对象不能手动通过 new 实例化），该对象实现了 Iterator 接口。

你可能觉得以上例子没啥实际用途，我再举一个比较有用的例子（来自 Modern PHP 一书），比如我想导入一个大小约为 4GB 的 CSV 文件（你可以理解为 Excel），而且我们的服务器运行在一个共享的 VPS 中，只提供了 1 GB 的内存，所以不能直接把 CSV 这个生成的数组直接都放在内存里。那我们怎么用生成器+迭代器来实现呢？代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 生成器产出
function getRows($file) {
    $handel = fopen($file, 'rb');
    if ($handel === false) {
        throw new Exception("Error Processing", 1);
    }
    while (feof($handel) === false) {
        yield fgetcsv($handel);
    }
    fclose($handel);
}
// 迭代器读取
foreach (getRows('./data.csv') as $row) {
    print_r($row);
}

导入导出这种需求在现实场景中是不是很常见，大家可以在项目里尝试使用生成器来取代传统的数组声明，可以帮公司省掉一大笔内存购买费用~

总结

生成器是功能多样性和简洁性之间的折中方案。生成器是只能向前进的迭代器，这意味着不能使用生成器在数据集中执行后退、快进或査找操作，只能让生成器计算并产生下一个值。迭代大型数据集或数列时最适合使用生成器，因为这样占用的系统内存量极小。生成器也能完成迭代器能完成的简单任务，而且使用的代码较少。

原文链接：述迭代器和生成器