2.1　Python中的數據結構

在任何編程語言中，數據結構都用于存儲和操作復雜的數據。在Python中，數據結構也是數據存儲容器，用于以有效方式對數據進行管理、組織和查找。它們用于存儲成組出現的數據元素，這些數據元素需要一起存儲和處理，每一組這樣的數據稱為一個集合。在Python中，有五種不同的數據結構可以用來存儲集合：

• 列表（list）：有序的可變元素序列。
• 元組（tuple）：有序的不可變元素序列。
• 集合（set）：無序元素序列（其中元素不重復）。
• 字典（dictionary）：無序的鍵值對序列。
• 數據幀（DataFrame）：存儲二維數據的二維結構。

下面我們在更詳細地介紹它們。

2.1.1　列表

在Python中，列表是用來存儲可變元素序列的主要數據結構。列表中存儲的數據元素序列不必是同一數據類型。

要創建一個列表，數據元素需要用[ ]括起來，并且需要用逗號隔開。例如，下面的代碼創建了一個含有四個數據元素的列表，其數據類型不完全相同：

在Python中，列表是一種創建一維可寫數據結構的便捷方法，在算法的不同內部階段都特別有用。

使用列表

數據結構關聯的實用功能非常有用，因為這些功能可以用來管理列表中的數據。

我們看看如何使用列表：

• 列表索引：由于元素在列表中的位置是確定的，因此可以使用索引來獲取某個特定位置的元素。下面的代碼演示了這個概念：

該代碼創建的四元素列表如圖2-1所示。

注意，索引從0開始，因此第二個元素Green由索引1即bin_color[1]檢索。

• 列表切片：通過指定索引范圍可以檢索列表中的元素子集，這個過程叫作切片。下面的代碼可以用來創建列表的一個切片：
• 

注意，列表是Python中非常流行的一維數據結構之一。

我們看看下面的代碼片段：

如果未指定起始索引，則意味著起始索引為列表的開始，如果未指定終止索引，則表示終止索引為列表的末尾，前面的代碼實際上已經演示了這個概念。

• 負索引：在Python中，也有負索引，負索引從列表的末尾開始計數。下面的代碼對此進行了演示：

注意，如果我們想將參考點設置為最后一個元素而不是第一個元素，負索引特別有用。

• 嵌套：列表的每個元素可以是簡單數據類型，也可以是復雜數據類型，這就允許在列表中進行嵌套。對于迭代和遞歸算法來說，這是非常重要的功能。

讓我們來看看下面的代碼，這是在一個列表中嵌套列表的例子：

• 迭代：Python允許使用for循環對列表中的每個元素進行迭代，這在下面的例子中進行了演示：

注意，前面的代碼會遍歷列表并打印每個元素。

lambda函數

在列表中可以使用大量的lambda函數。lambda函數在算法中特別重要，其提供了動態創建函數的能力。有時在文獻中，lambda函數也被稱為匿名函數。本小節將展示其用途：

• 過濾數據：為了過濾數據，需要先定義一個謂詞，說明需要完成什么工作，它是輸入一個參數并返回一個布爾值的函數。下面的代碼演示了它的使用方法：

在這段代碼中，我們使用了lambda函數來過濾一個列表，該函數指定了過濾標準。filter函數旨在依據定義的標準從序列中過濾掉不符合標準的元素。在Python中，filter函數通常與lambda函數一起使用。除了列表之外，它還可以用來從元組或集合中過濾元素。對于前面展示的代碼，定義的過濾標準是x>100，這段代碼將遍歷列表中的所有元素，并過濾掉不符合這個標準的元素。

• 數據轉換：map()函數可用于通過lambda函數進行數據轉換。示例如下：

將map函數和lambda函數一起使用可以提供相當強大的功能。當與map函數一起使用時，lambda函數可以用來聲明一個轉換器，對給定序列的每個元素進行轉換。在前面展示的代碼中，轉換器是取平方。因此，我們使用map函數對列表中的每個元素求平方。

