2015年12月10日 星期四

JavaScript 迭代器與產生器的介紹

處理一個集合中每一項是很常見的操作。JavaScript 提供了好幾種方法來迭代一個集合,從簡單的 for 和 for each 循環至 map(),filter() 和 array comprehensions。 迭代器和產生器,在 JavaScript 1.7 中, 迭代器的概念屬於核心語言中的重點,並提供了一種機制來定義 for...of 循環。
迭代器

迭代器是一個物件,知道如何存取物品從一個集合一次取出一項, 而跟蹤它的當前序列所在的位置。在  JavaScript 中 迭代器是一個物件,它提供了一個 next() 方法返回序列中的下一個項目。當這個序列消亡時這個方法可以隨時拋出一個StopIteration exception(異常)。

一旦新增,迭代器物件可以顯式地通過不斷呼叫 next(),或隱式地使用 JavaScript 的 for...in  和 for each 構造。

簡單的迭代器物件和陣列可以使用 Iterator() 函式新增(下面是一個簡單的對像):

var lang = { name: 'JavaScript', birthYear: 1995 };
var it = Iterator(lang);

一旦初始化,next()方法可以用來依次訪問物件中的鍵-值:

var pair = it.next(); // Pair is ["name", "JavaScript"]
pair = it.next(); // Pair is ["birthYear", 1995]
pair = it.next(); // A StopIteration exception is thrown

一個 for...in 循環結構可以直接取代next()方法的呼叫。 當StopIteration exception異常拋出時這個循環會自動終止。

var it = Iterator(lang);
for (var pair in it)
  print(pair); // prints each [key, value] pair in turn

假如我們只想迭代一個物件的 keys 時,我們可以通過把第二個參數設置為 true 來實現:

var it = Iterator(lang, true);
for (var key in it)
  print(key); // prints each key in turn

使用 Iterator() 來訪問物件內容的優點是對於那些已經加入物件的自定義屬性(不用管屬性名,一股腦的訪問,或者只訪問屬性,上面就是這樣)。它的原型不會包含在序列中。

Iterator() 也可以用於陣列:

var langs = ['JavaScript', 'Python', 'C++'];
var it = Iterator(langs);
for (var pair in it)
  print(pair); // prints each [index, language] pair in turn

基於物件,通過傳遞true作為第二個參數,將會導致迭代結果發生陣列索引上益(會嗎?我也沒搞明白,你知道的話請告訴我):

var langs = ['JavaScript', 'Python', 'C++'];
var it = Iterator(langs, true);
for (var i in it)
  print(i); // prints 0, then 1, then 2

也可以指定塊作用域變數(let是個javascript1.7的關鍵字,可以使用 let 建立只存在於 for 循環上下文中的變數)包括索引和值(index and value)在for…in循環中使用let關鍵字和非結構化賦值:

var langs = ['JavaScript', 'Python', 'C++'];
var it = Iterator(langs);
for (let [i, lang] in it)
 print(i + ': ' + lang); // prints "0: JavaScript" etc.

定義自定義迭代器

某些物件迭代集合的項目時應該使用特定的方式迭代。

    迭代一個序列物件時應該是一個接著一個。
    迭代一棵樹時應該使用深度優先或者廣度優先方式。
    迭代一個資料庫查詢結果物件時應該是一條一條地迭代,即使整個結果並沒有被加載到一個陣列中。
    一個迭代器在一個無限的數學序列(如斐波那契序列)應該能夠一個一個地返回結果而不新增一個無限長度的資料結構。

JavaScript可以讓你編寫程式碼來表示自定義迭代邏輯並鏈接到一個物件。

我們來新增一個簡單的序列物件用來存放low和high。

function Range(low, high){
  this.low = low;
  this.high = high;
}

現在我們要新增一個迭代器,可以返回這個序列中的一序列包容性的整數,這個迭代器介面要求我們我們實現一個next()方法,這個next()方法返回這個序列或者拋出一個StopIteration exception異常。

function RangeIterator(range){
  this.range = range;
  this.current = this.range.low;
}
RangeIterator.prototype.next = function(){
  if (this.current > this.range.high)
    throw StopIteration;
  else
    return this.current++;
};

我們的RangeIterator被一個序列範例所序列化,並且維持它自己當前的屬性屬性所在位置。

最後,為了RangeIterator與Range序列物件,我們需要給Range寫一個特殊的__iterator__方法,當我們試著迭代這個Range序列時會呼叫這個方法,並且應該返回一個RangeIterator迭代器範例。

Range.prototype.__iterator__ = function(){
  return new RangeIterator(this);
};

下面就寫段程式碼來實驗下我們自定義的迭代器吧:

var range = new Range(3, 5);
for (var i in range)
  print(i); // prints 3, then 4, then 5 in sequence

產生器(Generators): 一個更好的方法來構建迭代器

雖然迭代器是一個有用的工具,但是由於需要顯示地維持他們的內部狀態,所以他們的構造需要仔細的規劃(看得我眼花呀)。產生器給你提供了一個強大的選擇:它允許你通過寫一個可以存檔自己狀態的的簡單函式來定義一個迭代算法。

一個產生器其實是一種特殊類型的函式(這個函式作為一個為迭代器工作的工廠),一個函式如果它裡面包含了一個或一個以上的yield表達式,那麼這個函式就成為一個產生器了。

Note: 這個yield關鍵字只能被包含在下面的程式碼快中才有用 <script type="application/javascript;version=1.7">  (或者更高版本).XULscripts標記訪問這些功能不需要這個特殊的塊。

