✪基礎|想要成為大數據工程師?你需要掌握以下知識(下)


文| 林肯公園(拒絕任何不標明來源的轉載,轉發請標明本文來源36大數據)

接上篇《想要成為大數據工程師?你需要掌握以下知識(上)》。

在第一篇文章中,我們為大家介紹了大數據基礎平台架構和部分大數據工程師所需的技能,其中包括大數據通用處理平台、分散式存儲、資源調度、機器學習工具、數據分析/數據倉庫(SQL類)、消息隊列、流式計算、日誌收集、編程語言和數據分析挖掘等方面需要掌握的技術。

第一部分介紹完成後,有小夥伴表示要學這麼多知識才能成為大數據工程師,這也太難了。對此,筆者表示,孩子,你還是太單純了,那隻是第一部分。其實想想我們從小學到大學需要學的課程,這根本就是九牛一毛嘛,萬里長征不是一天走完的,長城也不是一天能夠建好的。要成為大數據工程師,那麼就需要循序漸進的掌握整個大數據系統里所包含的知識,你可以一個系列一個系列的學。比如說,你先學了數據分析挖掘所需掌握的技能MATLAB、SPSS和SAS后,找到數據分析師的工作,然後繼續學其他的技能,最後成為大數據工程師。

我們想要告訴大家的是成為大數據工程師需要掌握的知識體系,而作為初學者,你可以先從簡單的入手,慢慢在學更深的知識,拿出高考的恆心和堅持來,肯定能行。

值得一提的是,目前大數據工程師的月薪都是20K起,月收入兩萬的薪資是不是很誘人?而且大數據工程師是非常容易找到工作的,所以……Why not?

不扯犢子了,繼續說要成為大數據工程師需要掌握的技能第二部分知識點,這一部分內容主要包括數據可視化、機器學習和演算法三個分支。讓我們開始吧。

數據可視化

1、R

R不僅是編程語言,同時也R具有強大的統計計算功能和便捷的數據可視化系統。在此,推薦大家看一本書,這本書叫做《R數據可視化手冊》。

《R數據可視化手冊》重點講解R的繪圖系統,指導讀者通過繪圖系統實現數據可視化。書中提供了快速繪製高質量圖形的150多種技巧,每個技巧用來解決一個特定的繪圖需求。讀者可以通過目錄快速定位到自己遇到的問題,查閱相應的解決方案。同時,作者在大部分的技巧之後會進行一些討論和延伸,介紹一些總結出的繪圖技巧。 《R數據可視化手冊》側重於解決具體問題,是R數據可視化的實戰秘籍。《R數據可視化手冊》中絕大多數的繪圖案例都是以強大、靈活製圖而著稱的R包ggplot2實現的,充分展現了ggplot2生動、翔實的一面。從如何畫點圖、線圖、柱狀圖,到如何添加註解、修改坐標軸和圖例,再到分面的使用和顏色的選取等,本書都有清晰的講解。

此書在網上就可以購買得到,當然也有電子版。在此,我們放出一張用R做出來的可視化作品。

D3.js

D3 (Data-Driven Documents)是基於數據的文檔操作javascript庫,D3能夠把數據和HTML、SVG、CSS結合起來,創造出可交互的數據圖表。


ECharts

ECharts是一款數據可視化的純JavaScript圖標庫,其擁有混搭圖表、拖拽重計算、製作數據視圖、動態類型切換、圖例開關、數據區域選擇、值域漫遊、多維度堆積等非常豐富的功能。

ECharts (Enterprise Charts 商業產品圖表庫)是基於HTML5 Canvas的一個純Javascript圖表庫,提供直觀,生動,可交互,可個性化定製的數據可視化圖表。創新的拖拽重計算、數據視圖、值域漫遊等特性大大增強了用戶體驗,賦予了用戶對數據進行挖掘、整合的能力。

ECharts提供商業產品常用圖表庫,底層基於ZRender,創建了坐標系,圖例,提示,工具箱等基礎組件,並在此上構建出折線圖(區域圖)、柱狀圖(條狀圖)、散點圖(氣泡圖)、K線圖、餅圖(環形圖)、地圖、力導向布局圖,同時支持任意維度的堆積和多圖表混合展現。

