1、反匯編在常數(shù)因子優(yōu)化中的應(yīng)用 1n程序優(yōu)化是無止境的，其中常數(shù)因子也是程序優(yōu)化是無止境的，其中常數(shù)因子也是決定程序運行快慢的關(guān)鍵之一。決定程序運行快慢的關(guān)鍵之一。n然而在競賽中，漸進時間復雜度是人們關(guān)然而在競賽中，漸進時間復雜度是人們關(guān)注的重點，而同樣能夠決定程序運行快慢注的重點，而同樣能夠決定程序運行快慢的的常數(shù)因子常數(shù)因子優(yōu)化問題卻缺乏重視。優(yōu)化問題卻缺乏重視。緒言緒言n在在Visual C+語言環(huán)境下，從特定編譯器生語言環(huán)境下，從特定編譯器生成的匯編代碼出發(fā)，我探討了反匯編在常數(shù)成的匯編代碼出發(fā)，我探討了反匯編在常數(shù)因子優(yōu)化中的應(yīng)用，并提出了若干優(yōu)化改進因子優(yōu)化中的應(yīng)用，并提出了若干優(yōu)化

2、改進方案。方案。2引例：關(guān)于引例：關(guān)于memset函數(shù)的小實驗函數(shù)的小實驗n已知memset函數(shù)為O(N)復雜度的語句。#include const int Total=1000000000;const int Time=你喜歡的合法的數(shù)值;char fieldTotal/Time;int i,j;int main()for (;j10;j+)for (i=0;iTime;i+)memset(field,0,sizeof(field);return 0;n你能直接答出Time值與運行速度的關(guān)系？n觀看右邊的C+程序（假設(shè)計算機具有足夠大的內(nèi)存）3012345678902468運行時間(秒)Ti

3、me值的對數(shù)試驗結(jié)果Debug模式Release模式分析分析 可能你認為可能你認為Time值值不影響程序時間復雜不影響程序時間復雜度，因此對程序的速度，因此對程序的速度無影響。度無影響。Time值與運行速度的關(guān)系 但是，當上機實驗后，你會發(fā)現(xiàn)，但是，當上機實驗后，你會發(fā)現(xiàn)，Time值較大值較大或較小時運行速度會變慢，這是為什么呢？或較小時運行速度會變慢，這是為什么呢？#include const int Total=1000000000;const int Time=你喜歡的合法的數(shù)值;char fieldTotal/Time;int i,j;int main()for (;j10;j+)fo

