黎遠(yuǎn)松

（四川理工學(xué)院計(jì)算機(jī)學(xué)院，四川自貢643000）

程序執(zhí)行的時(shí)空測(cè)量方法研究

黎遠(yuǎn)松

（四川理工學(xué)院計(jì)算機(jī)學(xué)院，四川自貢643000）

程序執(zhí)行時(shí)所花費(fèi)的時(shí)間和內(nèi)存空間是評(píng)價(jià)一個(gè)程序性能優(yōu)劣的一個(gè)重要指標(biāo)。理論上，可以借助于數(shù)學(xué)這個(gè)強(qiáng)有力的工具估算出程序的時(shí)間復(fù)雜度和空間復(fù)雜度，然后用這兩個(gè)標(biāo)準(zhǔn)來(lái)度量程序的效率；實(shí)際上，在源代碼在線(xiàn)評(píng)測(cè)系統(tǒng)這樣的實(shí)際系統(tǒng)中無(wú)法使用。文章對(duì)程序執(zhí)行時(shí)所花費(fèi)的時(shí)間和內(nèi)存空間的測(cè)量方法進(jìn)行大量深入的研究，基于DOS平臺(tái)，提出了計(jì)時(shí)法，利用clock和coreleft測(cè)量程序執(zhí)行的時(shí)間和空間；基于Windows平臺(tái)，利用Get Process Times和Get Process MemoryInfo測(cè)量程序執(zhí)行的時(shí)間和空間，在四川理工ACM中得到應(yīng)用，實(shí)踐證明這些方法正確、有效。

程序；時(shí)間；空間；測(cè)量；方法

在源代碼在線(xiàn)評(píng)測(cè)系統(tǒng)的研究過(guò)程中發(fā)現(xiàn)，測(cè)量進(jìn)程執(zhí)行時(shí)所花費(fèi)的時(shí)間和所占用的內(nèi)存空間是一個(gè)亟待解決的重要問(wèn)題。利用API函數(shù)Get Tick Count（）獲取進(jìn)程的執(zhí)行時(shí)間［1］，在多任務(wù)環(huán)境里是不準(zhǔn)確的，負(fù)載的變化對(duì)實(shí)驗(yàn)結(jié)果影響明顯。

Windows 2000引入了新的進(jìn)程控制原語(yǔ)——作業(yè)對(duì)象。作業(yè)對(duì)象是可以作為單個(gè)實(shí)體管理的一個(gè)或多個(gè)進(jìn)程的集合。用戶(hù)可以設(shè)置整個(gè)執(zhí)行時(shí)間和處理器時(shí)間的分配、以及控制作業(yè)對(duì)象的調(diào)度選項(xiàng)［2］，但編程實(shí)現(xiàn)略顯復(fù)雜。

針對(duì)這些問(wèn)題，本文進(jìn)行大量深入的研究，提出了以下適用不同環(huán)境的測(cè)量方法。

1 基于DOS平臺(tái)的測(cè)量

1.1 運(yùn)行時(shí)間的測(cè)量

函數(shù)clock（）返回程序開(kāi)始運(yùn)行時(shí)經(jīng)過(guò)的時(shí)間，利用它測(cè)定運(yùn)行時(shí)間，方法如下∶

t1=clock（）；

被測(cè)程序

t2=clock（）；

t3=t2-t1；

在虛擬機(jī)（16M，單核2.33Ghz，DOS7.1，BC31）中測(cè)量以下程序的實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表1。

for（a=100；a＜200；a++）｛

for（b=100；b＜200；b++）｛

for（c=100；c＜200；c++）｛

d=711-a-b-c；

if（a*b*c*d==711000000）

｝｝｝

從表1中的time數(shù)據(jù)可以看出，被測(cè)程序的運(yùn)行時(shí)間穩(wěn)定在17 s。

由于DOS是單任務(wù)操作系統(tǒng)，被測(cè)程序受環(huán)境的影響極小，因此，測(cè)試結(jié)果變化極小。

DOS平臺(tái)的測(cè)量方法是最基本的方法，測(cè)量的結(jié)果也是最容易理解的。但在多任務(wù)環(huán)境里，準(zhǔn)確性難于保證［3-4］。

1.2 內(nèi)存空間的測(cè)量