Excel

Excel中大量的公式函數可以應用選擇,使用Microsoft Excel可以執行計算,分析信息並管理電子錶格或網頁中的數據信息列表與數據資料圖表製作,可以實現許多方便的功能,帶給使用者方便。與其配套組合的有:Word、PowerPoint、Access、InfoPath及Outlook,Publisher

事實上,Excel完全可以滿足大家日常工作中圖表製作和數據可視化的需求,所以,想要進入大數據行業,學好Excel是基礎。

Python

Python 的科學棧相當成熟,各種應用場景都有相關的模塊,包括機器學習和數據分析。數據可視化是發現數據和展示結果的重要一環,只不過過去以來,相對於 R 這樣的工具,發展還是落後一些。

幸運的是,過去幾年出現了很多新的Python數據可視化庫,彌補了一些這方面的差距。matplotlib 已經成為事實上的數據可視化方面最主要的庫,此外還有很多其他庫,例如vispy,bokeh, seaborn, pyga, folium 和 networkx,這些庫有些是構建在 matplotlib 之上,還有些有其他一些功能。


機器學習

機器學習基礎

聚類

將物理或抽象對象的集合分成由類似的對象組成的多個類的過程被稱為聚類。由聚類所生成的簇是一組數據對象的集合,這些對象與同一個簇中的對象彼此相似,與其他簇中的對象相異。「物以類聚,人以群分」,在自然科學和社會科學中,存在著大量的分類問題。聚類分析又稱群分析,它是研究(樣品或指標)分類問題的一種統計分析方法。聚類分析起源於分類學,但是聚類不等於分類。聚類與分類的不同在於,聚類所要求劃分的類是未知的。聚類分析內容非常豐富,有系統聚類法、有序樣品聚類法、動態聚類法、模糊聚類法、圖論聚類法、聚類預報法等。

在數據挖掘中,聚類也是很重要的一個概念。

傳統的聚類分析計算方法主要有如下幾種:

1、劃分方法(partitioning methods)

2、層次方法(hierarchical methods)

3、基於密度的方法(density-based methods)

4、基於網格的方法(grid-based methods)

5、基於模型的方法(model-based methods)

當然聚類方法還有:傳遞閉包法,布爾矩陣法,直接聚類法,相關性分析聚類,基於統計的聚類方法等。

時間序列

時間序列(或稱動態數列)是指將同一統計指標的數值按其發生的時間先後順序排列而成的數列。時間序列分析的主要目的是根據已有的歷史數據對未來進行預測。構成要素:長期趨勢,季節變動,循環變動,不規則變動。

種類:

絕對數時間序列

時期序列:由時期總量指標排列而成的時間序列 。

相對數時間序列

把一系列同種相對數指標按時間先後順序排列而成的時間序列叫做相對數時間序列。

平均數時間序列

平均數時間序列是指由一系列同類平均指標按時間先後順序排列的時間序列。

保證序列中各期指標數值的可比性

(一)時期長短最好一致
(二)總體範圍應該一致
(三)指標的經濟內容應該統一
(四)計算方法應該統一
(五)計算價格和計量單位可比

推薦系統

定義:它是利用電子商務網站向客戶提供商品信息和建議,幫助用戶決定應該購買什麼產品,模擬銷售人員幫助客戶完成購買過程」。

推薦系統有3個重要的模塊:用戶建模模塊、推薦對象建模模塊、推薦演算法模塊。通用的推薦系統模型流程如圖。推薦系統把用戶模型中興趣需求信息和推薦對象模型中的特徵信息匹配,同時使用相應的推薦演算法進行計算篩選,找到用戶可能感興趣的推薦對象,然後推薦給用戶。

回歸分析

回歸分析(regression analysis)是確定兩種或兩種以上變數間相互依賴的定量關係的一種統計分析方法。運用十分廣泛,回歸分析按照涉及的變數的多少,分為一元回歸和多元回歸分析;在線性回歸中,按照因變數的多少,可分為簡單回歸分析和多重回歸分析;按照自變數和因變數之間的關係類型,可分為線性回歸分析和非線性回歸分析。如果在回歸分析中,只包括一個自變數和一個因變數,且二者的關係可用一條直線近似表示,這種回歸分析稱為一元線性回歸分析。如果回歸分析中包括兩個或兩個以上的自變數,且自變數之間存在線性相關,則稱為多元線性回歸分析。

