算法合集之論反匯編在時(shí)間常數(shù)優(yōu)化中的應(yīng)用(已修改)
2024-10-28 20:35 本頁面
【正文】 反匯編在常數(shù)因子優(yōu)化中的應(yīng)用 四川省成都七中 周以蘇 ? 程序優(yōu)化是無止境的，其中常數(shù)因子也是決定程序運(yùn)行快慢的關(guān)鍵之一。 ? 然而在競賽中，漸進(jìn)時(shí)間復(fù)雜度是人們關(guān)注的重點(diǎn)，而同樣能夠決定程序運(yùn)行快慢的常數(shù)因子優(yōu)化問題卻缺乏重視。 緒言 ? 在 Visual C++語言環(huán)境下，從特定編譯器生成的匯編代碼出發(fā)，我探討了反匯編在常數(shù)因子優(yōu)化中的應(yīng)用，并提出了若干優(yōu)化改進(jìn)方案。 引例：關(guān)于 memset函數(shù)的小實(shí)驗(yàn) ? 已知 memset函數(shù)為O(N)復(fù)雜度的語句。 include const int Total=1000000000。 const int Time=你喜歡的合法的數(shù)值 。 char field[Total/Time]。 int i,j。 int main() { for (。j10。j++) for (i=0。iTime。i++) memset(field,0,sizeof(field))。 return 0。 } ? 你能直接答出 Time值與運(yùn)行速度的關(guān)系？ ? 觀看右邊的 C++程序 （假設(shè)計(jì)算機(jī)具有足夠大的內(nèi)存） 試驗(yàn)結(jié)果02468100 2 4 6 8T i m e 值的對數(shù)運(yùn)行時(shí)間(秒)D e b u g 模式 Release模 式分析 可能你認(rèn)為 Time值不影響程序時(shí)間復(fù)雜度，因此對程序的速度無影響。 Time值與運(yùn)行速度的關(guān)系 但是，當(dāng)上機(jī)實(shí)驗(yàn)后，你會發(fā)現(xiàn)， Time值較大或較小時(shí)運(yùn)行速度會變慢，這是為什么呢？ include const int Total=1000000000。 const int Time=你喜歡的合法的數(shù)值 。 char field[Total/Time]。 int i,j。 int main() { for (。j10。j++) for (i=0。iTime。i++) memset(field,0,sizeof(field))。 return 0。 } 分析 memset(table,0,sizeof(table))。 00401001 xor eax,eax 00401003 mov ecx,9C40h 00401008 mov edi,offset table 0040100D rep stos dword ptr [edi] ? Release模式下編譯器對 memset語句的處理如下 ? Debug模式下編譯器對 memset語句的處理如下 memset(field,0,sizeof(field))。 00411A6B push 2710h 00411A70 push 0 00411A72 push offset field 00411A77 call @ILT+350(_memset) 00411A7C add esp,0Ch memset(field,0,sizeof(field))。 00411A6B push 2710h 00411A70 push 0 00411A72 push offset field (428
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1