鄭春紅，王偉

（青島職業(yè)技術(shù)學(xué)院信息學(xué)院，青島266000）

0 引言

隨著人工智能、物聯(lián)網(wǎng)、云計算的興起，大數(shù)據(jù)越來越受到廣泛關(guān)注。大數(shù)據(jù)時代，以海量數(shù)據(jù)為中心的管理和處理技術(shù)已取得良好的發(fā)展態(tài)勢，大數(shù)據(jù)產(chǎn)業(yè)應(yīng)用推進(jìn)勢頭良好，在金融、醫(yī)療健康、汽車交通、文化娛樂、電子商務(wù)等應(yīng)用領(lǐng)域不斷創(chuàng)新發(fā)展。

大數(shù)據(jù)技術(shù)中較為核心的技術(shù)如Hadoop、HBase、Hive、Spark 等，這些核心技術(shù)的很多核心理念都是建立在計算機(jī)專業(yè)基礎(chǔ)課程之上的，如數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫原理、Linux 操作系統(tǒng)等。例如，Hadoop 技術(shù)中利用Map/Reduce 框架計算時，Map 結(jié)果在shuffle 階段進(jìn)行分區(qū)、排序、合并，再進(jìn)入Reduce 規(guī)約階段。其中，排序過程為了提高內(nèi)存利用率循環(huán)利用內(nèi)存空間，如80%（默認(rèn)）寫，處理后放到外存一個文件，寫的過程其他20%空間可以繼續(xù)寫，原來80%處理完釋放后又可以利用，其原理運(yùn)用的就是數(shù)據(jù)結(jié)構(gòu)中的循環(huán)隊列；再比如，Hadoop 技術(shù)采用HDFS 分布式文件管理系統(tǒng)管理數(shù)據(jù)，Map/Reduce 框架中一個Reduce 可以保證輸出結(jié)果有序，多個Reduce 要保證輸出數(shù)據(jù)全局有序，Map輸出結(jié)果要根據(jù)Reduce 的個數(shù)，采用除留余數(shù)法將數(shù)據(jù)分配到對應(yīng)的Reduce 中進(jìn)行計算，其方法采用的就是數(shù)據(jù)結(jié)構(gòu)中的Hash 函數(shù)。

本文主要分析《數(shù)據(jù)結(jié)構(gòu)》課程與大數(shù)據(jù)技術(shù)的關(guān)系并探索大數(shù)據(jù)背景下《數(shù)據(jù)結(jié)構(gòu)》課程的改革。

1 高職院?！稊?shù)據(jù)結(jié)構(gòu)》課程建設(shè)現(xiàn)狀

（1）亟待開發(fā)大數(shù)據(jù)背景下適合高職院校大數(shù)據(jù)專業(yè)學(xué)生的《數(shù)據(jù)結(jié)構(gòu)》校本課程

目前，隨著大數(shù)據(jù)技術(shù)的不斷發(fā)展，高職院校計算機(jī)專業(yè)相繼開設(shè)大數(shù)據(jù)專業(yè)，《數(shù)據(jù)結(jié)構(gòu)》作為專業(yè)核心課程，即是前面課程的升華，也是后續(xù)課程的先導(dǎo)，應(yīng)緊密結(jié)合大數(shù)據(jù)的相關(guān)技術(shù)理論，將知識點(diǎn)與大數(shù)據(jù)內(nèi)容建立鏈接，突出重點(diǎn)，通過實(shí)踐踐行大數(shù)據(jù)相關(guān)理論?，F(xiàn)在，高職院校亟待開發(fā)適合高職院校大數(shù)據(jù)專業(yè)學(xué)生的《數(shù)據(jù)結(jié)構(gòu)》校本課程及資源。

（2）數(shù)據(jù)結(jié)構(gòu)教學(xué)內(nèi)容與新技術(shù)發(fā)展脫節(jié)