文本挖掘

文本挖掘有時也被稱為文字探勘、文本數據挖掘等,大致相當於文字分析,一般指文本處理過程中產生高質量的信息。高質量的信息通常通過分類和預測來產生,如模式識別。文本挖掘通常涉及輸入文本的處理過程(通常進行分析,同時加上一些衍生語言特徵以及消除雜音,隨後插入到資料庫中) ,產生結構化數據,並最終評價和解釋輸出。』高品質』的文本挖掘通常是指某種組合的相關性,新穎性和趣味性。典型的文本挖掘方法包括文本分類,文本聚類,概念/實體挖掘,生產精確分類,觀點分析,文檔摘要和實體關係模型(即,學習已命名實體之間的關係) 。

決策樹

決策樹(Decision Tree)是在已知各種情況發生概率的基礎上,通過構成決策樹來求取凈現值的期望值大於等於零的概率,評價項目風險,判斷其可行性的決策分析方法,是直觀運用概率分析的一種圖解法。由於這種決策分支畫成圖形很像一棵樹的枝幹,故稱決策樹。在機器學習中,決策樹是一個預測模型,他代表的是對象屬性與對象值之間的一種映射關係。Entropy = 系統的凌亂程度,使用演算法ID3, C4.5和C5.0生成樹演算法使用熵。這一度量是基於信息學理論中熵的概念。

決策樹是一種樹形結構,其中每個內部節點表示一個屬性上的測試,每個分支代表一個測試輸出,每個葉節點代表一種類別。

分類樹(決策樹)是一種十分常用的分類方法。他是一種監管學習,所謂監管學習就是給定一堆樣本,每個樣本都有一組屬性和一個類別,這些類別是事先確定的,那麼通過學習得到一個分類器,這個分類器能夠對新出現的對象給出正確的分類。這樣的機器學習就被稱之為監督學習。

支持向量機

支持向量機(Support Vector Machine,SVM)是Corinna Cortes和Vapnik等於1995年首先提出的,它在解決小樣本、非線性及高維模式識別中表現出許多特有的優勢,並能夠推廣應用到函數擬合等其他機器學習問題中。

在機器學習中,支持向量機(SVM,還支持矢量網路)是與相關的學習演算法有關的監督學習模型,可以分析數據,識別模式,用於分類和回歸分析。

貝葉斯分類

貝葉斯分類是一類分類演算法的總稱,這類演算法均以貝葉斯定理為基礎,故統稱為貝葉斯分類。貝葉斯分類是統計學的分類方法,其分析方法的特點是使用概率來表示所有形式的不確定性,學習或推理都要用概率規則來實現。

神經網路

神經網路可以指向兩種,一個是生物神經網路,一個是人工神經網路。人工神經網路(Artificial Neural Networks,簡寫為ANNs)也簡稱為神經網路(NNs)或稱作連接模型(Connection Model),它是一種模仿動物神經網路行為特徵,進行分散式並行信息處理的演算法數學模型。這種網路依靠系統的複雜程度,通過調整內部大量節點之間相互連接的關係,從而達到處理信息的目的。

人工神經網路:是一種應用類似於大腦神經突觸聯接的結構進行信息處理的數學模型。在工程與學術界也常直接簡稱為「神經網路」或類神經網路。

機器學習工具

Mahout 

Mahout 是 Apache Software Foundation(ASF) 旗下的一個開源項目,提供一些可擴展的機器學習領域經典演算法的實現,旨在幫助開發人員更加方便快捷地創建智能應用程序。Mahout包含許多實現,包括聚類、分類、推薦過濾、頻繁子項挖掘。此外,通過使用 Apache Hadoop 庫,Mahout 可以有效地擴展到雲中。

Spark Mlib

