資源簡介

教學設計
課程基本信息
課題 6.1實時查詢系統(tǒng)中數(shù)據(jù)的組織
教學目標
1.了解大數(shù)據(jù)處理過程中常見的數(shù)據(jù)組織與處理方式 2. 能結合已知的數(shù)據(jù)結構知識，選用合理的數(shù)據(jù)結構去解決問題 3. 能用迭代的思想去看待數(shù)據(jù)結構的設計、數(shù)據(jù)的組織與存儲 4. 能激發(fā)進一步學習數(shù)據(jù)的組織與存儲、數(shù)據(jù)結構與算法設計的興趣
教學內(nèi)容
教學重點： 能用迭代的思想去看待數(shù)據(jù)結構的設計、數(shù)據(jù)的組織與存儲
教學難點： 能用迭代的思想去看待數(shù)據(jù)結構的設計、數(shù)據(jù)的組織與存儲
教學過程
一、情境導入 1、師：生活中人們?yōu)榱朔奖悖芏鄷r候會選擇在網(wǎng)絡平臺進行購物，新學期要開始了，小陳同學想在網(wǎng)購平臺購買一只書包，我們一起來看看他是如何選擇心儀的書包的？ ▲在觀看過程中，請同學們思考：小陳同學在該平臺查詢信息的方式和特點？ （播放視頻） 2、請幾位同學來說一說在視頻中看到的信息查詢的方式和特點。 二、實時查詢系統(tǒng)中的數(shù)據(jù)業(yè)務特點 師生共同小結： 像這樣實現(xiàn)實時查詢的系統(tǒng)中，我們可以發(fā)現(xiàn)其數(shù)據(jù)業(yè)務呈現(xiàn)以下特殊性： （1）能實現(xiàn)上千個請求的實時響應 （2）支持后續(xù)商品信息的更改
三、實時查詢系統(tǒng)中的數(shù)據(jù)結構和算法設計 1、數(shù)組 可以比較直接的表示商品之間按照某種屬性呈現(xiàn)的有序線性關系。當數(shù)據(jù)從數(shù)據(jù)庫讀取到數(shù)組后，我們可以按照各個屬性進行排序后，把他們分類存儲。 ▲請同學們小組討論并完成學生任務單中的“學習任務一”(1)(2)(3)。 （1）有數(shù)組如下，若要插入數(shù)字7，使數(shù)組仍然有序，該如何操作？ 索引0123456789元素13456891215
（2）程序實現(xiàn)：完成以下代碼填空 a=[1,3,4,5,6,8,9,12,15,0] #0表示該位置未存儲元素 num=int(input("輸入需要插入的數(shù)據(jù)：")) for i in range(len(a)): if a[i]>num: for j in range(len(a)-1,i-1,-1): _____①_______ ____②_______ break else: a[-1]=num print(a) （3）思考：如果數(shù)據(jù)量較多時，我們可以采用什么方法來查找位置？ ____________________________ 師生共同分析回顧在數(shù)組中查找與插入的操作，引出為提高查找效率，可使用二分查找，簡單回顧二分查找的過程，比較順序查找與二分查找的效率。 2、鏈表 ▲請同學們小組討論并完成學生任務單中的“學習任務二”(1)(2)(3)。 （1）有鏈表如下，若要插入數(shù)字26，使鏈表仍然有序，該如何操作？ （2）程序實現(xiàn)： a=[[12,1],[15,2],[22,3],[29,4],[35,5],[46,-1]] num=int(input("輸入需要插入的數(shù)據(jù)：")) head=0 p=head if numa[p][0]and p!=-1: q=p p=a[p][1] a.append([num,p]) ______②______ p=head while a[p][1]!=-1: print(a[p][0],end='->') _____③_______ print(a[p][0]) （3）思考：請同學們討論交流，分析數(shù)組與鏈表各自的優(yōu)勢和劣勢。 優(yōu)勢劣勢數(shù)組鏈表
師生共同分析回顧在鏈表中查找與插入的操作，結合程序代碼直觀的感知具體的算法實現(xiàn)。師生共同分析數(shù)組與鏈表各自的優(yōu)勢與劣勢。 優(yōu)勢劣勢數(shù)組利用二分查找 時間復雜度：O(log2n) 查找速度比較快插入位置之后的所有元素都必須往后移位，時間復雜度較大：O(n)鏈表插入新元素效率高，時間復雜度僅為O(1)查找時必須從頭節(jié)點開始依次遍歷，時間復雜度為O(n)
四、基于鏈表的數(shù)據(jù)結構和算法優(yōu)化 1、由于鏈表的處理，只是在查找時效率較低，而插入操作卻完全能滿足要求，所以可以在鏈表的基礎上繼續(xù)加以改進，以解決順序查找導致的低效問題。我們可以按以下思路來考慮： （1）減少查找插入位置過程中的比較次數(shù) （2）借鑒二分查找算法的思想 2、這里我們引入一個新的數(shù)據(jù)結構------跳躍表。 原鏈表如下，若要在原鏈表中查找18，我們需要比較6次，現(xiàn)在，我們通過拋硬幣的方式來提取一組關鍵節(jié)點放到上層作為一級索引，此時，我們只需要比較5次就可以找到18。如果用同樣的方法，為一級索引建立二級索引，我們只需要比較4次就可以找到18。 由此可見，關鍵節(jié)點起到一個索引表的作用，能快速定位到一個較小的查找區(qū)間，然后只需將索引位置對應到原鏈表，就可以找到了。如果數(shù)據(jù)比較多時，還可以繼續(xù)增設三、四級索引，進一步提升查找的速度。 跳躍表的時間復雜度：O(log2n) （1）跳躍表------增設關鍵節(jié)點 例如，原鏈表增加了新節(jié)點24，我們?nèi)匀徊捎脪佊矌诺姆绞絹頉Q定是否把24提升為上一層的關鍵節(jié)點，如果拋硬幣結果為不提升，那么24只出現(xiàn)在原鏈表中，如果拋硬幣結果為提升，那么把24提升到上一層索引，用同樣的方法來確定24要不要繼續(xù)往上提升。 （2）跳躍表------刪除關鍵節(jié)點 例如要刪除13，從二級索引開始，依次往下刪除各層的13。由于二級索引在刪除13以后只剩下一個關鍵節(jié)點，對于區(qū)間劃分和提高查找效率沒有任何意義，所以將剩下的節(jié)點1也刪除。 3、師生共同小結： 從數(shù)組到鏈表，再到跳躍表，我們可以發(fā)現(xiàn)，一個切合實際的數(shù)據(jù)結構和算法不是一蹴而就的，而是根據(jù)問題中的數(shù)據(jù)及其關系的特點，通過迭代逐步優(yōu)化得到的。 五、其他數(shù)據(jù)組織與處理方式 單純的采用傳統(tǒng)的磁盤數(shù)據(jù)庫來組織、處理海量的數(shù)據(jù)，其固有的數(shù)據(jù)組織、存取、處理等模式已經(jīng)無法適應當今很多數(shù)據(jù)業(yè)務對實時數(shù)據(jù)管理和查詢的需求，為了提升數(shù)據(jù)的處理性能，人們發(fā)明了內(nèi)存數(shù)據(jù)庫。 大部分的內(nèi)存數(shù)據(jù)庫主要從以下幾個方面來提升數(shù)據(jù)的處理性能： （1）減少對磁盤的訪問 （2）對數(shù)據(jù)進行分級存儲 （3）采用改進后的數(shù)據(jù)結構來組織、存儲數(shù)據(jù) 六、小結與拓展 師生共同小結： 本節(jié)課，我們了解了大數(shù)據(jù)處理過程中常見的數(shù)據(jù)組織與處理方式，以及在數(shù)據(jù)業(yè)務中，數(shù)據(jù)進行分類、整理等組織工作的必要性，還一起感受了數(shù)據(jù)結構設計過程中的迭代思想。 ▲課外拓展： 除了本節(jié)課提到的幾種數(shù)據(jù)結構，是否還有其他的數(shù)據(jù)結構來解決數(shù)據(jù)的組織與存儲問題呢？請同學們課后討論交流。如果有，請簡要描述該數(shù)據(jù)結構組織數(shù)據(jù)并處理的算法，并嘗試分析用該數(shù)據(jù)結構解決問題的時間復雜度。

展開更多......

收起↑