函數(shù)coreleft返回以前未用的堆空間的大小。只用在沒(méi)有分配或釋放對(duì)象時(shí)這個(gè)值才代表真正可用的內(nèi)存大小。獲得準(zhǔn)確的RAM大小需要遍歷堆空間，利用它測(cè)定未用的RAM內(nèi)存，方法如下∶

r1=coreleft（）；

被測(cè)程序∶

r2=coreleft（）；

r3=r2-r1；

實(shí)驗(yàn)結(jié)果見(jiàn)表2。

從表2中的數(shù)據(jù)可以看出，被測(cè)程序malloc（1024）在堆空間中分配了1 KB的RAM內(nèi)存，未用的RAM內(nèi)存空間減少1 KB，正確，但是這種方法只能測(cè)定以前未用的堆空間的大小，第三組靜態(tài)分配的內(nèi)存用coreleft測(cè)量不出來(lái)，因此，具有很大的局限性。

2 基于Windows平臺(tái)的測(cè)量

2.1 獲取進(jìn)程時(shí)間信息

選手程序執(zhí)行時(shí)間的多少，是一個(gè)重要的評(píng)測(cè)指標(biāo)［2，5-6］，這里利用API函數(shù)Get Process Times（）獲取進(jìn)程的執(zhí)行時(shí)間，方法為∶

用父進(jìn)程本身創(chuàng)建一個(gè)新進(jìn)程（Create Process），獲得pi.handle，然后等程序運(yùn)行完畢以后調(diào)用Get Process Times得到需要的時(shí)間（用戶(hù)模式與kernel模式）。

通過(guò)傳遞給Create Porcess的PROCESS_INFORMATION參數(shù)，創(chuàng)建進(jìn)程Wait For Single Object（pi.h Process，INFINITE），然后再調(diào)用Get Process Times。最后利用File Time To System Time函數(shù)轉(zhuǎn)成SYSTEMTIME，核心代碼如下∶

BOOL ret=Create Process（argv［1］，NULL，NULL，NULL，TRUE，0，NULL，NULL，&si，&pi）；

//argv［1］是選手程序的文件名

a=Wait For Single Object（pi.h Process，INFINITE）；

//等待選手程序執(zhí)行INFINITE

Get Process Times（pi.h Process，&Creation Time，& Exit Time，&Kernel Time，&User Time）；

File Time To System Time（&Kernel Time，&kt）；

File Time To System Time（&User Time，&ut）；

//時(shí)間格式轉(zhuǎn)換

t=（ut.w Second+kt.w Second）*1000+ut.w Milliseconds+kt.w Milliseconds；//秒轉(zhuǎn)換成毫秒

測(cè)試環(huán)境∶虛擬機(jī)，512 M，單核2.33 Ghz，Windows Server 2000，VC++6.0。實(shí)驗(yàn)結(jié)果見(jiàn)表3、表4。

從表4中的數(shù)據(jù)可以看出，利用函數(shù)GetProcess-Times（）來(lái)獲取進(jìn)程的執(zhí)行時(shí)間，在多任務(wù)環(huán)境里是準(zhǔn)確的，負(fù)載的變化對(duì)實(shí)驗(yàn)結(jié)果影響不明顯。

2.2 獲取進(jìn)程內(nèi)存信息

選手程序執(zhí)行時(shí)占用內(nèi)存的多少，是另一個(gè)重要的評(píng)測(cè)指標(biāo)［7-9］，獲取進(jìn)程執(zhí)行時(shí)所占用的內(nèi)存信息比獲取進(jìn)程執(zhí)行時(shí)所花費(fèi)的時(shí)間要困難得多。本文用父進(jìn)程本身創(chuàng)建一個(gè)新進(jìn)程（Create Process），獲得pi.handle，然后等程序運(yùn)行完畢以后調(diào)用Get Process Memory-Info得到當(dāng)前進(jìn)程所使用的內(nèi)存Working Set Size，單位是字節(jié)，核心代碼如下∶

Get Process MemoryInfo（pi.h Process，&pmc，sizeof（pmc））；

//獲取某一個(gè)進(jìn)程的內(nèi)存信息。

cout?″|″?t?″|″?pmc.Working Set Size/1024?″|″；//把Byte轉(zhuǎn)換KB