MLlib是一個機器學習庫,它提供了各種各樣的演算法,這些演算法用來在集群上針對分類、回歸、聚類、協同過濾等(可以在 Machine learning 上查看Toptal的文章,來獲取更過的信息)。其中一些演算法也可以應用到流數據上,例如使用普通最小二乘法或者K均值聚類(還有更多)來計算線性回歸。Apache Mahout(一個針對Hadoop的機器學習庫)已經脫離MapReduce,轉而加入Spark MLlib。

TensorFlow (Google 系)

TensorFlow是谷歌基於DistBelief進行研發的第二代人工智慧學習系統,其命名來源於本身的運行原理。Tensor(張量)意味著N維數組,Flow(流)意味著基於數據流圖的計算,TensorFlow為張量從圖象的一端流動到另一端計算過程。TensorFlow是將複雜的數據結構傳輸至人工智慧神經網中進行分析和處理過程的系統。


TensorFlow可被用於語音識別或圖像識別等多項機器深度學習領域,對2011年開發的深度學習基礎架構DistBelief進行了各方面的改進,它可在小到一部智能手機、大到數千台數據中心伺服器的各種設備上運行。TensorFlow將完全開源,任何人都可以用。

Amazon Machine Learning

Amazon Machine Learning 是一項面向各個水平階層開發人員的服務,可以幫助他們利用機器學習技術。Amazon Machine Learning 提供可視化的工具和嚮導,指導您按部就班地創建機器學習模型,而無需學習複雜的機器學習演算法和技術。當您的模型準備好以後,Amazon Machine Learning 只要使用簡單的 API 即可讓您的應用程序輕鬆獲得預測能力,而無需實現自定義預測生成碼或管理任何基礎設施。

Amazon Machine Learning 採用與 Amazon 內部數據科學家社區多年來一直使用的機器學習技術相同的技術,具有穩定可靠、容易擴展的特點。此服務使用強大的演算法通過發現已有數據中的規律來創建機器學習模型。然後,Amazon Machine Learning 會使用這些模型來處理新數據併為應用程序生成預測結果。

Amazon Machine Learning 具有極強的可擴展性,每天可以生成數十億條預測結果,並以高吞吐量實時地將其送出。使用 Amazon Machine Learning 不需要對硬體或軟體事先投入資金,只需要根據使用量付費,所以不妨先從小規模做起,然後根據應用程序的發展情況再酌情進行擴展。

DMTK (微軟分散式機器學習工具)

DMTK 是微軟分散式機器學習工具包。

DMTK 包括以下幾個項目:

DMTK framework(Multiverso): 參數伺服器架構的機器學習

LightLDA: 用於大規模主題模型的可擴展、快速、輕量級系統.

Distributed word embedding:文字嵌入分散式演算法.

Distributed skipgram mixture: 多義文字嵌入分散式演算法

演算法

一致性

數據一致性通常指關聯數據之間的邏輯關係是否正確和完整。而數據存儲的一致性模型則可以認為是存儲系統和數據使用者之間的一種約定。如果使用者遵循這種約定,則可以得到系統所承諾的訪問結果常用的一致性模型有:

a、嚴格一致性(linearizability, strict/atomic Consistency):讀出的數據始終為最近寫入的數據。這種一致性只有全局時鐘存在時才有可能,在分散式網路環境不可能實現。

b、順序一致性(sequential consistency):所有使用者以同樣的順序看到對同一數據的操作,但是該順序不一定是實時的。

c、因果一致性(causal consistency):只有存在因果關係的寫操作才要求所有使用者以相同的次序看到,對於無因果關係的寫入則並行進行,無次序保證。因果一致性可以看做對順序一致性性能的一種優化,但在實現時必須建立與維護因果依賴圖,是相當困難的。

d、管道一致性(PRAM/FIFO consistency):在因果一致性模型上的進一步弱化,要求由某一個使用者完成的寫操作可以被其他所有的使用者按照順序的感知到,而從不同使用者中來的寫操作則無需保證順序,就像一個一個的管道一樣。 相對來說比較容易實現。

e、弱一致性(weak consistency):只要求對共享數據結構的訪問保證順序一致性。對於同步變數的操作具有順序一致性,是全局可見的,且只有當沒有寫操作等待處理時才可進行,以保證對於臨界區域的訪問順序進行。在同步時點,所有使用者可以看到相同的數據。