數(shù)據(jù)結(jié)構(gòu)主要內(nèi)容有線性表、棧和隊列、串、數(shù)組和廣義表、樹和二叉樹、圖、查找、排序等，內(nèi)容抽象、繁雜，并且后續(xù)章節(jié)知識點(diǎn)較為復(fù)雜，高職院校學(xué)生難以理解和掌握。內(nèi)容設(shè)置上，每章節(jié)的知識點(diǎn)及實(shí)踐教學(xué)案例素材較為傳統(tǒng)且陳舊，與大數(shù)據(jù)等新型技術(shù)的發(fā)展脫節(jié)嚴(yán)重，難以起到對后續(xù)章節(jié)的先導(dǎo)作用。

（3）師資隊伍的培訓(xùn)有待提高[1]

目前，大數(shù)據(jù)專業(yè)科班出身的教師資源有限，專業(yè)教師大多通過短期或中長期培訓(xùn)學(xué)習(xí)大數(shù)據(jù)技術(shù)，自身的大數(shù)據(jù)理論水平和專業(yè)水平極為有限，實(shí)踐能力相對缺乏，將大數(shù)據(jù)核心理論技術(shù)融入《數(shù)據(jù)結(jié)構(gòu)》課程的能力有限。

2 將大數(shù)據(jù)融入《數(shù)據(jù)結(jié)構(gòu)》課程的建設(shè)方案

（1）將數(shù)據(jù)結(jié)構(gòu)內(nèi)容與大數(shù)據(jù)技術(shù)進(jìn)行鏈接

《數(shù)據(jù)結(jié)構(gòu)》作為計算機(jī)專業(yè)核心課程，亟待融入大數(shù)據(jù)前沿理論和技術(shù)的相關(guān)知識。同時，由于《數(shù)據(jù)結(jié)構(gòu)》課程較為抽象，學(xué)生在學(xué)習(xí)時如果能知道該知識點(diǎn)在當(dāng)前計算機(jī)行業(yè)前沿技術(shù)上的具體應(yīng)用，會極大地提高學(xué)生的學(xué)習(xí)興趣，提高教學(xué)效果。本文結(jié)合數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容，以及大數(shù)據(jù)技術(shù)理論與技術(shù)的發(fā)展，總結(jié)了大數(shù)據(jù)技術(shù)中用到的數(shù)據(jù)結(jié)構(gòu)，并將其融入到《數(shù)據(jù)結(jié)構(gòu)》課程的教學(xué)內(nèi)容中。激發(fā)學(xué)生的學(xué)習(xí)興趣，培養(yǎng)學(xué)生的大數(shù)據(jù)思維，為后續(xù)課程做充分的引導(dǎo)作用。

（2）將大數(shù)據(jù)技術(shù)滲入數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)中[2-3]

①線性表與內(nèi)存調(diào)度優(yōu)化

線性表中比較特殊的兩類數(shù)據(jù)結(jié)構(gòu)有棧和隊列，它們的操作具有局限性。棧是限定插入刪除操作只能在一端進(jìn)行的線性表，因此具有“先進(jìn)后出”的特點(diǎn)。隊列是限定插入在表的一端執(zhí)行，刪除在另一端，因此具有“先進(jìn)先出”的特點(diǎn)。

在傳統(tǒng)的《數(shù)據(jù)結(jié)構(gòu)》教學(xué)實(shí)踐中，通常用括號匹配檢驗、表達(dá)式求值等作為棧這部分內(nèi)容的實(shí)踐教學(xué)案例，用銀行排隊叫號、圖的廣度優(yōu)先遍歷等作為隊列這部分內(nèi)容的實(shí)踐教學(xué)案例。

由于在大數(shù)據(jù)技術(shù)中也廣泛應(yīng)用棧和隊列的結(jié)構(gòu)，可以將全新的案例引入到實(shí)踐教學(xué)中[4]。