被測(cè)程序∶int x［1024］；int y［1024］；int z［1024］；

由表5可以看出，Get Process MemoryInfo能正確地測(cè)量出程序所使用的內(nèi)存情況，分配單位為4KB。

需要強(qiáng)調(diào)的是，Get Process Times（）和Get Process MemoryInfo（）函數(shù)一定要位于Wait For Single Object（）函數(shù)之后，只有這樣才能獲取正確的信息。

3 結(jié)束語(yǔ)

基本DOS平臺(tái)的測(cè)量方法簡(jiǎn)單、有效，在算法的事后分析時(shí)得到應(yīng)用；基于Windows平臺(tái)的測(cè)量方法已應(yīng)用在理工ACM系統(tǒng)中，運(yùn)行良好。對(duì)于運(yùn)行時(shí)間和空間的評(píng)測(cè)和限制等，有待進(jìn)一步研究和解決。

［1］王騰'藥單霖.Online Judge系統(tǒng)的設(shè)計(jì)開(kāi)發(fā)［J］.計(jì)算機(jī)應(yīng)用與軟件'2006(12）:78-83.

［2］(美）Jeffrey Richter.WINDOWS核心編程［M］.北京:機(jī)械工業(yè)出版社'2008.

［3］張浩斌.基于開(kāi)放式云平臺(tái)的開(kāi)源在線(xiàn)評(píng)測(cè)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(jī)科學(xué)'2012'39(11A）:339-346.

［4］李臣龍'鮑廣喜.基于WAMP的在線(xiàn)評(píng)測(cè)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)［J］.電腦編程技巧與維護(hù)'2013'15:64-75.

［5］孟繁軍'劉東升'張麗萍'等.程序設(shè)計(jì)基礎(chǔ)教學(xué)策略的實(shí)踐研究［J］.內(nèi)蒙古師范大學(xué)學(xué)報(bào):教育科學(xué)版' 2013(3）:126-129.

［6］M ickey Williams.Windows 2000編程技術(shù)內(nèi)幕［M］.北京:機(jī)械工業(yè)出版社'1999.

［7］唐子蛟'項(xiàng)菲'符長(zhǎng)友.電子投票系統(tǒng)結(jié)果計(jì)算的誤差源分析［J］.四川理工學(xué)院學(xué)報(bào):自然科學(xué)版'2013' 26(4）:52-55.

［8］王曉'劉鳳仙'李琦.GIS與三維可視化在校園地下管網(wǎng)線(xiàn)管理中的應(yīng)用［J］.四川理工學(xué)院學(xué)報(bào):自然科學(xué)版'2013'26(3）:46-50.

［9］M ihail B.The U-Kenmotsu Hypersurfaces Axiom and Six-Dimensional Hermitian Submanifolds of cayley algebra［J］.Journal of Sichuan University of Science& Engineering(Natural Science Edition）'2013'Vol.26No.3: 1-6.

Research on Approaches to Measure Program Execution Time and Space

LIYuansong
（School of Computer Science，Sichuan University of Science&Engineering，Zigong 643000，China）

Time and space needed for process are two essentialmeasures of our algorithm.In theory，we calculate the time complexity and space complexity of the algorithm with the aid ofmathematics firstly，and thenmeasure the efficiency of the algorithm with these two standards.In fact，the time complexity and space complexity of the algorithm cannot be used in the actual system such as online judge system.Approaches to measure process execution time and space were deeply researched for this problem and timing based on DOSwas proposed，which measures program execution timing and memory with clock and coreleft.Base on windows with get process times and get processmemory Info，it had been applied in the SUSE ACM correctly and effectively.

program；time；measure；approach

TP393.6

A

1673-1549（2014）01-0053-03

10.11863/j.suse.2014.01.14

2013-10-09

四川省教育廳科研項(xiàng)目（13ZAO125）；軟件工程專(zhuān)業(yè)綜合改革項(xiàng)目（ZG-1202）

黎遠(yuǎn)松（1970-），男，重慶開(kāi)縣人，副教授，碩士，主要從事源代碼在線(xiàn)評(píng)測(cè)系統(tǒng)方面的研究，（E-mail）lys700620@yeah.net