f、 釋放一致性(release consistency):弱一致性無法區分使用者是要進入臨界區還是要出臨界區, 釋放一致性使用兩個不同的操作語句進行了區分。需要寫入時使用者acquire該對象,寫完后release,acquire-release之間形成了一個臨界區,提供 釋放一致性也就意味著當release操作發生后,所有使用者應該可以看到該操作。

g、最終一致性(eventual consistency):當沒有新更新的情況下,更新最終會通過網路傳播到所有副本點,所有副本點最終會一致,也就是說使用者在最終某個時間點前的中間過程中無法保證看到的是新寫入的數據。可以採用最終一致性模型有一個關鍵要求:讀出陳舊數據是可以接受的。

h、delta consistency:系統會在delta時間內達到一致。這段時間內會存在一個不一致的窗口,該窗口可能是因為log shipping的過程導致。這是書上的原話。。我也搞不很清楚。。 資料庫完整性(Database Integrity)是指資料庫中數據的正確性和相容性。資料庫完整性由各種各樣的完整性約束來保證,因此可以說資料庫完整性設計就是資料庫完整性約束的設計。包括實體完整性。域完整性。參照完整性。用戶定義完整性。可以主鍵。check約束。外鍵來一一實現。這個使用較多

paxos

Paxos演算法是萊斯利·蘭伯特(Leslie Lamport,就是 LaTeX 中的」La」,此人現在在微軟研究院)于1990年提出的一種基於消息傳遞的一致性演算法。這個演算法被認為是類似演算法中最有效的。

Paxos 演算法解決的問題是一個分散式系統如何就某個值(決議)達成一致。一個典型的場景是,在一個分散式資料庫系統中,如果各節點的初始狀態一致,每個節點執行相同的操作序列,那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列,需要在每一條指令上執行一個「一致性演算法」以保證每個節點看到的指令一致。一個通用的一致性演算法可以應用在許多場景中,是分散式計算中的重要問題。因此從20世紀80年代起對於一致性演算法的研究就沒有停止過。節點通信存在兩種模型:共享內存(Shared memory)和消息傳遞(Messages passing)。Paxos 演算法就是一種基於消息傳遞模型的一致性演算法。

raft

Raft是由Stanford提出的一種更易理解的一致性演算法,意在取代目前廣為使用的Paxos演算法。目前,在各種主流語言中都有了一些開源實現,比如本文中將使用的基於JGroups的Raft協議實現。

在Raft中,每個結點會處於下面三種狀態中的一種:

  • follower:所有結點都以follower的狀態開始。如果沒收到leader消息則會變成candidate狀態

  • candidate:會向其他結點「拉選票」,如果得到大部分的票則成為leader。這個過程就叫做Leader選舉(Leader Election)

  • leader:所有對系統的修改都會先經過leader。每個修改都會寫一條日誌(log entry)。leader收到修改請求后的過程如下,這個過程叫做日誌複製(Log Replication):

    • 複製日誌到所有follower結點(replicate entry)

    • 大部分結點響應時才提交日誌

    • 通知所有follower結點日誌已提交

    • 所有follower也提交日誌

    • 現在整個系統處於一致的狀態

gossip

Gossip演算法如其名,靈感來自辦公室八卦,只要一個人八卦一下,在有限的時間內所有的人都會知道該八卦的信息,這種方式也與病毒傳播類似,因此Gossip有眾多的別名「閑話演算法」、「疫情傳播演算法」、「病毒感染演算法」、「謠言傳播演算法」。

但Gossip並不是一個新東西,之前的泛洪查找、路由演算法都歸屬於這個範疇,不同的是Gossip給這類演算法提供了明確的語義、具體實施方法及收斂性證明。

Gossip演算法又被稱為反熵(Anti-Entropy),熵是物理學上的一個概念,代表雜亂無章,而反熵就是在雜亂無章中尋求一致,這充分說明了Gossip的特點:在一個有界網路中,每個節點都隨機地與其他節點通信,經過一番雜亂無章的通信,最終所有節點的狀態都會達成一致。每個節點可能知道所有其他節點,也可能僅知道幾個鄰居節點,只要這些節可以通過網路連通,最終他們的狀態都是一致的,當然這也是疫情傳播的特點。

