1、反匯編在常數因子優化中的運用 程序優化是無盡頭的，其中常數因子也是決議程序運轉快慢的關鍵之一。然而在競賽中，漸進時間復雜度是人們關注的重點，而同樣可以決議程序運轉快慢的常數因子優化問題卻缺乏注重。緒言在Visual C+言語環境下，從特定編譯器生成的匯編代碼出發，我討論了反匯編在常數因子優化中的運用，并提出了假設干優化改良方案。引例：關于memset函數的小實驗知memset函數為O(N)復雜度的語句。#include const int Total=1000000000;const int Time=你喜歡的合法的數值;char fieldTotal/Time;int i,j;int mai

2、n()for (;j10;j+)for (i=0;iTime;i+)memset(field,0,sizeof(field);return 0;他能直接答出Time值與運轉速度的關系？觀看右邊的C+程序假設計算機具有足夠大的內存分析 能夠他以為Time值不影響程序時間復雜度，因此對程序的速度無影響。Time值與運轉速度的關系 但是，當上機實驗后，他會發現，Time值較大或較小時運轉速度會變慢，這是為什么呢？#include const int Total=1000000000;const int Time=你喜歡的合法的數值;char fieldTotal/Time;int i,j;int m

3、ain()for (;j10;j+)for (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;二、除法求余的優化由于計算機內存是線性的，多維數組的元素在陳列為線性序列后存入存儲器，如下所示：0,00,10,20,31,01,11,21,32,02,12,22,33,03,13,23,3三、關于多維數組的性能優化0,00,10,20,31,01,11,21,32,02,12,22,33,03,13,23,3由于在構造上需求進展轉換，多維數組的引址操作被翻譯成了乘法操作。 數組定義：

4、a1010 Debug方式下，對數組的取值操作運用了imul運算 Release方式編譯時會進展和乘法運算一樣的優化：return aij;00411B6F moveax,dword ptr i 00411B75 imuleax,eax,28h 00411B78 leaecx,aeax 00411B7F movedx,dword ptr j 00411B85 moveax,dword ptr ecx+edx*4 三、關于多維數組的性能優化由于imul是一種比例時間較大的指令，假設能消去這一指令，便可以產生較大幅度的優化。三、關于多維數組的性能優化return aij;00411B6F move

5、ax,dword ptr i 00411B75 imuleax,eax,28h 00411B78 leaecx,aeax 00411B7F movedx,dword ptr j 00411B85 moveax,dword ptr ecx+edx*4 假設操作的變址方法固定比如像寬度優先搜索，變址操作為+1,-1,+N,-N，那么用指針加減操作以及輔助記錄就能獲得更快的速度消去了乘法操作。定義表和指針：int table200200;int*ptr,*ptr2;定義滑動常數：/East,South,West,Northconst go=1,200,-1,-200;/假設ptr已賦值ptr2=pt

6、r+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 eax這樣本來隱藏的乘法操作就被消去了。 三、關于多維數組的性能優化這種操作被我稱為指針的“行走操作。運用這個優化有個條件，就是指針變化方式固定。 讓我們經過一個例子來了解這種優化的作用。真的很有用三、關

7、于多維數組的性能優化題意描畫：在N*M的矩陣中，有一些妨礙，有一個物體放在某個格子上。它會按照一個時間表向某一方向運動，一個時間單位挪動格。某一秒他可以讓它運動，也可以讓它靜止。問物體最多能運動的長度。時間表由很多個時間片段構成，在每個時間片斷中，物體將向同一方向運動。數據規模：50%的數據中，1N, M200，時間長度(T)200；100%的數據中，1N, M200，時間片段個數(K)200，時間長度(T)40000。例：adv1900 (NOI2005)這道題有很多做法，其中最優做法是運用單調性降維。無論用什么方法，都必經一個關鍵步驟，這就是在不同的時間點間進展形狀轉移，并且，都要將這一步

8、“批處置化。最優做法的單調性降維，以及其他各式各樣的優化，如堆和RMQ等，都是基于對這一步驟的漸進時間復雜度的優化。 例：adv1900 (NOI2005)但是，利用“行走操作，我們完全可以另辟蹊徑?；诖瞬襟E具有的運用優化的典型特點： 1位于循環最里層，直接影響運轉速度； 2大量運用對數組的變化方式固定的操作，可以用指針“行走來優化。雖然最終還是運用“批處置化的思想，但是這種方法沒有把精神用在漸進復雜度的優化上，而轉向到了詳細的實現上。例：adv1900 (NOI2005)此題的挪動情況可以靠在挪動前進展對變量的初始化實現。在某個時間段中對前面位置的訊問可以用反方向“行走實現。對于取址運算中

9、的位運算，可以用強迫轉換指針的方法消去。對妨礙判別的實現可以用一致變量格式實現。例：adv1900 (NOI2005)例：adv1900 (NOI2005)下表展現了此方法與非“行走優化方法的速度對比(Debug方式)選手名稱：withoutWalk試題：adv1900 文件名：adv1900編號評測結果時間內存0正確0.016s520KB1正確0.016s520KB2正確0.016s520KB3正確0.063s520KB4正確0.344s520KB5超時1.016s520KB6正確0.781s520KB7超時1.031s520KB8正確0.625s520KB9超時1.156s520KB本題總得分70，有效用時5.064s。選手名稱：withWalk試題：adv1900 文件名：adv1900編號評測結果時間內存0正確0.016s520KB1正確0.016s520KB2正確0.016s520KB3正確0.047s520KB4正確0.234s520KB5正確0.703s520KB6正確0.547s520KB7正確0.734s520KB8正確0.484s520KB9正確0.797s520KB本題總得分100，有效用時3