在HBase 數(shù)據(jù)庫中，每個元素對同一份數(shù)據(jù)有多個版本，根據(jù)唯一的時間戳來區(qū)分版本，時間戳就是HBase 在寫數(shù)據(jù)時自動獲取的毫秒級系統(tǒng)時間，當(dāng)用戶查詢數(shù)據(jù)時，默認(rèn)將最新版本數(shù)據(jù)顯示給用戶，即后寫入的數(shù)據(jù)最先顯示給用戶，這就是利用棧的后進(jìn)先出的特點(diǎn)實(shí)現(xiàn)的。

在Hadoop 的MapReduce 計算框架中，Map 輸出數(shù)據(jù)經(jīng)過分區(qū)、排序、溢寫到外存文件，再作為Reduce 的輸入進(jìn)行計算。中間的排序過程是將數(shù)據(jù)讀到內(nèi)存進(jìn)行插入排序，內(nèi)存滿了就溢出了。為了防止溢出，會循環(huán)利用內(nèi)存空間，默認(rèn)可以設(shè)置80%內(nèi)存用于寫數(shù)據(jù)，當(dāng)該部分內(nèi)存空間寫滿后，自動寫到外存，其余20%空間可以繼續(xù)寫，原來80%處理完釋放后又可以利用，因此不會影響其他數(shù)據(jù)的寫入內(nèi)存過程，避免了內(nèi)存溢出。這里的循環(huán)利用內(nèi)存空間的方法，就是依據(jù)循環(huán)隊列的原理實(shí)現(xiàn)的。

②樹與決策樹

樹是用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合，主要內(nèi)容有二叉樹及遍歷算法、平衡二叉樹、哈夫曼樹等，通常用哈夫曼編碼作為樹這部分內(nèi)容的實(shí)踐教學(xué)案例。

在大數(shù)據(jù)中，樹型邏輯結(jié)構(gòu)有廣泛的應(yīng)用。例如HBase 數(shù)據(jù)庫中存放的數(shù)據(jù)，多是半結(jié)構(gòu)化或非結(jié)構(gòu)化的數(shù)據(jù)，如XML 文檔樹、HBase 數(shù)據(jù)模型等。

樹在機(jī)器學(xué)習(xí)中也有所應(yīng)用，可以作為教學(xué)案例融入《數(shù)據(jù)結(jié)構(gòu)》的課堂教學(xué)中。例如決策樹。決策樹（Decision Tree）也叫分類樹，是一種樹形結(jié)構(gòu)，樹中每個分支節(jié)點(diǎn)可以表示一個屬性，每個分支代表一種輸出，每個葉子可以代表一種類別，在已知各種情況發(fā)生概率的基礎(chǔ)上，通過構(gòu)成決策樹構(gòu)造的預(yù)測模型，可以用于評價項目風(fēng)險，判斷其可行性。

例如，表1 記錄的是近半個月天氣情況及小明外出踢足球的數(shù)據(jù)，圖1 是根據(jù)表1 數(shù)據(jù)創(chuàng)建的決策樹，有了決策樹，就可以根據(jù)未來天氣情況來預(yù)測小明是否會外出踢足球。通過這個例子，可以讓學(xué)生理解樹形結(jié)構(gòu)的應(yīng)用，了解決策樹的作用，為學(xué)生今后接觸機(jī)器學(xué)習(xí)算法做準(zhǔn)備。具體的決策樹構(gòu)造過程，即由給定數(shù)據(jù)集構(gòu)造決策樹的過程，可不做贅述。

圖1 預(yù)測小明是否外出踢足球的決策樹

數(shù)據(jù)結(jié)構(gòu)中的圖結(jié)構(gòu)是包含若干頂點(diǎn)的集合，以及表示頂點(diǎn)之間關(guān)系的邊的集合。圖的常見應(yīng)用有社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等。

