Sitemap

Python — Sequence

4 min readNov 15, 2022

--

學習Sequence的過程中,感覺一直是很發散的,東一塊西一塊的學習,所以這篇盡可能地把相關知識串聯在一起做比較,並且應用。

文章簡介

  • Sequence背景介紹
  • Sequence Slicing
  • Python Sequence Protocol(Mutable、Immutable、Inplace Operation)
  • Custom Sequence實作 — Polygon Sequence

Sequence背景介紹

Python Sequence type資料的定義: we can refer any element in the sequence by using its index number

根據這個定義,可以簡單地用例子來看list是Sequence type而set不是

list_a = [1,2,3,4]
print(list_a[0]) #1
print(list_a[2]) #3

set_a = {1,2,3,4}
print(set_a[0]) #'set' object is not subsciptable

Mutable & Immutable Sequence

  • Mutable: list
  • Immutable: str, tuple, range, bytes

Python Sequence Slicing

一開始說到Sequence最方便的特性就是可以直接使用index去取出我們想要的資料,而slicing可以使我們去access一個範圍的片段資料,而不只是單一一個element:

list_a = [1,2,3,4]
print(list_a[1:]) #[2,3,4]

Slice本身也是一個Python物件,constructor是:

slice(start, stop, step)

  • stop index would not be included
list_a = [1,2,3,4,5,6,7,8,9,10]
slice_obj = slice(0,10,2)
print(type(slice_obj)) #slice
print(list_a[slice_obj]) #[1,3,5,7,9]

Slicing replacement — for mutable Sequence

使用slicing來重新賦值,針對Sequence做範圍的elements做修改:

list_a = [1,2,3,4,5]
list_a[1:3] = (7,7,7) #1,2
print(list_a) #[1,7,7,7,4,5]

Slicing insertion — for mutable Sequence

在原有Sequence中插入新的element:

list_a = [1,2,3,4,5]
print(list_a[1:1]) #這裡的空間要為empty
list_a[1:1] = (8,8)
print(list_a) #[1,8, 8, 2, 3, 4, 5]

這裡要注意,如果是insertion的話,slicing的範圍要為空,不然就會變成範圍的replacement。

#說到插入新物件,可能會想到.insert(),不同之處在於若要insertion的物件為另一個Sequence的話,則slicing insertion會自動unpack被insert的element,並且以單一element插入,而.insert()則不會:

#Slicing insertion
list_a = [1,2,3,4,5]
list_a[1:1] = ('a','b','c') #Sequence
print(list_a) #[1,'a', 'b', 'c', 2, 3, 4, 5]

#.insert()
list_a = [1,2,3,4,5]
list_a.insert(1,('a','b','c'))
print(list_a) #[1,('a', 'b', 'c'), 2, 3, 4, 5]

Slicing deletion — for mutable Sequence

刪除element,其實就是把範圍裏面的值指派為空值就好:

#Deleting element using assignment
list_a = [1,2,3,4,5]
list_a[1:3] = []
print(list_a) #displayed [1,4,5]

以上大部分的Sequence slicing運用都是用同概念去做變化。

Python Sequence Protocol

透過Sequence Protocol,可以去理解Python中的Sequence是怎麼去implement、那些在檯面下的運作,最終幫助我們去寫自己的custom Sequence type。

Immutable Sequence

先寫相對單純的Immutable Sequence,只需要支援讀取的部分,我們宣告後無法對這類型的Sequence物件再做修改,例如built-in的string、tuple等等物件型態,要完成這類型的Sequence會需要implement以下幾個method:

  • .__getitem__:用index去對應element、若超出Sequence則raise IndexError
  • .__len__(): 回傳Sequence的長度

創建一個tuple來確認一下built-in method:

tuple_a = (1,2,3,4,5)
print(tuple_a.__len__()) #5
print(tuple_a.__getitem__(4)) #5

理解我們需要Implement的method以及想要各自達到的目的後,就可以來寫自己的Sequence了:目標是寫一個Immutable Sequence內含不同index下的費波那契值:


class Fib:
def __init__(self, value):
self.value = value #Define the length of the Sequence
def __len__(self):
return self.value
def __getitem__(self, index):
if isinstance(index, int):
if index < 0:
index = self.value + index #Handle [-1] index slicing
if index < 0 or index >= self.value:
raise IndexError
else:
return fib(index) #Call fib function
elif isinstance(index, slice):
range_tuple = slice(index.start, index.stop, index.step).indices(self.value)
fib_result = [fib(n) for n in range(*range_tuple)] #產出一系列的費波那契值
return fib_result
else:
return "The index is not valid."

def fib(n):
if n < 2:
return 1
else:
return fib(n-2) + fib(n-1)

fib_obj = Fib(10)
print(fib_obj[4]) #5
print(fib_obj[-1:-5: -1]) #[55,34,21,13]

這個Sequence使用的是lazy evaluation,意即就是當我們一開始宣告fib_obj = Fib(10)的時候,並不是一開始就宣告了1~10的費波那契數列,10只是做為定義Sequence長度之用,等到真的要透過.__getitem__()access特定element時才會呼叫fib(),去計算並return值。

Get John’s stories in your inbox

Join Medium for free to get updates from this writer.

除了一些基本規則,還多加上了一些程式碼去處理index為負值以及前面提到的slice的情況,讓整體更貼近built-in的Python Sequence。

Mutable Sequence

Mutable Sequence如Python built-in的list可以容許修改與賦值,所以我們加上把我們上面寫的Fib Sequence加上以下的method:

  • .append():將新element加在Sequence結尾
  • .insert():將新element加在指定index處
  • .extend():擴充、添加新element在Sequence結尾
  • .pop():將指定index的Sequence值取出來
  • .clear():清除整個Sequence
  • .__setitem__():根據給的index去修改Sequence值
  • .__delitem__():根據給的index去刪除Sequence值
