Python中的數據結構

迄今爲止，我在數據結構上讀過的所有書籍似乎都使用C/C++，並大量使用它們提供的「手動」指針控件。由於Python隱藏了用戶的那種內存管理和垃圾收集，甚至有可能以這種語言實現高效的數據結構，並且是否有理由這樣做而不是使用內置？Python中的數據結構

來源

2009-12-31 cornjuliox

大多數C/C++結構「heav [ily]使用手動指針」，因爲他們必須這樣做，而不是因爲這樣做效率更高。 – notnoop 2009-12-31 19:13:00

的Python爲您提供了一些強大的，高度優化的數據結構，既作爲內置插件，也作爲標準庫中的幾個模塊的一部分（當然還有lists和dicts，還有tuples，sets，arrays，array和模塊collections中的一些其他容器）。這些數據結構的組合（以及可能來自幫助模塊的某些功能，如heapq和bisect）通常足以實現實際編程中可能需要的最豐富的結構;然而，這並非總是如此。當你需要比豐富的庫提供的東西更多的東西時，考慮一個事實，即一個對象的屬性（和集合中的項目）基本上是指向其他對象（不帶指針算術）的「指針」，即「可重複引用」， Python就像在Java中一樣。在Python中，您通常在屬性或項目中使用None值來表示在C++中使用NULL的含義，或者在Java中使用null。

因此，舉例來說，你可以實現通過例如二叉樹：

class Node(object): 

    __slots__ = 'payload', 'left', 'right' 

    def __init__(self, payload=None, left=None, right=None): 
    self.payload = payload 
    self.left = left 
    self.right = right

加上方法或遍歷功能和類似操作（__slots__類屬性是可選的 - 主要是一個內存優化，以避免每個實例攜帶它自己的__dict__，這將比三個所需的屬性/參考大得多）。可能最好由專用Python類來表示，而不是由其它現有的Python結構的直接成分的數據結構的

其它實例，包括tries（參見例如here）和graphs（參見例如here）。

來源

2009-12-31 20:37:01

對於一些簡單的數據結構（例如堆棧），您可以使用內置列表來完成您的工作。使用更復雜的結構（例如布隆過濾器），您必須使用語言支持的基元自己實現它們。

如果它們真的滿足您的需求，那麼您應該使用builtins，因爲它們在很長一段時間內都會被一羣人調試和優化。自己從頭開始可能會產生較差的數據結構。

但是，如果您需要一些不可用的基元，或者如果基元性能不夠好，您必須實現自己的類型。

像指針管理等細節只是實現對話，並沒有真正限制語言本身的能力。

來源

2009-12-31 19:16:30

C/C++數據結構手冊只是試圖教給你各種結構背後的基本原理 - 它們通常不建議你通過構建自己的棧和列表庫來實際出去並重新發明輪子。不管你使用的是Python，C++，C＃，Java等等，你都應該首先查看內置的數據結構。他們通常會使用相同的系統原語來實現，而這些原語你必須自己動手做，但是經過了嘗試和測試。

只有當提供的數據結構不允許你完成你所需要的，並且沒有可供選擇的可靠的庫時，你是否應該從頭開始構建一些東西（或者擴展提供的東西）。

來源

2009-12-31 19:18:24 csj

無論如何，Python如何處理低級對象並不太奇怪。 This document應該消除歧義;它基本上是你已經熟悉的所有指針邏輯。

來源

2009-12-31 19:20:19 avpx

在Python中實現類似C++向量的東西是不可能的，因爲您沒有像C/C++那樣的數組原語。然而，任何事情更復雜的可實施（有效），在它的上面，包括但不限於：鏈表，哈希表，多集，布隆過濾器等

來源

2009-12-31 19:20:59

我不熟悉C++向量的實現，但是Python列表類型*實現爲一個數組（http://bytes.com/topic/python/answers/101848-list-implementation）而不是鏈接名單。這不是什麼矢量基本上是什麼？ – 2009-12-31 19:24:28

是的，Python被實現爲一個數組（與C++向量相同）。我說的是你不能在* Python中實現你自己的列表*，除了現有的列表之外。 – 2009-12-31 19:35:02

嗯，python列表類型更像Java的ArrayList（即指向Object的指針數組）。 – 2009-12-31 19:45:28

使用Python，您可以訪問其他人編寫和調試的大量庫模塊。在某個地方的賠率非常好，有一個模塊至少可以完成你想要的一部分，而賠率甚至可以在C中用於執行。例如，如果你需要做矩陣運算，你可以使用NumPy，它是用C和Fortran編寫的。

Python足夠慢，如果您嘗試在本地Python中編寫某種真正計算密集的代碼（例如，快速傅里葉變換），您將不會很高興。另一方面，你可以得到一個C編碼的傅里葉變換作爲SciPy的一部分，並使用它。

我從來沒有遇到過要解決Python中的問題的情況，並且說：「補償，我不能表達我需要的數據結構。」

如果你是先驅者，並且你正在做一些Python中沒有任何庫模塊的東西，那麼你可以嘗試用純Python編寫它。如果速度夠快，就完成了。如果速度太慢，可以對其進行分析，找出緩慢部分的位置，然後使用Python C API將它們重寫爲C語言。我從來沒有需要這樣做。

來源

2009-12-31 21:38:52 steveha

Python中的數據結構

回答

相關問題