欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

探究數(shù)組排序提升Python程序的循環(huán)的運(yùn)行效率的原因

 更新時(shí)間:2015年04月01日 16:43:43   作者:foreign keys  
這篇文章主要介紹了探究數(shù)組排序提升Python程序的循環(huán)的運(yùn)行效率的原因,作者用代碼實(shí)踐了多個(gè)小片段來進(jìn)行對(duì)比解釋,需要的朋友可以參考下

早上我偶然看見一篇介紹兩個(gè)Python腳本的博文,其中一個(gè)效率更高。這篇博文已經(jīng)被刪除,所以我沒辦法給出文章鏈接,但腳本基本可以歸結(jié)如下:
fast.py
 

import time
a = [i for i in range(1000000)]
sum = 0
t1 = time.time()
for i in a:
  sum = sum + i
t2 = time.time()
print t2-t1

slow.py
 

import time
from random import shuffle
a = [i for i in range(1000000)]
shuffle(a)
sum = 0
t1 = time.time()
for i in a:
  sum = sum + i
t2 = time.time()
print t2-t1

如你所見,兩個(gè)腳本有完全相同的行為。都產(chǎn)生一個(gè)包含前一百萬個(gè)整數(shù)的列表,并打印對(duì)這些整數(shù)求和的時(shí)間。唯一的不同是 slow.py 先將整數(shù)隨機(jī)排序。盡管這看起來有些奇怪,似乎隨機(jī)化足夠?qū)⒊绦蛎黠@變慢。在我機(jī)器上,運(yùn)行的Python2.7.3, fast.py 始終比 slow.py 快十分之一秒(fast.py 執(zhí)行大約耗時(shí)四分之三秒,這是不平常的增速)。你不妨也試試看。(我沒有在Python3上測(cè)試,但結(jié)果應(yīng)該不會(huì)差太多。)

那為什么列表元素隨機(jī)化會(huì)導(dǎo)致這么明顯的減速呢?博文的原作者把這記作“分支預(yù)測(cè)(branch prediction)”。如果你對(duì)這個(gè)術(shù)語不熟悉,可以在 StackOverflow 的提問中看看,這里很好地解釋了這個(gè)概念。(我的疑慮是原文的原作者遇到了這個(gè)問題或者與此類似的問題,并把這個(gè)想法應(yīng)用到不太適合應(yīng)用的Python片段中。)

當(dāng)然,我懷疑分支預(yù)測(cè)(branch prediction)是否是真正導(dǎo)致問題的原因。在這份Python代碼中沒有頂層條件分支,而且合乎情理的是兩個(gè)腳本在循環(huán)體內(nèi)有嚴(yán)格一致的分支。程序中沒有哪一部分是以這些整數(shù)為條件的,并且每個(gè)列表的元素都是不依賴于數(shù)據(jù)本身的。當(dāng)然,我還是不確定python是否算得上足夠“底層”,以至于CPU級(jí)別的分支預(yù)測(cè)能夠成為python腳本性能分析中的一個(gè)因素。Python畢竟是一門高級(jí)語言。

因此,如果不是分支預(yù)測(cè)的原因,那為什么 slow.py 會(huì)這么慢?通過一點(diǎn)研究,經(jīng)過一些“失敗的開端”之后,我覺得自己找到了問題。這個(gè)答案需要對(duì)Python內(nèi)部虛擬機(jī)有點(diǎn)熟悉。

失敗的開端:列表vs.生成器(lists and generators)

我的第一想法是Python對(duì)排序的列表[i for i in range(1000000)] 的處理效率要比隨機(jī)列表高。換句話說,這個(gè)列表可以用下面的生成器替代:

def numbers():
  i = 0
  while i < 1000000:
    yield i
    i += 1

我想這可能在時(shí)間效率上更高效些。畢竟,如果Python在內(nèi)部使用生成器替代真正的列表可以避免在內(nèi)存中一次保存所有整數(shù)的麻煩,這可以節(jié)省很多開銷。slow.py 中的隨機(jī)列表不能輕易的被一個(gè)簡單生成器捕獲,所有VM(虛擬機(jī))無法進(jìn)行這樣的優(yōu)化。