class Fib:
def __init__(self, value):
self.list = [fib(x) for x in range(value+1)] #Define the length of the Sequence
self.length = len(self.list)
def __len__(self):
return self.length
def __getitem__(self, index):
if isinstance(index, int):
if index < 0:
index = self.length + index #Handle [-1] index slicing
if index < 0 or index >= self.length:
raise IndexError
else:
return self.list[index]
elif isinstance(index, slice):
return self.list[index]
else:
return "The index is not valid."
def append(self,value):
self.list.append(value)
def insert(self, index, value):
self.list.insert(index, value)
def extend(self, other_fib):
if isinstance(other_fib, Fib):
self.list += other_fib.list
else:
raise ValueError("Can only use extend with Fib type sequence")
def pop(self, index):
return self.list.pop(index)
def clear(self):
self.list.clear()
self.length = 0
def __setitem__(self, key, value):
self.list[key] = value
def __delitem__(self, key):
del self.list[key]

def fib(n):
if n < 2:
return 1
else:
return fib(n-2) + fib(n-1)

Inplace Operation

Inplace運算算是補充的部分,主要是在Inplace下,Mutable Sequence的結果和Immutable會有差異、所以特別寫一下:

根據Python built-in的Mutable Sequence Inplace運算規則,我們得到以下預期的運算結果,若:

  • Sequence1 + Sequence2 are two same object type, result is a new object
  • Sequence1 += Sequence2: Sequence2 can be any type's iterable object, result is the same object of Sequence1 — Inplace
  • Sequence * n: n is a not negative integer, result is a new object with same object type as Sequence
  • Sequence *= n: n is a not negative integer, result is the same object with same object type as Sequence — Inplace

用程式碼檢驗一下:

Normal operation

list_a = [1,2,3,4]
list_b = [5,6,7]
print(id(list_a)) #1498769969664

#Do the operation
list_a = list_a + list_b #Create a new list

#Show memory address
print(id(list_a)) #1498770191808

Inplace Operation

list_a = [1,2,3,4]
list_b = [5,6,7]
print(id(list_a)) #2421997031936

#Do the operation
list_a += list_b #Same object as list_a

#Show memory address
print(id(list_a)) #2421997031936

而Immutable Sequence,不管是不是Inplace Operation,都會創建新的一個物件:

Normal Operation

tuple_a = (1,2,3,4)
tuple_b = (5,6,7)
print(id(tuple_a)) #2647914163920

#Do the operation
tuple_a = tuple_a + tuple_b #Create a new tuple

#Show memory address
print(id(tuple_a)) #2647910969888

Inplace Operation

tuple_a = (1,2,3,4)
tuple_b = (5,6,7)
print(id(tuple_a)) #1956331695824

#Do the operation
tuple_a += tuple_b #Also create a new tuple

#Show memory address
print(id(tuple_a)) #1956328501792

針對一般Operation或是Inplace Operation,我們也可以選擇使用以下method implement在我們的custom Class裡面的:

  • .__add__: for "+"
  • __iadd__: for "+="
  • __mul__: for "*"
  • __imul__: for "*="

還有其他Sequence的method我沒有提及,像是檢查element有沒有在Sequence的.__contains()__等等,就等有需要或是有興趣時再搜尋就可以了。

Custom Sequence實作 — Polygon Sequence

目標是建立一個多邊形的點序列,紀錄每個點,以Sequence實現:

import numbers

#點class
class Point:
def __init__(self, x, y):
if isinstance(x, numbers.Real) and isinstance(y, numbers.Real): #Check if argument is valid real number
self._pt = (x, y)
else:
raise TypeError("Point must be real number")

#多邊形class - 由點構成
class Polygon:
def __init__(self, *pts):
if pts:
self._pts = [Point(*pt) for pt in pts]
else:
self._pts = []

def __repr__(self):
pts_str = ", ".join([str(pt) for pt in self._pts])
return f"Polygon({pts_str})"

def __len__(self):
return len(self._pts)

def __getitem__(self, key):
return self._pts[key]

def __setitem__(self, key, value):
try:
rhs = [Point(*pt) for pt in value] #看傳入的value是iterable or single Point
is_single = False
except TypeError:
try: #檢查是不是single Point
rhs = Point(*value)
is_single = True
except TypeError:
raise TypeError("Invalid Point or iterable of Points")
if (isinstance(key, int) and is_single == True) or (isinstance(key, slice) and is_single == False):
self._pts[key] = rhs
else:
raise TypeError("Incompatible assignment")

def __delitem__(self, key):
del self._pts[key]

def __add__(self,other):
if isinstance(other, Polygon):
new_pts = self._pts + other._pts
return Polygon(*new_pts)
else:
raise TypeError("can only concatenate with another Polygon")

def __iadd__(self, other):
if isinstance(other, Polygon):
self._pts = self._pts + other._pts
return self
else:
points = [Point(*pt) for pt in other]
self._pts = self._pts + points
return self

def append(self, pt):
self._pts.append(Point(*pt))

def insert(self, key, pt):
self._pts.insert(key, Point(*pt))

def extend(self, pts):
if isinstance(pts, Polygon):
self._pts += pts._pts
else:
points = [Point(*pt) for pt in pts]
self._pts += points

def pop(self, key):
return self._pts.pop(key)

def clear(self):
self._pts.clear()

#建立多邊形
polygon_1 = Polygon((10,10), (20,20), (40,40))

--

--