在 Python 開發中，當需要建立大量物件時，記憶體管理就顯得尤為重要。預設情況下，Python 物件會帶有一個 __dict__ 屬性用於儲存物件的屬性，這會增加記憶體開銷。__slots__ 屬性提供了一種最佳化記憶體使用的方式，它允許我們明確指定物件的屬性，避免建立 __dict__，從而減少記憶體佔用。尤其在處理大量物件例項時，例如遊戲開發、科學計算等場景，使用 __slots__ 能夠顯著提升效能。然而，__slots__ 也有一些限制，例如無法動態新增屬性，需要在設計階段就確定物件的屬性結構。

問題描述

在模擬計算中，我們可能需要建立數以萬計的物件，每個物件都佔用一定的記憶體空間。例如，在粒子模擬中，每個粒子都有一個位置和速度。如果我們使用傳統的物件定義方式，則每個物件都會有一個預設的 __dict__ 屬性，這會導致記憶體佔用增加。

使用 __slots__ 來最佳化記憶體使用

Python 中的 __slots__ 屬性可以用來定義物件的屬性列表。透過使用 __slots__，我們可以避免建立預設的 __dict__ 屬性，從而減少記憶體佔用。

以下是使用 __slots__ 最佳化記憶體使用的例子：

class Particle:
    __slots__ = ('x', 'y', 'ang_vel')

    def __init__(self, x, y, ang_vel):
        self.x = x
        self.y = y
        self.ang_vel = ang_vel

在這個例子中，Particle 類別使用 __slots__ 來定義其屬性列表。這樣，Python 就不會為每個 Particle 物件建立預設的 __dict__ 屬性，從而減少記憶體佔用。

測試結果

使用 memory_profiler 工具來測試記憶體佔用情況，結果如下：

Increment  |  MiB
---------|------
100000    | 13.7

與未最佳化的版本相比，使用 __slots__ 最佳化記憶體使用後，記憶體佔用減少了約 10 MiB。

最佳化技術概述

在本章中，我們探討了最佳化的基本原理，並將這些原理應用於一個測試應用。最佳化應用時，首先需要測試和找出應用的瓶頸。我們學習瞭如何使用 Unix 命令 time、Python 的 timeit 模組和 pytest-benchmark 套件來撰寫和測試基準。同時，我們也學習瞭如何使用 cProfile、line_profiler 和 memory_profiler 來分析應用的效能，並使用 KCachegrind 來圖形化分析效能資料。

關鍵問題

1. 當建構軟體應用時，以下三項哪一項最重要：正確性（程式做它應該做的事）、效率（程式在速度和記憶體管理上進行最佳化）和功能性（程式執行）？
2. 如何使用 Python 的 assert 陳述式來檢查程式的正確性？
3. 在最佳化軟體程式的背景下，什麼是基準？
4. 如何使用 Python 的 timeit 魔術命令來估計程式碼的速度？
5. 在最佳化程式的背景下，cProfile 傳回的輸出欄位有哪三種不同型別的資訊？
6. 在最佳化中，dis 模組的角色是什麼？
7. 在 exercise.py 檔案中，我們撰寫了一個簡單的函式 close()，它檢查兩個粒子是否彼此接近（具有 1e-5 的容差）。在 benchmark() 中，我們隨機初始化兩個粒子，並在執行模擬後呼叫 close()。猜測 close() 中哪部分佔用了最多的執行時間，並使用 cProfile 來分析 benchmark() 中的函式；結果是否確認您的猜測？

進一步閱讀

• 一個對 Python 中 bytecode 的初學者友好的介紹：https://
• profiler.html

基準測試和最佳化

基準測試是評估程式碼效能的重要工具。透過基準測試，我們可以找出程式碼中哪些部分需要最佳化。最佳化程式碼可以使用各種技術，包括改善演算法、減少迴圈次數和使用更有效的資料結構。

Python 中的最佳化工具

Python 提供了多種最佳化工具，包括 cProfile、line_profiler 和 memory_profiler。這些工具可以幫助我們找出程式碼中哪些部分需要最佳化，並提供有關程式碼效能的詳細資訊。

大 O 標記法

大 O 標記法是一種用於分析演算法和資料結構的時間複雜度的工具。它可以幫助我們瞭解程式碼的效能如何隨著輸入大小的增加而變化。

快取和記憶化

快取和記憶化是兩種用於改善程式碼效能的技術。快取涉及儲存常用的資料，以便快速存取。記憶化涉及儲存函式的結果，以便避免重複計算。

資料結構

資料結構是組織和儲存資料的方式。選擇合適的資料結構可以大大改善程式碼的效能。Python 提供了多種內建的資料結構，包括列表、字典和集合。

最佳化技術