然而,這不是一個(gè)有用的發(fā)現(xiàn)。如果在slow.py的 shuffle() 和循環(huán)之間插入 a.sort(),程序會(huì)像 fast.py一樣快。很明顯,數(shù)字排序后的一些細(xì)節(jié)讓程序更快。

失敗的開端:列表對(duì)比數(shù)組

我的第二個(gè)想法是有可能數(shù)據(jù)結(jié)構(gòu)造成的緩存問題。a 是一個(gè)列表,這自然讓我相信a實(shí)際上是通過鏈表來實(shí)現(xiàn)的。如果shuffle操作故意隨機(jī)化這個(gè)鏈表的節(jié)點(diǎn),那么 fast.py 可能可以把列表的所有鏈表元素分配在相鄰地址,從而采用高級(jí)局部緩存,而slow.py會(huì)出現(xiàn)很多緩存未命中的情況,因?yàn)槊總€(gè)節(jié)點(diǎn)引用不在同一個(gè)緩存行上的另外一個(gè)節(jié)點(diǎn)。

不幸的是,這也不對(duì)。Python的列表對(duì)象不是鏈接的列表,而是真正意義上的數(shù)組。尤其是用C結(jié)構(gòu)體定義了Python列表對(duì)象:
 

typedef struct {
 PyObject_VAR_HEAD
 PyObject **ob_item;
 Py_ssize_t allocated;
} PyListObject;

……換句話說,ob_item 是一個(gè)指向PyObjects指針數(shù)組的指針,并且分配的大小是我們分配給數(shù)組的大小。因此,這對(duì)于解決這個(gè)問題也沒幫助(盡管這對(duì)我不確定Python中關(guān)于列表操作的算法復(fù)雜度有些安慰:列表的添加操作算法復(fù)雜度是O(1),訪問任意列表元素的算法復(fù)雜度是O(1),等等)。我只是想說明為什么Guido選擇稱它們?yōu)榱斜怼發(fā)ists”而不是數(shù)組“arrays”,而實(shí)際上它們卻是數(shù)組。

解決辦法:整體對(duì)象

數(shù)組元素在內(nèi)存中是相鄰的,因此這樣的數(shù)據(jù)結(jié)構(gòu)不會(huì)帶來緩存問題。事實(shí)證明緩存位置是 slow.py 變慢的原因,但這來自于一個(gè)意料之外的地方。在Python中,整數(shù)是分配在堆中的對(duì)象而不是一個(gè)簡單的值。尤其是在虛擬機(jī)中,整數(shù)對(duì)象看起來像下面這樣:
 

typedef struct {
 PyObject_HEAD
 long ob_ival;
} PyIntObject;

上面結(jié)構(gòu)體中唯一“有趣”的元素是ob_ival(類似于C語言中的整數(shù))。如果你覺得使用一個(gè)完整的堆對(duì)象來實(shí)現(xiàn)整數(shù)很浪費(fèi),你也許是對(duì)的。很多語言就為了避免這樣而做優(yōu)化。例如 Matz的 Ruby 解釋器通常以指針的方式存儲(chǔ)對(duì)象,但是對(duì)頻繁使用的指針做例外處理。簡單來說,Ruby解釋器把定長數(shù)作為對(duì)象應(yīng)用塞到同樣的空間,并用最低有效位來標(biāo)記這是一個(gè)整數(shù)而不是一個(gè)指針(在所有現(xiàn)代系統(tǒng)中,malloc總是返回以2的倍數(shù)對(duì)齊的內(nèi)存地址)。在那時(shí),你只需要通過合適的位移來獲取整數(shù)的值——不需要堆位置或者重定向。如果CPython做類似的優(yōu)化,slow.py 和 fast.py 會(huì)有同樣的速度(而且他們可能都會(huì)更快)。

