Algorithm

這周實(shí)現(xiàn)了最基本的動態(tài)數(shù)據(jù)結(jié)構(gòu)鏈表，并用數(shù)組和鏈表分別實(shí)現(xiàn)了棧和隊(duì)列。

git代碼地址

數(shù)組和鏈表的總結(jié)

一、什么是鏈表？

1.和數(shù)組一樣，鏈表也是一種線性表。

2.從內(nèi)存結(jié)構(gòu)來看，鏈表的內(nèi)存結(jié)構(gòu)是不連續(xù)的內(nèi)存空間，是將一組零散的內(nèi)存塊串聯(lián)起來，從而進(jìn)行數(shù)據(jù)存儲的數(shù)據(jù)結(jié)構(gòu)。

3.鏈表中的每一個(gè)內(nèi)存塊被稱為節(jié)點(diǎn)Node。節(jié)點(diǎn)除了存儲數(shù)據(jù)外，還需記錄鏈上下一個(gè)節(jié)點(diǎn)的地址，即后繼指針next。

二、為什么使用鏈表？即鏈表的特點(diǎn)

1.插入、刪除數(shù)據(jù)效率高O(1)級別（只需更改指針指向即可），隨機(jī)訪問效率低O(n)級別（需要從鏈頭至鏈尾進(jìn)行遍歷）。

2.和數(shù)組相比，內(nèi)存空間消耗更大，因?yàn)槊總€(gè)存儲數(shù)據(jù)的節(jié)點(diǎn)都需要額外的空間存儲后繼指針。

三、常用鏈表：單鏈表、循環(huán)鏈表和雙向鏈表

1.單鏈表

1）每個(gè)節(jié)點(diǎn)只包含一個(gè)指針，即后繼指針。

2）單鏈表有兩個(gè)特殊的節(jié)點(diǎn)，即首節(jié)點(diǎn)和尾節(jié)點(diǎn)。為什么特殊？用首節(jié)點(diǎn)地址表示整條鏈表，尾節(jié)點(diǎn)的后繼指針指向空地址null。

3）性能特點(diǎn)：插入和刪除節(jié)點(diǎn)的時(shí)間復(fù)雜度為O（1），查找的時(shí)間復(fù)雜度為O(n)。

2.循環(huán)鏈表

1）除了尾節(jié)點(diǎn)的后繼指針指向首節(jié)點(diǎn)的地址外均與單鏈表一致。

2）適用于存儲有循環(huán)特點(diǎn)的數(shù)據(jù)，比如約瑟夫問題。

3.雙向鏈表

1）節(jié)點(diǎn)除了存儲數(shù)據(jù)外，還有兩個(gè)指針分別指向前一個(gè)節(jié)點(diǎn)地址（前驅(qū)指針prev）和下一個(gè)節(jié)點(diǎn)地址（后繼指針next）。

2）首節(jié)點(diǎn)的前驅(qū)指針prev和尾節(jié)點(diǎn)的后繼指針均指向空地址。

3）性能特點(diǎn)：

和單鏈表相比，存儲相同的數(shù)據(jù)，需要消耗更多的存儲空間。
插入、刪除操作比單鏈表效率更高O(1)級別。以刪除操作為例，刪除操作分為2種情況：給定數(shù)據(jù)值刪除對應(yīng)節(jié)點(diǎn)和給定節(jié)點(diǎn)地址刪除節(jié)點(diǎn)。對于前一種情況，單鏈表和雙向鏈表都需要從頭到尾進(jìn)行遍歷從而找到對應(yīng)節(jié)點(diǎn)進(jìn)行刪除，時(shí)間復(fù)雜度為O(n)。對于第二種情況，要進(jìn)行刪除操作必須找到前驅(qū)節(jié)點(diǎn)，單鏈表需要從頭到尾進(jìn)行遍歷直到p->next = q，時(shí)間復(fù)雜度為O(n)，而雙向鏈表可以直接找到前驅(qū)節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(1)。
對于一個(gè)有序鏈表，雙向鏈表的按值查詢效率要比單鏈表高一些。因?yàn)槲覀兛梢杂涗浬洗尾檎业奈恢胮，每一次查詢時(shí)，根據(jù)要查找的值與p的大小關(guān)系，決定是往前還是往后查找，所以平均只需要查找一半的數(shù)據(jù)。
4.雙向循環(huán)鏈表：首節(jié)點(diǎn)的前驅(qū)指針指向尾節(jié)點(diǎn)，尾節(jié)點(diǎn)的后繼指針指向首節(jié)點(diǎn)。

