一種極值查找算法在區(qū)域自動(dòng)站資料質(zhì)量控制中的應(yīng)用

楊遠(yuǎn)恒，田 蘭，卜英竹，鄒 蓓

(貴州省氣象信息中心，貴州 貴陽(yáng) 550002)

一種極值查找算法在區(qū)域自動(dòng)站資料質(zhì)量控制中的應(yīng)用

楊遠(yuǎn)恒，田 蘭，卜英竹，鄒 蓓

(貴州省氣象信息中心，貴州 貴陽(yáng) 550002)

在區(qū)域自動(dòng)氣象站兩要素資料的質(zhì)量控制研究中，根據(jù)兩要素資料的特點(diǎn)，實(shí)現(xiàn)一種極值查找算法，快速的定位極值數(shù)據(jù)，提高查找的效率。該文著重分析該查找算法的實(shí)現(xiàn)，以供探討。

區(qū)域自動(dòng)站質(zhì)量控制;極值查找;算法

1 引言

在區(qū)域自動(dòng)氣象站兩要素資料的質(zhì)量控制研究中，利用歷史極值檢查方法進(jìn)行實(shí)時(shí)資料質(zhì)量控制時(shí)，需要將實(shí)時(shí)觀測(cè)值與歷史極端值進(jìn)行比較，以便過濾出可疑值。因此，在進(jìn)行實(shí)時(shí)質(zhì)量控制時(shí)，需要在極端歷史資料文件中查找到極端歷史值。一般方法是將每一個(gè)臺(tái)站的實(shí)時(shí)觀測(cè)值和所有臺(tái)站的歷史極值進(jìn)行逐一的比較，以便查找到臺(tái)站的歷史極值。這種方法處理效率較低，不能滿足質(zhì)量控制實(shí)時(shí)業(yè)務(wù)需求。為保證兩要素資料質(zhì)量控制的實(shí)時(shí)處理，避免因查找極端歷史值耗時(shí)，本文根據(jù)兩要素資料的特點(diǎn)，實(shí)現(xiàn)一種數(shù)據(jù)查找算法，以提高歷史極值檢查的效率。

2 算法設(shè)想

由于區(qū)域兩要素站是近年來才新建的臺(tái)站，其歷史極端要素值是根據(jù)常規(guī)地面觀測(cè)站的歷史極端要素值，通過兩要素臺(tái)站與地面觀測(cè)站之間區(qū)域的對(duì)應(yīng)關(guān)系，實(shí)現(xiàn)兩要素臺(tái)站極值的初始化。在新生成的每個(gè)兩要素極值文件中，每個(gè)臺(tái)站對(duì)應(yīng)一條歷史極值記錄，例如，月極端最低溫度記錄如下：

R1101-78-66-35 1 76 104 121 142 81 34-24-66

其中，每條極值記錄包含了臺(tái)站編號(hào)(如R1101)以及1—12月的極端值。

兩要素臺(tái)站編號(hào)是5位數(shù)編碼，其中，“R”是固定標(biāo)識(shí)，R后第1位數(shù)字代表地區(qū)、第2位數(shù)字代表縣、第3、4位數(shù)字代表該縣的第幾個(gè)兩要素站。

按照臺(tái)站編碼的規(guī)則，可以將臺(tái)站編號(hào)(staID)分別按照“地區(qū)級(jí)編碼”和“縣級(jí)編碼”分成不同的臺(tái)站類別(stasort)。若按照“地區(qū)級(jí)編碼”，貴陽(yáng)地區(qū)臺(tái)站類別為“R1＊＊＊”，遵義地區(qū)的臺(tái)站類別為“R2＊＊＊”，等等。同理，若按照“縣級(jí)編碼”，如貴陽(yáng)地區(qū)又可以劃分為8種臺(tái)站類別：“R11＊＊、R12＊＊、R13＊＊、R14＊＊、R15＊＊、R16＊＊、R17＊＊、R18＊＊”，其他地區(qū)依次類推。因此，當(dāng)初始化兩要素極值文件時(shí)，首先，每條極值記錄以臺(tái)站編號(hào)為索引，然后根據(jù)“縣級(jí)編碼”進(jìn)行臺(tái)站類別歸類，每個(gè)臺(tái)站類別的臺(tái)站編號(hào)再按照第3、4位數(shù)字進(jìn)行排序，同時(shí)存儲(chǔ)到文件中，為實(shí)現(xiàn)歷史極值檢查算法做前期準(zhǔn)備。

通常，在資料的處理過程中，根據(jù)記錄的臺(tái)站編號(hào)，采取遍歷極值記錄的方式就可以查找到極值記錄，這種查找方式使得每一條實(shí)時(shí)記錄都需要循環(huán)遍歷極值數(shù)組。隨著兩要素臺(tái)站的不斷新建，處理兩要素資料的數(shù)據(jù)量不斷加大，為了提供更快更好的氣象服務(wù)，兩要素資料的質(zhì)量控制處理需要具備較高的實(shí)時(shí)性，采取常規(guī)的查找方式，增加了算法的時(shí)間復(fù)雜度，在一定程度上降低了資料質(zhì)量控制處理的實(shí)時(shí)性。