4、r (i=0;i(i-1);原始代碼：const a=1,2,4,8,16,32,64,128,256,512,1024,2048,4096;c=b%ai;d=e/ai;二、除法（求余）的優(yōu)化二、除法（求余）的優(yōu)化17n由于計算機內(nèi)存是線性的，多維數(shù)組的元素在排列為線性序列后存入存儲器，如下所示：0,00,10,20,31,01,11,21,32,02,12,22,33,03,13,23,3三、關(guān)于多維數(shù)組的性能優(yōu)化三、關(guān)于多維數(shù)組的性能優(yōu)化0,00,10,20,31,01,11,21,32,02,12,22,33,03,13,23,318n由于在結(jié)構(gòu)上需要進行轉(zhuǎn)換，多維數(shù)組的引址操作被翻譯成

5、了乘法操作。n 數(shù)組定義：a1010n Debug模式下，對數(shù)組的取值操作使用了imul運算（ Release模式編譯時會進行和乘法運算相同的優(yōu)化）：return aij;00411B6F moveax,dword ptr i 00411B75 imul eax,eax,28h 00411B78 leaecx,aeax 00411B7F movedx,dword ptr j 00411B85 moveax,dword ptr ecx+edx*4 三、關(guān)于多維數(shù)組的性能優(yōu)化三、關(guān)于多維數(shù)組的性能優(yōu)化19n由于imul是一種比例時間較大的指令，如果能消去這一指令，便能夠產(chǎn)生較大幅度的優(yōu)化。三、關(guān)于

6、多維數(shù)組的性能優(yōu)化三、關(guān)于多維數(shù)組的性能優(yōu)化return aij;00411B6F moveax,dword ptr i 00411B75 imul eax,eax,28h 00411B78 leaecx,aeax 00411B7F movedx,dword ptr j 00411B85 moveax,dword ptr ecx+edx*4 n如果操作的變址方法固定（比如像寬度優(yōu)先搜索，變址操作為+1,-1,+N,-N），那么用指針加減操作以及輔助記錄就能獲得更快的速度（消去了乘法操作）。20定義表和指針：int table200200;int*ptr,*ptr2;定義滑動常數(shù)：/East,S

7、outh,West,Northconst go=1,200,-1,-200;/假設(shè)ptr已賦值ptr2=ptr+go0;00411A4C mov eax,dword ptr go 00411A51 mov ecx,dword ptr ptr 00411A57 lea edx,ecx+eax*4 00411A5A mov dword ptr ptr2,edx return *ptr2;00411A60 mov eax,dword ptr ptr2 00411A65 mov eax,dword ptr eaxn這樣本來隱藏的乘法操作就被消去了。 三、關(guān)于多維數(shù)組的性能優(yōu)化三、關(guān)于多維數(shù)組的性能優(yōu)化

8、21n這種操作被我稱為指針的“行走”操作。使用這個優(yōu)化有個條件，就是指針變化方式固定。 n讓我們通過一個例子來了解這種優(yōu)化的作用。三、關(guān)于多維數(shù)組的性能優(yōu)化三、關(guān)于多維數(shù)組的性能優(yōu)化22n題意描述：題意描述：在N*M的矩陣中，有一些障礙，有一個物體放在某個格子上。它會按照一個時間表向某一方向運動，一個時間單位移動格。某一秒你可以讓它運動，也可以讓它靜止。問物體最多能運動的長度。時間表由很多個時間片段構(gòu)成，在每個時間片斷中，物體將向同一方向運動。n數(shù)據(jù)規(guī)模：數(shù)據(jù)規(guī)模：50%的數(shù)據(jù)中，1N, M200，時間長度時間長度(T)200(T)200；100%的數(shù)據(jù)中，1N, M200，時間片段個數(shù)(K)

9、200，時間長度時間長度(T)40000(T)40000。例：例：adv1900 (NOI2005)23n這道題有很多做法，其中最優(yōu)做法是使用單調(diào)性降維。n無論用什么方法，都必經(jīng)一個關(guān)鍵步驟，這就是在不同的時間點間進行狀態(tài)轉(zhuǎn)移，并且，都要將這一步“批處理”化。n最優(yōu)做法的單調(diào)性降維，以及其他各式各樣的優(yōu)化，如堆和RMQ等，都是基于對這一步驟的漸進時間復雜度的優(yōu)化。 例：例：adv1900 (NOI2005)24n但是，利用“行走”操作，我們完全可以另辟蹊徑。n基于此步驟具有的使用優(yōu)化的典型特點：基于此步驟具有的使用優(yōu)化的典型特點： （1）位于循環(huán)最里層，直接影響運行速度； （2）大量使用對數(shù)組

10、的變化方式固定的操作，可以用指針“行走”來優(yōu)化。n雖然最終還是使用“批處理化”的思想，但是這種方法沒有把精力用在漸進復雜度的優(yōu)化上，而轉(zhuǎn)向到了具體的實現(xiàn)上。例：例：adv1900 (NOI2005)25n本題的移動情況可以靠在移動前進行對變量的初始化實現(xiàn)。n在某個時間段中對前面位置的詢問可以用反方向“行走”實現(xiàn)。n對于取址運算中的位運算，可以用強制轉(zhuǎn)換指針的方法消去。n對障礙判斷的實現(xiàn)可以用統(tǒng)一變量格式實現(xiàn)。例：例：adv1900 (NOI2005)26例：例：adv1900 (NOI2005)n下表展現(xiàn)了此方法與非“行走”優(yōu)化方法的速度對比(Debug模式)表表3：“行走行走”優(yōu)化方法優(yōu)化方法表表4：非：非“行走行走”優(yōu)化方優(yōu)化方法法27總結(jié)總結(jié) n匯編語言具有高速、高效的特點，并且它的細微匯編語言具有高速、高效的特點，并且它的細微差異，都會導致程序運行速度的一定的變化。差異，都會導致程序運行速度的一定的變化。n上述幾個實例展現(xiàn)