Algorithm
什么是"正確"的算法？
"正確"的算法是要根據(jù)不同應(yīng)用環(huán)境和場(chǎng)景確定的挪拟。假設(shè)面試官就問對(duì)一組數(shù)據(jù)進(jìn)行排序校坑，你將怎么做闯团？一般人第一反應(yīng)就會(huì)是使用快速排序算法O(nlogn)作答晾虑。但這個(gè)回答卻忽略了使用環(huán)境因素决左，和數(shù)據(jù)特征。
- 如果包括大量重復(fù)元素則 三路快排則是一個(gè)非常好的選擇走贪。
- 如果大部分?jǐn)?shù)據(jù)離正確位置很近，就是說數(shù)據(jù)近乎有序惑芭，那么插入排序法則是更好的選擇
- 如果數(shù)據(jù)范圍有限坠狡，那么使用計(jì)數(shù)排序則會(huì)更好。
- 如果需要是穩(wěn)定的排序遂跟，那么需要是歸并排序逃沿。
- 查看一下 數(shù)據(jù)量多大，是否只能使用鏈表或者一臺(tái)機(jī)器根本存不下這些數(shù)據(jù)幻锁。
優(yōu)化算法的思路
- 遍歷常見的算法思路：?jiǎn)栴}分類凯亮，是索引指針，還是遞歸哄尔，分治假消，動(dòng)態(tài)規(guī)劃等方式。
- 遍歷常見的數(shù)據(jù)結(jié)構(gòu)：棧岭接，隊(duì)列富拗，數(shù)臼予，圖來解決問題。
- 空間和時(shí)間的交換（哈希表）
- 預(yù)處理信息（排序）
- 瓶頸處找答案啃沪。
算法復(fù)雜度和數(shù)據(jù)規(guī)模
1秒內(nèi)：
O(n^2) 處理大約10^4級(jí)別的數(shù)據(jù)
O(nlogn) 處理大約10^8級(jí)別的數(shù)據(jù)
O(n) 處理大約10^7級(jí)別的數(shù)據(jù)
遞歸的時(shí)間復(fù)雜度是什么粘拾？
如果遞歸函數(shù)中，只進(jìn)行一次遞歸調(diào)用创千，遞歸深度為depth缰雇；
在每個(gè)遞歸函數(shù)中，時(shí)間復(fù)雜度為T追驴；則總體的時(shí)間復(fù)雜度為O(T * depth)
Review
一械哟、《Flink-客戶端操作》
Flink提供了豐富的客戶端操作來提交任務(wù)和與任務(wù)進(jìn)行交互。本期課程將分為5個(gè)部分進(jìn)行講
解氯檐，包括 Flink命令行戒良，Scala Shell，SQL Client(后續(xù)支持DDL語句)冠摄，Restful API 和 Web糯崎。）
二、《Flink Window Time》
Tips/Technology
一河泳、Google大數(shù)據(jù)處理發(fā)展過程
第一階段：無統(tǒng)一大數(shù)據(jù)處理框架沃呢，MapReduce應(yīng)運(yùn)而生解決了統(tǒng)一容錯(cuò)，讓開發(fā)人員只關(guān)心業(yè)務(wù)邏輯等問題
拆挥。
第二階段：MapReduce無法自動(dòng)調(diào)優(yōu)薄霜，大量Map和Reduce代碼后期很難維護(hù)。FlumeJava出現(xiàn)了纸兔，將執(zhí)行計(jì)劃先遍歷一遍形成有向無環(huán)圖自動(dòng)惰瓜。
第三階段：FlumeJava只支持批處理，無法對(duì)無解數(shù)據(jù)進(jìn)行處理所以在2015年發(fā)布了Dataflow模型汉矿，希望集合現(xiàn)在市場(chǎng)上的框架崎坊，進(jìn)行流批的統(tǒng)一。
第四階段：Google全面推進(jìn)Beam
- MapReduce: https://research.google.com/archive/mapreduce-osdi04.pdf
- Flumejava: https://research.google.com/pubs/archive/35650.pdf
- MillWheel: https://research.google.com/pubs/archive/41378.pdf
- Data flow Model: https://www.vldb.org/pvldb/vol8/p1792-Akidau.pdf
二洲拇、Flink和Spark對(duì)比
- 從流處理角度：Spark是微批處理奈揍，所以窗口操作只支持處理時(shí)間和事件事件，不支持?jǐn)?shù)據(jù)時(shí)間和自定義窗口赋续。Flink沒有這些問題男翰。
- 從SQL角度：都提供SQL交互，Spark目前比較完善纽乱，F(xiàn)link后期會(huì)把Blink的DDL語句進(jìn)行合并蛾绎。
- 從迭代計(jì)算角度：Flink支持有環(huán)圖，針對(duì)機(jī)器學(xué)習(xí)的算法效率高。
- 從生態(tài)角度：Spark歷史比較久社區(qū)活躍秘通，支持的庫(kù)比較多为严。Flink支持的庫(kù)比較少但在國(guó)內(nèi)由阿里在推廣。
Share
《慢下來》
紀(jì)伯倫有句話：我們已經(jīng)走得太遠(yuǎn)肺稀，以至于忘記了為什么出發(fā)第股。我們做事情總是很急，總怕自己錯(cuò)過了什么话原，到頭來其實(shí)什么也沒記住夕吻，但卻滿足了自身的焦慮感。有些時(shí)候我們目的還沒有搞清楚繁仁，在世俗的驅(qū)動(dòng)下涉馅，隨波逐流的就去做了，做了半天其實(shí)方向都是錯(cuò)的黄虱。給自己一個(gè)建議稚矿，慢下來，只要方向是對(duì)的慢慢走早晚會(huì)到終點(diǎn)捻浦。
Research
項(xiàng)目部署晤揣、袋鼠云版本遷移、華為產(chǎn)品對(duì)接
