有哪些用Python語言講算法和數(shù)據(jù)結(jié)構(gòu)的書？《用Python解決數(shù)據(jù)結(jié)構(gòu)與算法問題》，一本免費(fèi)的算法書，強(qiáng)烈推薦。學(xué)習(xí)Python語法和API是遠(yuǎn)遠(yuǎn)不夠的。掌握算法和數(shù)據(jù)結(jié)構(gòu)這些永不過時(shí)的核心技能，

有哪些用Python語言講算法和數(shù)據(jù)結(jié)構(gòu)的書？

《用Python解決數(shù)據(jù)結(jié)構(gòu)與算法問題》，一本免費(fèi)的算法書，強(qiáng)烈推薦。學(xué)習(xí)Python語法和API是遠(yuǎn)遠(yuǎn)不夠的。掌握算法和數(shù)據(jù)結(jié)構(gòu)這些永不過時(shí)的核心技能，是決定一個(gè)程序員的關(guān)鍵因素。;的職業(yè)發(fā)展。算法和數(shù)據(jù)結(jié)構(gòu)對(duì)于職業(yè)程序員來說非常重要。對(duì)于同一個(gè)問題，不同算法的效率千差萬別。問題規(guī)模小的時(shí)候你可能感覺不到，但是一旦數(shù)據(jù)上升到TB級(jí)別，兩者的差距就像西瓜和芝麻的區(qū)別。

舉個(gè)簡(jiǎn)單的例子:我們要計(jì)算前n個(gè)整數(shù)的和，你想到的第一個(gè)算法可能是迭代。代碼很直觀，初學(xué)者也能讀懂，就是從1到n，得到最后的結(jié)果。這個(gè)算法的效率隨著n的增加而變化，時(shí)間復(fù)雜度為O(n)，線性時(shí)間大O表示最壞情況下的運(yùn)行時(shí)間。

試想，當(dāng)這個(gè)數(shù)字足夠大的時(shí)候，花費(fèi)的時(shí)間將是不可估量的。當(dāng)然，比線性時(shí)間差的算法還有很多。當(dāng)然最后還是有一個(gè)理想的算法，就是恒水平，O(1)恒水平復(fù)雜度。也就是說，程序的運(yùn)行時(shí)間與要處理的數(shù)據(jù)大小無關(guān)。

如果前n個(gè)整數(shù)的和是用數(shù)學(xué)方程而不是迭代計(jì)算的，其復(fù)雜度為O(1)。很榮幸回答你的問題。以下是這本書的目錄。希望對(duì)你有幫助！

如何理解Python中的集合和字典？

字典和集合是高度優(yōu)化的數(shù)據(jù)結(jié)構(gòu)，特別是對(duì)于查找、添加和刪除操作。本節(jié)將通過示例介紹它們?cè)谔囟▓?chǎng)景中的性能，并將它們與列表等其他數(shù)據(jù)結(jié)構(gòu)進(jìn)行比較。

例如，有一個(gè)存儲(chǔ)產(chǎn)品信息(產(chǎn)品ID、名稱和價(jià)格)的列表，現(xiàn)在的需求是借助產(chǎn)品ID找出價(jià)格。實(shí)現(xiàn)代碼如下:

定義查找_產(chǎn)品_價(jià)格(產(chǎn)品，product_id):

對(duì)于身份證，價(jià)格在products:

如果我是product_id:

退貨價(jià)格

不返回

產(chǎn)品[

(111, 100),

(222, 30),

(333, 150)

]

打印(產(chǎn)品222的價(jià)格是{}。格式(find_product_price(products，222)))

運(yùn)行結(jié)果如下:

產(chǎn)品222的價(jià)格是30英鎊

在上述程序的基礎(chǔ)上，如果鏈表有n個(gè)元素，因?yàn)闄z查搜索過程需要遍歷列表，所以最壞情況下的時(shí)間復(fù)雜度是O(n)。即使先對(duì)列表進(jìn)行排序，再使用二分搜索法算法，也要O(logn)時(shí)間復(fù)雜度，更不用說O(nlogn)時(shí)間對(duì)列表進(jìn)行排序了。

但是如果用字典來存儲(chǔ)這些數(shù)據(jù)，那么查找會(huì)非常方便高效，而且可以用O(1)的時(shí)間復(fù)雜度來完成，因?yàn)椴恍枰闅v字典，直接通過鍵的哈希值就可以找到對(duì)應(yīng)的值。實(shí)現(xiàn)代碼如下:

產(chǎn)品{

111: 100，

222: 30，

333: 150

}

打印(產(chǎn)品222的價(jià)格是{}。格式(產(chǎn)品[222])

運(yùn)行結(jié)果如下:

產(chǎn)品222的價(jià)格是30英鎊

有些讀者可能對(duì)時(shí)間復(fù)雜性沒有直觀的理解。它不 沒關(guān)系。我再給你舉個(gè)例子。在下面的代碼中，初始化100，000個(gè)元素的產(chǎn)品，分別計(jì)算使用list和set統(tǒng)計(jì)產(chǎn)品價(jià)格數(shù)量的運(yùn)行時(shí)間:

#統(tǒng)計(jì)時(shí)間需要使用時(shí)間模塊中的函數(shù)，就知道了。

導(dǎo)入時(shí)間

def find_unique_price_using_list(products):

唯一價(jià)格列表[]

對(duì)于_，products:的價(jià)格# A

如果價(jià)格不在unique_pric: # B

唯一價(jià)格(價(jià)格)

return len(唯一價(jià)格列表)

id[范圍(0，100000)中x的x]

價(jià)格[x對(duì)x，在范圍(200000，300000)內(nèi)]

產(chǎn)品列表(郵政編碼(id，價(jià)格))

#計(jì)算列表版本的時(shí)間

start_using_list _counter()

查找_唯一_價(jià)格_使用_列表(產(chǎn)品)

end_using_list _count: { }打印(經(jīng)過的時(shí)間)。格式(end_using_list - start_using_list))