要注意到的一點是,即使有的節點因宕機而重啟,有新節點加入,但經過一段時間后,這些節點的狀態也會與其他節點達成一致,也就是說,Gossip天然具有分散式容錯的優點。

數據結構

棧,隊列,鏈表

作為一種數據結構,是一種只能在一端進行插入和刪除操作的特殊線性表。它按照先進後出的原則存儲數據,先進入的數據被壓入棧底,最後的數據在棧頂,需要讀數據的時候從棧頂開始彈出數據(最後一個數據被第一個讀出來)。棧具有記憶作用,對棧的插入與刪除操作中,不需要改變棧底指針。

是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top),另一端為棧底(bottom);棧底固定,而棧頂浮動;棧中元素個數為零時稱為空棧。插入一般稱為進棧(PUSH),刪除則稱為退棧(POP)。棧也稱為後進先出表。

隊列是一種特殊的線性表,特殊之處在於它只允許在表的前端(front)進行刪除操作,而在表的後端(rear)進行插入操作,和棧一樣,隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾,進行刪除操作的端稱為隊頭。

鏈表是一種物理存儲單元上非連續、非順序的存儲結構,數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點(鏈表中每一個元素稱為結點)組成,結點可以在運行時動態生成。每個結點包括兩個部分:一個是存儲數據元素的數據域,另一個是存儲下一個結點地址的指針域。 相比于線性表順序結構,操作複雜。由於不必須按順序存儲,鏈表在插入的時候可以達到O(1)的複雜度,比另一種線性表順序表快得多,但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間,而線性表和順序表相應的時間複雜度分別是O(logn)和O(1)。

散列表

散列表(Hash table,也叫哈希表),是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說,它通過把關鍵碼值映射到表中一個位置來訪問記錄,以加快查找的速度。這個映射函數叫做散列函數,存放記錄的數組叫做散列表。

給定表M,存在函數f(key),對任意給定的關鍵字值key,代入函數后若能得到包含該關鍵字的記錄在表中的地址,則稱表M為哈希(Hash)表,函數f(key)為哈希(Hash) 函數。

二叉樹,紅黑樹,B樹

二叉樹


在電腦科學中,二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作「左子樹」(left subtree)和「右子樹」(right subtree)。二叉樹常被用於實現二叉查找樹和二叉堆。


二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點),二叉樹的子樹有左右之分,次序不能顛倒。二叉樹的第i層至多有2^{i-1}個結點;深度為k的二叉樹至多有2^k-1個結點;對任何一棵二叉樹T,如果其終端結點數為n_0,度為2的結點數為n_2,則n_0=n_2+1。

一棵深度為k,且有2^k-1個節點稱之為滿二叉樹;深度為k,有n個節點的二叉樹,當且僅當其每一個節點都與深度為k的滿二叉樹中,序號為1至n的節點對應時,稱之為完全二叉樹。


紅黑樹


紅黑樹(Red Black Tree) 是一種自平衡二叉查找樹,是在電腦科學中用到的一種數據結構,典型的用途是實現關聯數組。


它是在1972年由Rudolf Bayer發明的,當時被稱為平衡二叉B樹(symmetric binary B-trees)。後來,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的「紅黑樹」。紅黑樹和AVL樹類似,都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡,從而獲得較高的查找性能。

它雖然是複雜的,但它的最壞情況運行時間也是非常良好的,並且在實踐中是高效的: 它可以在O(log n)時間內做查找,插入和刪除,這裡的n 是樹中元素的數目。

B樹

在B-樹中查找給定關鍵字的方法是,首先把根結點取來,在根結點所包含的關鍵字K1,…,Kn查找給定的關鍵字(可用順序查找或二分查找法),若找到等於給定值的關鍵字,則查找成功;否則,一定可以確定要查找的關鍵字在Ki與Ki+1之間,Pi為指向子樹根節點的指針,此時取指針Pi所指的結點繼續查找,直至找到,或指針Pi為空時查找失敗。


在數學中,一個圖(Graph)是表示物件與物件之間的關係的數學對象,是圖論的基本研究對象。


常用演算法

1.排序