在前一章中，我們提到改善應用程式的效能最有效的方法之一，就是使用更好的演算法和資料結構。Python 的標準函式庫提供了大量可直接整合到應用程式中的現成演算法和資料結構。透過本章節學習到的工具，您將能夠選擇適合任務的正確演算法，從而取得巨大的速度提升。

即使許多演算法已經存在一段時間，它們在今天的世界中仍然尤為重要，因為我們不斷地生產、消費和分析越來越多的資料。購買更大的伺服器或進行微最佳化可能在某段時間內有效，但透過演算法改善來達到更好的擴充套件性，可以徹底解決問題。

在本章中，我們將學習如何使用標準演算法和資料結構來達到更好的擴充套件性。同時，也會涵蓋使用第三方函式庫的更高階使用案例，並學習如何實作快取，一種用於透過快取機制來實作更快回應時間的技術。

主題列表

本章節將涵蓋以下主題：

• 使用正確的演算法和資料結構
• 使用快取和記憶化來提高效率
• 使用列表推導和生成器來進行高效的迭代

技術要求

相關程式碼和資源可以在 PacktPublishing/Advanced-Python-Programming-Second-Edition/ tree/main/Chapter02 中找到。

使用正確的演算法和資料結構

演算法改善尤其能夠有效地提高應用程式的效能，因為它們通常允許應用程式更好地擴充套件以適應越來越大的輸入。 演算法的執行時間可以根據其計算複雜度進行分類，計算複雜度是描述執行任務所需的資源的特徵。 這種分類使用大O符號表示，描述了執行任務所需的操作的上限，大O符號通常取決於輸入大小。具體而言，大O符號描述了演算法的執行時間或記憶體需求如何隨著輸入大小的增加而增加。因此，較低的大O符號表示更高效的演算法，這也是我們的目標。

例如，對列表中的每個元素進行遞增可以使用for迴圈實作，如下所示：

輸入 = list(range(10))
for i, _ in enumerate(輸入):
    輸入[i] += 1

如果操作不依賴於輸入大小（例如，存取列表的第一個元素），則該演算法被認為需要常數時間，或者說是O(1)時間。這意味著無論我們有多少資料，執行演算法所需的時間始終相同。

列表和雙端佇列

Python 列表是有序的元素集合，並且在 Python 中實作為可調整大小的陣列。陣列是一種基本的資料結構，由一系列連續的記憶體位置組成，每個位置包含一個 Python 物件的參照。 列表在存取、修改和附加元素方面表現出色。存取或修改元素涉及從底層陣列的適當位置提取物件參照，並具有 O(1) 的複雜度。附加元素也非常快速。當一個空列表被建立時，會分配一個固定大小的陣列，並且當我們插入元素時，陣列中的插槽會逐漸被填滿。一旦所有插槽都被佔據，列表需要增加其底層陣列的大小，從而觸發一個可能需要 O(N) 時間的記憶體重新分配。然而，這些記憶體分配是很少見的，因此對於附加操作的時間複雜度被稱為摻合 O(1) 時間。

列表的操作中可能存在效率問題的是那些在列表的開頭（或中間）新增或刪除元素的操作。當專案被插入或從列表的開頭刪除時，陣列中的所有後續元素都需要被移位，因此需要 O(N) 的時間。

以下表格顯示了在大小為 10,000 的列表上進行不同操作的時間： 表 1.1 – 列表操作的速度

在某些情況下，需要在集合的開頭和結尾高效地執行插入或刪除元素的操作。Python 的 collections.deque 類提供了一個具有這些屬性的資料結構。deque 這個詞是「雙端佇列」的簡稱，因為這種資料結構的設計目的是在集合的開頭和結尾高效地新增和刪除元素，就像佇列一樣。在 Python 中，雙端佇列是作為雙向連結串列實作的。

雙端佇列除了 pop 和 append 之外，還暴露了 popleft 和 appendleft 方法，它們的執行時間為 O(1)： 表 1.2 – 雙端佇列操作的速度

儘管具有這些優點，雙端佇列不應該用於替代大多數情況下的常規列表。因為在雙端佇列中存取中間元素是一個 O(N) 的操作，如下表所示： 表 1.3 – 雙端佇列存取中間元素的低效率

在列表中搜尋專案是一個通常需要 O(N) 的操作，使用 list.index 方法實作。加速列表搜尋的一種簡單方法是保持陣列有序，並使用 bisect 模組進行二分搜尋。

bisect 模組允許在排序陣列上進行快速搜尋。bisect.bisect 函式可以用於排序列表上找到插入元素的索引，以保持陣列有序。以下示例展示瞭如果我們想要在排序列表中找到元素的索引以保持排序，可以使用 bisect 模組：

