分而治之：據(jù)不同的成因選擇不同的解決方案。
成語(yǔ)大全如是說(shuō)。而似乎分治只借了這個(gè)成語(yǔ)的名饥追，意思卻偏向于問(wèn)題的拆解再合并，就是把一個(gè)復(fù)雜的問(wèn)題分解成多個(gè)相同或相似的子問(wèn)題罐盔，再把子問(wèn)題分解成更小的問(wèn)題但绕。這種分解問(wèn)題的思維，惶看。這里先埋一個(gè)雷：MapReduce壁熄，游魚過(guò)會(huì)再提帚豪。
從算法開始
No.1 經(jīng)典排序算法——快速排序
當(dāng)有人問(wèn)起：你知道哪幾種排序算法啊草丧？大多說(shuō)人不加思索都能說(shuō)出三種：冒泡排序（你要是說(shuō)你只知道選擇和插入狸臣。。昌执。我估計(jì)也不太可能）烛亦、選擇排序、插入排序懂拾∶呵荩快速排序就是對(duì)冒泡排序的一次改進(jìn)。
冒泡排序是兩兩比較岖赋，當(dāng)兩兩不符合當(dāng)前規(guī)定的順序時(shí)檬果，則交換兩者的位置。而快速排序就是選定一個(gè)基準(zhǔn)值唐断，假設(shè)從小到大选脊，基準(zhǔn)值左邊的如果比基準(zhǔn)值大就放到右邊，基準(zhǔn)值左邊的如果比基準(zhǔn)值小就放到右邊脸甘，然后在左右兩邊再循環(huán)這個(gè)過(guò)程恳啥。
如下圖所示：
算法：（備注，相對(duì)于圖片局部?jī)?yōu)化了丹诀，減少了交換的次數(shù)）
#!usr/bin/c++
#include <iostream>
using namespace std;
#需要快排的數(shù)組a钝的，數(shù)組第一位low，數(shù)組最后一位high铆遭。
void Qsort(int a[], int low, int high)
{
#初始數(shù)組第一位low>=數(shù)組最后一位high硝桩，說(shuō)明這一層排序已經(jīng)到了最小的字元：數(shù)組內(nèi)單個(gè)元素。
if(low >= high)
{
return;
}
int first = low;
int last = high;
int key = a[first];/*用數(shù)組的第一個(gè)記錄作為樞軸*/
while(first < last)
{
while(first < last && a[last] >= key)
{
--last;
}
a[first] = a[last];/*將比第一個(gè)小的移到低端*/
while(first < last && a[first] <= key)
{
++first;
}
a[last] = a[first];/*將比第一個(gè)大的移到高端*/
}
a[first] = key;/*樞軸保存到first處枚荣，此時(shí)因?yàn)閒irst一路走來(lái)保證first前面的小于key碗脊，last一路走來(lái)保證last后面的大于key，且直到最后first遇到了last*/
/*對(duì)第一位到樞紐的前一位進(jìn)行二次快排*/
Qsort(a, low, first-1);
/*對(duì)最后一位到樞紐的后一位進(jìn)行二次快排*/
Qsort(a, first+1, high);
}
int main()
{
int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);
for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
cout << a[i] << "";
}
return 0;
}/*參考數(shù)據(jù)結(jié)構(gòu)p274(清華大學(xué)出版社棍弄，嚴(yán)蔚敏)*/
至于對(duì)經(jīng)典快速排序算法的再優(yōu)化望薄，魚就不說(shuō)了，愛看看吧呼畸，十分雜亂且刺激痕支。
No.2 經(jīng)典排序算法——?dú)w并排序
快排是分治法從全局有序化（左邊小右邊大）逐步局部有序化（小的是唯一一個(gè)，大的也是唯一一個(gè)蛮原，那這三個(gè)數(shù)不就排好序了嗎）的排序卧须，歸并則是從局部有序化（從兩個(gè)數(shù)開始排好序）逐步全局有序化（全部都排好序）的過(guò)程。
因?yàn)榫植渴怯行虻模詺w并排序是用的以下的手法：
#!/usr/bin/python
def MergeSort(lists):
if len(lists) <= 1:
return lists
num = int( len(lists) / 2 )
left = MergeSort(lists[:num])
right = MergeSort(lists[num:])
return Merge(left, right)
def Merge(left,right):
r, l=0, 0
result=[]
while l<len(left) and r<len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += list(left[l:])
result += list(right[r:])
return result
print(MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45]))
#from 百科,不得不說(shuō)這些寫百科的也真的是隨手花嘶，歪門邪道的錯(cuò)誤
經(jīng)過(guò)函數(shù)式的洗禮
絕大多數(shù)的高級(jí)語(yǔ)言都帶入了Map(映射)函數(shù)笋籽、Reduce(歸約)函數(shù)的理念
#!/usr/bin/js
//array.map(function(currentValue,index,arr), thisValue)
//currentValue=>當(dāng)前元素的值，index=>當(dāng)前元素的索引椭员，arr=>當(dāng)前數(shù)組對(duì)象车海，thisValue=>作為執(zhí)行回調(diào)使用
//例子
var numbers = [4, 9, 16, 25];
function myFunction() {
x = document.getElementById("demo")
x.innerHTML = numbers.map(Math.sqrt);
}
//from runoob
#!/usr/bin/js
//array.reduce(function(total, currentValue, currentIndex, arr), initialValue)
//比Map多了total作為歸并后的返回值。
//例子
var numbers = [65, 44, 12, 4];
function getSum(total, num) {
return total + num;
}
function myFunction(item) {
document.getElementById("demo").innerHTML = numbers.reduce(getSum);
}
//from runoob
先回到最一開始?xì)w并排序的邏輯上去——可以看到MergeSort()是在用遞歸分解問(wèn)題隘击，即一個(gè)大問(wèn)題分解成一個(gè)小問(wèn)題侍芝。而Merge則是在歸并，把有序的小問(wèn)題合并成一個(gè)有序的大問(wèn)題埋同，因?yàn)樾?wèn)題是有序的州叠，所以排序成本極低（小于n）。由此對(duì)比下Map和Reduce的函數(shù)邏輯凶赁，盡管排序少了對(duì)小問(wèn)題的Map映射處理咧栗，也是實(shí)現(xiàn)了Reduce的思想進(jìn)行了歸約，假設(shè)現(xiàn)在有一個(gè)一百萬(wàn)無(wú)序的數(shù)組虱肄，正常的排序算法時(shí)間復(fù)雜度都在nlgn~n^2之間不定致板，如果用一臺(tái)電腦去處理，可能要幾個(gè)小時(shí)的時(shí)間浩峡。而歸并排序在Reduce的過(guò)程中成本極低可岂，則可以采用分布式處理的方式错敢，先把問(wèn)題Map出去翰灾，交給服務(wù)器集群進(jìn)行處理，最后再Reduce回來(lái)得到最后的結(jié)果稚茅。
對(duì)纸淮，就是這樣分治策略是分布式系統(tǒng)的邏輯基礎(chǔ)，現(xiàn)如今大多數(shù)分布式處理都來(lái)源于MapReduce思想亚享，由此游魚還認(rèn)識(shí)了Lisp語(yǔ)言咽块。
在MapReduce里，Map處理的是原始數(shù)據(jù)欺税，自然是雜亂無(wú)章的侈沪，每條數(shù)據(jù)之間互相沒有關(guān)系；到了Reduce階段晚凿，數(shù)據(jù)是以key后面跟著若干個(gè)value來(lái)組織的亭罪，這些value有相關(guān)性，至少它們都在一個(gè)key下面歼秽，于是就符合函數(shù)式語(yǔ)言里map和reduce的基本思想了应役。去借用MapReduce模型的話，開發(fā)人員只需要考慮如何進(jìn)行數(shù)據(jù)處理，提取特征喊暖，最后再考慮如何歸納特征闯割。開發(fā)人員不用考慮如何并發(fā)的問(wèn)題迈着。
落地到編程模型
分布式存儲(chǔ)HDFS——分布式處理MapReduce
這方面魚推薦大家多去閱讀文獻(xiàn)，不獻(xiàn)丑了底瓣。只大概說(shuō)說(shuō)，復(fù)制一下個(gè)人之前Apache Storm的筆記
Apache Storm
一 優(yōu)勢(shì)
- Apache 產(chǎn)品通用優(yōu)勢(shì)：可以通過(guò)線性增加資源來(lái)保持性能
- 適用性蕉陋、語(yǔ)言普適性濒持、分布式處理快的優(yōu)勢(shì)、操作智能
- 優(yōu)秀的防呆措施
二寺滚、理念
Input data source: 數(shù)據(jù)源
Spout: 流的源柑营，通過(guò)編寫 Spout 以從數(shù)據(jù)源讀取數(shù)據(jù)
Bolt:邏輯處理單元， Spout 將數(shù)據(jù)傳遞到 Bolt 和 Bolt過(guò)程村视，并產(chǎn)生新的數(shù)據(jù)流官套。 Bolt 可以拍行過(guò)濾、聚合蚁孔、加入奶赔，并與數(shù)據(jù) 源和數(shù)據(jù)庫(kù)進(jìn)行交互
Tuple:有序元素的列表
Stream:元組的無(wú)序序列
關(guān)鍵詞：拓?fù)浜吐酚?/p>
三、集群架構(gòu)
Apache Storm 的集群架構(gòu)杠氢，采用了主從設(shè)備模式站刑。這種模式參照于？
Zookeeper framework:協(xié)助 Supervisor 和 nimbus 交互
Nimbus : Storm 集群的主節(jié)點(diǎn)鼻百，又稱Master绞旅。而工作結(jié)點(diǎn)分發(fā)數(shù)據(jù)并監(jiān)控故障
Supervisor:工作節(jié)點(diǎn)又稱 Workers,負(fù)責(zé)管理工作進(jìn)程以完成分配的任務(wù)
Worker process:工作進(jìn)程，其執(zhí)行與特定拓?fù)湎嚓P(guān)的任務(wù)温艇。其創(chuàng)建執(zhí)行器因悲，并要求它們完成任務(wù)
Execute:執(zhí)行器。由工作進(jìn)程產(chǎn)生的單個(gè)線程勺爱，用于特定的spout與 bolt
Task:任務(wù)晃琳，實(shí)際執(zhí)行數(shù)據(jù)處理。它是個(gè) spout 或 bolt
四琐鲁、工作流程