將雜亂無章的數據元素,通過一定的方法按關鍵字順序排列的過程叫做排序。假定在待排序的記錄序列中,存在多個具有相同的關鍵字的記錄,若經過排序,這些記錄的相對次序保持不變,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,則稱這種排序演算法是穩定的;否則稱為不穩定的。

插入排序

有一個已經有序的數據序列,要求在這個已經排好的數據序列中插入一個數,但要求插入后此數據序列仍然有序,這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中,從而得到一個新的、個數加一的有序數據,演算法適用於少量數據的排序,時間複雜度為O(n^2)。是穩定的排序方法。插入演算法把要排序的數組分成兩部分:第一部分包含了這個數組的所有元素,但將最後一個元素除外(讓數組多一個空間才有插入的位置),而第二部分就只包含這一個元素(即待插入元素)。在第一部分排序完成後,再將這個最後元素插入到已排好序的第一部分中。

插入排序的基本思想是:每步將一個待排序的紀錄,按其關鍵碼值的大小插入前面已經排序的文件中適當位置上,直到全部插入完為止。

桶排序

桶排序 (Bucket sort)或所謂的箱排序,是一個排序演算法,工作的原理是將數組分到有限數量的桶子里。每個桶子再個別排序(有可能再使用別的排序演算法或是以遞歸方式繼續使用桶排序進行排序)。桶排序是鴿巢排序的一種歸納結果。當要被排序的數組內的數值是均勻分配的時候,桶排序使用線性時間(Θ(n))。但桶排序並不是 比較排序,他不受到 O(n log n) 下限的影響。

堆排序

堆排序(Heapsort)是指利用堆積樹(堆)這種數據結構所設計的一種排序演算法,它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆,是完全二叉樹。大根堆的要求是每個節點的值都不大於其父節點的值,即A[PARENT[i]] >= A[i]。在數組的非降序排序中,需要使用的就是大根堆,因為根據大根堆的要求可知,最大的值一定在堆頂。

2.快速排序

快速排序(Quicksort)是對冒泡排序的一種改進。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,然後再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。

3,最大子數組

最大和子數組是數組中和最大的子數組,又名最大和子序列。子數組是數組中連續的n個元素,比如a2,a3,a4就是一個長度為3的子數組。顧名思義求最大和子數組就是要求取和最大的子數組。

n個元素的數組包含n個長度為1的子數組:{a0},{a1},…{an-1};

n個元素的數組包含n-1個長度為2的子數組:{a0,a1},{a1,a2},{an-2,an-1};

………………………………………………………………………………………………

n個元素的數組包含1個長度為n的子數組:{a0,a1,…,an-1};

所以,一個長度為n的數組包含的子數組個數為n+(n-1)+…+1=n*(n-1)/2。

4.最長公共子序列

一個數列 ,如果分別是兩個或多個已知數列的子序列,且是所有符合此條件序列中最長的,則 稱為已知序列的最長公共子序列。

最長公共子序列,英文縮寫為LCS(Longest Common Subsequence)。其定義是,一個序列 S ,如果分別是兩個或多個已知序列的子序列,且是所有符合此條件序列中最長的,則 S 稱為已知序列的最長公共子序列。而最長公共子串(要求連續)和最長公共子序列是不同的。

最長公共子序列是一個十分實用的問題,它可以描述兩段文字之間的「相似度」,即它們的雷同程度,從而能夠用來辨別抄襲。對一段文字進行修改之後,計算改動前後文字的最長公共子序列,將除此子序列外的部分提取出來,這種方法判斷修改的部分,往往十分準確。簡而言之,百度知道、百度百科都用得上。

5.最小生成樹

一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖,且包含原圖中的所有 n 個結點,並且有保持圖連通的最少的邊。最小生成樹可以用kruskal(克魯斯卡爾)演算法或prim(普里姆)演算法求出。

最短路徑

用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展,直到擴展到終點為止。Dijkstra演算法能得出最短路徑的最優解,但由於它遍歷計算的節點很多,所以效率低。

6.矩陣的存儲和運算

