DIV CSS 佈局教程網

用 JavaScript 動手實作 MapReduce:原理與範例解析
編輯:JavaScript基礎知識     

Google 在 2003 到 2006 年間連續發表了三篇影響深遠的論文:2003 年在 SOSP 上發布的 GFS、2004 年在 OSDI 上發布的 MapReduce,以及 2006 年在 OSDI 上發布的 BigTable。GFS 是分散式檔案系統,對後續的檔案系統設計具有指導意義;MapReduce 是一種平行計算的程式設計模型,用於作業調度;BigTable 則是建構在 GFS、Chubby、SSTable 等技術之上的分散式結構化資料儲存系統。Google Search、Google Earth、Google Analytics 等大量應用都建立在這三者之上,因此它們被並稱為 Google 的「三寶」。本文就來把 MapReduce「開膛剖肚」看一遍。

MapReduce 是什麼

MapReduce 既是程式設計模型,也是處理與生成超大資料集的演算法模型實作。使用者的工作是撰寫兩個函數:一個 Map 函數,把輸入的 key/value 資料集合轉換為中間的 key/value 集合;一個 Reduce 函數,把所有具有相同中間 key 的 value 合併起來。

動手寫一遍

常言道「實踐出真知」,是騾子是馬,拉出來遛遛才知道。最近和幾個朋友一起學 JavaScript,上網亂逛時意外發現竟然有人用 JavaScript 實作了 MapReduce 演算法,於是轉過來分享,並補上一些自己的說明。程式碼如下:

var Job = {
// 待處理的資料
data : [
" We are glad to see you here. This site is dedicated to",
"poetry and to the people who make poetry possible",
"poets and their readers. FamousPoetsAndPoems.com is",
"a free poetry site. On our site you can find a large",
"collection of poems and quotes from over 631 poets",
"Read and Enjoy Poetry",
"I, too, sing America",
"I am the darker brother",
"They send me to eat in the kitchen",
"When company comes",
"But I laugh",
"And eat well",
"And grow strong",
"Tomorrow",
"Ill be at the table",
"When company comes",
"Nobodyll dare",
"Say to me",
"Eat in the kitchen",
"Then",
"Besides",
"Theyll see how beautiful I am",
"And be ashamed",
"I, too, am America"
],
// 將資料中的每行字串用空格分隔開,
// 並「重組」成 {key: 單詞, value: 1} 格式的物件,回傳物件陣列
map : function(line) {
  var splits = line.split(" ");
  var temp = [];
  for(var i = 0; i < splits.length; i++) {
    temp.push({key : splits[i], value : 1});
  }
  return temp;
},
// 計算每個單詞在「資料」(data)中出現的次數
reduce : function(allSteps) {
  var result = {};
  for(var i = 0; i < allSteps.length; i++) {
    var step = allSteps[i];
    result[step.key] = result[step.key] ? (result[step.key] + 1) : 1;
  }
  return result;
},
// 初始化,同時是運行的入口
init : function() {
  var allSteps = [];
  for(var i = 0; i < Job.data.length; i++) {
    // 如果這裡能多執行緒呼叫 Job.map 函數就更逼真了
    allSteps = allSteps.concat(Job.map(Job.data[i]));
  }
  // 美中不足,這裡不能多執行緒呼叫 Job.reduce 函數
  var result = Job.reduce(allSteps);
  console.log(JSON.stringify(result));
}
}; // Job
// 開始執行
Job.init();

把這段程式碼貼進瀏覽器主控台(Console),或者存成 HTML 檔用瀏覽器打開,就能在主控台看到統計結果——每個單詞在整組詩句裡出現的次數。

美中不足之處

文章發布後就有網友吐槽:「一個連多執行緒都沒有的 JS 搞什麼 MapReduce?」這個問題其實我也注意到了。看到這段程式碼的註解後我就納悶:JavaScript 不是單執行緒嗎,怎麼還能模擬 MapReduce?仔細讀完程式碼並單步除錯之後,更加印證了這個看法。

不過再想想,這並不影響我們理解 MapReduce 的原理。這只是一個單執行緒、最基礎的版本;先把這個吃透,再去理解真正的多節點版本就容易多了。真正的 MapReduce 之所以需要拆成 Map 與 Reduce 兩階段,關鍵正是「Map 階段可以任意水平擴展、彼此獨立」,而 Reduce 階段則負責聚合,這個分層思想才是它真正的價值所在。

下一步

後續考慮在這個範例的基礎上,用 Java 實作一個多執行緒版本,那樣的模擬會更貼近真實情境。等把一些細節想清楚,再來分享程式碼。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved