婧愪簬Google鐨勫苟琛岀紪绋嬫ā寮忋€傜畝鑰岃█涔嬶紝灏辨槸浠诲姟鐨勫垎瑙ｇ害缁撴灉鐨勬眹鎬伙紝杩欐槸涓€绉峉implified鐨勫摬瀛︺€?br />
"闈㈠澶嶆潅闂锛屽彜浜烘暀瀵兼垜浠“鍒?/strong>鑰?strong>娌?/strong>涔?rdquo;锛?rdquo;Divide and Conquer“銆侻ap/Reduce鍏跺疄灏辨槸Divide/Conquer鐨勮繃绋嬶紝閫氳繃鎶婇棶棰?Divide锛屼娇杩欎簺Divide鍚庣殑Map杩愮畻楂樺害骞惰锛屽啀灏哅ap鍚庣殑缁撴灉Reduce锛堟牴鎹煇涓€涓狵ey锛夛紝寰楀埌鏈€缁堢殑缁撴灉銆?/p>
Googler鍙戠幇杩欐槸闂鐨勬牳蹇冿紝鍏跺畠閮芥槸鍏辨€ч棶棰樸€傚洜姝わ紝浠栦滑鎶奙apReduce鎶借薄鍒嗙鍑烘潵銆傝繖鏍凤紝Google鐨勭▼搴忓憳鍙互鍙叧蹇冨簲鐢ㄩ€昏緫锛屽叧蹇冩牴鎹摢浜汯ey鎶婇棶棰樿繘琛屽垎瑙ｏ紝鍝簺鎿嶄綔鏄疢ap鎿嶄綔锛屽摢浜涙搷浣滄槸Reduce鎿嶄綔銆傚叾瀹冨苟琛岃绠椾腑鐨勫鏉傞棶棰樿濡傚垎甯冦€佸伐浣滆皟搴︺€佸閿欍€佹満鍣ㄩ棿閫氫俊閮戒氦缁橫ap/Reduce Framework鍘诲仛锛屽緢澶х▼搴︿笂绠€鍖栦簡鏁翠釜缂栫▼妯″瀷銆?/p>
MapReduce鐨勫彟涓€涓壒鐐规槸锛孧ap鍜孯educe鐨?strong>杈撳叆鍜岃緭鍑洪兘鏄腑闂翠复鏃舵枃浠?/strong>锛圡apReduce鍒?鐢℅oogle鏂囦欢绯荤粺鏉ョ鐞嗗拰璁块棶杩欎簺鏂囦欢锛夛紝鑰屼笉鏄笉鍚岃繘绋嬮棿鎴栬€呬笉鍚屾満鍣ㄩ棿鐨勫叾瀹冮€氫俊鏂瑰紡銆傛垜瑙夊緱锛岃繖鏄疓oogle涓€璐殑椋庢牸锛屽寲绻佷负绠€锛岃繑鐠炲綊 鐪熴€?quot;
-- 寮曡嚜 http://www.mengyan.org/blog/archives/2006/11/15/138.html
MapReduce 鐢变袱涓牳蹇冩搷浣滅粍鎴愶細
1. Map
Map鏄妸涓€缁勬暟鎹竴瀵逛竴鐨勬槧灏勪负鍙﹀鐨勪竴缁勬暟鎹紝鍏舵槧灏勭殑瑙勫垯鐢?span style="color: rgb(0, 0, 255);">涓€涓嚱鏁?/span>鏉ユ寚瀹氾紝姣斿瀵筟1, 2, 3, 4]杩涜涔?鐨勬槧灏勫氨鍙樻垚浜哰2, 4, 6, 8]銆?br />Map鎿嶄綔鏄嫭绔嬬殑瀵规瘡涓厓绱犺繘琛屾搷浣滐紝灏嗕骇鐢熶竴缁勫叏鏂扮殑鏁版嵁锛岃€屽師鏉ョ殑鏁版嵁淇濇寔涓嶅彉銆傚洜姝わ紝瀹冩槸楂樺害骞惰鐨勩€?br />
2. Reduce
Reduce鏄涓€缁勬暟鎹繘琛屽綊绾︼紝杩欎釜褰掔害鐨勮鍒欑敱涓€涓嚱鏁?/span>鎸囧畾锛屾瘮濡傚[1, 2, 3, 4]杩涜姹傚拰鐨勫綊绾﹀緱鍒扮粨鏋滄槸10锛岃€屽瀹冭繘琛屾眰绉殑褰掔害缁撴灉鏄?4銆?br />Reduce鎿嶄綔铏界劧涓嶅Map鎿嶄綔骞惰鎬ч偅涔堝ソ锛屼絾鏄畠鎬讳細寰楀埌涓€ 涓浉瀵圭畝鍗曠殑缁撴灉锛屽ぇ瑙勬ā杩愮畻涔熺浉瀵圭嫭绔嬶紝鍥犳涔熸槸姣旇緝閫傚悎骞惰鐨勩€?br />
鏃犺鏄疢ap杩樻槸Reduce閮芥槸浠ュ彟澶栫殑鍑芥暟涓哄弬鏁?/span>锛屽湪 FP锛?a href="http://en.wikipedia.org/wiki/Functional_Programming" title="Functional Programming" class="mw-redirect">Functional Programming锛変腑锛岃繖鏍风殑鍑芥暟琚О涓洪珮闃跺嚱鏁帮紙high-order function锛夈€傛鏄洜涓哄畠浠彲浠ュ悓鍏跺畠鍑芥暟鐩哥粨鍚堬紝鎵€浠ワ紝鎴戜滑鍙鎶奙ap鍜孯educe杩欎袱涓珮闃跺嚱鏁拌繘琛屽苟琛屽寲澶勭悊锛岃繖鏍蜂究褰㈡垚浜嗕竴涓互Map鍜孯educe涓哄熀纭€鐨勬鏋讹紝鍏蜂綋搴旂敤鐩稿叧浠ｇ爜鍐欏湪鐢ㄦ埛浠ｇ爜涓紝涔嬪悗涓嶮apReduce缁撳悎鑾峰緱骞惰澶勭悊鐨勮兘 鍔涖€傚綋鐒讹紝杩欎箞鍋氱殑鍓嶆彁鏄寜鐓ц繖涓鏋剁殑瑕佹眰锛屾妸璁＄畻褰掔粨涓篗ap鍜孯educe鎿嶄綔銆?br />
涓轰粈涔堟槸Map鍜孯educe锛?br />
鍦? Map杩囩▼涓紝鎴戜滑灏嗘暟鎹苟琛岋紝涔熷氨鏄皢鏁版嵁鍒嗗紑锛岃€孯educe鍒欐妸鍒嗗紑鐨勬暟鎹悎鍒颁簡涓€璧凤紝鎹㈠彞璇濊锛孧ap鏄竴涓垎鐨勮繃绋嬶紝Reduce鍒欏搴旂潃鍚堬紝 杩欎竴鍒嗕竴鍚堜究鍦ㄤ笉鐭ヤ笉瑙変腑瀹屾垚浜嗚绠椼€?br />鎵€浠ワ紝绔欏湪璁＄畻鐨勪袱绔潵鐪嬶紝涓庢垜浠€氬父鐔熸倝鐨勪覆琛岃绠楁病鏈変换浣曞樊鍒紝鎵€鏈夌殑澶嶆潅鎬ч兘鍦ㄤ腑闂撮殣钘忎簡銆傛墍鏈夎繖浜涘苟琛屽寲鑳藉姏鐨勮幏寰楅兘涓嶧P鏈夌潃瀵嗕笉鍙垎鐨勫叧绯汇€?br />
鍏充簬FP锛?br />
鍥犱负鍑芥暟寮忕紪绋嬬殑姣忎竴涓鍙烽兘鏄?final 鐨勶紝娌℃湁鍑芥暟浜х敓杩囧壇浣滅敤銆傚洜涓轰粠鏈湪鏌愪釜鍦版柟淇敼杩囧€硷紝涔熸病鏈夊嚱鏁颁慨鏀硅繃鍦ㄥ叾浣滅敤鍩熶箣澶栫殑閲忓苟琚叾浠栧嚱鏁颁娇鐢紙濡傜被鎴愬憳鎴栧叏灞€鍙橀噺锛夈€傝繖鎰忓懗鐫€鍑芥暟姹傚€?鐨勭粨鏋滃彧鏄叾杩斿洖鍊硷紝鑰屾儫涓€褰卞搷鍏惰繑鍥炲€肩殑灏辨槸鍑芥暟鐨勫弬鏁般€傚彧闇€鍦ㄦ剰鍏跺弬鏁帮紝鑰屼笉蹇呰€冭檻鍑芥暟璋冪敤椤哄簭锛屼笉鐢ㄨ皑鎱庡湴璁剧疆澶栭儴鐘舵€併€?br />
鍑芥暟寮忕▼搴忔棤闇€浠讳綍淇敼鍗冲彲骞惰鎵ц銆備笉鐢ㄦ媴蹇冩閿佸拰涓寸晫鍖猴紝鍥犱负浣犱粠鏈敤閿侊紒鍑芥暟寮忕▼搴忛噷娌℃湁浠讳綍鏁版嵁琚悓涓€绾跨▼淇敼涓ゆ锛屾洿涓嶇敤璇翠袱涓笉鍚岀殑绾跨▼浜嗐€?杩欐剰鍛崇潃鍙互涓嶅亣鎬濈储鍦扮畝鍗曞鍔犵嚎绋嬭€屼笉浼氬紩鍙戞姌纾ㄧ潃骞惰搴旂敤绋嬪簭鐨勪紶缁熼棶棰樸€?br />
鍗充娇浣犵殑绋嬪簭鏈韩灏辨槸鍗曠嚎绋嬬殑锛岄偅涔堝嚱鏁板紡绋嬪簭鐨勭紪璇戝櫒浠嶇劧鍙互浼樺寲瀹冧娇鍏惰繍琛屼簬澶氫釜CPU涓娿€?br />
鍑芥暟寮忕紪绋?vs 鍛戒护寮忕紪绋?/strong>
1. 鍑芥暟寮忕紪绋嬬殑鍩烘湰鐗圭偣鏄細
涓板瘜鐨勬暟鎹被鍨嬶紱
鍑芥暟鏄繍绠楀厓锛?/p>
鍦ㄥ嚱鏁板唴淇濆瓨鏁版嵁锛?/p>
鏀寔闂寘鍜岄珮闃跺嚱鏁帮紙楂橀樁鍑芥暟鑳界敤鍙︿竴涓嚱鏁帮紙闂存帴鍦帮紝鐢ㄤ竴涓〃杈惧紡锛?浣滀负鍏惰緭鍏ュ弬鏁帮紝鍦ㄦ煇浜涙儏鍐典笅锛屼粬鐢氳嚦杩斿洖涓€涓嚱鏁颁綔涓哄叾杈撳嚭鍙傛暟銆傦級锛?/p>
鏀寔鎳掓儼璁＄畻锛坙azy evaluation锛夛紱
浣跨敤閫掑綊浣滀负鎺у埗娴佺▼鐨勬満鍒讹紱
鍔犲己浜嗗紩鐢ㄩ€忔槑鎬э紱
鍑芥暟鍐呯殑杩愮畻瀵瑰嚱鏁板鏃犲壇浣滅敤銆?/p>
鍑芥暟寮忕紪绋嬪彧鎻忚堪鍦ㄧ▼搴忚緭鍏ヤ笂鎵ц鐨勬搷浣滐紝涓嶅繀浣跨敤涓存椂鍙橀噺淇濆瓨涓棿缁撴灉銆傞噸鐐规槸鎹曟崏"鏄粈涔堜互鍙婁负浠€涔?quot;锛岃€屼笉鏄?quot;濡備綍鍋?quot;銆備笌灏嗛噸鐐规斁鍦ㄦ墽琛岃繛 缁懡浠や笂鐨勮繃绋嬫€х紪绋嬬浉姣旓紝鍑芥暟寮忕紪绋嬬殑閲嶇偣鏄嚱鏁扮殑瀹氫箟鑰屼笉鏄姸鎬佹満锛圫tate Machine锛夌殑瀹炵幇銆傛槸涓€绉嶅己璋冭〃杈惧紡鐨勮绠楄€岄潪鍛戒护鐨勬墽琛岀殑涓€绉嶇紪绋嬮鏍笺€傝〃杈惧紡鏄敤鍑芥暟缁撳悎鍩烘湰鍊兼瀯鎴愮殑锛屽畠绫讳技浜庣敤鍙傛暟璋冪敤鍑芥暟锛堝嚱鏁板紡鐨勪紭缇?鐨勮鏄庡彲瑙併€奆unctional Programming For The Rest of Us銆嬶級銆?/p>
2. 鍛戒护寮忕紪绋?br />
鍛戒护寮忕紪绋嬫槸涓€绉嶇敤绋嬪紡鐘舵€佹弿杩拌绠楃殑鏂规硶銆備娇鐢ㄨ繖绉嶈寖鍨嬬殑缂栫▼浜哄憳鐢ㄨ鍙ユ敼鍔ㄧ▼寮忕姸鎬併€?br />鍑芥暟寮忕紪绋嬫槸涓€绉嶅己璋冭〃杈惧紡鐨勮绠楄€岄潪鍛戒护鐨勬墽琛岀殑涓€绉嶇紪绋嬮鏍笺€傝〃杈惧紡鏄敤鍑芥暟缁撳悎鍩烘湰鍊兼瀯鎴愮殑锛岀被浼间簬鐢ㄥ弬鏁拌皟鐢ㄥ嚱鏁般€?
涔熷氨鏄锛屽嚱鏁板紡缂栫▼涓昏鏄嚱鏁拌皟鐢紝鑰屼笉鏄叾浠栫殑绋嬪紡璇彞銆?鑰屽懡浠ゅ紡缂栫▼锛屾槸閫氳繃绋嬪紡璇彞鐨勬墽琛岃繍琛岀殑銆傜▼寮忚鍙ョ殑鎵ц锛屼細鏀瑰姩绋嬪紡涓繚瀛樼殑鐘舵€併€?
|