from bisect import bisect
排序列表 = [1, 3, 5, 7, 9]
索引 = bisect(排序列表, 6)
print(索引)  # 輸出：3

您可以在 Algorithms.ipynb 筆記本中找到本章節中使用的程式碼，該筆記本可以使用 Jupyter 開啟。首先，我們將研究列表和雙端佇列。

在排序陣列中插入元素

當我們想要在排序陣列中插入一個元素時，需要確保插入後的陣列仍然保持排序。Python 的 bisect 模組提供了一個高效的方法來實作這一點。

使用 bisect.bisect 函式

bisect.bisect 函式使用二分查詢演算法來找到插入元素的正確位置。這個演算法的時間複雜度為 O(log N)，使得它非常快速。

import bisect

collection = [1, 2, 4, 5, 6]
index = bisect.bisect(collection, 3)
print(index)  # Output: 2

在這個例子中，bisect.bisect 函式傳回了 2，這是插入 3 的正確位置，以保持陣列的排序。

bisect.bisect 的時間複雜度

bisect.bisect 函式的時間複雜度為 O(log N)，這意味著它的執行時間隨著輸入大小的增加而增加得很慢。如果一個程式在輸入大小為 1000 時需要 1 秒，則在輸入大小為 2000 時需要 2 秒，在輸入大小為 4000 時需要 3 秒，依此類推。

處理已存在的元素

如果要插入的元素已經存在於陣列中，bisect.bisect 函式會傳回已存在元素的後面位置。為了避免這種情況，可以使用 bisect.bisect_left 函式，它會傳回已存在元素的前面位置。

import bisect

