for...in迴圈在運行時出錯了錯誤,並沒有要求枚舉對象的修改與當前保持一致。事實上,ES對併發修改在不同js環境下的行為的規範留有餘地。標準規定: 如果被枚舉的對象在枚舉期間添加了新的屬性,那麼在枚舉期間並不能保證新添加的屬性能被訪問。 上面規範的實際後果:如果我們修改了被枚舉的對象,則不能保證... ...
註冊列表示例
一個社交網路有一組成員,每個成員有一個存儲其朋友信息的註冊列表。
function Member(name){
this.name=name;
this.friends=[];
}
var a=new Member('鐘二'),
b=new Member('張三'),
c=new Member('趙四'),
d=new Member('王五'),
e=new Member('阮六'),
f=new Member('耿七');
a.friends.push(b);
b.friends.push(c);
c.friends.push(e);
d.friends.push(b);
e.friends.push(d,f);
搜索該網路意味著需要遍歷該社交網路圖。
通常通過工作集來實現。工作集以單個根節點開始,然後添加發現的節點,移除訪問過的節點。
for...in遍歷圖
使用for...in迴圈來實現該遍歷是很方便的。
Member.prototype.inNetwork=function(other){
var visited={};
var workset={};
workset[this.name]=this;
for(var name in workset){
var member=workset[name];
delete workset[name];
if(name in visited){
continue;
}
visited[name]=member;
if(member===other){
return true;
}
member.friends.forEach(function(friend){
workset[friend.name]=friend;
});
}
return false;
}
上面代碼有什麼問題嘛?在大多環境下可以工作,但有一些環境這段代碼就不能工作了。
a.inNetwork(f);//false
這裡為什麼呢。這裡說明for...in迴圈在運行時出錯了錯誤,並沒有要求枚舉對象的修改與當前保持一致。事實上,ES對併發修改在不同js環境下的行為的規範留有餘地。標準規定:
如果被枚舉的對象在枚舉期間添加了新的屬性,那麼在枚舉期間並不能保證新添加的屬性能被訪問。
上面規範的實際後果:如果我們修改了被枚舉的對象,則不能保證for...in迴圈的行為是可預見的。
另一種遍歷圖
自己管得迴圈控制。當使用迴圈時,應該使用自己的字典抽象以避免原型污染。可以將字典放置在WorkSet類中來追蹤當前集合中的元素數量。
function WorkSet(){
this.entries=new Dict();
this.count=0;
}
WorkSet.prototype.isEmpty=function(){
return this.count===0;
};
WorkSet.prototype.add=function(key,val){
if(this.entries.has(key)){
return;
}
this.entries.set(key,val);
this.count++;
};
WorkSet.prototype.get=function(key){
return this.entries.get(key);
};
WorkSet.prototype.remove=function(key){
if(!this.entries.has(key)){
return;
}
this.entries.remove(key);
this.count--;
};
為了提取集合的任意一個元素,給Dict類添加一個新方法
Dict.prototype.pick=function(){
for(var key in this.elements){
if(this.has(key)){
return key;
}
}
throw new Error('empty dictionary');
};
WorkSet.prototype.pick=function(){
return this.entries.pick();
};
下麵改寫上一版本的inNetwork方法,這裡使用while來迴圈。每次選擇任意一個元素並從工作集中刪除。
Member.prototype.inNetwork=function(other){
var visited={};
var workset=new WorkSet();
workset.add(this.name,this);
while(!workset.isEmpty()){
var name=workset.pick();
var member=workset.get(name);
workset.remove(name);
if(name in visited){
continue;
}
visited[name]=member;
if(member === other){
return true;
}
member.friends.forEach(function(friend){
workset.add(friend.name,friend);
})
}
return false;
};
其中pick方法是一個不確定性的例子。不確定性是指一個操作並不能保證使用語言的主義產生一個單一的可預見的結果。這個不確定性是因為for...in迴圈可能在不同的js環境中選擇不同的枚舉順序。使用不確定性可能會使你的程式引入一個不可預測的元素。測試可能在某個平臺通過,某些平臺不通過,或同一平臺不同時候,結果也可能不同。
工用列表演算法
不確定性的來源是難以避免的,考慮使用一個確定的工作集演算法替代方案。即工作列表演算法。將工作條目存儲到數組中而不是集合中,則inNetwork方法,將總是以相同的順序遍歷圖。
Member.prototype.inNetwork=function(other){
var visited={};
var worklist=[this];
while(worklist.length>0){
var member=worklist.pop();
if(member.name in visited){
continue;
}
visited[memeber.name]=member;
if(member === other){
return true;
}
member.friends.forEach(function(friend){
worklist.push(friend);
})
}
return false;
};
這一版本inNetwork方法會確定性地添加和刪除工作條目。無論發現什麼路徑,該方法對於連接的成員總是返回true,所以最終結果是一樣的。
提示
-
當使用for...in迴圈枚舉一個對象的屬性時,確保不要修改對象
-
當迭代一個對象時,如果該對象的內容可能會在迴圈期間被改變,應該使用while迴圈或經典的for迴圈來代替for...in迴圈
-
為了在不斷變化的數據結構中能夠預測枚舉,考慮使用一個有序的數據結構,例如數組,而不要使用字典
附錄:示例完整版
function Member(name){
this.name=name;
this.friends=[];
}
Member.prototype.inNetwork=function(other){
var visited={};
var worklist=[this];
while(worklist.length>0){
var member=worklist.pop();
if(member.name in visited){
continue;
}
visited[member.name]=member;
if(member === other){
return true;
}
member.friends.forEach(function(friend){
worklist.push(friend);
})
}
return false;
};
//測試代碼
var a=new Member('鐘二'),
b=new Member('張三'),
c=new Member('趙四'),
d=new Member('王五'),
e=new Member('阮六'),
f=new Member('耿七');
a.friends.push(b);
b.friends.push(c);
c.friends.push(e);
d.friends.push(b);
e.friends.push(d,f);
a.inNetwork(f);//true
a.inNetwork(d);//true
f.inNetwork(a);//false