四、選擇數(shù)組還是鏈表？

1.插入、刪除和隨機(jī)訪問的時(shí)間復(fù)雜度

數(shù)組：插入、刪除的時(shí)間復(fù)雜度是O(n)，隨機(jī)訪問的時(shí)間復(fù)雜度是O(1)。

鏈表：插入、刪除的時(shí)間復(fù)雜度是O(1)，隨機(jī)訪問的時(shí)間復(fù)雜端是O(n)。

2.數(shù)組缺點(diǎn)

1）若申請內(nèi)存空間很大，比如100M，但若內(nèi)存空間沒有100M的連續(xù)空間時(shí)，則會申請失敗，盡管內(nèi)存可用空間超過100M。

2）大小固定，若存儲空間不足，需進(jìn)行擴(kuò)容，一旦擴(kuò)容就要進(jìn)行數(shù)據(jù)復(fù)制，而這時(shí)非常費(fèi)時(shí)的。

3.鏈表缺點(diǎn)

1）內(nèi)存空間消耗更大，因?yàn)樾枰~外的空間存儲指針信息。

2）對鏈表進(jìn)行頻繁的插入和刪除操作，會導(dǎo)致頻繁的內(nèi)存申請和釋放，容易造成內(nèi)存碎片，如果是Java語言，還可能會造成頻繁的GC（自動垃圾回收器）操作。

4.如何選擇？

數(shù)組簡單易用，在實(shí)現(xiàn)上使用連續(xù)的內(nèi)存空間，可以借助CPU的緩沖機(jī)制預(yù)讀數(shù)組中的數(shù)據(jù)，所以訪問效率更高，而鏈表在內(nèi)存中并不是連續(xù)存儲，所以對CPU緩存不友好，沒辦法預(yù)讀。
如果代碼對內(nèi)存的使用非?？量?，那數(shù)組就更適合。

Review

Flink官網(wǎng) https://flink.apache.org/
從一手資料出發(fā)了解Flink架構(gòu)，使用場景，基本概念（DataStream、DataSet、并行度、State和CheckPoint等）
調(diào)用Flink方法測試demo上傳至github。

FlinkExemple

Tips

kafka可視化工具

Kafka Tool

redis可視化工具

1、fastoredis

2、Redis Desktop Manager

Share

一次很失敗的股市操作

這個(gè)月可謂是中國股市輝煌的一個(gè)月，超越了2015的大牛市漲幅。我雖然在底部開始定投股市，但這波可謂掙的教訓(xùn)比錢要多的多。低位定投50ETF，和創(chuàng)業(yè)板50，證券，一手好牌打爛。本來給自己定的規(guī)則是每月只買不賣，默默操作至少一年，無所謂一時(shí)漲跌做好所謂的價(jià)值投資。沒想到自己并不是股神。

所有政策為什么要禁“賭”，因?yàn)樵谫€局中情緒這貨真的控制不住，短期節(jié)奏之中，玩著玩著就忘記了當(dāng)時(shí)的原則，一旦好運(yùn)氣休假會賭的忘記自己。我曾經(jīng)覺得自己是一個(gè)股市可以做到堅(jiān)守原則的人。沒想到熊市沒有擾亂我，反而是突如其來的大漲把我弄到情緒崩潰，先盈利后踏空再追高。

事后反思。貪欲背后就是妄念，深深的妄念背后是人們對自己的不自知，人往往都是高估自己的。所以先認(rèn)清自己再丟掉妄念，讓我們會成為更加真實(shí)而理性的人。

Research

本周預(yù)研方向主要是Flink

目前需要完成的業(yè)務(wù)場景為：

• 從官方支持的Connector流式數(shù)據(jù)源（kafka）讀數(shù)據(jù)作為Source，然后從靜態(tài)數(shù)據(jù)源（HDFS）讀數(shù)據(jù)，都注冊成表，并完成標(biāo)準(zhǔn)sql的編寫，后入到Sink中。
• Flink中注冊UDF函數(shù)，并在SQL模塊中使用
• 自定義Connector包括（redis、hbase、hive、es 等）