<dl id="3wz6h"></dl><li id="3wz6h"></li>

      1. <dl id="3wz6h"></dl>

      2. <dl id="3wz6h"><ins id="3wz6h"></ins></dl>

            <dl id="3wz6h"></dl>

            <dl id="3wz6h"><ins id="3wz6h"></ins></dl>
            1. 
              
              <output id="3wz6h"><ins id="3wz6h"><nobr id="3wz6h"></nobr></ins></output>

              <li id="3wz6h"><ins id="3wz6h"></ins></li>
              
              

            2. <output id="3wz6h"><ins id="3wz6h"><nobr id="3wz6h"></nobr></ins></output>
              首頁»Python»改善 Python 程序的 91 個建議(五)

              改善 Python 程序的 91 個建議(五)

              來源:馭風者 發布時間:2017-05-17 閱讀次數:

              建議 74:為包編寫單元測試

              直接上一個實例:

              __author__ = 'Windrivder'
              
              import unittest
              
              from app import create_app, db
              from flask import current_app
              
              
              class BasicsTestCase(unittest.TestCase):
              
                  def setUp(self):    # 測試前運行
                      self.app = create_app('testing')
                      self.app_context = self.app.app_context()
                      self.app_context.push()
                      db.create_all()  # 創建全新的數據庫
              
                  def tearDown(self):  # 測試后運行
                      db.session.remove()
                      db.drop_all()   # 刪除數據庫
                      self.app_context.pop()
              
                  # 測試程序實例是否存在
                  def test_app_exists(self):
                      self.assertFalse(current_app is None)
              
                  # 測試程序能在測試配置中運行
                  def test_app_is_testing(self):
                      self.assertTrue(current_app.config['TESTING'])
              
              __author__ = 'Windrivder'
              
              import time
              import unittest
              from datetime import datetime
              
              from app import create_app, db
              from app.models import AnonymousUser, Follow, Permission, Role, User
              
              
              class UserModelTestCase(unittest.TestCase):
              
                  def test_password_setter(self):
                      u = User(password='Cat')
                      self.assertTrue(u.password_hash is not None)
              
                  def test_no_password_getter(self):
                      u = User(password='Cat')
                      with self.assertRaises(AttributeError):
                          u.password
              
                  def test_password_verifycation(self):
                      u = User(password='Cat')
                      self.assertTrue(u.verify_password('Cat'))
                      self.assertFalse(u.verify_password('Dog'))
              
                  def test_password_salts_are_random(self):
                      u = User(password='Cat')
                      u2 = User(password='Cat')
                      self.assertTrue(u.password_hash != u2.password_hash)
              
                  def test_roles_and_permission(self):
                      Role.insert_roles()
                      u = User(email='[email protected]', password='cat')
                      self.assertTrue(u.can(Permission.WRITE_ARTICLES))
                      self.assertFalse(u.can(Permission.MODERATE_COMMENTS))
              
                  def test_anonymous_user(self):
                      u = AnonymousUser()
                      self.assertFalse(u.can(Permission.FOLLOW))
              
                  def test_timestamps(self):
                      u = User(password='cat')
                      db.session.add(u)
                      db.session.commit()
                      self.assertTrue(
                          (datetime.utcnow() - u.member_since).total_seconds() < 3)
                      self.assertTrue(
                          (datetime.utcnow() - u.last_seen).total_seconds() < 3)
              
                  def test_ping(self):
                      u = User(password='cat')
                      db.session.add(u)
                      db.session.commit()
                      time.sleep(2)
                      last_seen_before = u.last_seen
                      u.ping()
                      self.assertTrue(u.last_seen > last_seen_before)
              

              以上代碼是在學習 Flask 框架時,在書中學習到的單元測試。

              建議 75:利用測試驅動開發提高代碼的可測性

              測試驅動開發(Test Driven Development,TDD)是敏捷開發中一個非常重要的理念,它提倡在真正開始編碼之前測試先行,先編寫測試代碼,再在其基礎上通過基本迭代完成編碼,并不斷完善。一般來說,遵循以下過程:

              • 編寫部分測試用例,并運行測試

              • 如果測試通過,則回到測試用例編寫的步驟,繼續添加新的測試用例

              • 如果測試失敗,則修改代碼直到通過測試

              • 當所有測試用例編寫完成并通過測試之后,再來考慮對代碼進行重構

              關于測試驅動開發和提高代碼可測性方面有幾點需要說明:

              • TDD 只是手段而不是目的,因此在實踐中盡量只驗證正確的事情,并且每次僅僅驗證一件事。當遇到問題時不要局限于 TDD 本身所涉及的一些概念,而應該回頭想想采用 TDD 原本的出發點和目的是什么

              • 測試驅動開發本身就是一門學問

              • 代碼的不可測性可以從以下幾個方面考量:實踐 TDD 困難;外部依賴太多;需要寫很多模擬代碼才能完成測試;職責太多導致功能模糊;內部狀態過多且沒有辦法去操作和維護這些狀態;函數沒有明顯返回或者參數過多;低內聚高耦合等等。

              建議 76:使用 Pylint 檢查代碼風格

              如果團隊遵循 PEP8 編碼風格,Pylint 是個不錯的選擇(還有其他選擇,比如 pychecker、pep8 等)。Pylint 始于 2003 年,是一個代碼分析工具,用于檢查 Python 代碼中的錯誤,查找不符合代碼編碼規范以及潛在的問題。支持不同的 OS 平臺,如 Windows、Linux、OSX 等,特性如下:

              • 代碼風格審查。它以 Guido van Rossum 的 PEP8 為標準,能夠檢查代碼的行長度,不符合規范的變量名以及不恰當的模塊導入等不符合編碼規范的代碼

              • 代碼錯誤檢查。如未被實現的接口,方法缺少對應參數,訪問模塊中未定義的變量等

              • 發現重復以及設計不合理的代碼,幫助重構。

              • 高度的可配置化和可定制化,通過 pylintrc 文件的修改可以定義自己適合的規范。

              • 支持各種 IDE 和編輯器集成。如 Emacs、Eclipse、WingIDE、VIM、Spyder 等

              • 能夠基于 Python 代碼生成 UML 圖。Pylint0.15 中就集成了 Pyreverse,能夠輕易生成 UML 圖形

              • 能夠與 Hudson、Jenkins 等持續集成工具相結合支持自動代碼審查。

              使用 Pylint 分析代碼,輸出分為兩部分:一部分為源代碼分析結果,第二部分為統計報告。報告部分主要是一些統計信息,總體來說有以下6 類:

              • Statistics by type:檢查的模塊、函數、類等數量,以及它們中存在文檔注釋以及不良命名的比例

              • Raw metrics:代碼、注釋、文檔、空行等占模塊代碼量的百分比統計

              • Duplication:重復代碼的統計百分比

              • Messages by category:按照消息類別分類統計的信息以及和上一次運行結果的對比

              • Messages:具體的消息 ID 以及它們出現的次數

              • Global evaluation:根據公式計算出的分數統計:10.0 - ((float(5 * error + warning + refactor + convention) / statement) * 10)

              我們來重點討論一下源代碼分析主要以消息的形式顯示代碼中存在的問題,消息以 MESSAGE_TYPE:LINE_NUM:[OBJECT:]MESSAGE 的形式輸出,主要分為以下 5 類:

              • (C)慣例,違反了編碼風格標準

              • (R)重構,寫得非常糟糕的代碼

              • (W)警告,某些 Python 特定的問題

              • (E)錯誤,很可能是代碼中的 bug

              • (F)致命錯誤,阻止 Pylint 進一步運行的錯誤

              比如如果信息輸出 trailing-whitespace 信息,可以使用命令 pylint --help-msg="trailing-whitespace" 來查看,這里提示是行尾存在空格。

              如果不希望對這類代碼風格進行檢查,可以使用命令行過濾掉這些類別的信息,比如 pylint -d C0303,W0312 BalancePoint.py。

              Pylint 支持可配置化,如果在項目中希望使用統一的代碼規范而不是默認的風格來進行代碼檢查,可以指定 --generate-rcfile 來生成配置文件。默認的 Pylintrc 可以在 Pylint 的目錄 examples 中找到。如默認支持的變量名的正則表達式為:variable-rgx=[a-z_][a-z0-9_]{2,30}$,可以根據自己需要進行相應修改。其他配置如 reports 用于控制是否輸出統計報告;max-module-lines 用于設置模塊最大代碼行數;max-line-length 用于設置代碼行最大長度;max-args 用于設置函數的參數個數等。讀者可自行查看 pylintrc 文件。

              建議 77:進行高效的代碼審查

              建議 78:將包發布到 PyPI

              可以是發布到官方的 PyPI 或者團隊私有的 PyPI。這里先講把包發布到官方的 PyPI,標準庫 distutils 支持將包發布到 PyPI 的功能:

              # 現在 PyPI 上注冊一個用戶
              $ python setup.py register
              # 注冊包名
              $ python setup.py register -n 
              # 上傳包
              $ python setup.py sdist upload
              

              第 8 章 性能剖析與優化

              建議 79:了解代碼優化的基本原則

              代碼優化是指在不改變程序運行結果的前提下使得程序運行的效率更高,優化的代碼意味著代運行速度更快或者占用的資源更少。

              1. 優先保證代碼是可工作的。

              2. 權衡優化的代價。

              3. 定義性能指標,集中力量解決首要問題。

              4. 不要忽略可讀性。

              建議 80:借助性能優化工具

              常見的性能優化工具有 Psyco、Pypy 和 cPython 等。

              1. Psyco:Psyco 是一個 just-in-time 的編譯器,它能夠在不改變源代碼的情況下提高一定的性能,Psyco 將操作編譯成部分優化的機器碼,其操作分成三個不同的級別,有“運行時”、“編譯時”和“虛擬時”變量,并根據需要提高和降低變量的級別。運行時變量只是常規 Python 解釋器處理的原始字節碼和對象結構。一旦 Psyco 將操作編譯成機器碼,那么編譯時變量就會在機器寄存器和可直接訪問的內存位置中表示。同時 Python 能高速緩存已編譯的機器碼以備以后重用,這樣能節省一點時間。但 Psyco 也有其缺點,其本身所占內存較大。2012 年 Psyco 項目停止維護并正式結束,由 Pypy 所接替。

              2. Pypy:Python 的動態編譯器,是 Psyco 的后繼項目。其目的是,做到 Psyco 沒有做到的動態編譯。Pypy 的實現分為兩部分,第一部分“用 Python 實現的 Python”,實際上它是使用一個名為 RPython 的 Python 子集實現的,Pypy 能夠將 Python 代碼轉成 C、.NET、Java 等語言和平臺的代碼;第二部分 Pypy 集成了一種編譯 rPython 的即時(JIT)編譯器,和許多編譯器、解釋器不同,這種編譯器不關心 Python 代碼的詞法分析和語法樹,所以它直接利用 Python 語言的 Code Object(Python 字節碼的表示)。Pypy 直接分析 Python 代碼所對應的字節碼,這些字節碼既不是以字符形式也不是以某種二進制格式保存在文件中。

              建議 81:利用 cProfile 定位性能瓶頸

              程序性能影響往往符合 80/20 法則,即 20% 的代碼的運行時間占用了 80% 的總運行時間。

              profile 是 Python 的標準庫,可以統計程序里每一個函數的運行時間,并且提供了多樣化的報表,而 cProfile 則是它的 C 實現版本,剖析過程本身需要消耗的資源更少。所以在 Python3 中,cProfile 代替了 profile,成為默認的性能剖析模塊。

              def foo():
                  sum = 0
                  for i in range(100):
                      sum += i
                  return sum
              if __name__ == "__main__":
                  import cProfile
                  cProfile.run("foo()")
              
              4 function calls in 0.000 seconds
              
              Ordered by: standard name
              
              ncalls  tottime  percall  cumtime  percall filename:lineno(function)
                  1    0.000    0.000    0.000    0.000 <ipython-input-1-e5d41600b11d>:1(foo)
                  1    0.000    0.000    0.000    0.000 <string>:1(<module>)
                  1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
                  1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
              

              除了用這種方式,cProfile 還可以直接用 Python 解釋器調用 cProfile 模塊來剖析 Python 程序,如在命令行輸入 python -m cProfile prof1.py結果和調用cProfile.run()一樣。

              cProfile 的統計結果分為 ncalls、tottime、percall、cumtime、percall、filename:lineno(function) 等若干列。

              統計項意義ncalls函數的被調用次數tottime函數總計運行時間,不含調用的函數運行時間percall函數運行一次的平均時間,等于 tottime/ncallscumtime函數總計運行時間,含調用的函數運行時間percall函數運行一次的平均時間,等于 cumtime/ncallsfilename:lineno(function)函數所在的文件名、函數的行號、函數名

              通常情況下,cProfile 的輸出都直接輸出到命令行,而且默認是按照文件名排序輸出的。cProfile 簡單地支持了一些需求,可以在 cProfile.run() 函數里再提供一個實參,就是保存輸出的文件名。同樣,在命令行參數里,也可以加多一個參數,用來保存 cProfile 的輸出。

              cProfile 解決了我們的對程序執行性能剖析的需求,但還有一個需求:以多種形式查看報表以便快速定位瓶頸。我們可以通過 pstats 模塊的另一個類 Stats 來解決。Stats 的構造函數接受一個參數——就是 cProfile 的輸出文件名。Status 提供了對 cProfile 輸出結果進行排序、輸出控制等功能。我們可以修改前文的程序:

              if __name__ == "__main__":
                  import cProfile
                  cProfile.run("foo()", "prof.txt")
                  import pstats
                  p = pstats.Stats("prof.txt")
                  p.sort_stats("time").print_stats()
              

              Stats 有若干個函數,這些函數組合能輸出不同的 cProfile 報表,功能非常強大,下面簡單介紹一些:

              函數函數的作用strip_dirs()用以除去文件名前面的路徑信息add(filename,[...])把 profile 的輸出文件加入 Stats 實例中統計dump_stats(filename)把 Stats 的統計結果保存到文件sort_stats(key, [...])把最重要的一個函數,用以排序 profile 的輸出reverse_order()把 Stats 實例里的數據反序重排print_stats([restriction,...])把 Stats 報表輸出到 stdoutprint_callers([restriction,...])輸出調用了指定的函數的相關信息print_callees([restriction,...])輸出指定的函數調用過的函數的相關信息

              這里最重要的函數就是 sort_stats 和 print_stats,通過這兩個函數我們幾乎可以用適當的形式瀏覽所有的信息了。下面是詳細介紹:

              1. sort_stats() 接收一個或者多個字符串參數,如 time、name 等,表明要根據哪一列來排序。比如可以通過用 time 為 key 來排序得知最消耗時間的函數;也可以通過 cumtime 來排序,獲知總消耗時間最多的函數。

                參數意義ncalls被調用次數cumulative函數運行的總時間file文件名module模塊名pcalls簡單統計調用line行號name函數名nflName、file、linestdname標準函數名time函數內部運行時間
              2. print_stats 輸出最后一次調用 sort_stats 之后得到的報表。print_stats 有多個可選參數,用以篩選輸出的數據。print_stats 的參數可以是數字也可以是 Perl 風格的正則表達式。

                下面舉一些例子:

                # 將 stats 里的內容取前面 10%,然后再將包含 "foo:" 這個字符串的結果輸出
                print_stats(".1", "foo:")
                # 將 stats 里的包含 "foo:" 字符串的內容的前 10% 輸出
                print_stats("foo:", ".1")
                # 將 stats 里前 10 條數據輸出
                print_stats(10)
                # profile 輸出結果的時候相當于如下調用了 Stats 的函數
                p.strip_dirs().sort_stats(-1).print_stats()
                

                其中,sort_stats 函數的參數是 -1,這是為了與舊版本兼容而保留的。sort_stats 可以接受 -1、0、1、2 之一,這 4 個數分貝對應 "stdname"、"calls"、"time" 和 "cumulative"。但如果你使用了數字為參數,那么 pstats 只按照第一個參數進行排序,其他參數將被忽略。

              除了編程接口外,pstats 還提供了友好的命令行交互環境,在命令行執行 python -m pstats 就可以進入交互環境,在交互環境里可以使用 read 或 add 指令讀入或加載剖析結果文件, stats 指令用以查看報表,callees 和 callers 指令用以查看特定函數的被調用者和調用者。

              如果我們想測試向 list 中添加一個元素需要多少時間,可以使用 timeit 模塊:

              class Timer([stmt="pass"[, setup="pass"[, timer=<time function>]]])
              
              • stmt 參數是字符串形式的一個代碼段,這個代碼段將被評測運行時間;

              • setup 參數用以設置 stmt 的運行環境;

              • timer 可以由用戶使用自定義精度的計時函數。

              timeit.Timer 有 3 個成員函數:

              • timeit([number=1000000]) :timeit() 執行一次 Timer 構造函數中的 setup 語句之后,就重復執行 number 次 stmt 語句,然后返回總計運行消耗的時間;

              • repeat([repeat=3[, number=1000000]]) :repeat() 函數以 number 為參數調用 timeit 函數 repeat 次,并返回總計運行消耗的時間;

              • print_exc([file=None]) :print_exec() 函數以代替標準的 tracback,原因在于 print_exec() 會輸出錯行的源代碼。

              除了可以使用 timeit 的編程接口外,也可以在命令行里使用 timeit,非常方便:

              python -m timeit [-n N] [-r N] [-s S] [-t] [-c] [-h] [statement ...]
              

              其中參數的定義如下:

              • -n N/--number=N,statement 語句執行的次數

              • -r N/--repeat=N,重復多少次調用 timeit(),默認為 3

              • -s S/--setup=S,用以設置 statement 執行環境的語句,默認為 "pass"

              • -t/--time,計時函數,除了 Windows 平臺外默認使用 time.time() 函數

              • -c/--clock,計時函數,Windows 平臺默認使用 time.clock() 函數

              • -v/--verbose,輸出更大精度的計時數值

              • -h/--help,簡單的使用幫助

              厲害:

              python -m timeit "[].append(1)"
              10000000 loops, best of 3: 0.116 usec per loop
              

              建議 82:使用 memory_profiler 和 objgraph 剖析內存使用

              Python 還提供了一些工具可以用來查看內存的使用情況以及追蹤內存泄漏(如 memory_profiler、objgraph、cProfile、PySizer 及 Heapy 等),或者可視化地顯示對象之間的引用(如 objgraph),從而為發現內存問題提供更直接的證據。我們來看看memory_profiler、objgraph兩個工具的使用。

              1. memory_profiler:在需要進行內存分析的代碼之前用 @profile 進行裝飾,然后運行命令 python -m memory_profiler 文件名 ,便可以輸出每一行代碼的內存使用以及增長情況。

              2. Objgraph:

                • 安裝:pip install objgraph

                • 功能分類:

                  • 統計,如 objgraph.count(typename[, objects]) 表示根據傳入的參數顯示被 gc 跟蹤的對象的數目;objgraph.show_most_common_types([limit=10, objects]) 表示顯示常用類型對應的對象的數目

                  • 定位和過濾對象,如 objgraph.by_type(typename[, objects]) 表示根據傳入的參數顯示被 gc 跟蹤的對象信息;objgraph.at(addr) 表示根據給定的地址返回對象

                  • 遍歷和顯示對象圖。如 objgraph.show_refs(objs[, max_depth=3, extra_ignore=(), filter=None, too_many=10, highlight=None, filename=None, extra_info=None, refcounts=False]) 表示從對象 objs 開始顯示對象引用關系圖;objgraph.show_backrefs(objs[, max_depth=3, extra_ignore=(), filter=None, too_many=10, highlight=None, filename=None, extra_info=None, refcounts=False]) 表示顯示以 objs 的引用作為結束的對象關系圖。

                • 例子:

                  1. 生成對象x的引用關系圖:

                  >>> import objgraph
                  >>> x = ['a', '1', [2, 3]]
                  >>> objgraph.show_refs([x], filename="test.png")
                  
                  1. 顯示常用類型不同類型對象的數目,限制輸出前3行:

                  >>> objgraph.show_most_common_types(limit=3)
                  wrapper_descriptor            1031
                  function                    975
                  builtin_function_or_method    615
                  

              建議 83:努力降低算法復雜度

              時間復雜度:

              O(1) < O(log * n) < O(n) < O(n log n) < O(n^2) < O(c^n) < O(n!) < O(n^n)

              常見數據結構基本操作時間復雜度:

              建議 84:掌握循環優化的基本技巧

              循環的優化應遵循的原則是盡量減少循環過程中的計算量,多重循環的情形下盡量將內層的計算提到上一層。

              1. 減少循環內部的計算:

                # 每次循環都要重新計算
                for i in range(iter):
                    d = math.sqrt(y)
                    j += i * d
                # 高效率
                d = math.sqrt(y)
                for i in range(iter):
                    j += i * d
                
              2. 將顯式循環改為隱式循環:n * (n + 1) / 2,不必使用for循環計算,但要注意可讀性

              3. 在循環中盡量引用局部變量,在命名空間中局部變量優先搜索,因此局部變量的查詢會比全局變量要快,當在循環中需要多次引用某一個變量的時候,盡量將其轉換為局部變量:

                # 示例一
                x = [10, 34, 56, 78]
                def f(x):
                    for i in range(len(x)):
                        x[i] = math.sin(x[i])
                    return x
                # 示例二
                def g(x):
                    loc_sin = math.sin
                    for i in range(len(x)):
                        x[i] = loc_sin(x[i])
                    return x
                # 示例二比示例一性能更佳
                
              4. 關注內層嵌套循環,盡量將內層循環的計算往上層移:

                # 示例一
                for i in range(len(v1)):
                    for j in range(len(v2)):
                        x = v1[i] + v2[j]
                
                # 示例二
                for i in range(len(v1)):
                    v1i = v1[i]
                    for j in range(len(v2)):
                        x = v1i + v2[j]
                

              建議 85:使用生成器提高效率

              放一張圖來理解,來自這里

              實際上當需要在循環過程中依次處理一個序列中的元素的時候,就應該考慮生成器。

              當解釋器執行遇到 yield 的時候,函數會自動返回 yield 語句之后的表達式的值。不過與 return 不同的是,yield 語句在返回的同時會保存所有的局部變量以及現場信息,以便在迭代器調用 next() 或 send() 方法的時候還原,而不是直接交給垃圾回收器(return() 方法返回后這些信息會被垃圾回收器處理)。

              這樣就能夠保證對生成器的每一次迭代都會返回一個元素,而不是一次性在內存中生成所有的元素。自 Python2.5 開始,yield 語句變為表達式,可以直接將其值賦給其他變量。

              生成器的優點總體來說有如下幾條:

              • 生成器提供了一種更為便利的產生迭代器的方式,用戶一般不需要自己實現 __iter__ 和 next 方法,它默認返回一個迭代器

              • 代碼更為簡潔優雅

              • 充分利用了延遲評估(Lazy evaluation)的特性,僅在需要的時候才產生對應的元素,而不是一次生成所有的元素,從而節省了內存空間,提高了效率,理論上無限循環成為了可能

              • 使得協同程序更為容易實現。協同程序是有多個進入點,可以掛起恢復的函數,這基本就是 yield 的工作方式。Python2.5 之后生成器的功能更完善,加入了 send()、close() 和 throw() 方法。其中 send() 不僅可以傳遞值給 yield 語句,而且能夠恢復生成器,因此生成器能大大簡化協同程序的實現。

              建議 86:使用不同的數據結構優化性能

              如果 Python 中的查找、排序算法已經優化到極限,比如sort()使用 key 參數比使用cmp參數性能更高;那么首先應該考慮使用不同的數據結構優化性能。

              list,它的內存管理類似 C++ 的 std::vector,即預先分配一定數量的”車位“,當預分配的內存用完時,又繼續往里面插入元素,會啟動新一輪的內存分配。

              list 對象會根據內存增長算法申請一塊更大的內存,然后將原有的所有元素拷貝過去,銷毀之前的內存,再插入新元素。當刪除元素時,也是類似,刪除后發現已用空間比預分配空間的一半還少時,list 會另外申請一塊小內存,再做一次元素拷貝,然后銷毀原有的大內存。可見,如果 list 對象經常有元素數量的“巨變”,比如增加、刪除得很頻繁,那么應當考慮使用 deque。

              deque 就是雙端隊列,同時具備棧和隊列的特性,能夠提供在兩端插入和刪除時復雜度為 O(1) 的操作。相對于 list,它最大的優勢在于內存管理方面。如果不熟悉 C++ 的 std::deque,可以把 deque 想象為多個 list 連在一起,它的每一個 list 也可以存儲多個元素。它的優勢在于插入時,已有空間已經用完,那么它會申請一個新的內存空間來容納新的元素,并將其與已有的其他內存空間串接起來,從而避免元素拷貝;在刪除元素時也類似,無需移動元素。所以當元素數量巨變時,它的性能比 list 要好上許多倍。

              對于 list 這種序列容器來說,除了 pop(0) 和 insert(0, v) 這種插入操作非常耗時之外,查找一元素是否在其中,也是 O(n) 的線性復雜度。在 C 語言中,標準庫函數 bsearch() 能夠通過二分查找算法在有序隊列中快速查找是否存在某一元素。在 Python 中,對保持 list 對象有序以及在有序隊列中查找元素有非常好的支持,這是通過標準庫 bisect 來實現的。

              bisect 并沒有實現一種新的“數據結構”,其實它是用來維護“有序列表”的一組函數,可以兼容所有能夠隨機存取的序列容器,比如 list。它可使在有序列表中查找某一元素變得非常簡單。

              def index(a, x):
                  i = bisect_left(a, x)
                  if i != len(a) and a[i] == x:
                      return i
                  raise ValueError
              

              保持列表有序需要付出額外的維護工作,但如果業務需要在元素較多的列表中頻繁查找某些元素是否存在或者需要頻繁地有序訪問這些元素,使用 bisect 則相當值得。

              對于序列容器,除了插入、刪除、查找之外,還有一種很常見的需求是獲取其中的極大值或極小值元素,比如在查找最短路徑的A*算法中就需要在Open表中快速找到預估值最小的元素。這時候,可以使用 heapq 模塊。類似 bisect,heapq 也是維護列表的一組函數,其中 heapify() 的作用是把一個序列容器轉化為一個堆。

              In [1]: import heapq
              
              In [2]: import random
              
              In [3]: alist = [random.randint(0, 100) for i in range(10)]
              
              In [4]: alist
              Out[4]: [62, 72, 18, 55, 86, 26, 88, 21, 4, 97]
              
              In [5]: heapq.heapify(alist)
              
              In [6]: alist
              Out[6]: [4, 21, 18, 55, 86, 26, 88, 72, 62, 97]
              

              可以看到,轉化為堆后,alist 的第一個元素 alist[0] 是整個列表中最小的元素,heapq 將保證這一點,從而保證從列表中獲取最小值元素的時間復雜度是 O(1)。

              In [7]: heapq.heappop(alist)
              Out[7]: 4
              
              In [8]: alist
              Out[8]: [18, 21, 26, 55, 86, 97, 88, 72, 62]
              

              除了通過 heapify() 函數將一個列表轉換為堆之外,也可以通過 heappush()、heappop() 函數插入、刪除元素,針對常見的先插入新元素再獲取最小元素、先獲取最小元素再插入新元素的需求,還有 heappushpop(heap, item) 和 heapreplace(heap, item) 函數可以快速完成。另外可以看出,每次元素增減之后的序列變化很大,所以千萬不要亂用 heapq,以免帶來性能問題。

              heapq 還有 3 個通用函數值得介紹,其中 merge() 能夠把多個有序列表歸并為一個有序列表(返回迭代器,不占用內存),而 nlargest() 和 nsmallest() 類似于 C++ 中的 std::nth_element(),能夠返回無序列表中最大或最小的 n 個元素,并且性能比 sorted(iterable, key=key)[:n] 要高。

              除了對容器的操作可能會出現性能問題外,容器中存儲的元素也有很大的優化空間,這是因為在很多業務中,容器存儲的元素往往是同一類型的,比如都是整數,而且整數的取值范圍也確定,此時就可以用 array 優化程序性能。

              array 實例化的時候需要指定其存儲的元素類型,如c,表示存儲的每個人元素都相當于C語言中的 char 類型,占用內存大小為 1 字節。

              QQ群:WEB開發者官方群(515171538),驗證消息:10000
              微信群:加小編微信 849023636 邀請您加入,驗證消息:10000
              提示:更多精彩內容關注微信公眾號:全棧開發者中心(fsder-com)
              網友評論(共0條評論) 正在載入評論......
              理智評論文明上網,拒絕惡意謾罵 發表評論 / 共0條評論
              登錄會員中心
              云南十一选往期