#使用集合做同樣的工作

def find_unique_price_using_set(products):

unique_price_set集合()

對(duì)于_，products:的價(jià)格

唯一價(jià)格(價(jià)格)

return len(唯一價(jià)格集)

#計(jì)算集合版本的時(shí)間

啟動(dòng)使用設(shè)置計(jì)數(shù)器()

查找_唯一_價(jià)格_使用_集合(產(chǎn)品)

end_using_set _count: { }打印(經(jīng)過的時(shí)間)。格式(結(jié)束使用設(shè)置-開始使用設(shè)置)

運(yùn)行結(jié)果如下:

使用list: 68的時(shí)間流逝。56866 . 66666666667

使用s: 0.01表示時(shí)間流逝。58660.08888888861

可見兩者在只有10萬條數(shù)據(jù)的情況下，速度相差如此之大。而企業(yè)的后臺(tái)數(shù)據(jù)往往是幾億甚至幾十億的量級(jí)。因此，如果使用不合適的數(shù)據(jù)結(jié)構(gòu)，很容易導(dǎo)致服務(wù)器崩潰，不僅影響用戶體驗(yàn)，還會(huì)給公司帶來巨大的財(cái)產(chǎn)損失。

那么，為什么字典和收藏的效率如此之高，尤其是查找、插入和刪除的操作？

字典和收藏的工作原理。

字典和集合的效率與其內(nèi)部數(shù)據(jù)結(jié)構(gòu)密切相關(guān)。與其他數(shù)據(jù)結(jié)構(gòu)不同，字典和集合的內(nèi)部結(jié)構(gòu)是哈希表:

對(duì)于字典來說，這個(gè)表存儲(chǔ)三個(gè)元素:散列、鍵和值。

對(duì)于集合，哈希表中只存儲(chǔ)一個(gè)元素。

對(duì)于以前版本的Python，其哈希表結(jié)構(gòu)如下:

|哈希值(哈希)鍵值(值)

。|...

0 |哈希0鍵0值0

。|...

1 | hash1 k:·邁克，多比科 1999-01-01，g:男}

然后，它將以類似于下面的形式存儲(chǔ):

條目[

[ - , - , - ]

[-230273521，出生日期，1999年1月1日]，

[ - , - , - ],

[ - , - , - ],

[1231236123，姓名，邁克]，

[ - , - , - ],

[9371539127，性別，男]

]

顯然，這是對(duì)存儲(chǔ)空間的極大浪費(fèi)。為了提高存儲(chǔ)空間的利用率，目前的哈希表除了字典本身的結(jié)構(gòu)之外，還會(huì)將索引與哈希值、鍵和值分開，就是下面這種結(jié)構(gòu):

指數(shù)

-

無|索引|無|無|索引|無|索引...

-

進(jìn)入

-

哈希0鍵0值0

-

hash1 key1值1

-

hash2鍵2值2

-

...

-

在此基礎(chǔ)上，上述字典在新哈希表結(jié)構(gòu)下的存儲(chǔ)形式為:

索引[無，1，無，無，0，無，2]

條目[

[1231236123，姓名，邁克]，

[-230273521，出生日期，1999年1月1日]，

[9371539127，性別，男]

]

通過對(duì)比可以發(fā)現(xiàn)，空間利用率有了很大的提高。

明確具體的設(shè)計(jì)結(jié)構(gòu)，然后分析如何使用哈希表完成數(shù)據(jù)的插入、查找和刪除。

哈希表插入數(shù)據(jù)

在向字典中插入數(shù)據(jù)時(shí)，Python會(huì)先根據(jù)鍵(通過hash(key)函數(shù))計(jì)算出相應(yīng)的哈希值，而在向集合中插入數(shù)據(jù)時(shí)，Python會(huì)根據(jù)元素本身(通過hash (value)函數(shù))計(jì)算出相應(yīng)的哈希值。

例如:

dic {nam:1}

打印(哈希(名稱))

s《哈希表詳解》一節(jié)中詳細(xì)了解。

哈希表查找數(shù)據(jù)

在哈希表中查找數(shù)據(jù)類似于插入操作。Python會(huì)根據(jù)哈希值找到元素在哈希表中應(yīng)該存放的位置，然后將其哈希值和key與該位置的元素進(jìn)行比較(集合直接比較元素值):

如果它們相等，就證明找到了；

另一方面證明了元素存儲(chǔ)的時(shí)候遇到了哈希，需要繼續(xù)用原來的方法解決哈希，直到找到元素或者找到空位。

這里發(fā)現(xiàn)的空白意味著目標(biāo)元素沒有存儲(chǔ)在哈希表中。

哈希表刪除元素

對(duì)于刪除操作，Python會(huì)臨時(shí)給這個(gè)位置的元素賦一個(gè)特殊值，然后在哈希表調(diào)整大小時(shí)刪除它。

應(yīng)該注意的是，哈希的發(fā)生通常會(huì)降低字典和集合操作的速度。因此，為了保證其效率，集合中的字典和哈希表通常會(huì)保證至少留有1/3的剩余空間。隨著元素的不斷插入，當(dāng)剩余空間不足1/3時(shí)，Python會(huì)重新獲得更多的內(nèi)存空間并擴(kuò)展哈希表，同時(shí)表中所有的元素位置都會(huì)重新排出。