鄂爾多斯市人力資源和社會(huì)保障局綜合保障中心 達(dá)斯孟

當(dāng)前大數(shù)據(jù)應(yīng)用在政務(wù)服務(wù)各個(gè)領(lǐng)域正在如火如荼的進(jìn)行，Python語言作為一種高效的編程語言正在成為軟件開發(fā)的趨勢(shì)，本文從Python語言不同數(shù)據(jù)結(jié)構(gòu)在社保大數(shù)據(jù)應(yīng)用方面進(jìn)行了構(gòu)造方法的介紹、性能的比較和造成性能差異的分析。

社保領(lǐng)域作為我國(guó)重要的民生工程，一直備受關(guān)注。社保大數(shù)據(jù)在推動(dòng)社會(huì)保險(xiǎn)管理服務(wù)模式創(chuàng)新，改進(jìn)公共服務(wù)水平，減少重復(fù)參保，查處重復(fù)領(lǐng)取待遇方面有著非常重要和廣泛的應(yīng)用。Python語言可以被應(yīng)用于系統(tǒng)編程、GUI編程、互聯(lián)網(wǎng)腳本、數(shù)據(jù)編程等多個(gè)領(lǐng)域。根據(jù)2018年5月KDnuggets對(duì)“最受歡迎的分析、數(shù)據(jù)科學(xué)、機(jī)器學(xué)習(xí)工具”的調(diào)查，Python以65.2%的比例奪冠。本文以A市社保大數(shù)據(jù)比對(duì)工作中應(yīng)用Python語言編寫相關(guān)應(yīng)用程序時(shí)所應(yīng)用的集合SET、列表LIST等兩個(gè)高頻數(shù)據(jù)結(jié)構(gòu)進(jìn)行性能和特點(diǎn)分析，以便為更多政務(wù)服務(wù)領(lǐng)域提供可供遵循的指導(dǎo)。

1 Python數(shù)據(jù)結(jié)構(gòu)中的集合SET，列表LIST介紹

要用好Python語言并發(fā)揮其作用，必須理解數(shù)據(jù)結(jié)構(gòu)的一般性知識(shí)和Python的特殊情況[1]，筆者在社保大數(shù)據(jù)應(yīng)用領(lǐng)域使用的是Python數(shù)據(jù)結(jié)構(gòu)中的集合SET，列表LIST。要弄清楚上述兩個(gè)數(shù)據(jù)結(jié)構(gòu)首先要從上述數(shù)據(jù)結(jié)構(gòu)的構(gòu)造原理進(jìn)行探究。首先我們要明確任何數(shù)據(jù)結(jié)構(gòu)其實(shí)都是一種從內(nèi)存獲取數(shù)據(jù)地址從而讀取或者操作數(shù)據(jù)的一種方式。就像生活中我們想要出售一處房產(chǎn)，但是你不可能像推銷其他產(chǎn)品一樣將房產(chǎn)攜帶在身上四處給人看，最好的做法就是你告訴潛在客戶一個(gè)地址讓客戶根據(jù)你給的地址自己過來訪問。這個(gè)過程其實(shí)就是我們計(jì)算機(jī)用來讀取內(nèi)存中數(shù)據(jù)的一種形象的方式。在Python中我們建立一個(gè)列表MYLIST=LIST[1，2，3，4]的列表，其中的MYLIST本質(zhì)上就是指針，指向LIST[1，2，3，4]占據(jù)的內(nèi)存地址塊。不同的數(shù)據(jù)結(jié)構(gòu)其本質(zhì)的區(qū)別就在于如何讓指針更快，更準(zhǔn)確的指向需要訪問的地址。

1.1 LIST數(shù)據(jù)結(jié)構(gòu)

Python中的LIST是處理一組有序元素得數(shù)據(jù)結(jié)構(gòu)[2]。本質(zhì)上是一個(gè)over-allocate的數(shù)組實(shí)現(xiàn)的。LIST可能是計(jì)算機(jī)科學(xué)中使用最為頻繁的數(shù)據(jù)結(jié)構(gòu)。Python中的LIST共有三類，分別為單鏈序列Singly Linked LIST，雙鏈序列Doubly Linked LIST，環(huán)形序列Circular Linked LIST。下面對(duì)三類序列進(jìn)行分析：

如圖1所示為單鏈序列Singly Linked LIST：除了末尾節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)都包含一個(gè)數(shù)據(jù)值部分和指向下一節(jié)點(diǎn)的地址部分。單鏈序列只能進(jìn)行單向的索引，因?yàn)槊總€(gè)節(jié)點(diǎn)只包含下一節(jié)點(diǎn)的位置。