那么CPython是怎樣處理整數(shù)的呢?解釋器的什么行為給我們?nèi)绱硕嗟囊苫??Python解釋器每次將整數(shù)分配到40Byte的“塊”中(block)。當(dāng)Python需要生成新的整型對(duì)象時(shí),就在當(dāng)前的整數(shù)“塊”中開辟下一個(gè)可用空間,并將整數(shù)存儲(chǔ)在其中。我們的代碼在數(shù)組中分配一百萬個(gè)整數(shù),大部分相鄰的整數(shù)會(huì)被放到相鄰的內(nèi)存中。因此,在有序的一百萬個(gè)數(shù)中遍歷展現(xiàn)出不錯(cuò)的緩存定位,而在隨機(jī)排序的前一百萬個(gè)數(shù)中定位出現(xiàn)頻繁的緩存未命中。

因此,“為什么對(duì)數(shù)組排序使得代碼更快”的答案就是它根本沒有這個(gè)作用。沒有打亂順序的數(shù)組遍歷的速度更快,因?yàn)槲覀冊(cè)L問整型對(duì)象的順序和分配的順序一致(他們必須被分配)。

相關(guān)文章

  • PyTorch在Windows環(huán)境搭建的方法步驟

    PyTorch在Windows環(huán)境搭建的方法步驟

    這篇文章主要介紹了PyTorch在Windows環(huán)境搭建的方法步驟,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-05-05
  • Django admin禁用編輯鏈接和添加刪除操作詳解

    Django admin禁用編輯鏈接和添加刪除操作詳解

    今天小編就為大家分享一篇Django admin禁用編輯鏈接和添加刪除操作詳解,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2019-11-11
  • Pytorch中的variable, tensor與numpy相互轉(zhuǎn)化的方法

    Pytorch中的variable, tensor與numpy相互轉(zhuǎn)化的方法

    這篇文章主要介紹了Pytorch中的variable, tensor與numpy相互轉(zhuǎn)化的方法,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-10-10
  • 使用XML庫的方式,實(shí)現(xiàn)RPC通信的方法(推薦)

    使用XML庫的方式,實(shí)現(xiàn)RPC通信的方法(推薦)

    下面小編就為大家?guī)硪黄褂肵ML庫的方式,實(shí)現(xiàn)RPC通信的方法(推薦)。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2017-06-06
  • Python基于yaml文件配置logging日志過程解析

    Python基于yaml文件配置logging日志過程解析

    這篇文章主要介紹了Python基于yaml文件配置logging日志過程解析,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-06-06
  • Python操作MySQL簡單實(shí)現(xiàn)方法

    Python操作MySQL簡單實(shí)現(xiàn)方法

    這篇文章主要介紹了Python操作MySQL簡單實(shí)現(xiàn)方法,通過一個(gè)簡單的實(shí)例講述了Python針對(duì)mysql數(shù)據(jù)庫的增刪改查技巧,需要的朋友可以參考下
    2015-01-01
  • python實(shí)現(xiàn)json文件的增刪改操作方法

    python實(shí)現(xiàn)json文件的增刪改操作方法

    這篇文章主要介紹了python實(shí)現(xiàn)json文件的增刪改操作,本文通過示例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2023-06-06
  • python利用lxml庫剩下操作svg圖片

    python利用lxml庫剩下操作svg圖片

    在大多數(shù)場(chǎng)景中,我們都用?lxml?庫解析網(wǎng)頁源碼,但你是否知道,lxml?庫也是可以操作?svg?圖片的。本文就來和大家聊聊具體操作方法,希望對(duì)大家有所幫助
    2023-01-01
  • 詳解使用Python寫一個(gè)向數(shù)據(jù)庫填充數(shù)據(jù)的小工具(推薦)

    詳解使用Python寫一個(gè)向數(shù)據(jù)庫填充數(shù)據(jù)的小工具(推薦)

    這篇文章主要介紹了用Python寫一個(gè)向數(shù)據(jù)庫填充數(shù)據(jù)的小工具,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-09-09
  • 如何用Python一次性下載抖音上音樂

    如何用Python一次性下載抖音上音樂

    不知道什么時(shí)候開始,中國出現(xiàn)了南抖音、北快手的互文格局。喜歡抖音主要是兩個(gè)初衷,學(xué)做菜聽音樂。抖音捧紅了很多人,也讓很多本不怎么讓大家熟知的歌曲、BGM,經(jīng)過翻唱、混剪與視頻搭配,從而傳播大街小巷。有沒有想過將這些好聽的剪輯批量下載下來呢?
    2021-05-05

最新評(píng)論