前一段時間在博客園裡看到這樣一篇文章，那位兄弟談到程序效率的關鍵是“簡短”。他說，“程序越簡短，其可執行代碼就越少，就越有效率”，而在編寫程序的時候，“要盡量改進我們的算法，而改進算法中最重要的一條，就是減少語句”。這句話從表面上似乎正確，但我認為性能這問題不能用“簡短”這種方式去思考，否則會進入一些誤區。我整理了一下思路，希望可以從幾個方面把詳細談一下這個問題。
首先，如果說“簡短的代碼效率高”，那麼什麼叫作“簡短”呢？姑且理解為“代碼少”吧。如果“代碼少”能夠得出“效率高”，那我認為還需要其他一些條件，例如：
代碼完全是順序執行的
每行代碼的效率相同
但是，這對於使用高級語言的程序員來說，這兩條基本上都無法成立，因為：
代碼中有條件跳轉（如循環），因此一段簡短的代碼最終執行的“次數”可能比一段復雜的代碼要多。這是很常見的情況，並非如那位兄弟所說“兩三行代碼寫出死循環”這樣的“特例”。
每行代碼的效率幾乎不可能相同。試想一個i++和一個方法調用，他們的性能開銷怎麼可能相同呢？再者，這個特性並非是“高級語言”特有的，連CPU指令也是一樣（以後我們再來詳談這個問題）。
其實這就是目前編程工作中不可能回避的現狀，那就是高級語言並不直接反映出機器的執行過程。同時，我們不能從代碼表面的簡短程度來判斷程序效率的高低。正如那位朋友所談，影響程序的關鍵因素之一是算法的選擇，但我不同意他說算法優化的關鍵在於“減少語句”。從一定程度上講，選擇高效的算法的確是為了減少指令執行的“總量”，但它並不是如那篇文章所說通過“少一些變量”，“少一些判斷”來進行的，而是在於大幅的邏輯改變來減少總體的操作。
事實上，我們很容易便能舉出代碼簡短，但是性能較差的算法。就拿最常見的排序算法來說，冒泡排序不可謂不簡單：
public void BubbleSort(int[] array)
{
for (int i = array.Length - 1; i >= 0; i--)
{
for (int j = 1; j <= i; j++)
{
if (array[j - 1] > array[j])
{
int temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}
}
}
}
而快速排序與之相比實在是復雜太多了：
public void QuickSort(int[] array)
{
QuickSortInternal(array, 0, array.Length);
}
private void QuickSortInternal(int[] array, int begin, int end)
{
if (end == begin)
{
return;
}
else
{
int pivot = FindPivotIndex(array, begin, end);
if (pivot > begin) QuickSortInternal(array, begin, pivot - 1);
if (pivot < end) QuickSortInternal(array, pivot + 1, end);
}
}
private int FindPivotIndex(int[] array, int begin, int end)
{
int pivot = begin;
int m = begin + 1;
int n = end;
while (m < end && array[pivot] >= array[m])
{
m++;
}
while (n > begin && array[pivot] <= array[n])
{
n--;
}
while (m < n)
{
int temp = array[m];
array[m] = array[n];
array[n] = temp;
while (m < end && array[pivot] >= array[m])
{
m++;
}
while (n > begin && array[pivot] <= array[n])
{
n--;
}
}
if (pivot != n)
{
int temp = array[n];
array[n] = array[pivot];
array[pivot] = temp;
}
return n;
}
OMG，為什麼快速排序會那麼復雜？其原因在於，快速排序的性能關鍵之一，在於選擇一個好的中軸（pivot）元素，選擇一個好的中軸元素可以盡可能減少的交換操作的次數，以此提高算法的效率。而冒泡排序，做法的確“簡短”，但是其性能在大部分場合都不如快速排序來的好。而且，同樣是快速排序，也可以有多種實現方法，有的語言還可以實現地非常簡單，如Haskell：
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
這便是Haskell版的快速排序，夠短吧。但是它的效率不如之前那段長長的C#——當然，這麼比可能不公平，因為兩者使用的數據結構不同，C#基於數組進行排序，而Haskell卻使用的是不可變的單向鏈表。
算法是效率的關鍵，但選擇合適的算法也並非是一件十分容易的事情。我們都知道一個算法它有時間復雜度，空間復雜度等等，但這些是什麼呢？是從數學角度得出的“理論值”。一個算法的時間復雜度，考慮的是算法的時間隨規模增長的變化規律，它能確保的只是“當規模大到一定程度時”，時間復雜度低的算法效率肯定相對較高。但是在實際開發過程中，我們遇到的數據量往往都是有限的，其形式甚至還有一定規律可循。因此，“理論上”時間復雜度低的算法，並非時時刻刻都有上佳表現。
例如，對於一個已經排序的數組來說，冒泡排序的性能無人能敵；對於一個高效的快速排序算法來說，如果元素數量少於一個阈值時就會使用插入排序（因為快速排序時間復雜度的常數較大）；再比如，一個算法使用空間換時間，但是空間一大，物理內存中的數據可能就會被放到磁盤交換區上（也有人把它叫做虛擬內存，但是我不認同這個叫法），此時讀取時可能就要從硬盤上重新加載數據頁，性能可能就更低一些了。說個更近的，有時候每次都創建對象，性能反而比緩存起來要高，不是嗎？
因此我認為，無論怎麼樣，“簡短”不應該是評價一段代碼是否高效的因素。您可能會說，算法對性能來說自然很關鍵，但是這裡說的“簡短”不是指算法的改變，而是指在算法相同的情況下，少一些賦值，判斷操作等等，這樣指令少了性能不是更高了嗎？不過我的考慮是，既然算法已經確定了，那麼究竟有哪些地方值得我們減少一些賦值或判斷操作呢？即便這樣的確有效果，但我想，如果保留合理的賦值和判斷如果可以讓代碼更清晰，那就不要進行如此“手動”而“原始”更 “想當然”的優化吧。清晰、正確比高效更重要。
最重要的是，沒有Profiling，一切優化都是徒勞的。如果您認為減少賦值和判斷可以有效提高性能，那麼也用Profiling來證明一下，不是嗎？當然，我並沒有說一些細節上的調整對性能影響不大，我接下來也會討論直接對匯編進行的優化。但是，即使我們有需要優化匯編的場景……它們基本上也不是靠所謂減少賦值和判斷來起到效果的。
最後補充一句：這篇文章裡我談到的“算法”是指廣義的“實現方式”，通俗地講便是“代碼的寫法”。而“冒泡排序”等面向指定問題的解法，我把它稱之為“經典算法”。在這裡，我們還是加以區分吧。
文章來源：http://www.cnblogs.com/JeffreyZhao/archive/2010/01/07/short-code-is-not-always-fast-1-algorithms.html