圖1 單鏈序列Fig.1 Singly Linked LIST

如圖2所示為雙鏈序列Doubly Linked LIST：除了末尾節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)都包含一個(gè)數(shù)據(jù)值部分和指向下一節(jié)點(diǎn)的地址部分和指向上一節(jié)點(diǎn)的地址部分。雙鏈序列可以進(jìn)行向前和向后的雙向查找，因?yàn)槊總€(gè)節(jié)點(diǎn)即包含了前一節(jié)點(diǎn)的地址又包含了后一節(jié)點(diǎn)的地址。

圖2 雙鏈序列Fig.2 Doubly Linked LIST

如圖3所示為環(huán)形序列Circular Linked LIST：環(huán)形序列的末尾節(jié)點(diǎn)的下一節(jié)點(diǎn)指向的是序列的第一個(gè)節(jié)點(diǎn)，其他都和單項(xiàng)序列是一樣的。

圖3 環(huán)形序列Fig.3 Circular Linked LIST

三種序列對(duì)存放于其中的數(shù)據(jù)都進(jìn)行了精確的索引，數(shù)據(jù)值可以重復(fù)。其特點(diǎn)為高擴(kuò)展，可任意大小位置切片，任意位置刪除或插入。

1.2 SET數(shù)據(jù)結(jié)構(gòu)

Python中的SET數(shù)據(jù)結(jié)構(gòu)是由具有唯一性的hashable對(duì)象所組成的無序集合。由于SET數(shù)據(jù)結(jié)構(gòu)索引數(shù)據(jù)的方式為hash算法，因此相同值的數(shù)據(jù)經(jīng)過hash算法后其哈希值也是相等的，所以SET中不會(huì)有重復(fù)的數(shù)據(jù)。常見的用途包括成員檢測(cè)、從序列中去除重復(fù)項(xiàng)以及數(shù)學(xué)中的集合類計(jì)算，例如交集、并集、差集與對(duì)稱差集等[3]。

2 集合SET，列表LIST性能比對(duì)

在A市社保大數(shù)據(jù)應(yīng)用領(lǐng)域，目前需求最密集的數(shù)據(jù)應(yīng)用方式為跨統(tǒng)籌區(qū)或跨險(xiǎn)種（企業(yè)養(yǎng)老保險(xiǎn)、機(jī)關(guān)養(yǎng)老保險(xiǎn)、城鄉(xiāng)居民養(yǎng)老保險(xiǎn)）比對(duì)重復(fù)參保與重復(fù)待遇領(lǐng)取人員。由于政務(wù)服務(wù)特點(diǎn)，上述數(shù)據(jù)大多以Excel格式存放于社保部門不同科室且每個(gè)表格的數(shù)據(jù)較多（通常為幾十萬條）。因此如何高效、精準(zhǔn)、快速進(jìn)行數(shù)據(jù)比對(duì)就顯得尤為重要。

下面筆者以10000機(jī)關(guān)養(yǎng)老待遇領(lǐng)取人員和10000城鄉(xiāng)居民待遇領(lǐng)取人員比對(duì)為例展示Python中不同數(shù)據(jù)結(jié)構(gòu)在上述需求中的性能差異（如表1所示）。LIST數(shù)據(jù)結(jié)構(gòu)主要的算法為將兩個(gè)數(shù)據(jù)源的10000人的數(shù)據(jù)分別裝入兩個(gè)LIST中。之后經(jīng)過FOR循環(huán)進(jìn)行遍歷比對(duì)。

表1 為數(shù)據(jù)比對(duì)結(jié)果Tab.1 Shows the results of data comparison

SET數(shù)據(jù)結(jié)構(gòu)主要的算法為將兩個(gè)數(shù)據(jù)源的10000人的數(shù)據(jù)分別裝入兩個(gè)SET中，通過intersection函數(shù)求解交集。

3 集合SET，列表LIST性能差異分析

經(jīng)過上述實(shí)驗(yàn)結(jié)果可以看出SET數(shù)據(jù)結(jié)構(gòu)在社保大數(shù)據(jù)比對(duì)中效率明顯更優(yōu)。其原因主要在于SET數(shù)據(jù)結(jié)構(gòu)和LIST數(shù)據(jù)結(jié)構(gòu)的構(gòu)造方法的不同。眾所周知，最快速的訪問數(shù)據(jù)集合中數(shù)據(jù)的方式是隨機(jī)訪問，而不是順序訪問。下面我們就對(duì)兩種數(shù)據(jù)結(jié)構(gòu)分別進(jìn)行分析。從上述實(shí)驗(yàn)結(jié)果得知LIST的查找效率較低，下面我們首先查看LIST的查找算法的抽象源碼和原理圖（如圖4所示）。

