Python 部分知識點總結（五）

一、高價函數和柯里化

1. First?Class?Object
   ? ? ? ? 函數在?Python?中是一等公民
   ? ? ? ? 函數也是對象，可調用的對象
   ? ? ? ? 函數可以作為普通變量、參數、返回值等
2. 高階函數
   ? ? ? ? 數學概念?y=g(f(x))
   ? ? ? ? 在數學和計算機科學中，高階函數應該是至少滿足下面一個條件的函數：
   ? ? ? ? ? ? 接受一個或多個函數作為參數
   ? ? ? ? ? ? 輸出一個函數
3. sorted(iterable[,key][,reverse])
   ? ? ? 返回一個新的列表，對一個可迭代對象的所有元素排序，排序規則為?key?定義的函數，reverse?表示是否排序翻轉，sorted() 返回新列表，list.sort()?就地修改
4. filter(function,iterable) –> filter object
   ? ? ? 過濾可迭代對象的元素，返回一個迭代器
   ? ? ? function?一個具有一個參數的函數，返回?bool
   ? ? ??>>> list(filter(lambda x:x%3==0,[1,9,55,150,-3,78,28,123]))? ?–>? [9, 150, -3, 78, 123]
5. map(func,*iterables)? ?–> map object
   ? ? ? 對多個可迭代對象的元素按照指定的函數進行映射，返回一個迭代器
   ? ? ??>>> list(map(lambda x:2*x+1,range(5)))? ? ? ? ? ?–>? [1, 3, 5, 7, 9]
   ? ? ??>>> dict(map(lambda x:(x%5,x),range(500)))? ? –>? {0: 495, 1: 496, 2: 497, 3: 498, 4: 499}
6. 柯里化：指的是將原來接受兩個參數的函數編程新的接受一個參數的函數的過程，新的函數返回一個以原有第二個參數的函數，z = f(x,y)?轉換成 z = f(x)(y)?的形式，通過嵌套函數就可以把函數轉換成柯里函數

二、裝飾器

1. 最簡單的用法
   def logger(fn):
   ????def wrapper(*args,**kwargs):
   ????????print(‘BEGIN’)
   ????????x = fn(*args,**kwargs)
   ????????print(‘END’)
   ????????return x
   ????return wrapper
   @logger
   def add(x,y):
   ????return x+y
   add(100,2)
2. 裝飾器（無參）
   ? ? ? ? ?它是一個函數
   ? ? ? ? ?函數作為它的形參
   ? ? ? ? ?返回值也是一個函數
   ? ? ? ? ?可以使用 @functionname?方法，簡化使用
3. 裝飾器是高階函數，但裝飾器是對傳入函數的功能的裝飾（功能增強）
4. 文檔字符串
   ? ? ? ? Python?是文檔字符串?Documetation?Strings
   ? ? ? ? 在函數語句塊的第一行，且習慣是多行的文本，所以多使用三引號
   ? ? ? ? 慣例是首字母大寫，第一行寫概述，空一行，第三行寫詳細描述
   ? ? ? ? 可以使用特殊屬性 __doc__?訪問這個文檔
5. 帶參裝飾器
   ? ? ? ? ?它是一個函數
   ? ? ? ? ?函數作為它的形參
   ? ? ? ? ?返回值是一個不帶參的裝飾器函數
   ? ? ? ? ?使用 @functionname(參數列表)? 方式調用
   ? ? ? ? ?可以看做在裝飾器外層又加了一層函數
6. functools.update_wrapper(wrapper,wrapped,assigned=WRAPPER_ASSIGNMENTS,updated=WRAPPER_UPDATES)
   ? ? ? ? ? 類似?copy_properties?功能
   ? ? ? ? ? wrapper?包裝函數、被更新者，wrapped?被包裝函數、數據源
   ? ? ? ? ? 元組 WRAPPER_ASSIGNMENTS?中是要被覆蓋的屬性：’__module__’（模塊名）、’__name__’（名稱）、’__qualname__’（限定名）、’__doc__’（文檔）、’__annotations__’（參數注解）
   ? ? ? ? ? 元組 WRAPPER_UPDATES?中是要被更新的屬性，__dict__?屬性字典
   ? ? ? ? ? 增加一個 __wrapped__?屬性，保留著?wrapped?函數
   ? ? ? ? ? 使用的時候只需要加上一句：import?functools? ?functools.update_wrapper(wrapper,fn)