• 數據聚合：對于數據聚合，可以使用reduce()函數，該函數會循環運行定義的函數，對列表中每對元素值進行處理：

注意，reduce函數需要定義一個數據聚合函數，前面代碼中的數據聚合函數是doSum，它定義了如何對給定列表中的各項元素進行聚合。聚合從最前面的兩個元素開始，然后用聚合結果替換這兩個元素。這樣，列表元素會減少，該過程不斷重復，直到最后得到一個聚合數字。doSum函數中的x1和x2分別代表了每輪迭代中的兩個數字，doSum則代表了它們聚合的標準。

前面代碼塊所得結果是一個單值（即270）。

range函數

range函數可以用來輕松地生成一個大的數字列表。它用作自動填充列表的數字序列。

range函數使用起來很簡單，使用時只需指定列表中想要的元素個數。在默認情況下，列表中的元素從0開始，并逐漸遞增1：

我們還可以指定結束的數字（不包含）和步長（兩個相鄰元素之間的差值）：

上面的range函數給出從3到29的奇數（不包括結束數字，也就是29）。

列表的時間復雜度

列表的時間復雜度可以使用大O記號來表示，整理如下：

注意，添加單個元素所需的時間與列表的規模無關，而表格中其他操作的復雜度則取決于列表的規模。列表的規模越大，性能受到的影響就越明顯。

2.1.2　元組

第二個可以用于存儲集合的數據結構是元組。與列表相反，元組是不可變的（只讀）數據結構。元組由一些被（ ）包圍的元素組成。

同列表一樣，元組中的元素可以是不同類型的，元組也允許其元素使用復雜數據類型。因此，元組中也可以包含其他元組，這就提供了一種創建嵌套數據結構的方法。創建嵌套數據結構的能力在迭代和遞歸算法中特別有用。

下面的代碼演示了如何創建元組：

注意，在前面的代碼中，a[2]指的是第三個元素，即一個元組(100,200,300)。a[2][1]指的是這個元組中的第二個元素，也就是200。

元組的時間復雜度

元組的Append函數的時間復雜度總結如下（使用大O記號）：

注意，Append函數是在一個已經存在的元組末尾添加一個元素，其復雜度為O(1)。

注意，元組是不可變的數據類型，其中沒有Append函數。這里所說的Append其實是創建了一個新的元組，具體見如下代碼：

可以看到，我們成功地將新元素添加到元組的末尾，但其實是創建了一個新的元組。

2.1.3　字典

以鍵值對的形式保存數據是非常重要的，尤其是在分布式算法中。在Python中，這些鍵值對的集合被存儲為一個稱為字典的數據結構。要創建一個字典，應該選擇一個在整個數據處理過程中最適合識別數據的屬性作為鍵。值可以是任何類型的元素，例如，數字或字符串。Python總是使用復雜的數據類型（如列表）作為值。如果用字典作為值的數據類型，則可以創建嵌套字典。

為了創建一個為各種變量分配顏色的簡單字典，需要將鍵值對用{ }括起來。例如，下面的代碼創建了一個由三個鍵值對組成的簡單字典：

前面一段代碼所創建的三個鍵值對也在圖2-2中進行了說明。

現在，我們看看如何檢索和更新與鍵相關聯的值：

1. 要檢索一個與鍵相關聯的值，可以使用get函數，也可以使用鍵作為索引：

2. 要更新與鍵相關聯的值，可以使用以下代碼：

請注意，前面的代碼演示了如何更新一個與字典中的某個特定鍵相關的值。

字典的時間復雜度

下表給出了使用大O記號表示的字典的時間復雜度：

從字典的復雜度分析中可以發現一個需要注意的重要現象，那就是獲取或設置鍵值所需的時間與字典的大小完全無關。這意味著，將一個鍵值對添加到一個大小為3的字典中所花費的時間與將一個鍵值對添加到一個大小為100萬的字典中所花費的時間是一樣的。

