pigfoot’s weblog

We should forget about small efficiencies — Donald Knuth

Archive for the ‘IT’ Category

Page 4 of 581234567...Last »

Trend Micro Program Contest 2009 Training #2: MapReduce overview

Author: pigfoot

5 May

孫子兵法．謀攻篇：「凡用兵之法：十則圍之，五則攻之，倍則分之。」

這句話的意思是，當我們的兵力大過敵人兵力十倍，就用包圍攻擊來殲滅對方。反過來說，當對方的兵力大過我們，就想辦法分開他們而各自擊破。雖然我的翻譯不是很好，但是老祖宗的智慧，就是 computer science 中，一個非常著名的演算法 divide and conquer。

我們會用到雲端運算，要處理的資料一定是非比尋常的大，大多數的這類的分散式演算法本質上都和 divide and conquer 接近。我們這邊要介紹的 framework，就是 Google 所提的 MapReduce。

以下的圖，就是一個簡化過的 MapReduce 的 work flow。一般來說，它分成四個階段:

hadoop-2

1) Input

雖然原始的資料量太大，但是我們有很多個 node 可以來運算。所以將原始的資料切成若干等份的 block，並往下一個階段送。

2) Map

對傳過來的 block 中的每一個元素，進行 Map function 的運算成為中繼資料。然後將中繼資料往下一個階段送。

3) Reduce

對傳過來的中繼資料，以及前一個 reduce 的結果，進行 Reduce function 的運算。然後將運算結果往下一個階段送。Reduce 和 Map 不同，它有兩個 input。

4) Output

將運算結果寫進檔案系統，完成運算。

這個 design pattern 就是這麼簡單，不知不覺得用上 MapReduce。當然，Map 和 Reduce 的數目，與可以運算的 Node，都是影響效能的關鍵，這個我們容後再講。目前我們所要知道的，就是如何把問題轉化成 MapReduce 的解法，一旦可以套用，那問題幾乎是解了一半了，剩下的就是動手 coding 而己。

我再舉另一些例子。如何從某個電子書中找到最常用到的單字? 這個問題是不是有點像在用 google search 時，出現的關鍵字自動補齊功能 (search autocomplete) 呢? 只是問題簡化過而己。我們來看看這個問題怎麼用 MapReduce。

1) Input

電子書以章為單位，分別送給每一個 Map。

2) Map

Map 找出該章裡所有的單字，接著送給 Reduce。

3) Reduce

Reduce 對上一個 Reduce 排序好的結果，加上對應的 Map 送過來的單字，兩者再排序之後送給下一個 Reduce。

4) Output

最後一個 Reduce 處理完之後，就是最終的單字排序名單。

大家可以多想一些例子來練習這樣的 work flow。

雖然概念上是這樣，但是實際上的作法大家都略有差異。下一篇就是針對 Hadoop 的 MapReduce 來作說明。