在大數(shù)據(jù)分析技術(shù)中，機(jī)器學(xué)習(xí)的無監(jiān)督學(xué)習(xí)領(lǐng)域有一種基于劃分的聚類方法：K-means（k-均值）算法。該算法基于圖這類數(shù)據(jù)結(jié)構(gòu)，將海量樣本集中的每個樣本看作是圖中的一個頂點(diǎn)，K 值是要聚成的類別數(shù)量，算法首先隨機(jī)在圖中取k 個假定的中心點(diǎn)（種子點(diǎn)），然后對需要分類的其他所有點(diǎn)分別求到這k 個種子點(diǎn)的距離，距離哪個種子點(diǎn)最近就聚到那類。接下來，在每個點(diǎn)群中選取新的點(diǎn)群中心，再迭代上述過程。

將K-means 算法與圖這部分知識相鏈接，可以拓展學(xué)生的四維空間，開拓學(xué)生的大數(shù)據(jù)方面的知識視野。

④哈希表與數(shù)據(jù)分布式存儲及HBase 表設(shè)計優(yōu)化

順序查找、二分查找、哈希表是數(shù)據(jù)結(jié)構(gòu)中的三大查找方法。其中，哈希表是將關(guān)鍵碼值通過哈希函數(shù)映射到表中一個位置，從而可以直接通過關(guān)鍵碼值直接訪問數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。主要內(nèi)容有哈希函數(shù)的選取及沖突處理方法，在傳統(tǒng)實(shí)踐教學(xué)中，通常已單機(jī)小數(shù)量集為例，將哈希表的查找效率與線性表的順序存儲和鏈?zhǔn)酱鎯Φ牟檎倚首霰容^，來驗證其不僅是一種高效的存儲結(jié)構(gòu)，還是一種常見的高效的查找方法。

在大數(shù)據(jù)技術(shù)中，海量數(shù)據(jù)的存儲和處理是在分布式集群上實(shí)現(xiàn)的，如何實(shí)現(xiàn)分布式存儲和實(shí)現(xiàn)高效率的查找是一個關(guān)鍵的問題，而哈希表在這時發(fā)揮了它的優(yōu)勢。

在Hadoop 的MapReduce 計算框架中，Mapper 任務(wù)劃分?jǐn)?shù)據(jù)的過程就是Partition（分區(qū)），分區(qū)的過程就是將大量數(shù)據(jù)按照關(guān)鍵字值決定Mapper 輸出記錄被送到哪個Reducer 上處理，這一過程就是哈希分區(qū)。分區(qū)后可以實(shí)現(xiàn)并行處理數(shù)據(jù)，從而提高計算效率。

在HBase 中，表的索引是通過鍵值來實(shí)現(xiàn)的，表中數(shù)據(jù)通過RowKey（行鍵）按字典順序排序后，進(jìn)行分區(qū)，分布式存儲到多個region（分區(qū)）。如果數(shù)據(jù)聚集存儲到部分region，而其余region 空閑，這將導(dǎo)致在分布式系統(tǒng)中不能并發(fā)工作，也會降低查詢效率。為了使負(fù)載均衡，在設(shè)計RowKey 時，可以遵循散列原則，將RowKey 的最高位作為散列字段，由程序循環(huán)生成，這樣可以實(shí)現(xiàn)將數(shù)據(jù)均衡分布在每個Region，實(shí)現(xiàn)負(fù)載均衡，提高查詢效率。

通過引入上述案例，可以讓學(xué)生理解哈希表不僅可以實(shí)現(xiàn)單機(jī)小數(shù)據(jù)集的高效存儲和查詢，在數(shù)據(jù)的分布式存儲中也有著非常廣泛的實(shí)際應(yīng)用。

⑤排序算法在大數(shù)據(jù)技術(shù)中的應(yīng)用

數(shù)據(jù)結(jié)構(gòu)中的排序算法有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。在教學(xué)過程中，重點(diǎn)內(nèi)容是內(nèi)部排序中的選擇排序、插入排序、交換排序。