7. @functools.wraps(wrapped,assigned=WRAPPER_ASSIGNMENTS,updated=WRAPPER_UPDATES)
   ? ? ? ? ? ? ?類似?copy_properties?功能
   ? ? ? ? ? ? ?wrapped?被包裝函數
   ? ? ? ? ? ? ?元組?WRAPPER_ASSIGNMENTS?中是要被覆蓋的屬性：’__module__’（模塊名）、’__name__’（名稱）、’__qualname__’（限定名）、’__doc__’（文檔）、’__annotations__’（參數注解）
   ? ? ? ? ? ? ?元組?WRAPPER_UPDATES?中是要被更新的屬性，__dict__?屬性字典
   ? ? ? ? ? ? ?增加一個 __wrapped__?屬性，保留著?wrapped?函數
   ? ? ? ? ? ? ?使用的時候只需要加一句：import functools? ?@functools.wraps(fn)
8. partial?方法
   ? ? ? ? ? 偏函數，把函數部分的參數固定下來，相當于為部分的參數添加了一個固定的默認值，形成一個新的函數并返回
   ? ? ? ? ? 從?partial?生成的新函數，是對原函數的封裝
   def partial(func,*args,**keywords):
   ????def newfunc(*fargs,**fkeywords):
   ????????newkeywords = keywords.copy()
   ????????newkeywords.update(fkeywords)??# 如果有關鍵字參數，就更新值
   ????????return func(*(args + fargs),**newkeywords)??# 如果全是位置參數，就在后面追加
   ????newfunc.func = func??# 保留原函數
   ????newfunc.args = args??# 保留原函數的位置參數
   ????newfunc.keywords = keywords??# 保留原函數的關鍵字參數
   ????return newfunc
9. @functools.lru_cache(maxsize=128,typed=False)
   ? ? ? ? ? ?Least-recently-used?裝飾器，lru?即最近最少使用，cache?緩存
   ? ? ? ? ? ?如果?maxsize?設置為?None，則禁用?LRU?功能，并且緩存可以無限制增長，當?maxsize?是 2?的冪時，LRU?功能執行的最好
   ? ? ? ? ? ?如果?typed?設置為?True，則不同類型的函數參數將單獨緩存，如?f(3)?和 f(3.0)? 將被視為具有不同結果的不同調用
   ? ? ? ? ? ?使用方法：import functols? ? @functools.lru_cache()
   ? ? ? ? ? ?通過一個字典緩存被裝飾函數的調用和返回值
   ? ? ? ? ? lru_cache?裝飾器應用
   ? ? ? ? ? ? ? ? 使用前提：同樣的函數參數一定得到同樣的結果；函數執行時間很長，且要多次執行
   ? ? ? ? ? ? ? ? 缺點：不支持緩存過期，key?無法過期、失效；不支持清除操作；不支持分布式，是一個單機的緩存
   ? ? ? ? ? ? ? ? 適用場景：單機上需要空間換時間的地方，可以用緩存來將計算變成快速的查詢

三、參數注解

1. 函數定義的弊端
   ? ? ? ? ?Python?是動態語言，變量隨時可以被賦值，且能賦值為不同的類型
   ? ? ? ? ?Python?不是靜態編譯型語言，變量類型是運行器決定的
2. 解決動態語言定義的弊端：增加文檔?Documentation?String
   ? ? ? ? ?這只是一個慣例，不是強制標準，不能要求程序員一定為函數提供說明文檔
   ? ? ? ? ?函數定義更新了，文檔未必同步更新
3. 解決動態語言定義的弊端：函數注解
   ?? ??? ?def add(x:int,y:int) -> int:
   ?????? ??? ?”’
   ?????? ??? ?:param x:int
   ?????? ??? ?:param y:int
   ?????? ??? ?:return:int
   ?????? ??? ?”’
   ?????? ??? ?return x + y
   ?? ??? ?add(4,5)? ? ? ? ? ? ? ? –>? 9
   ?? ??? ?add(‘mag’,’edu’)? ?–> ‘magedu’