2.1.4　集合

集合被定義為元素集，可以是不同類型的元素，這些元素都被{ }括起來。例如，請看下面的代碼塊：

集合定義的特性是，它只存儲每個元素的不同值。如果我們試圖添加另一個具有重復值的元素，它會忽略重復值，如下面的代碼所示：

為了演示在集合上可以進行什么樣的操作，我們來定義兩個集合：

• 一個名為yellow的集合，里面包含了黃色的東西。
• 另一個名為red的集合，里面包含了紅色的東西。

請注意，這兩個集合之間有公共部分。這兩個集合及其關系可以借助圖2-3進行展示。

如果想在Python中實現這兩個集合，代碼將是這樣的：

現在，考慮以下代碼，它演示了如何使用Python進行集合操作：

如前面的代碼片段所示，Python中的集合可以有并和交等運算。我們知道，并運算將兩個集合的所有元素合并到一起，而交運算則給出兩個集合之間的公共元素集合。需要注意以下兩點：

• yellow|red用于獲得前面定義的兩個集合（yellow和red）的并。
• yellow&red用于獲得前面定義的兩個集合（yellow和red）的交。

集合的時間復雜度

以下是集合的時間復雜度分析：

從集合的復雜度分析中可以發現一個需要注意的重要現象，那就是添加一個元素所需的時間與該集合的大小完全無關。

2.1.5　數據幀

數據幀是Python的pandas包中的一種數據結構，用來存儲可用的表格數據。它是算法中重要的數據結構之一，用于處理傳統的結構化數據。我們看看以下表格：

現在，我們使用數據幀來表示它。

可以使用以下代碼創建一個簡單的數據幀：

請注意，在上面的代碼中，df.column是一個用來指定各列名稱的列表。

數據幀術語

我們來看看在數據幀中使用的一些術語：

• 軸（axis）：在pandas的文檔中，一個數據幀的單列或單行稱為軸。
• 軸族（axes）：如果軸的數量大于1，則它們作為一組，稱為軸族。
• 標簽（label）：數據幀允許用標簽來命名列和行。

創建數據幀的子集

從根本上說，創建數據幀子集的方法主要有兩種（比如說子集的名字是myDF）：

• 選擇列
• 選擇行

選擇列

在機器學習算法中，選擇合適的特征集是一項重要任務。算法在特定階段時可能不需要全部特征。在Python中，特征選擇是通過選擇列來實現的，下面對選擇列進行說明。

可以按列的名稱來檢索各列，如下所示：

在數據幀中，列的位置是確定的，可以通過指定列的位置取出各列，具體如下：

請注意，在這段代碼中，我們正在檢索DataFrame的前三行（一共有三行數據）。

選擇行

數據幀中的每一行都對應著問題空間中的一個數據點。如果我們想要創建問題空間中數據元素的子集，則需要執行選擇行操作。這個子集可以通過使用以下兩種方法之一來創建：

• 指定各行的位置
• 指定一個過濾器

通過位置來檢索各行的子集，具體操作如下：

注意，上面的代碼將返回前兩行以及所有列。

如果要通過指定過濾器來創建子集，需要使用一個或多個列來定義選擇標準。例如，可以通過如下的方法選擇數據元素的子集：

請注意，這段代碼創建了由所有滿足過濾器中規定條件的行所組成的子集。

2.1.6　矩陣

矩陣是一種具有固定列數和行數的二維數據結構，矩陣中的每個元素都可以通過指定它的列和行來引用。

在Python中，可以通過使用numpy中的array函數來創建矩陣，如下面的代碼所示：

上面的代碼創建了一個三行三列的矩陣。

矩陣運算

有很多運算可以用于矩陣數據。例如，我們嘗試對前面創建的矩陣進行轉置，可以使用transpose()函數，將列轉換成行、行轉換成列：

需要注意的是，在多媒體數據處理中經常使用矩陣運算。

前面已經學習了Python中的數據結構，我們下面學習抽象數據類型。