Popularity: 9% [?]

  • 1 Comment
  • Filed under: Develop, IT, Web

    • Trend Micro Program Contest 2009 Training #1: Hadoop Virtual Image

    Author: pigfoot

    4 May

    Hadoop

    子曰：「工欲善其事,必先利其器。」

    當然，比賽最好先熟一下工具會比較有信心。我第一個要先介紹的 framework 就是 Hadoop (Wikipedia: Hadoop)。

    因為 Hadoop 算是一個非常知名的雲端運算平台，加上 Wikipedia 寫的也非常的仔細，所以我這邊就不贅述了。但是因為它的設定不太容易而且費時，加上這部份對於簡單的程式來說，並沒有太大的影響。所以我推薦在開發階段，可以先用 Hadoop Virtual Image 就可以了。

    Hadoop Virtual Image 是一個 Ubuntu Linux 7.04 的 OS, 然後內建了 Java machine (Sun JRE 6 u2) 以及 Hadoop 0.13.0 的一個 virtual machine image。我們可以用免費的 VMware Player 來執行它。

    雖然它沒有 GUI，但是最令人感到興奮的是，它預設已經把 Hadoop 的環境設定好成 pseudo-distributed mode (也就是在同一台電腦上用不同的 port 當作不同的機器，然後在利用 ssh 去跟這些假機器作溝通)。雖然預設只有一個機器，不過目前應該無傷大雅。

    以下就是用 VMware Player 執行這個 virtual machine image 的樣子。

    hadoop-vmware_01

    然後用 guest 登入:

    hadoop-vmware_02

    因為這個 guest OS 已經裝了 Hadoop, 所以我們可以執行它裡面的範例程式來簡單的跑一下。指令如下:

    $ hadoop jar hadoop-examples.jar pi 4 10000

    這個範例就是在 Hadoop 的平台上, 用蒙地卡羅法 (Monte Carlo Method) 來分散計算 Pi 的值。換句話說，這就是最簡單的雲端運算 (因為只有一個機器)。

    下面是跑完的結果:

    hadoop-vmware_03

    有看到上面的正常結果，代表我們的環境是正常的，可以開始作一些程式開發了。為了更了解雲端運算，它的 working flow 是一定要先知道。下一篇就是要來講 Google 所提出來的 MapReduce framework。

    Popularity: 9% [?]

  • 0 Comments
  • Filed under: Develop, IT, Web

    • Trend Micro Program Contest 2009

    Author: pigfoot

    30 Apr

    Sorry. This post is chinese only.

    本篇開放全文轉貼轉寄，不受創用 CC license 保護。

    敝公司趨勢科技最近舉辦了騰雲駕霧程式競賽，因為我參加過 2000 年第一屆程式競賽，有入選決賽 (參賽經驗分享)，雖然現在己經過了九年，我依然覺得這個比賽的經驗對我來說是非常珍貴的，所以跑去當工作人員。一問之下才知道，原來很多人不敢報名，是因為對啥雲端運算完全不熟，怕去當炮灰，我覺得實在非常可惜啊!

    各位正在學校唸書的學弟妹，不要真的覺得畢業以後去投甚麼 yes123 求職網，薪水可以加一倍。前提是你必須要在這個不景氣的就業市場被老闆欽點才有可能啊! 怎麼樣才能夠脫穎而出，為自己的履歷加上畫龍點睛的決定性關鍵，程式比賽就是一個很好的機會。我想光是在趨勢科技的程式競賽中進入決賽，不論是哪家企業，一定都會有正面的加分作用，更何況前面的名次還會有趨勢科技預聘書。

    那大家可能覺得說，這是比啥鬼雲端運算，我甚麼都不知道可以參加嗎? 各位，如果我還有在校生資格的話一定會報名。為甚麼? 因為:

    1) 大家都是齊頭式的平等
    對! 這是大部份學校老師不會教的事。那還有甚麼好怕的? 大家都不熟的狀況下，反而是評審比較難出題目不是嗎? 那是不是有可以吸引評審的創意，贏面就非常高了呢?

    2) 正式競賽之前，會提供相關的教學課程內容
    也就是說初賽之前，會有教學課程讓大家先熟悉。為了怕遠距離的教學效果不好，現在只要報名就可以來我們公司上課。目前確定的有: cloud computing overview，開發工具加 sample 練習，初賽環境與初賽進行方向等等課程。

    各位看倌您看看，報名費: 0, 學費: 0, 能夠學到 cloud computing，真的是 *無價* 啊! 光是這項就值回票價了 (其實還是免費票)。如果畢業以後想去會用到_這些專長的公司_，這不是天下掉下來的禮物嗎?

    我憑著良心說實話，這些代價其實都是轉嫁到趨勢科技身上要自行吸收的。不光是在這個不景氣的時代還提供獎金，R&D 部門也要花額外的時間準備，又沒有綁約說入決賽的隊伍，在畢業後一定要來趨勢科技，幾乎沒有好處。但是老闆娘真的是佛心來的，聽到我們這些曾經加比賽的人，都非常同意當年這個比賽對我們的人生，有著很重要的教育意義，她就排除萬難決定再次舉辦。

    是的，真的因為教育是無價的! 所以才會好康大放送啊! 大家要把握這個大好的機會快快報名! 最後報名時間就是在 6/2 號! 報名網址在這 http://www.trend.org/fd/tabid/66/Default.aspx/，或是點最上面的 banner 也可以。

    孔子說：「不教而戰，是謂棄之。」所以我接下來會寫一些教學的文章當做先修課。有興趣的也可以到這次的雲端BLOG，也有其它同事的教學文章。

    Popularity: 9% [?]

  • 0 Comments
  • Filed under: IT, Office, Talk, Web

    • Firefox 3.5 Beta 4 Optimized Build

    Author: pigfoot

    30 Apr

    Get Firefox!

    What’s New

    • Portable edition has been also provided since now. It will create a profile folder “Firefox (Profile)” if needed.
    • Firefox 3.1 becomes 3.5, hence the previous build was Firefox 3.1b3
    • Use P2 If in doubt
    • Mozilla Firefox 3.5b4 Official Release Notes
    • Firefox 3.5 is based on the Gecko 1.9.1 rendering platform, which has been under development for the past 9 months. Firefox 3.5 is an incremental release on the previous version with significant changes to improve web compatibility, performance, and ease of use
    • Improved tools for controlling your private data, including a Private Browsing Mode
    • Improved performance and stability with the new TraceMonkey JavaScript engine.
    • Support for native JSON, and web worker threads
    • Reduce memory usage by using jemalloc
    • Speed improvement by using Profile-Guided Optimization (PGO)

    Firefox 3.5 Beta 4 community edition en_US (20090429)

    Popularity: 100% [?]

  • 47 Comments
  • Filed under: Gecko, IT

    • Firefox 3.0.10 Release Optimized Build

    Author: pigfoot

    29 Apr

    Get Firefox!

    What’s New

    Firefox 3.0.10 community edition en_US (20090427)

    Firefox 3.0.10 community edition zh_TW (20090427)

    Firefox 3.0.10 community edition zh_CN (20090428)

    Firefox 3.0.10 community edition ja (20090428)

    Firefox 3.0.10 community edition de (20090428)

    Firefox 3.0.10 community edition fr (20090428)

    Popularity: 23% [?]

  • 5 Comments
  • Filed under: Gecko, IT

    • Mozilla Firefox 3.0.9 Release Build

    Author: pigfoot

    26 Apr

    Get Firefox!

    What’s New

    Mozilla Firefox 3.0.9 Release en_US (20090423)

    Mozilla Firefox 3.0.9 Release zh_TW (20090423)

    Mozilla Firefox 3.0.9 Release zh_CN (20090423)

    Mozilla Firefox 3.0.9 Release ja (20090424)

    Mozilla Firefox 3.0.9 Release de (20090424)

    Mozilla Firefox 3.0.9 Release fr (20090424)

    Popularity: 14% [?]

  • 6 Comments
  • Filed under: Gecko, IT

    • Mozilla Firefox 3.0.8 Release Build

    Author: pigfoot

    8 Apr

    Get Firefox!

    What’s New

    Mozilla Firefox 3.0.8 Release en_US (20090331)

    Mozilla Firefox 3.0.8 Release zh_TW (20090331)

    Mozilla Firefox 3.0.8 Release zh_CN (20090331)

    Mozilla Firefox 3.0.8 Release ja (20090331)

    Mozilla Firefox 3.0.8 Release de (20090401)

    Mozilla Firefox 3.0.8 Release fr (20090401)

    Popularity: 9% [?]

  • 2 Comments
  • Filed under: IT
    • Page 4 of 581234567...Last »

    PhotoStream

      20100618_MyBirthday20100618_MyBirthday20100618_MyBirthday

    Categories

    Recent Comments

    Links


    Archives


    Meta

    Copyright © 2007 - pigfoot’s weblog - is proudly powered by WordPress
    Illacrimo Theme is created by: Design Disease brought to you by LifeSpy.