圖4 LIST數(shù)據(jù)存儲(chǔ)方式Fig.4 LIST data storage method

從圖四中可以看出我們現(xiàn)在有一個(gè)test=LIST[10，11，12，8，9，13，14]的未排序序列，序列中共有7個(gè)整數(shù)值。根據(jù)源代碼如果我們要查找13這個(gè)Key值，則需要從這個(gè)序列的head位置起循環(huán)比對(duì)（源碼中的WHILE循環(huán)）如果比對(duì)不成功則進(jìn)行temp=temp.next操作進(jìn)入下一節(jié)點(diǎn)進(jìn)行比對(duì)直到比對(duì)成功為止則返回True跳出循環(huán)。因此得出LIST（以雙向鏈表為例）查找數(shù)據(jù)時(shí)需要按照索引順序?qū)φ麄€(gè)序列進(jìn)行遍歷直至匹配到Key值。它適用于對(duì)順序敏感的數(shù)據(jù)。平均查找復(fù)雜度是O(n)（如果是以排序的序列則平均查找復(fù)雜度是O(log n)）。

從上述分析得知要從一個(gè)LIST中查找某一Key值必須要對(duì)整個(gè)LIST進(jìn)行遍歷，如果想要查找的Key值在序列的前端則還比較省時(shí)間，如果所要查找的Key值在序列的末尾則需要遍歷完整個(gè)序列才可以匹配到Key值。這樣無疑是非常耗費(fèi)系統(tǒng)資源和時(shí)間的。因此我們不禁要問，為什么不能有一種數(shù)據(jù)結(jié)構(gòu)可以直接告訴我所要查找的Key值的位置，從而讓我可以直接去訪問呢，就像我們之前提到的例子所說的那樣，直接告客戶一個(gè)詳細(xì)的地址，而不是像LIST一樣只告訴客戶需要出售的房產(chǎn)在某一個(gè)小區(qū)（內(nèi)存塊），讓客戶逐戶去查找是否為要出售的房屋。而SET數(shù)據(jù)結(jié)構(gòu)恰好就是利用哈希算法實(shí)現(xiàn)了一次尋址即得到結(jié)果的結(jié)構(gòu)。下面我們首先查看set的查找算法的抽象源碼和原理圖（如圖5所示）。

從圖5中可以看出我們現(xiàn)在有一個(gè)test=set（對(duì)象1，對(duì)象2，對(duì)象3，對(duì)象4，對(duì)象5，對(duì)象6，對(duì)象7）的集合，其中共有7個(gè)對(duì)象值。根據(jù)源代碼如果我們要查找對(duì)象6這個(gè)Key值，首先我們需要通過ComputeHash(Key)函數(shù)計(jì)算對(duì)象6的哈希值(13)，之后通過哈希算法對(duì)13這個(gè)哈希值進(jìn)行除7取余的哈希計(jì)算得到哈希表中的索引位置(6)，之后判斷索引位置的值是否與要查找的KEY值相等，如果相等則返回成功（在哈希算法出現(xiàn)沖突的情況下有可能出現(xiàn)索引值相同但是數(shù)據(jù)不相同的情況）。最終得到需要查找的值。因此SET數(shù)據(jù)結(jié)構(gòu)的查找復(fù)雜度是O(1)(理想無沖突狀態(tài)下)，且和SET規(guī)模大小無關(guān)。在SET中查找任何值在理想情況下只需要查找一次，只需要將需要查找的值進(jìn)行哈希算法，將其哈希值與SET中相應(yīng)位置進(jìn)行比對(duì)，如果比對(duì)成功，則找到，如果比對(duì)失敗，則不存在。

圖5 SET哈希算法實(shí)現(xiàn)方式Fig.5 Implementation of SET hash algorithm

4 結(jié)語

根據(jù)上述實(shí)驗(yàn)數(shù)據(jù)和結(jié)構(gòu)原理，我們可以得出Python在社保大數(shù)據(jù)應(yīng)用領(lǐng)域中SET具有查找比對(duì)速度的絕對(duì)優(yōu)勢(shì)，其優(yōu)勢(shì)來源于其數(shù)據(jù)結(jié)構(gòu)的構(gòu)成方法，而LIST則在數(shù)據(jù)比對(duì)查找方面不具有速度優(yōu)勢(shì)，但是在需要按照某種規(guī)則進(jìn)行排序使用數(shù)據(jù)時(shí)具有優(yōu)勢(shì)。