def index_bisect(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return None

collection = [1, 2, 3, 4, 5]
index = index_bisect(collection, 3)
print(index)  # Output: 2

在這個例子中，index_bisect 函式會傳回已存在元素 3 的前面位置。

圖表翻譯：

  graph LR
    A[插入元素] --> B[二分查詢]
    B --> C[找到正確位置]
    C --> D[插入元素]
    D --> E[保持陣列排序]

這個圖表顯示了插入元素的過程，從插入元素到找到正確位置，然後插入元素，最後保持陣列的排序。

高效率的Python最佳化技術

在Python中，最佳化技術是提高程式效率的關鍵。以下將介紹幾種高效率的Python最佳化技術。

使用bisect模組

bisect模組是Python中的一個內建模組，提供了二分查詢的功能。二分查詢是一種高效率的查詢演算法，尤其是在大型集合中。以下是使用bisect模組的範例：

import bisect

def bisect_example():
    # 建立一個排序好的列表
    sorted_list = [1, 3, 5, 7, 9]
    
    # 使用bisect查詢元素
    index = bisect.bisect_left(sorted_list, 5)
    
    return index

print(bisect_example())  # Output: 2

使用字典

字典是Python中的一種資料結構，提供了高效率的查詢、插入和刪除功能。字典是根據雜湊表的實作，平均時間複雜度為O(1)。

def dictionary_example():
    # 建立一個字典
    dictionary = {"apple": 1, "banana": 2, "cherry": 3}
    
    # 查詢元素
    value = dictionary["apple"]
    
    return value

print(dictionary_example())  # Output: 1

使用雜湊函式

雜湊函式是將輸入資料對映到一個固定大小的輸出資料的函式。Python提供了內建的雜湊函式，例如hash()。

def hash_example():
    # 使用雜湊函式
    hash_code = hash("hello")
    
    return hash_code

print(hash_example())  # Output: -1182655621190490452

處理碰撞

雜湊表可能會發生碰撞，即兩個不同的輸入資料對映到相同的輸出資料。Python的內建雜湊函式已經處理了碰撞問題，因此不需要手動處理。

使用字典計數元素

字典可以用來高效率地計數元素。以下是使用字典計數元素的範例：

def count_elements():
    # 建立一個列表
    list = [1, 2, 2, 3, 3, 3]
    
    # 建立一個字典
    dictionary = {}
    
    # 計數元素
    for element in list:
        if element in dictionary:
            dictionary[element] += 1
        else:
            dictionary[element] = 1
    
    return dictionary

print(count_elements())  # Output: {1: 1, 2: 2, 3: 3}

檔案搜尋引擎的基本原理

在這個例子中，我們將探討如何使用Python建立一個簡單的檔案搜尋引擎。這個搜尋引擎的基本原理是建立一個反向索引（inverted index），它是一種特殊的資料結構，允許我們快速地查詢包含特定單詞的檔案。

建立反向索引

首先，我們需要建立一個反向索引。這個索引是一個字典，鍵是單詞，值是包含這個單詞的檔案列表。以下是建立反向索引的Python程式碼：

from collections import defaultdict

def build_inverted_index(docs):
    index = defaultdict(list)
    for doc_id, doc in enumerate(docs):
        for word in doc.split():
            index[word].append(doc_id)
    return index

docs = [
    "the cat is under the table",
    "the dog is under the table",
    "cats and dogs smell roses",
    "Carla eats an apple"
]

index = build_inverted_index(docs)
print(index)

這個程式碼建立了一個反向索引，索引中每個單詞都對應著包含這個單詞的檔案列表。

查詢檔案

現在，我們可以使用這個反向索引來查詢包含特定單詞的檔案。以下是查詢檔案的Python程式碼：

def search_docs(index, query):
    return [docs[doc_id] for doc_id in index.get(query, [])]

query = "table"
results = search_docs(index, query)
print(results)

這個程式碼查詢包含單詞"table"的檔案，並傳回包含這個單詞的檔案列表。

最佳化搜尋引擎

我們可以使用Counter類別來最佳化搜尋引擎。以下是最佳化搜尋引擎的Python程式碼：

from collections import Counter

def build_inverted_index(docs):
    index = Counter()
    for doc_id, doc in enumerate(docs):
        for word in doc.split():
            index[word] += 1
    return index

def search_docs(index, query):
    return [docs[doc_id] for doc_id, doc in enumerate(docs) if query in doc]

docs = [
    "the cat is under the table",
    "the dog is under the table",
    "cats and dogs smell roses",
    "Carla eats an apple"
]

index = build_inverted_index(docs)
query = "table"
results = search_docs(index, query)
print(results)

這個程式碼使用Counter類別來建立反向索引，並使用列表推導式來查詢包含特定單詞的檔案。

圖表翻譯：

  graph LR
    A[檔案集合] -->|建立反向索引|> B[反向索引]
    B -->|查詢檔案|> C[包含單詞的檔案列表]
    C -->|傳回結果|> D[搜尋結果]

這個圖表展示了搜尋引擎的基本原理，從建立反向索引到查詢包含特定單詞的檔案。

最佳化查詢效率：倒排索引的力量

當我們需要頻繁查詢檔案集合時，使用線性掃描的方法可能會導致效率低下。為了改善查詢效率，我們可以使用倒排索引（inverted index）這種資料結構。倒排索引是一種將每個詞彙對映到包含該詞彙的檔案列表的資料結構。

建立倒排索引

建立倒排索引的過程涉及遍歷檔案集合，並為每個詞彙建立一個列表，該列表包含包含該詞彙的檔案索引。以下是建立倒排索引的示例程式碼：

index = {}
for i, doc in enumerate(docs):
    for word in doc.split():
        if word not in index:
            index[word] = [i]
        else:
            index[word].append(i)

查詢檔案

一旦我們建立了倒排索引，查詢檔案就變得非常簡單。例如，如果我們想要查詢包含「table」詞彙的檔案，我們可以直接查詢倒排索引並取得相應的檔案：

results = index["table"]
result_documents = [docs[i] for i in results]

倒排索引的優點

使用倒排索引可以將查詢時間複雜度從 O(N) 降低到 O(1)，使得查詢效率大大提高。這種技術不僅在搜尋引擎中被廣泛使用，也在資料函式庫和其他需要快速查詢的系統中被採用。

圖表翻譯：

  flowchart TD
    A[建立倒排索引] --> B[查詢檔案]
    B --> C[取得結果]
    C --> D[傳回結果]

內容解密：

上述程式碼和圖表展示瞭如何建立倒排索引和查詢檔案的過程。透過建立倒排索引，我們可以快速查詢包含特定詞彙的檔案，從而提高查詢效率。這種技術在搜尋引擎和資料函式庫中被廣泛使用。

從效能最佳化視角來看，Python 的 __slots__ 提供了一個有效的機制來降低物件的記憶體佔用，尤其在處理大量物件例項時效果顯著。分析顯示，透過避免為每個物件建立 __dict__ 屬性，__slots__ 能有效減少記憶體消耗，在實務應用中，例如粒子模擬等需要大量物件的場景，能有效提升系統效能。然而，__slots__ 也存在一些限制，例如限制了動態新增屬性，需要在設計階段就明確物件的屬性結構。對於需要高度動態性的應用程式，則需權衡使用 __slots__ 的利弊。展望未來，隨著 Python 持續發展，預期會有更多針對記憶體管理的最佳化策略出現，而 __slots__ 作為一種輕量級的最佳化手段，仍將在特定應用場景中扮演重要角色。對於追求極致效能的開發者而言，深入理解 __slots__ 的原理和應用，將有助於打造更精簡高效的 Python 程式。玄貓認為，在大量物件的應用場景中，__slots__ 值得被優先考慮，以有效控制記憶體消耗，提升系統整體效能。