Sequence

必須足以下條件：

• 物件的集合
• countable
• zero based indexing (__getitem__)
• 為什麼 index 要從0開始？
  • 0 based: 0 <= n < len(s)
  • 1 based: 1 <= n < len(s) + 1 Upper bound 用小於的原因是計算長度時不須再+1
• 有序(positional ordering)
  • 舉例來說 list 和 set 都是物件的容器，但 list 可以被排序， set 不行，因此 list 是 Sequence Type 而 set 不是

特性：

• Homogeneous vs Heterogeneous 同質即序列的物件型態必須是相同的
• Iterable vs non iterable 可以迭代的容器不一定是序列，如set
• Mutable vs Immutable Mutable sequence can be modified. 要注意的是在操作新序列的時候更動到原本的序列(in-place)，如 reverse()

以 list 為例，這幾個操作皆為原地算法（inplace）：

• l.clear()
• l.append()
• l.pop()
• l.extend()
• l.insert()
• l +=
• l *=
• l[somesliceobj] = 若是 concat(+)、repetition(*)、slicing 都是關聯至新的物件參考

要注意的是，容器序列（儲存物件參考）的 concat 和 repetition 有可能只是儲存多個相同物件的參考

Standard Method

• x in s, x not in s
  • 定義自 __containes__
• concat: s1 + s2
  • Type 須相同，回傳新的物件
  • 定義自 __add__
• inplace contat: s1 += s2
  • mutate 原物件若 sequence是 mutable
  • Type 不須相同，回傳 s1
  • 定義自 __iadd__
• repetition: s * n
  • Type 須相同，回傳新的物件
  • 定義自 __mul__, __rmul__
• inplace repetition: s *= n
  • mutate 原物件若 sequence 是 mutable
  • Type 不須相同，回傳 s1
  • 定義自 __imul__
• len(s)
  • 無限序列不適用
• min(s), max(s) with order comparision methods
• s.index(x)
• s[i]
  • 不是所有序列都支援 item assignment
• slicing: s[start:end]
  • 總是回傳新的物件

註：range不具concat及repetition

list vs tuple

Contsant folding

Constant folding is the process of recognizing and evaluating constant expressions at compile time rather than computing them at runtime.

Shallow copy

Deep copy

不管包了幾層，只要 sqeunce 中有 mutable object ，就要特別注意。 Cutom object 可以透過__copy__及__deepcopy__來定義 copy 行為。 Python 的 standard libary 的 copy 模組提供 deepcopy，用 Recursion 複製時會確保新的物件保持相同的關聯

Construct and Storage efficiency

Slicing

• slice 基於 indexing ，所以只適用於 Sequence Type
• slice 是特定物件

使用 Slicing 來 Assignment 不會改變記憶體關聯（inplace）

Custom Sequence Type

Sorting

built-in sorted

• 針對該可迭代物件的 copy 來操作
• 總是回傳 list
• 使用演算法 TimSort

當我們沒有提供 key method，可以視為以物件本身來排序

sorted(iterable) -> sorted(iterable, key=lambda x: x)

註：

• complex type 不能排序，可用其絕對值 key=abs 或虛數 key=lambda c: c.imag 來排

Inplace 與非 Inplace 的排序效率

List comprehension

• python 編譯到 list comprehension 代碼
• 解析 syntax 來建立 function (函式有 local scope 可訪問 global scope)
• 執行該 function 並回傳特定 sequence type