當一個產生器函式被一個函式體呼叫時並不會馬上執行;相反,它會返回一個generator-iterator物件。每次呼叫generator-iterator的next()方法將會執行這個函式體至下一個yield表達式並且返回一個結果。當函式執行完或者執行到一個return時拋出一個StopIteration exception異常。

用一個案例來闡述:

function simpleGenerator(){
  yield "first";
  yield "second";
  yield "third";
  for (var i = 0; i < 3; i++)
    yield i;
}

var g = simpleGenerator();
print(g.next()); // prints "first"
print(g.next()); // prints "second"
print(g.next()); // prints "third"
print(g.next()); // prints 0
print(g.next()); // prints 1
print(g.next()); // prints 2
print(g.next()); // StopIteration is thrown

一個產生器函式可以直接用作為一個類的__iterator__方法,大大的減少了新增一個自定義迭代器的程式碼量,下面是Range重寫成一個產生器:

function Range(low, high){
  this.low = low;
  this.high = high;
}
Range.prototype.__iterator__ = function(){
  for (var i = this.low; i <= this.high; i++)
    yield i;
};
var range = new Range(3, 5);
for (var i in range)
  print(i); // prints 3, then 4, then 5 in sequence

並不是所有的產生器都會終止;它也可以新增一個無窮序列的產生器。下面實現了斐波納契數列的產生器:

function fibonacci(){
  var fn1 = 1;
  var fn2 = 1;
  while (1){
    var current = fn2;
    fn2 = fn1;
    fn1 = fn1 + current;
    yield current;
  }
}

var sequence = fibonacci();
print(sequence.next()); // 1
print(sequence.next()); // 1
print(sequence.next()); // 2
print(sequence.next()); // 3
print(sequence.next()); // 5
print(sequence.next()); // 8
print(sequence.next()); // 13

產生器可以有參數,但被限制在函式第一次呼叫時。產生器可以通過一個return語句來終止(因為他們將拋出一個topIteration exception)。下面是一個變異的fibonacci()函式有一個limit參數,一旦滿足條件將終止。

function fibonacci(limit){
  var fn1 = 1;
  var fn2 = 1;
  while (1){
    var current = fn2;
    fn2 = fn1;
    fn1 = fn1 + current;
    if (limit && current > limit)
      return;
    yield current;
  }
}

高級產生器

產生器按照要求產生values,這樣可以高效的表示序列,這點對於小算盤來說很重要,上面的無窮序列就是一個很好的證明。

除了next()方法,generator-iterator物件也有一個send()方法可以用來修改產生器的內部狀態。傳遞一個值給send()將被視為最後一個yield表達式的結果(產生器暫停)。你必須在你使用send(參數)前通過呼叫next()來啟動產生器。

這裡是斐波那契產生器使用send()來重新啟動序列:

function fibonacci(){
  var fn1 = 1;
  var fn2 = 1;
  while (1){
    var current = fn2;
    fn2 = fn1;
    fn1 = fn1 + current;
    var reset = yield current;
    if (reset){
        fn1 = 1;
        fn2 = 1;
    }
  }
}

var sequence = fibonacci();
print(sequence.next());     // 1
print(sequence.next());     // 1
print(sequence.next());     // 2
print(sequence.next());     // 3
print(sequence.next());     // 5
print(sequence.next());     // 8
print(sequence.next());     // 13
print(sequence.send(true)); // 1
print(sequence.next());     // 1
print(sequence.next());     // 2
print(sequence.next());     // 3

注意:有意思的一點是,呼叫 send(undefined) 和呼叫 next() 是完全同等的。不過,當呼叫 send() 方法啟動一個新的產生器時,除了 undefined 其它的值都會拋出一個 TypeError 異常。.

你可以呼叫 throw 方法並且傳遞一個它應該拋出的異常值來強制產生器拋出一個異常。此異常將從當前上下文拋出並暫停產生器,類似當前的 yield 執行,只不過換成了 throw value 語句。

如果在拋出異常的處理過程中沒有遇到 yield ,該異常將會被傳遞直到呼叫 throw() 方法,並且隨後呼叫 next() 將會導致 StopIteration 異常被拋出。

產生器擁有一個 close() 方法來強制產生器結束。結束一個產生器會產生如下影響:

    所有產生器中有效的 finally 字句將會執行
    如果 finally 字句拋出了除 StopIteration 以外的任何異常,該異常將會被傳遞到 close() 方法的呼叫者
    產生器會終止

產生器表達式

在 JavaScript 1.8 引入

陣列推導式的一個明顯缺點是,它們會導致整個陣列在記憶體中構造。當輸入到推導式的本身是個小陣列時它的開銷是微不足道的--但是,當輸入陣列很大或者新增一個新的昂貴(或者是無限的)陣列產生器時就可能出現問題。

產生器允許對序列延遲計算(lazy computation),在需要時按需計算元素。產生器表達式在句法上幾乎和陣列推導式相同--它用圓括號來代替方括號(而且用 for...in 代替 for each...in)--但是它新增一個產生器而不是陣列,這樣就可以延遲計算。你可以把它想像成新增產生器的簡短語法。

假設我們有一個迭代器 it 來迭代一個巨大的整數序列。我們需要新增一個新的迭代器來迭代偶數。一個陣列推導式將會在記憶體中新增整個包含所有偶數的陣列:

var doubles = [i * 2 for (i in it)];

而產生器表達式將會新增一個新的迭代器,並且在需要的時候按需來計算偶數值:

var it2 = (i * 2 for (i in it));
print(it2.next()); // The first value from it, doubled
print(it2.next()); // The second value from it, doubled

當一個產生器被用做函式的參數,圓括號被用做函式呼叫,意味著最外層的圓括號可以被省略:

var result = doSomething(i * 2 for (i in it));

沒有留言:

張貼留言