列矩陣(column major)和行矩陣(row major)是數學上的概念,和電腦無關,它只是一套約定(convention),按照矢量和矩陣的乘法運算時,矢量是列矢還是行矢命名,這裡只說4×4矩陣。齊次矢量可以看成是一個1×4的矩陣,就是行矢;或者4×1的矩陣,就是列矢。

雲計算

雲計算(Cloud Computing)是分散式計算(Distributed Computing)、並行計算(Parallel Computing)、效用計算(Utility Computing)、[5] 網路存儲(Network Storage Technologies)、虛擬化(Virtualization)、負載均衡(Load Balance)、熱備份冗余(High Available)等傳統電腦和網路技術發展融合的產物。

雲計算(cloudcomputing)是基於互聯網的相關服務的增加、使用和交付模式,通常涉及通過互聯網來提供動態易擴展且經常是虛擬化的資源。

雲服務

SaaS

SaaS是Software-as-a-Service(軟體即服務)的簡稱,隨著互聯網技術的發展和應用軟體的成熟, 在21世紀開始興起的一種完全創新的軟體應用模式。它與「on-demand software」(按需軟體),the application service provider(ASP,應用服務提供商),hosted software(托管軟體)所具有相似的含義。它是一種通過Internet提供軟體的模式,廠商將應用軟體統一部署在自己的伺服器上,客戶可以根據自己實際需求,通過互聯網向廠商定購所需的應用軟體服務,按定購的服務多少和時間長短向廠商支付費用,並通過互聯網獲得廠商提供的服務。

SaaS 應用軟體的價格通常為「全包」費用,囊括了通常的應用軟體許可證費、軟體維護費以及技術支持費,將其統一為每個用戶的月度租用費。

PaaS

PaaS是Platform-as-a-Service的縮寫,意思是平台即服務。 把伺服器平台作為一種服務提供的商業模式。通過網路進行程序提供的服務稱之為SaaS(Software as a Service),而雲計算時代相應的伺服器平台或者開發環境作為服務進行提供就成為了PaaS(Platform as a Service)。

所謂PaaS實際上是指將軟體研發的平台(計世資訊定義為業務基礎平台)作為一種服務,以SaaS的模式提交給用戶。因此,PaaS也是SaaS模式的一種應用。但是,PaaS的出現可以加快SaaS的發展,尤其是加快SaaS應用的開發速度。在2007年國內外SaaS廠商先後推出自己的PAAS平台。

IaaS

IaaS(Infrastructure as a Service),即基礎設施即服務。

消費者通過Internet 可以從完善的電腦基礎設施獲得服務。這類服務稱為基礎設施即服務。基於 Internet 的服務(如存儲和資料庫)是 IaaS的一部分。Internet上其他類型的服務包括平台即服務(Platform as a Service,PaaS)和軟體即服務(Software as a Service,SaaS)。PaaS提供了用戶可以訪問的完整或部分的應用程序開發,SaaS則提供了完整的可直接使用的應用程序,比如通過 Internet管理企業資源。

Openstack

OpenStack是一個開源的雲計算管理平台項目,由幾個主要的組件組合起來完成具體工作。OpenStack支持幾乎所有類型的雲環境,項目目標是提供實施簡單、可大規模擴展、豐富、標準統一的雲計算管理平台。OpenStack通過各種互補的服務提供了基礎設施即服務(IaaS)的解決方案,每個服務提供API以進行集成。

OpenStack是IaaS(基礎設施即服務)組件,讓任何人都可以自行建立和提供雲端運算服務。

此外,OpenStack也用作建立防火牆內的「私有雲」(Private Cloud),提供機構或企業內各部門共享資源。

Docker

Docker 是一個開源的應用容器引擎,讓開發者可以打包他們的應用以及依賴包到一個可移植的容器中,然後發布到任何流行的 Linux 機器上,也可以實現虛擬化。容器是完全使用沙箱機制,相互之間不會有任何介面。

Docker 使用客戶端-伺服器 (C/S) 架構模式,使用遠程AP

36大數據(dashuju36)


---
資料來源:✪基礎|想要成為大數據工程師?你需要掌握以下知識(下)
如果內容有不適當或對出處有疑慮,請立即通知客服中心
Facebook留言板
您可能有興趣
客服信箱 客服信箱
一則未讀訊息
聯絡線上客服