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中的数据结构

回答

相关问题