JavaScript优化循环
循環是所有編程語言中最爲重要的機制之一，幾乎任何擁有實際意義的計算機程序(排序、查詢等)都裏不開循環。而循環也正是程序優化中非常讓人頭疼的一環，我們往往需要不斷去優化程序的複雜度，卻因循環而糾結在時間複雜度和空間複雜度之間的抉擇。
在 JavaScript 中，有3種原生循環，for () {}, while () {}和do {} while ()，其中最爲常用的要數for () {}。
然而for正是 JavaScript 工程師們在優化程序時最容易忽略的一種循環。
我們先來回顧一下for的基本知識。
JavaScript 的for語法繼承自C語言，for循環的基本語法有兩種使用方法。
1. 循環數組
for循環的基本語法
for ( /* 初始化 */; /* 判斷條件 */; /* 循環處理 */ ) {
//... 邏輯代碼
}
我們以一段實例代碼來進行詳細說明。
var array = [1, 2, 3, 4, 5];
var sum = 0;
for (var i = 0, len = array.length; i < len; ++i) {
sum += array[i];
}
console.log('The sum of the array\'s items is %d.', sum);
//=> The sum of the array's items is 15.
在這段代碼中，我們首先定義並初始化了一個用存儲待累加項的數組和一個總和整形變量。接下來，我們開始進行循環。在該for循環的初始化代碼中，我們也定義並初始化了兩個變量：i(計數器)和len(循環數組長度的別名)，當i小於len時，循環條件成立，執行邏輯代碼；每次邏輯代碼執行完畢以後，i自增1。
在循環的邏輯代碼中，我們把當前循環的數組項加到總和變量中。
這個循環用流程圖表示爲如下。
從這個流程圖中我們不難發現，程序中真正的循環體不僅有我們的邏輯代碼，還包含了實現循環自身的執行判斷和循環處理。
這樣，我們的優化思路就清晰了，我們可以從四個方面進行優化。
循環體前的初始化代碼
循環體中的執行判斷條件
邏輯代碼
邏輯代碼後的處理代碼
PS: 其中第一點和第二點存在重要關係。
1.1 優化初始化代碼和執行判斷條件
我們先來看看一段大家都非常熟悉的代碼。
// Wrong!
for (var i = 0; i < list.length; ++i) {
//... 邏輯代碼
}
相信現在大部分寫着 JavaScript 的工程師依然使用着這段看似很正常的循環方法，但爲什麼我在這裏說它是錯誤的呢？
我們把這個循環的所有東西都拆開來看看：
初始化代碼 - 這段循環只定義並初始化了一個計數器變量。
執行判斷條件 - 當計數器小於list的長度時成立。
處理代碼 - 計數器自增1。
我們再回顧一下上面的流程圖，發現有什麼倪端沒？
真正的循環體不僅有我們的邏輯代碼，還包含了實現循環自身的執行判斷和處理代碼。也就是說，i < list.length這個判斷條件是每一次循環前都要執行的。而 JavaScript 中，對對象的屬性或方法進行讀取時，需要進行一次查詢。
似乎明白了點什麼了吧？這個判斷條件存在兩個操作：1. 從list數組中查詢length屬性；2. 比較i與list.length的大小。
假設list數組含有 n 個元素，則程序需要在這個循環的執行判斷中進行 2n 次操作。
如果我們把代碼改成這樣：
// Well
for (var i = 0, len = list.length; i < len; ++i) {
//...
}
在這段改進後的代碼中，我們在循環體執行前的初始化代碼中，增加定義並初始化了一個len變量，用於存儲list.length的值(關於變量、表達式、指針和值的相關內容將在第二篇中討論)。這樣，我們在循環體中的執行判斷中就無需再次對list數組進行屬性查詢，操作數爲原先的一半。
以上步驟我們完善了算法的時間複雜度，而如果要繼續優化空間複雜度的話，要如何做呢？如果你的邏輯代碼不受循環順序限制，那你可以嘗試以下優化方式。
for (var i = list.length - 1; i >= 0; --i) {
//...
}
這段代碼通過把循環順序倒置，把i計數器從最後一個元素下標(list.length - 1)開始，向前循環。以達到把循環所需變量數減到 1 個，而且在執行判斷中，降低了變量查詢的次數，減少了執行 CPU 指令前的耗時。
1.2 優化邏輯代碼
在循環中，我們得到循環當前的數組元素自然是爲了對其或利用其進行一些操作，這不免會出現對該元素數次的調用。
var array = [
{ name: 'Will Wen Gunn', type: 'hentai' },
{ name: 'Vill Lin', type: 'moegril' }
];
for (var i = array.length - 1; i >= 0; --i) {
console.log('Name: %s', array[i].name);
console.log('He/She is a(n) %s', array[i].type);
console.log('\r\n');
}
/*=>
Name: Vill Lin
He/She is a(n) moegril
Name: Will Wen Gunn
He/She is a(n) hentai
*/
這段代碼中，程序需要對每個數組元素的name和type屬性進行查詢。如果數組有 n 個元素，程序就進行了 4n 次對象查詢。
1. array[i] 2. array[i].name 3. array[i] 4. array[i].type
相信此時你一定想到了解決方法了吧，那就是把當前數組元素的值賦值到一個變量中，然後在邏輯代碼中使用它。
var array = [
{ name: 'Will Wen Gunn', type: 'hentai' },
{ name: 'Vill Lin', type: 'moegril' }
];
var person = null;
for (var i = array.length - 1; i >= 0 && (person = array[i]); --i) {
console.log('Name: %s', person.name);
console.log('He/She is a(n) %s', person.type);
console.log('\r\n');
}
person = null;
這樣看起來的確美觀了不少。
1. array[i] => var person 2. person.name 3. person.type
有點像 EMCAScript5 中的forEach，不過這兩者之間差別很大，這裏不多做解釋。
PS：感謝大家的指正，經過實驗得知，如果數組內的元素是直接傳值定義的，則在循環中得到值一定是值，而非指針。 所以無論是定義表達式還是變量，都會有額外的內存空間請求。
1.3 優化處理代碼
實際上，循環體中的處理代碼並沒有太多東西可以進行優化，i計數器也就是自增1就足夠了。
PS：如果有什麼好的建議或方法，歡迎提供。:)
2. 循環對象(Object)
在 JavaScript 中，for還可以對 Object 的屬性和方法進行歷遍。需要注意的是，for循環無法對對象所屬的包裝類型或是構造函數中原型屬性、方法(prototype)進行歷遍。
語法比循環數組還要簡單。
for (/* 初始化 */ var key in object) {
//... 邏輯代碼
}
我們常常這個方法來進行對對象的操作。
var person = {
'name' : 'Will Wen Gunn',
'type' : 'hentai',
'skill' : ['Programming', 'Photography', 'Speaking', 'etc']
};
for (var key in person) {
value = person[key];
// if the value is array, convert it to a string
if (value instanceof Array) {
value = value.join(', ');
}
console.log('%s: %s', key, value);
}
/*=>
name: Will Wen Gunn
type: hentai
skill: Programming, Photography, Speaking, etc
*/
如果你曾使用過 MongoDB，那你對它的 Query 機制絕對不會陌生。因爲 MongoDB 的 Query 機制就像是它的 API 的靈魂，靈活的 CURD 操作方式爲 MongoDB 贏得了不少人氣和發展動力。
而在 NanoDB 的 Mongo API 實現中，Query 的實現方式就大面積地使用了循環對象。
var myDB = nano.db('myDB');
var myColl = myDB.collection('myColl');
var _cursor = myColl.find({
type : 'repo',
language : 'JavaScript'
});
_cursor
.sort({
star: 1
})
.toArray(function(err, rows) {
if (err)
return console.error(err);
console.log(rows);
});
而我們需要優化的，並非循環本身，而是對你需要進行歷遍的對象進行優化。
就比如說 NanoDB 中的 NanoCollection 類，雖然表面看上去就是一個數組，存有所有的元素，或是一個對象，用元素的 ID 作爲鍵，然後對元素進行存儲。
但事實並非如此，曾經使用過 Underscore 的同學應該會知道其中的_.invert方法。這是一個相當有趣的方法，它把所傳入的對象的鍵與值反過來。
var person = {
'name' : 'Will Wen Gunn',
'type' : 'hentai'
};
var _inverted = _.invert(person);
console.log(_inverted);
/*=>
{
'Will Wen Gunn' : 'name',
'hentai' : 'type'
}
*/
如果你是需要使用循環對象來對對象的某些屬性的值進行查詢，那你就可以嘗試一下以下方法。
var person = {
'name' : 'Will Wen Gunn',
'type' : 'hentai'
};
var name = 'Will Wen Gunn';
var _inverted = _.invert(person);
if (_inverted[name] === 'name') {
console.log('Catched!');
}
//=> Catched!
然而利用for進行對象查詢並沒有太大的可優化之處，一切都還需從實際需求出發。: P
接下來我們來看看其他兩種循環，while () {}和do {} while ()。相信任何接收過計算機科學課程的朋友都這兩個循環都不會陌生。他們唯一的區別就在與執行循環體的邏輯順序。
while () {}的執行順序與for () {}類似，執行判斷在邏輯代碼之前，不過省去了初始化和處理代碼。
當給予的條件時，便執行邏輯代碼，直到條件不再成立爲止。
var sum = 0;
while (sum < 10) {
sum += sum + 1;
}
console.log(sum);
//=> 15
do {} while ()則是把執行判斷放到了邏輯代碼之後，也就是“先斬後奏”。
var sum = 0;
do {
sum += sum + 1;
} while (sum < 10);
console.log(sum);
//=> 15
while () {}與do {} while ()同樣不需要計數器，而是通過某些條件來判斷是否執行或繼續執行邏輯代碼。
3. while () {}和do {} while ()
while () {}和do {} while ()主要用於業務邏輯中，爲達到某一目的而不斷執行一系列操作，如任務隊列。
但這兩種循環是危險的，因爲它們默認只受執行條件的控制，如果一旦邏輯代碼內一直沒有對執行判斷產生任何影響，就會出現死循環。
var sum = 0;
// WARNING!
while (sum < 10) {
sum = 1 + 1;
}
這樣的代碼無異於while (true) {}，所以在使用之前，必須明確執行條件和如何對執行條件產生影響的方法。
4. 善用循環控制語句
相信所有 JavaScript 工程師都使用過break語句，但continue語句卻相對少用。實際上，在不少優秀的 JavaScript 開源項目中，都能發現continue的身影。
爲了地瞭解continue語句的作用，我們還是先來看看一段實例代碼。
// Node.js Broadcast Server
var net = require('net');
var util = require('util');
var broadcastServer = net.createServer();
// Client Store
broadcastServer.clients = [];
// Clients Broadcast Method
net.Socket.prototype.broadcast = function(msg) {
var clients = broadcastServer.clients;
// 獲得發佈廣播的客戶端在集閤中的下標
var index = clients.indexOf(this);
for (var i = clients.length - 1; i >= 0; --i) {
if (i === index) {
// 如果爲發佈廣播的客戶端，則結束當前循環體
continue;
}
currClient = clients[i];
if (!currClient.destroyed) {
currClient.write(
util.format(
'\r[Echo Client %s:%d] %s\nInput: ',
currClient.remoteAddress, currClient.remotePort, msg)
);
}
}
};
// A new client connected
broadcastServer.on('connection', function(client) {
broadcastServer.clients.push(client);
// Welcome
client.write('[Broadcast Server] Welcome!\nInput:');
client.broadcast(client, 'Joined!');
// Message handle
client.on('data', function(msg) {
client.broadcast(msg);
client.write('\rInput:');
});
// Disconnect handle
client.on('end', function() {
client.broadcast('Left!');
})
});
// Bind
broadcastServer.listen(8080, function() {
console.log('Broadcast Server bound.');
});
這段代碼基於 Node.js 的net模塊實現了一個 Broadcast Server，在其中的broadcast方法中，我們使用了continue語句，用以實現將信息向除發佈廣播的客戶端外的所有已建立連接的客戶端。
代碼內容相當簡單，當某一客戶端需要向其他客戶端發佈廣播時，則調用該客戶端所對應client對象的broadcast方法，在broadcast方法中，程序會先獲取當前客戶端在以緩存的客戶端 Socket 集合中的位置下標，然後對所有客戶端 Socket 進行循環發佈，當循環計數器來到之前獲得的位置下標，則跳過當前循環體中的邏輯代碼，繼續下一個循環。
相信學習過 C/C++ 語言的工程師都會從各種地方得到這樣一個忠告：“不要使用 goto 語句。”
而這個“臭名詔著”的goto語句其實就是一個代碼流程控制器，關於goto語句的詳細內容這裏不會詳細說明。然而 JavaScript 沒有明顯的goto語句，但從break語句和continue語句中，不難發現 JavaScript 中goto的影子。
這是因爲break語句和continue語句允許接受由一個定義好的 label 名稱，以進行代碼跳轉。
我們來看看 MDN 提供的實例代碼。
var i, j;
loop1:
for (i = 0; i < 3; i++) { //The first for statement is labeled "loop1"
loop2:
for (j = 0; j < 3; j++) { //The second for statement is labeled "loop2"
if (i == 1 && j == 1) {
continue loop1;
} else {
console.log("i = " + i + ", j = " + j);
}
}
}
// Output is:
// "i = 0, j = 0"
// "i = 0, j = 1"
// "i = 0, j = 2"
// "i = 1, j = 0"
// "i = 2, j = 0"
// "i = 2, j = 1"
// "i = 2, j = 2"
// Notice how it skips both "i = 1, j = 1" and "i = 1, j = 2"
在這段實例代碼中，實現了兩層循環，而在每層循環外都定義了一個label，用於之後的continue語句進行調用。
第一層循環在loop1的 label 中，也就是說在後面的程序中，如果在continue語句或break語句選擇了loop1 label，就會跳出最外層循環。
第二層循環在頂層循環中的loop2的 label 中，若在continue語句或break語句中選擇了loop2 label，就會回到頂層循環的循環體內。
通過使用循環控制語句，我們可以對原有的循環執行判斷進行干涉，以至於可以構建出十分複雜的邏輯系統。說句題外話，Linux kernel 中有非常多的goto語句，至於爲什麼還是能經常聽到不要用goto語句之流的言論，就自己 Google 吧。
5. 高級循環
5.1 展開循環
我們先來看看兩段代碼，你猜猜哪一個的性能更加。
// Setup
var array = [
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"],
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"],
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"],
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"],
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"],
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"],
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"],
["DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA", "DATA"]
];
function process(item) {
// Do something with item
}
// Case 1
for (var i = array.length - 1; i >= 0; i--) {
for (var j = array[i].length - 1; j >= 0; i--) {
process(array[i][j]);
}
}
// Case 2
for (var i = array.length - 1; i >= 0; i = i - 4) {
for (var j = array[i].length - 1; j >= 0; j = j - 6) {
process(array[i][j]);
process(array[i][j - 1]);
process(array[i][j - 2]);
process(array[i][j - 3]);
process(array[i][j - 4]);
process(array[i][j - 5]);
}
for (var j = array[i - 1].length - 1; j >= 0; j = j - 6) {
process(array[i][j]);
process(array[i][j - 1]);
process(array[i][j - 2]);
process(array[i][j - 3]);
process(array[i][j - 4]);
process(array[i][j - 5]);
}
for (var j = array[i - 2].length - 1; j >= 0; j = j - 6) {
process(array[i][j]);
process(array[i][j - 1]);
process(array[i][j - 2]);
process(array[i][j - 3]);
process(array[i][j - 4]);
process(array[i][j - 5]);
}
for (var j = array[i - 3].length - 1; j >= 0; j = j - 6) {
process(array[i][j]);
process(array[i][j - 1]);
process(array[i][j - 2]);
process(array[i][j - 3]);
process(array[i][j - 4]);
process(array[i][j - 5]);
}
}
我需要對array中的所有子數組的元素進行歷遍，有兩種方案，一種是我們平常所使用的方法，另一種是把循環任務展開。答案是 Case 2 性能更好，因爲在每 6 個元素之間的執行判斷都全部刪除了，自然比往常的都要快。
這裏我們來看看一種更給力的解決方案。如果一個業務環節中需要對大數據集進行迭代處理，而這個數據集從開始迭代起，數據量不會再改變，那麼可以考慮採用一種名爲 Duff 裝置的技術。這項技術是以其的創造者 Tom Duff 的名字來命名的，這項技術最先實現於 C 語言。後來 Jeff Greenberg 將其移植到 JavaScript 中，並經過 Andrew B. King 修改並提出了一種更爲高效的版本。
//credit: Speed Up Up Your Site (New Riders, 2003)
var iterations = Math.floor(values.length / 8);
var leftover = values.length % 8;
var i = 0;
if (leftover > 0) {
do {
process(values[i++]);
} while (--leftover > 0);
}
do {
process(values[i++]);
process(values[i++]);
process(values[i++]);
process(values[i++]);
process(values[i++]);
process(values[i++]);
process(values[i++]);
process(values[i++]);
} while (--iterations > 0);
這種技術的工作原理是通過計算values的長度除以 8 以得到需要迭代的次數，並以Math.floor()函數來保證結果爲整數，然後再計算不能被 8 整除時的餘數，並對這些元素單獨進行處理，其餘則 8 次爲單次展開次數來進行迭代。
我將這種裝置再加以封裝，可以得到一種帶有異步味道的 API。
function duff(array, mapper) {
var n = Math.floor(array.length / 8);
var l = array.length % 8;
var i = 0;
if (l > 0) {
do {
mapper(array[i++]);
} while (--i > 0);
}
do {
mapper(array[i++]);
mapper(array[i++]);
mapper(array[i++]);
mapper(array[i++]);
mapper(array[i++]);
mapper(array[i++]);
mapper(array[i++]);
mapper(array[i++]);
} while (--n > 0);
}
duff([...], function(item) {
//...
});
這裏是一組對於以上三種迭代解決方案的性能測試及其結果。http://jsperf.com/spreaded-loop
5.2 非原生循環
在任何編程語言中，能夠實現循環的，不止語言所提供的原生循環語句，還可以通過其他方式來間接實現。
讓我們先來溫習一下高中數學的一點內容——數列的通項公式。
bacause
a[1] = 1
a[n] = 2 * a[n - 1] + 1
so
a[n] + 1 = 2 * a[n - 1] + 2
= 2 * (a[n - 1] + 1)
(a[n] + 1) / (a[n - 1] + 1) = 2
then
a[n] + 1 = (a[n] + 1) / (a[n - 1] + 1) * (a[n - 1] + 1) / (a[n - 2] + 1) * ... * (a[2] + 1) / (a[1] + 1) * (a[i] + 1)
a[n] + 1 = 2 * 2 * ... * 2 * 2
a[n] + 1 = 2^n
a[n] = 2^n - 1
final
a[n] = 2^n - 1
看了上面這段簡單的演算，估計你也猜到我們將要討論的內容了吧。是的，我們還可以使用遞歸來實現循環。
遞歸是數學和計算機科學中非常重要的一種應用方法，它是指函數在其使用時調用其自身。
在 Node.js 社區中，遞歸被用來實現一種非常重要的技術：中間件技術。這是一段尚未公佈的新版本的 webjs 中的中間件實現代碼。
/**
* Middlewares run method
* @param {String} url Current request url
* @param {Object} req the request object
* @param {Object} res the response object
* @param {Function} out Complete Callback
* @return {Function} the server
*/
server.runMiddlewares = function(url, req, res, out) {
var index = -1;
var middlewares = this._usingMiddlewares;
// run the next middleware if it is exists
function next(err) {
index++;
// current middleware
var curr = middlewares[index];
if (curr) {
var check = new RegExp(curr.route);
// Check the route
if (check.test(url)) {
try {
function later() {
debug('A middleware says it need to be later on %s', url);
// The dependencies do not right now
if (middlewares.indexOf(curr) !== middlewares.length - 1) {
_later(curr);
index--;
next();
} else {
debug('A middleware dependencies wrong');
// This middleware can not run
out();
}
}
// Run the middleware
if (utils.isFunc(curr.handler)) {
// Normal middleware function
curr.handler(req, res, next, later);
} else if (utils.isObject(curr.handler) && utils.isFunc(curr.handler.emit)) {
// Server object
curr.handler.emit('request', req, res, next, later);
} else {
// There are something wrong about the middleware
next();
}
} catch(err) {
next();
}
} else {
next();
}
} else {
// Out to next step of the pipeline
out();
}
}
// if the middleware depend on other middlewares,
// it can let it later to run
function _later(curr) {
var i = middlewares.indexOf(curr);
var _tmp1 = middlewares.slice(0, i);
_tmp1.push(middlewares[i + 1], curr);
var _tmp2 = middlewares.slice(i + 2);
[].push.apply(_tmp1, _tmp2);
middlewares = _tmp1;
}
// first middleware
next();
return this;
};
雖然這段代碼看上去很複雜，不過如果我們對其精簡之後，就清晰許多了。
server.runMiddlewares = function(url, req, res, out) {
var index = -1;
var middlewares = this._usingMiddlewares;
// run the next middleware if it is exists
function next(err) {
index++;
// current middleware
var curr = middlewares[index];
if (curr) {
var check = new RegExp(curr.route);
// Check the route
if (check.test(url)) {
// run the current middleware
curr.handler(req, res, next);
} else {
next();
}
} else {
// Out to next step of the pipeline
out();
}
}
// first middleware
next();
return this;
};
遞歸之所以可以用於中間件系統的實現，是因爲遞歸是最適合 Node.js 中異步 I/O 的程序流程響應方式。
在這段中間件實現代碼中，this._usingMiddlewares爲循環數組，function next()是循環體，其中check.test(url)爲執行判斷條件，而循環處理代碼就是循環體中最前面的index計數器自增 1 和next函數自身的遞歸調用。
建议继续学习：
- 在C++中实现foreach循环，比for_each更简洁！ (阅读：8625)
- for 循环为何可恨？ (阅读：4457)
- 循环、迭代、遍历和递归 (阅读：4452)
- C/C++循环获取文件中的每行数据（别以为很简单！） (阅读：3878)
- 优化次数过多的循环 (阅读：2650)
- 数组的优化循环展开与分割 (阅读：2487)
- Loop Benchmarks (阅读：2387)
- Perl6有用的和有意思的循环 (阅读：1974)
- iOS下自己动手造无限循环图片轮播 (阅读：1915)
扫一扫订阅我的微信号：IT技术博客大学习
- 作者：Will Wen Gunn 来源： Life Map
- 标签： 循环
- 发布时间：2015-01-20 23:12:37
-
[54] IOS安全–浅谈关于IOS加固的几种方法 -
[52] android 开发入门
-
[52] 如何拿下简短的域名
-
[51] 图书馆的世界纪录
-
[49] Oracle MTS模式下 进程地址与会话信
-
[49] Go Reflect 性能
-
[47] 【社会化设计】自我（self）部分――欢迎区
-
[46] 读书笔记-壹百度:百度十年千倍的29条法则
-
[36] 程序员技术练级攻略
-
[29] 视觉调整－设计师 vs. 逻辑