在海量數(shù)據(jù)的分布式存儲中，排序是極為關(guān)鍵和重要的一項工作。例如，與傳統(tǒng)數(shù)據(jù)庫不同，在HBase中，表是三維的，由行鍵、列鍵（列族：列名）、時間戳組成。為了便于對數(shù)據(jù)的訪問，表中每行按行鍵的字典順序升序排序，行鍵相同的按列鍵升序排序，如果行鍵和列鍵都相同，則按時間戳降序排序。排序后，按行鍵檢索時，即可快速定位分區(qū)，查找到指定行并返回最新版本數(shù)據(jù)。

通過這個案例可以加深學(xué)生對排序應(yīng)用的理解，并對排序在大數(shù)據(jù)技術(shù)中的重要性有一個初步的了解。

（3）創(chuàng)新教學(xué)模式，培養(yǎng)學(xué)生的大數(shù)據(jù)思維和創(chuàng)新能力

①創(chuàng)新改進(jìn)教學(xué)方法[5]，激發(fā)學(xué)生學(xué)習(xí)興趣

大數(shù)據(jù)時代背景下，教師在充分了解學(xué)生的學(xué)習(xí)狀態(tài)、知識水平、能力特長的同時，要積極改進(jìn)教學(xué)方法，合理規(guī)劃課堂教學(xué)過程，充分調(diào)動學(xué)生學(xué)習(xí)的積極性和主動性，提高教學(xué)效果。

②合理應(yīng)用網(wǎng)絡(luò)資源，引導(dǎo)學(xué)生自主學(xué)習(xí)

授人以魚不如授人以漁，教會學(xué)生知識不如教會學(xué)生學(xué)習(xí)的方法。大數(shù)據(jù)時代，網(wǎng)絡(luò)學(xué)習(xí)資源豐富，教師可以通過藍(lán)墨云班課等教學(xué)平臺分享與課程內(nèi)容相關(guān)的網(wǎng)絡(luò)資源，為學(xué)生提供學(xué)習(xí)的第二課堂，引導(dǎo)學(xué)生自主學(xué)習(xí)。

③構(gòu)建數(shù)據(jù)結(jié)構(gòu)的大數(shù)據(jù)實(shí)驗平臺，為實(shí)踐教學(xué)提供豐富的案例和實(shí)驗。

為了將數(shù)據(jù)結(jié)構(gòu)相關(guān)的大數(shù)據(jù)技術(shù)引入課堂教學(xué)內(nèi)容，可以在實(shí)訓(xùn)室搭建大數(shù)據(jù)實(shí)驗平臺，例如Hadoop、HBase 等，教師可以通過大數(shù)據(jù)實(shí)驗平臺演示教學(xué)案例，也可以讓學(xué)生在平臺環(huán)境下進(jìn)行實(shí)踐練習(xí)，在實(shí)踐中理解數(shù)據(jù)結(jié)構(gòu)中的知識在大數(shù)據(jù)中的實(shí)際應(yīng)用，培養(yǎng)學(xué)生的大數(shù)據(jù)思維和創(chuàng)新能力。

3 結(jié)語

大數(shù)據(jù)技術(shù)發(fā)展如火如荼，其技術(shù)理論與傳統(tǒng)專業(yè)基礎(chǔ)課程密切相關(guān)，數(shù)據(jù)結(jié)構(gòu)作為計中的線性表、隊列、樹、圖、排序等內(nèi)容在大數(shù)據(jù)相關(guān)技術(shù)理論中均有廣泛實(shí)踐應(yīng)用，將數(shù)據(jù)結(jié)構(gòu)內(nèi)容與大數(shù)據(jù)前沿技術(shù)相結(jié)合，探索《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)改革，可以在《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)過程中有的放矢，激發(fā)學(xué)生學(xué)習(xí)興趣，培養(yǎng)學(xué)生大數(shù)據(jù)思維。今后，隨著對大數(shù)據(jù)技術(shù)的進(jìn)一步深入了解，可以開發(fā)數(shù)據(jù)結(jié)構(gòu)與大數(shù)據(jù)相關(guān)的綜合實(shí)踐教學(xué)內(nèi)容。