趣味编程:在JavaScript中实现简单的yield功能(问题)
2010-06-08 15:33 by 老赵, 8239 visits说起迭代器(Iterator)大家一定都不陌生,无论是是Java,C#或是Python等语言都有内置标准的迭代器结构,它们也都提供了内置的for或foreach关键字简化迭代器的“使用”。不过对于迭代器的“生成”,不同语言之间的就会有很大差距。例如,在C#和Python中都提供了yield来简化迭代器的“创建”,此时生成一个迭代器便再简单不过了。但对于Java程序员来说,即使到了Java 7还必须为在迭代器内部手动维护状态,非常痛苦。而更重要的一点是,利用yield我们可以轻松地创建一个“延迟”的,“无限”的序列。那么,我们能否在JavaScript中享受到这样的yield生成器呢?
yield的功效
先来演示一下yield的作用,例如我们要写一个C#方法,返回一个迭代器(即.NET中的IEnumerable),它会生成从minInclusive到maxExclusive之间的整数序列:
// C# public static IEnumerable<int> Range(int minInclusive, int maxExlusive) { for (int i = minInclusive; i < maxExlusive; i++) yield return i; }
而在Java中便会麻烦许多:
// Java public class Range implements Iterable<Integer> { private int m_maxExclusive; private int m_current; public Range(int minInclusive, int maxExclusive) { this.m_maxExclusive = maxExclusive; this.m_current = minInclusive; } @Override public Iterator<Integer> iterator() { return new Iterator<Integer>() { public boolean hasNext() { return m_current < m_maxExclusive; } public Integer next() { int current = m_current; m_current = m_current + 1; return current; } public void remove() { throw new UnsupportedOperationException(); } }; } }
其实就最终执行的代码来说,C#和Java是差不多的,只不过C#的编译器帮助开发人员节省了许多工作。事实上,在这个简单的示例中其实还不能体现出yield的优越性,您可以想象一下,如果我们迭代器中需要有更多的逻辑,如while,if,for,break等配合使用,那么yield会带来多大的可读性。嗯,就说可读性,如果给您上面编写的Range类,您多久可以理解它的作用呢?再观察一下C#代码呢?
可能您会说,完全可以在Range类中先创建一个数组,保存所有元素,然后在next()时一一返回,这可读性就强了。没错,只可惜这样做会占用太多内存。假如我传入-108和108作为参数,那程序十有八九会出现问题(顺便一问,创建这样一个数组需要占用多少内存?)。yield的一个重要特性便是“延迟”,便是“按需生成”。我们完全可以创建一个“范围”十分巨大——甚至是无限大的迭代器:
// C# public static IEnumerable<int> Infinite(int start) { while (true) yield return start++; }
然后只取其前N项使用:
// sum of 0 .. 99 int sum = Infinite(0).Take(100).Sum();
此外yield还有一些十分重要的使用模式,不过这方面话题我打算留在《Why Java Sucks and C# Rocks(6):yield及其作用》一文中进行详细讨论了。
JavaScript中的迭代器
JavaScript中有迭代器吗?有迭代器的生成器(即yield类似功能)吗?有,还真有,您可以关注一下MDN中的JavaScript 1.7说明,其中就有几乎和C#完全一样的功能,例如这样生成并使用一个无限的斐波那契数列:
// JavaScript function fib() { var i = 0, j = 1; while (true) { yield i; var t = i; i = j; j += t; } } var g = fib(); for (var i = 0; i < 10; i++) { document.write(g.next() + "<br />"); }
只不过我们目前还没法编写这样的JavaScript代码,如果要使用迭代器,那么还得自己动手丰衣足食。
其实如果不谈“生成器”,光“迭代器”本身是没有任何神秘之处的,它们只是一种定义好的“编程模型”罢了,例如Java里的Iterable和Iterator或是.NET里的IEnumerable和IEnumerator。因此,如果要说建立一个迭代器,那么其实只是确定一个编程模型:
// JavaScript function range(minInclusive, maxExclusive) { // ... } for (var iter = range(0, 10); iter; iter = iter.next()) { document.write(iter.value + "<br />"); }
range方法会返回一个迭代器,然后可以在一个for里进行使用。您会发现这个模型和.NET或是Java里的迭代器都不一样,它们在遍历过程中使用的都是同一个迭代器,而在我的模型中,一个迭代器其实更像是一个单向链表,它包含两个成员,value字段用于表示当前的值,next方法则返回下一个节点。这么做的原因是,我比较懒的写一些包含副作用的逻辑,因为维护状态实在是一件麻烦的事情,远不如创建并返回新对象来的简单。
如果使用“创建数组”的方法来实现一个迭代器,那么range的确很简单:
// JavaScript function ArrayIterator(array, index) { this.value = array[index]; this._array = array; this._index = index; } ArrayIterator.prototype.next = function () { var newIndex = this._index + 1; if (newIndex >= this._array.length) return null; return new ArrayIterator(this._array, newIndex); } function range(minInclusive, maxExclusive) { var array = []; for (var i = minInclusive; i < maxExclusive; i++) { array.push(i); } return new ArrayIterator(array, 0); }
这段代码您一定能够理解,我就不多做解释了。这种做法的优势在于十分容易实现,但是缺点也很明显,之前已经谈过就不再重复了。
题目要求
那么,我们又能否为JavaScript添加“生成器”?我的意思是,像yield那样的生成器。要求很简单,只要能用它实现最简单的功能即可,例如:
// C# public static IEnumerable<int> OneToThree() { yield return 1; yield return 2; yield return 3; }
如果您觉得实现这个非常简单,不妨再尝试着使用更好的做法来实现刚才的range函数。此外,您也可以实现如刚才C#的Infinite那样的无限数列,或者……那著名的斐波那契数列也可以咯。这样“求出斐波那契数列中,所有N以内的元素之和”便可以简单地:
function fibSeq() { /* ... */ } function sumOfFib(max) { return toIter(fibSeq()).takeWhile(function (i) { return i <= max}).sum(); }
如何,一起来尝试一下吧!
沙发我来做。