我提出的第一個版本非常直接

    def f1(list):
        string = ""
        for item in list:
            string = string + chr(item)
        return string

“那不可能是最快的方法，”我的朋友說，“這個怎麼樣？”

    def f2(list):
        return reduce(lambda string, item: string + chr(item), list, "")

這個版本執行的字串操作集與第一個版本完全相同，但消除了 for 迴圈的開銷，轉而使用 reduce() 函式更快、隱含的迴圈。

“當然，”我回答道，“但它的代價是每個列表項都有一個函式呼叫（lambda 函式）。我敢打賭它會更慢，因為 Python 中的函式呼叫開銷比 for 迴圈開銷更大。”

（好吧，所以我已經做了比較。f2() 比 f1() 多花了 60% 的時間。就是這樣 :-)）

“嗯，”我的朋友說，“我需要它更快。”“好的，”我說，“這個版本怎麼樣？”

    def f3(list):
        string = ""
        for character in map(chr, list):
            string = string + character
        return string

令我們驚訝的是，f3() 的速度是 f1() 的_兩倍_！這讓我們感到驚訝的原因有兩點：首先，它使用了更多的儲存空間（map(chr, list) 的結果是另一個相同長度的列表）；其次，它包含兩個迴圈而不是一個（map() 函式隱含的一個，以及 for 迴圈）。

當然，空間與時間是眾所周知的權衡，所以第一個不應該讓我們感到驚訝。然而，為什麼兩個迴圈比一個迴圈快呢？有兩個原因。

首先，在 f1() 中，內建函式 chr() 在每次迭代中都會被查詢，而在 f3() 中它只被查詢一次（作為 map() 的引數）。我告訴我的朋友，這種查詢相對昂貴，因為 Python 的動態作用域規則意味著它首先在當前模組的全域性字典中查詢（不成功），然後才在內建函式字典中查詢（在那裡找到）。更糟糕的是，不成功的字典查詢（平均而言）比成功的查詢稍慢，因為雜湊鏈的工作方式。

f3() 比 f1() 更快的第二個原因是，由位元組碼直譯器執行的 chr(item) 呼叫可能比由 map() 函式執行時慢一點——位元組碼直譯器必須為每個呼叫執行三條位元組碼指令（載入 'chr'，載入 'item'，呼叫），而 map() 函式則全部在 C 中完成。

這使我們考慮了一種折衷方案，它不會浪費額外的空間，但會加快 chr() 函式的查詢速度

    def f4(list):
        string = ""
        lchr = chr
        for item in list:
            string = string + lchr(item)
        return string

正如所料，f4() 比 f3() 慢，但只慢了 25%；它仍然比 f1() 快大約 40%。這是因為區域性變數查詢_遠_快於全域性或內建變數查詢：Python“編譯器”優化了大多數函式體，使得對於區域性變數，無需進行字典查詢，簡單的陣列索引操作就足夠了。f4() 相對於 f1() 和 f3() 的相對速度表明 f3() 更快的兩個原因都有貢獻，但第一個原因（查詢次數更少）更為重要。（要獲得更精確的資料，我們需要對直譯器進行插樁。）

儘管如此，我們最好的版本 f3() 仍然只比最直接的版本 f1() 快兩倍。我們能做得更好嗎？

我擔心演算法的二次行為會拖垮我們。到目前為止，我們一直使用包含 256 個整數的列表作為測試資料，因為我的朋友需要該函式來處理這些資料。但是，如果將其應用於包含兩千個字元的列表呢？我們將一個字元一個字元地連線越來越長的字串。不難看出，除了開銷之外，以這種方式建立一個長度為 N 的列表，總共需要複製 1 + 2 + 3 + ... + (N-1) 個字元，即 N*(N-1)/2，或 0.5*N**2 - 0.5*N。除此之外，還有 N 次字串分配操作，但對於足夠大的 N，包含 N**2 的項將佔據主導地位。事實上，對於一個長 8 倍（2048 項）的列表，這些函式都花費了遠超 8 倍的時間；實際上接近 16 倍。我不敢嘗試一個長 64 倍的列表。

有一種通用技術可以避免此類演算法中的二次行為。我將其編碼如下，用於長度正好為 256 項的字串

    def f5(list):
        string = ""
        for i in range(0, 256, 16): # 0, 16, 32, 48, 64, ...
            s = ""
            for character in map(chr, list[i:i+16]):
                s = s + character
            string = string + s
        return string

不幸的是，對於 256 個專案的列表，這個版本的執行速度略慢於 f3()（儘管在 20% 以內）。由於編寫通用版本只會使其更慢，我們沒有再進一步追究這條路徑（除了我們還將其與一個不使用 map() 的變體進行了比較，當然那個更慢）。

最後，我嘗試了一種截然不同的方法：_只_使用隱含的迴圈。請注意，整個操作可以描述如下：對每個列表項應用 chr()；然後連線生成的字元。我們已經為第一部分使用了隱含迴圈：map()。幸運的是，string 模組中有一些字串連線函式是用 C 實現的。特別是，string.joinfields(list_of_strings, delimiter) 連線字串列表，在每兩個字串之間放置一個選擇的分隔符。沒有什麼能阻止我們連線字元列表（在 Python 中，字元只是長度為一的字串），使用空字串作為分隔符。瞧！

    import string
    def f6(list):
        return string.joinfields(map(chr, list), "")