為了能夠減少頻繁循環(huán)遍歷極值記錄，比較快的查找到極值，考慮對(duì)極值記錄進(jìn)行預(yù)處理，通過預(yù)處理的輔助幫助來實(shí)現(xiàn)快速定位極值的目的。也就是說，從極值文件中讀取記錄初始化極值數(shù)組時(shí)，預(yù)先對(duì)極值記錄按臺(tái)站類別進(jìn)行統(tǒng)計(jì)，結(jié)果存放在輔助數(shù)組中，當(dāng)查找極值時(shí)，由實(shí)時(shí)資料記錄的臺(tái)站編號(hào)，通過輔助數(shù)組計(jì)算，就可以縮小在極值數(shù)組中查找的范圍，提高了查找效率。并且存在一種特殊情況，如果臺(tái)站編號(hào)的第3、4位數(shù)字編碼是順序遞增編碼，那么可以直接計(jì)算出該臺(tái)站的歷史記錄的準(zhǔn)確位置，從而實(shí)現(xiàn)更加快捷的查找到極值記錄。

3 具體實(shí)現(xiàn)

第一步，預(yù)處理實(shí)現(xiàn)輔助數(shù)組的初始化。在初始化極值數(shù)組(extremum)的同時(shí)，按照“縣級(jí)編碼”統(tǒng)計(jì)出每種臺(tái)站類別的臺(tái)站個(gè)數(shù)，并存放到一個(gè)輔助數(shù)組(assistant)中。首先獲得極值記錄中的staID所屬的臺(tái)站類別，如果當(dāng)前記錄的staID所屬的臺(tái)站類別(curstasort)不等于前一條記錄臺(tái)站類別(prestasort)，則表明前一個(gè)類別的臺(tái)站個(gè)數(shù)統(tǒng)計(jì)結(jié)束，開始統(tǒng)計(jì)下一個(gè)臺(tái)站類別的臺(tái)站個(gè)數(shù)。

第二步，準(zhǔn)確查找到極值數(shù)據(jù)。當(dāng)接收到實(shí)時(shí)數(shù)據(jù)記錄時(shí)，根據(jù)記錄的staID，準(zhǔn)確計(jì)算出對(duì)應(yīng)的極值在極值數(shù)組中的位置。例如：staID為R1303，通過輔助數(shù)組可以得知，在臺(tái)站類別“R13＊＊”之前存在“R11＊＊、R12＊＊”2個(gè)臺(tái)站類別，“R13*＊”類別的初始位置(INITPOS)為前2個(gè)類別的統(tǒng)計(jì)數(shù)之和，即：

INITPOSR13＊＊=INITPOSR11＊＊+INITPOSR12＊＊

考慮特殊情況：如果staID的第3、4位數(shù)字編碼是順序遞增，那么可以知道，“R1303”在“R13＊＊”類別的位置是在第3個(gè)：N3，則“R1303”在極值數(shù)組中的位置POS為：

其中x為staID在某一類臺(tái)站類別中的第幾個(gè)臺(tái)站個(gè)數(shù)。當(dāng)計(jì)算出具體的位置，那么可以直接從數(shù)組中取出相應(yīng)的極值，達(dá)到了快速的找到極值的目的，優(yōu)化了程序的運(yùn)行。

但是，如果兩要素的臺(tái)站編號(hào)的第3、4位編碼不是按照順序遞增編碼，而是隨機(jī)編碼，通過以上計(jì)算就不能確定該臺(tái)站在該類別中的位置，而需要在同一個(gè)類別中，通過極值記錄的臺(tái)站編號(hào)(ext-StaID)和當(dāng)前記錄的臺(tái)站編號(hào)(curStaID)判斷而獲得極值。

通過判斷，縮小了查找極值數(shù)據(jù)的范圍，同樣實(shí)現(xiàn)了快速的定位極值的目的，優(yōu)化了程序的運(yùn)行。

4 總結(jié)

通過輔助數(shù)組的方式查找氣象極值記錄，其輔助數(shù)組和極值記錄一一對(duì)應(yīng)，當(dāng)極值文件中的記錄發(fā)生變化時(shí)，相應(yīng)的輔助數(shù)組中統(tǒng)計(jì)數(shù)也會(huì)發(fā)生變化。同時(shí)，該算法在實(shí)現(xiàn)查找極值的過程中降低了算法的時(shí)間復(fù)雜度，但增加一個(gè)輔助數(shù)組的開銷，增加了算法的空間復(fù)雜度。在區(qū)域自動(dòng)站實(shí)時(shí)質(zhì)量控制處理時(shí)，能夠簡(jiǎn)單、快速的查找到極值記錄，提高了兩要素實(shí)時(shí)資料質(zhì)量控制處理的效率，能夠滿足區(qū)域自動(dòng)站實(shí)時(shí)質(zhì)量控制實(shí)時(shí)業(yè)務(wù)需求。

［1］ 吳偉民，嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)(C語言版)［M］.北京：清華大學(xué)出版社，2009.

P413

B

1003-6598(2011)03-0050-02

2010-06-11

楊遠(yuǎn)恒(1979-)，女，工程師，主要從事氣象數(shù)據(jù)處理工作。