典型數(shù)據(jù)結(jié)構(gòu)的性能分析

按照分類標準的不同，數(shù)據(jù)結(jié)構(gòu)可以分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)對象中的數(shù)據(jù)元素之間的相互關(guān)系，與數(shù)據(jù)的存儲尚未關(guān)聯(lián)，是從具體問題抽象出來的數(shù)學模型，主要分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)等。

常用的數(shù)據(jù)存儲結(jié)構(gòu)有數(shù)組、棧、隊列、鏈表、樹、哈希表、堆、圖等，這些數(shù)據(jù)結(jié)構(gòu)有各自的優(yōu)缺點，適用的場景也各不相同，這些數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點如下表：

執(zhí)行效率較快的數(shù)據(jù)結(jié)構(gòu)復(fù)雜程度一般較高，但并不是使用最快的結(jié)構(gòu)就是最好的方案，仍需要根據(jù)實際情況進行考慮。

為進一步說明選擇不同數(shù)據(jù)結(jié)構(gòu)對于完成相同的操作會導(dǎo)致程序性能的差異，選用數(shù)組、鏈表結(jié)構(gòu)以查找數(shù)據(jù)為例進行測試。

使用有序數(shù)組數(shù)據(jù)結(jié)構(gòu)編寫查找程序，程序編寫完成后，利用gettimeofday這個計時函數(shù)對有序數(shù)組查找耗時進行測試，數(shù)組個數(shù)為10^7，結(jié)果顯示其查找完成花費了0.048ms的時間。

選取有序鏈表作為數(shù)據(jù)存儲結(jié)構(gòu)編寫程序進行目標數(shù)據(jù)的查找。程序運行后利用計時函數(shù)測試耗時情況如下，完成查找10^7個數(shù)據(jù)所花費時間為19ms，程序性能不如使用有序數(shù)數(shù)組數(shù)據(jù)結(jié)構(gòu)。

在滿足精度要求的情況下，不同的數(shù)據(jù)類型也會對程序的性能有影響，具體包括兩個方面，一是選擇存儲空間更小的數(shù)據(jù)類型，二是選擇更適合硬件結(jié)構(gòu)的數(shù)據(jù)類型。

通常小尺寸類型數(shù)據(jù)的訪問速度比大尺寸類型數(shù)據(jù)快，且小尺寸的數(shù)據(jù)可以在緩存中放更多的數(shù)據(jù)。為驗證上述結(jié)論，使用SSE指令對兩種數(shù)據(jù)類型進行加法運算，并測試運行時間進行對比。程序測試結(jié)果顯示在處理單個數(shù)據(jù)時，SSE指令處理短整型數(shù)據(jù)的速度比處理整型數(shù)據(jù)快2倍左右。

不同的數(shù)據(jù)類型的程序在相同架構(gòu)上的性能也有所不同。此時在滿足正確性以及計算精度的要求下，可以對數(shù)據(jù)類型進行轉(zhuǎn)換，幫助發(fā)揮硬件平臺特性，提升程序的運算性能。

當使用256*256大小的矩陣規(guī)模進行測試時，單精度矩陣乘測試結(jié)果為0.036s，雙精度為0.068s，加速比為1.88倍。

選擇適合的數(shù)據(jù)結(jié)構(gòu)

在解決具體問題時選擇合適的數(shù)據(jù)結(jié)構(gòu)是非常重要的，以稀疏矩陣向量乘法為例進一步說明數(shù)據(jù)結(jié)構(gòu)選擇的重要性。稀疏矩陣向量乘是科學工程計算的核心算法，為了提升稀疏矩陣向量乘法的性能，將采用坐標存儲、行壓縮、對角存儲以及埃爾帕克存儲四種稀疏矩陣存儲格式實現(xiàn)稀疏矩陣向量乘法并進行測試對比。

坐標存儲。坐標存儲格式也稱為三元組存儲格式，其分別存儲每個非零元素的行索引row、列索引col以及數(shù)值data。這種存儲方式的主要優(yōu)點是靈活、簡單、易于按行和按列訪問稀疏矩陣。

當稀疏矩陣存儲格式為坐標存儲格式時，向量乘法部分代碼實現(xiàn)如下。

行壓縮存儲。主要思想是逐行對稀疏矩陣進行壓縮，并且記錄每行首個非零元素的位置信息。行壓縮存儲格式由三個數(shù)組構(gòu)成，數(shù)值data按行存放非零元素，列號col記錄對應(yīng)于data中每個非零元素位于的列數(shù)，指針ptr記錄每行第一個非零元素在data中的存儲位置。

當稀疏矩陣存儲格式為行壓縮存儲時，向量乘法實現(xiàn)部分代碼如下。

對角存儲。對角存儲格式專為由多條非零對角線組成的稀疏矩陣設(shè)計，對角存儲格式采用一個二維矩陣和一個向量來存儲原矩陣，其中二維矩陣中的每一列用來存儲原矩陣中的一條對角線，而向量則用來存儲各列對應(yīng)原矩陣中主對角線的偏移量。

當稀疏矩陣存儲格式為對角存儲時，向量乘法實現(xiàn)部分代碼如下。

ELLPACK存儲。對于一個m*n的矩陣，每行最多有k個非零值元素，ELLPACK格式將非零值存儲于一個m*k的稠密矩陣Data中。相應(yīng)的列指針被存儲在指數(shù)矩陣 Indices中，然后用0或者其它的哨兵值來填補空缺。與對角存儲格式一樣，indices和data矩陣都是按列順序來存儲的，當稀疏矩陣存儲格式為ELLPACK時，向量乘法實現(xiàn)如下。

當稀疏矩陣存儲格式為ELLPACK時，向量乘法實現(xiàn)如下。

1. 當采用對角存儲格式時，其性能往往好于其它格式。缺點是采用對角格式，非零元素的坐標需要通過計算才能得到，因此通常在稀疏矩陣向量乘法計算中不會采用對角格式。

2. 只有非零元所占比例大于某一閾值時，使用ELLPACK存儲格式會取得更好的性能。

3. 對角存儲和ELLPACK這兩種格式都需要對矩陣進行補零操作，對稀疏矩陣向量乘程序性能有一定影響，而坐標存儲和行壓縮存儲格式則不存在這個問題，它們只存儲矩陣中的非零元素，不會引入不必要的開銷。

4. 每種稀疏矩陣存儲結(jié)構(gòu)的不同將導(dǎo)致在進行優(yōu)化時必須選擇不同的方法，因此需針對每一種方法選擇不同的優(yōu)化策略，以獲得最優(yōu)的性能。