這個函式比我們最快的競爭者 f3() 快四到五倍。此外，它沒有其他版本的二次行為。

贏家是...

第二天，我忽然想起 Python 的一個不為人知的角落：array 模組。它恰好有一個操作，可以從 Python 整數列表中建立 1 位元組寬的整數陣列，並且每個陣列都可以寫入檔案或轉換為字串作為二進位制資料結構。以下是使用這些操作實現的函式

    import array
    def f7(list):
        return array.array('B', list).tostring()

這比 f6() 快大約三倍，或者比 f3() 快 12 到 15 倍！它還使用了更少的中間儲存——它只分配了 N 位元組的 2 個物件（加上固定的開銷），而 f6() 首先分配了一個包含 N 個專案的列表，這通常需要 4N 位元組（在 64 位機器上為 8N 位元組）——假設字元物件與程式中其他地方的類似物件共享（就像小整數一樣，Python 在大多數情況下會快取長度為一的字串）。

“停，”我的朋友說，“在你還沒進入負值時間之前——這已經足夠快了，我的程式。”我同意了，儘管我本來還想嘗試一種方法：用 C 語言編寫整個函式。這可以實現最小的儲存要求（它會立即分配一個長度為 N 的字串）並在 C 程式碼中節省一些指令，我知道這些指令存在於 array 模組中，因為它具有通用性（它支援 1、2 和 4 位元組的整數寬度）。然而，它無法避免必須一個接一個地從列表中提取專案，並從中提取 C 整數，這兩者在 Python-C API 中都是相當昂貴的操作，所以我預計與 f7() 相比，速度提升最多是適度的。考慮到編寫和測試擴充套件的努力（與快速編寫 Python 單行程式碼相比），以及對非標準 Python 擴充套件的依賴，我決定不再追求這個選項……

結論

如果你需要速度，請選擇內建函式——你無法超越用 C 編寫的迴圈。查閱庫手冊，看看是否有你想要的內建函式。如果沒有，這裡有一些迴圈最佳化的指導方針

• _第一條規則：_ 只有在有確鑿證據表明存在速度瓶頸時才進行最佳化。只最佳化最內層的迴圈。（這條規則與 Python 無關，但重複它並無壞處，因為它能節省大量工作。:-)）
• 小即是美。鑑於 Python 在位元組碼指令和變數查詢方面的巨大開銷，增加額外的測試以節省一點點工作量通常不划算。
• 使用內在操作。map() 中的隱含迴圈比顯式 for 迴圈更快；帶有顯式迴圈計數器的 while 迴圈甚至更慢。
• 避免在內層迴圈中呼叫用 Python 編寫的函式。這包括 lambda 函式。將內層迴圈內聯可以節省大量時間。
• 區域性變數比全域性變數快；如果在一個迴圈中使用全域性常量，請在迴圈之前將其複製到區域性變數中。在 Python 中，函式名（全域性或內建）也是全域性常量！
• 嘗試使用 map()、filter() 或 reduce() 來替換顯式 for 迴圈，但前提是你能夠使用內建函式：map 結合內建函式勝過 for 迴圈，但帶有內聯程式碼的 for 迴圈勝過 map 結合 lambda 函式！
• 檢查你的演算法是否存在二次行為。但請注意，更復雜的演算法只對大 N 值才值得，對於小 N 值，複雜性並不能帶來回報。在我們的例子中，256 被證明足夠小，以至於更簡單的版本仍然稍快一點。你的情況可能有所不同——這值得研究。
• 最後但並非最不重要的一點：收集資料。Python 出色的 profile 模組可以快速顯示你程式碼中的瓶頸。如果你正在考慮同一個演算法的不同版本，請使用 time.clock() 函式在緊密迴圈中進行測試。

順便說一下，這是我使用的計時函式。它使用引數 a 呼叫函式 f n*10 次，並列印函式名，後跟所花費的時間，四捨五入到毫秒。10 次重複呼叫是為了最大程度地減少計時函式本身的迴圈開銷。你甚至可以進一步進行 100 次呼叫……還要注意，表示式 range(n) 是在計時括號之外計算的——這是另一個最大限度地減少計時函式造成的開銷的技巧。如果你擔心這種開銷，可以透過呼叫一個什麼都不做的函式來校準它。

    import time
    def timing(f, n, a):
        print f.__name__,
        r = range(n)
        t1 = time.clock()
        for i in r:
            f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a)
        t2 = time.clock()
        print round(t2-t1, 3)

尾聲

幾天後，我的朋友又回來了，問道：“你如何進行反向操作？也就是說，從字串中建立整數 ASCII 值列表。”哦不，又來了，我腦海中閃過……

但這次，相對輕鬆。有兩個候選，顯而易見的那個

    def g1(string):
        return map(ord, string)

以及不那麼明顯的那個

    import array
    def g2(string):
        return array.array('b', string).tolist()

對這些進行計時錶明 g2() 的速度大約是 g1() 的五倍。不過有一個問題：g2() 返回的整數範圍是 -128..127，而 g1() 返回的整數範圍是 0..255。如果你需要正整數，g1() 會比你對 g2() 結果進行任何後處理都要快。（注意：自本文撰寫以來，array 模組中添加了 'B' 型別程式碼，它儲存無符號位元組，因此不再有理由偏好 g1()。）

示例程式碼

• 計時 f1() 到 f7()
• 計時 g1() 和 g2()