4. 函數注解
   ? ? ? ? ?Python 3.5?引入
   ? ? ? ? ?對函數的返回值進行類型注解
   ? ? ? ? ?對函數的返回值進行類型注解
   ? ? ? ? ?只對函數參數做第一個輔助的說明，并不對函數參數進行類型檢查
   ? ? ? ? ?提供給第三方工具，做代碼分析，發現隱藏的?bug
   ? ? ? ? ?函數注解的信息，保存在 __annotations__?屬性中
   ? ? ? ? ?add.__annotations__? ?–>?{‘return’: str, ‘x’: int, ‘y’: str}
5. inspet?模塊：提供獲取對象信息的函數，可以檢查函數和類、類型檢查
   ? ? ? ? ?inspect.isfunction(add)，是否是函數
   ? ? ? ? ?inspect.ismethod(add)，是否是類的方法
   ? ? ? ? ?inspect.isgenerator(add)，是否是生成器對象
   ? ? ? ? ?inspect.isgeneratorfunction(add)，是否是生成器函數
   ? ? ? ? ?inspect.isclass(add)，是否是類
   ? ? ? ? ?inspect.ismodule(add)，是否是模塊
   ? ? ? ? ?inspect.isbuiltin(add)，是否是內建對象
   ? ? ? ? ?signature：獲取簽名（函數簽名包含了一個函數的信息，包括函數名、它的參數新類型、它所在的類型和名稱空間及其他信息）
6. Parameter?對象
   ? ? ? ? ? 保存在元組中，是只讀的
   ? ? ? ? ? name，參數的名字
   ? ? ? ? ? annotation，參數的注解，可能沒有定義
   ? ? ? ? ? default，參數的缺省值，可能沒有定義
   ? ? ? ? ? empty，特殊的類，用來標記?default?屬性或者注釋?annotation?屬性的空值
   ? ? ? ? ? kind，實參如何綁定到形參，就是形參的類型
   ? ? ? ? ? ? ? ? POSITIONAL_ONLY，值必須是位置參數提供
   ? ? ? ? ? ? ? ? POSITIONLY_OR_KEYWORD，值可以作為關鍵字或者位置參數提供
   ? ? ? ? ? ? ? ? VAR_POSITIONLY，可變位置參數，對應 *args
   ? ? ? ? ? ? ? ? KEYWORD_ONLY，keyword-only參數，對應 *? 或者 *args?之后的出現的非可變關鍵字參數
   ? ? ? ? ? ? ? ? VAR_KEYWORD，可變關鍵字參數，對應 **kwargs

四、堆排序

1. 堆（Heap）
   ? ? ? ? ?堆是一個完全二叉樹
   ? ? ? ? ?每個非葉子結點都要大于或者等于其左右孩子結點的值稱為?大頂堆
   ? ? ? ? ?每個非葉子結點都要小于或者等于其左右孩子結點的值稱為?小頂堆
   ? ? ? ? ?根結點一定是大頂堆中的最大值，一定是小頂堆中的最小值
2. 構建大頂堆的核心算法
   ? ? ? ? ?度數為 2?的結點?A，如果它的左右孩子結點的最大值比它大，將這個最大值和該結點交換
   ? ? ? ? ?度數為 1?的結點?A，如果它的左孩子的值大于它，則交換
   ? ? ? ? ?如果結點 A?被交換到新的位置，還需要和其孩子結點重復上面的過程
3. 構建大頂堆的起點結點選擇
   ? ? ? ? ?從完全二叉樹的最后一個結點的雙親結點開始，即最后一層的最右邊葉子結點的父結點開始
   ? ? ? ? ?結點數為?n，則起始結點的編號為?n//2
   ? ? ?構建大頂堆的下一個結點的選擇
   ? ? ? ? 從起始結點開始向左找其同層結點，到頭后再從上一層的最右邊結點開始繼續向左逐個查找，直至根結點
   ? ? ?排序
   ? ? ? ? 將大頂堆根結點這個最大值和最后一個葉子結點交換，那么最后一個葉子結點就是最大值，將這個葉子結點盤排除在待排序結點之外，然后從新的根結點開始，重新調整為大頂堆后，重復上一步
4. 總結
   ? ? ? ? 是利用堆性質的一種選擇排序，在堆頂選出最大值或者最小值
   ? ? ? ? 由于堆排序對原始記錄的排序狀態并不敏感，因此它無論是最好、最壞，平均時間復雜度為 O(nlogn)
   ? ? ? ? 只是使用了一個交換用的空間，空間復雜度為?O(1)
   ? ? ? ? 不穩定的排序算法