Colab（四）：Data Structure

 Colab（四）：Data Structure

2021/03/10

-----

https://pixabay.com/zh/photos/stones-wall-quarry-stone-texture-770264/

-----

一、為什麼要學資料結構。

-----

「演算法 + 資料結構 = 程式」[1] 是 Pascal 的發明人 Niklaus Wirth 的名言，以及名著 [2]。這句話可以進一步推廣，「基因演算法 + 資料結構 = 遺傳程式」 [3]。演算法影響解決問題的大方向，資料結構決定了實作這個程式的難易度 [4]。所以，不管你是不是要用 Python 學習演算法與資料結構，你既然決定了用 Python 寫程式，自然要知道 Python 上面有什麼資料結構可以使用 [5], [6]。

-----

二、Built-in Data Structures。

-----

Python 內建的四種資料結構是 list、tuple [7] 與 set、dict [8]。dict 可以多練習一下 [9]。

◎ List

可以用 help(list) 看看總共有有哪些 method。

List 有許多函式可以處理，比剛剛的實作 [7] 細緻一點 [10]。程式碼要稍微品味一下。List 可以用中括號建立（my_list = [] #create empty list）。內容可以是整數、實數、邏輯值，或字串（my_list = [1, 2, 3, 'example', 3.132] #creating list with data）。

建立資料後，可以再新增資料（使用 append()、extend()、insert()）。append() 用於新增單一筆資料（my_list.append([555, 12]) #add as a single element）。extend() 用於新增多筆資料（my_list.append([555, 12]) #add as a single element）。insert() 用於在某個位置插入一筆資料（my_list.insert(1, 'insert_example') #add element i）。以上三個函式，都是附屬於 list 的 method，而非內建函式。

刪除資料可以用 del 這個保留字，也可以用 remove、pop、clear 這三個 list 內建的 method。

◎ Dictionary

dict 用大括號建立（my_dict = {'First':'Python','Second':'Java'}）。一樣，可以用 help(dict) 看一下有哪些運算或動作可以使用。

◎ Tuple

tuple 使用小括號。tuple 跟 list 很像，但是 list 裡面的值可以修改，tuple 裡面的值不能修改。但是 tuple 的元素還是可以新增（my_tuple = my_tuple + (4, 5, 6) #add elements）。總之，如果元素不打算修改，可以使用 tuple，效能較佳。tuple  也可以是巢狀（多維的）。

◎ Sets

set 跟 dict 有點像，也是使用大括號建立。一樣都不能有重複的元素，也可以說重複的元素無效。其中一個重點是，dict 的元素是 key-value，用冒號連結 key 跟 value。set，既然是 set，自然可以進行 set 的運算，如交集、聯集、相減等等。運算可以用函式，或者用比較簡潔的符號。

-----

三、User-Defined Data Structures

-----

◎ Arrays vs. List

由於 array 不是 Python 內建的資料結構，而是使用者自訂。有兩個方法可以使用 array，用 import as 或者 from import。

第一種方法：

import array as arr

第二種方法：

from array import *

使用第二種方法之後，就可以用 help(array) 檢查有哪些 method 可以使用了。array 跟 list 最大的差別，是 array 裡面的元素，型別都相同。

◎ Stack

◎ Queue

Stack 堆疊是 FILO 先進後出。Queue 列隊是 FIFO 先進先出。Stack 跟 Queue（>>> from collections import deque）可以使用 list 實現 [11]。

◎ Trees

◎ Linked Lists

◎ Graphs

◎ HashMaps

其他資料結構請自行參考 [10]。

-----

◎ 實作練習

-----

一、6 資料容器一 [7]。

二、8 資料容器二 [8]。

三、字典. Dictionary，另一個存資料的好方法 [9]。

四、Data Structures in Python | List, Tuple, Dict, Sets, Stack, Queue | Edureka [10]。

五、Data Structures — Python 3.9.2 documentation [11]。

-----

誤：

starrings = {

    "Rachel Green": "Jennifer Aniston",

    "Monica Geller": "Courteney Cox",

    "Phoebe Buffay": "Lisa Kudrow",

    "Joey Tribbiani": "Matt LeBlanc",

    "Chandler Bing": "Matthew Perry",

    "Ross Geller": "David Schwimmer"

}

for starring in starrings:

    print starring

正：

starrings = {

    "Rachel Green": "Jennifer Aniston",

    "Monica Geller": "Courteney Cox",

    "Phoebe Buffay": "Lisa Kudrow",

    "Joey Tribbiani": "Matt LeBlanc",

    "Chandler Bing": "Matthew Perry",

    "Ross Geller": "David Schwimmer"

}

for starring in starrings:

    print(starring)

-----

誤：

starrings = {

    "Rachel Green": "Jennifer Aniston",

    "Monica Geller": "Courteney Cox",

    "Phoebe Buffay": "Lisa Kudrow",

    "Joey Tribbiani": "Matt LeBlanc",

    "Chandler Bing": "Matthew Perry",

    "Ross Geller": "David Schwimmer"

}

for starring in starrings.keys():

    print starring

正：

starrings = {

    "Rachel Green": "Jennifer Aniston",

    "Monica Geller": "Courteney Cox",

    "Phoebe Buffay": "Lisa Kudrow",

    "Joey Tribbiani": "Matt LeBlanc",

    "Chandler Bing": "Matthew Perry",

    "Ross Geller": "David Schwimmer"

}

for starring in starrings.keys():

    print(starring)

-----

誤：

for starring in starrings.values():

    print starring

正：

for starring in starrings.values():

    print(starring)

-----

誤：

my_squares = {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

for i in my_squares:

print(“Key is”, i, “Value is”, my_squares[i])

正：

my_squares = {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

for i in my_squares:

    print("Key is", i, "Value is", my_squares[i])

-----

References

[1] Algorithms & data structures

Wirth, Niklaus. Algorithms & data structures. Prentice-Hall, Inc., 1985.

[2] TWIDEEM CIVS

https://twideem.github.io/pages/overcast/20140306A.html

[3] Genetic algorithms + data structures= evolution programs

Michalewicz, Zbigniew. Genetic algorithms + data structures= evolution programs. Springer Science & Business Media, 2013.

[4] 演算法＋資料結構＝程式 | iThome

https://www.ithome.com.tw/voice/142263

[5] 技術雜談：為什麼要 (或不要) 用 Python 實作資料結構和演算法 | Michael Chen 的技術文件

https://michaelchen.tech/blog/why-or-why-not-using-python-for-algorithms/

[6] 輕鬆學習 Python：資料結構. 利用資料結構儲存多筆資料 | by Yao-Jen Kuo | 數據交點 | Medium

https://medium.com/datainpoint/python-essentials-data-structures-4ba25f2deaf5

-----

[7] 6 資料容器一

https://bookdown.org/tonykuoyj/hello-py/containers-1.html

[8] 8 資料容器二

https://bookdown.org/tonykuoyj/hello-py/containers-2.html

[9] Python 初學第九講 — 字典. Dictionary，另一個存資料的好方法 | by 陳子晴 | ccClub | Medium

https://medium.com/ccclub/ccclub-python-for-beginners-tutorial-533b8d8d96f3

[10] Data Structures in Python | List, Tuple, Dict, Sets, Stack, Queue | Edureka

https://www.edureka.co/blog/data-structures-in-python/

-----

補充：

[11] 5. Data Structures — Python 3.9.2 documentation

https://docs.python.org/3/tutorial/datastructures.html

-----

從 Colab 到 Kaggle（目錄）

https://hemingwang.blogspot.com/2021/03/colab_12.html

-----