Python中的数据结构

Question

到目前为止,我读过的关于数据结构的所有书籍似乎都使用了C/C++,并大量使用了它们提供的"手动"指针控件.由于Python隐藏了来自用户的那种内存管理和垃圾收集,因此甚至可以用这种语言实现高效的数据结构,有没有理由这样做而不是使用内置函数？

Answer 1

Python为您提供了一些强大的,高度优化的数据结构,既可以作为内置函数,也可以作为标准库中的一些模块的一部分(当然,lists和dicts,以及模块数组中的tuple s,sets,arrays 和其他一些容器)在模块集合中).

这些数据结构的组合(以及来自helq模块的一些函数,例如heapq和bisect)通常足以实现现实生活中可能需要的更丰富的结构; 然而,这并非总是如此.

当你需要的东西比富库提供的更多时,考虑一下这样一个事实:对象的属性(和集合中的项)本质上是指向其他对象(没有指针算术)的"指针",即"可重复引用",在Python中就像在Java的.在Python中,通常使用None属性或项中的值来表示NULL在C++中意味着什么,或者null在Java中意味着什么.

因此,例如,您可以通过以下方式实现二叉树:

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__类属性是可选的 - 主要是内存优化,以避免每个Node实例携带自己的实例__dict__,这将大大大于三个所需的属性/引用).

可以最好地由专用Python类表示的数据结构的其他示例,而不是通过其他现有Python结构的直接组合,包括tries(参见例如这里)和graphs(参见例如这里).

Answer 2

对于一些简单的数据结构(例如堆栈),您可以使用内置列表来完成工作.对于更复杂的结构(例如布隆过滤器),您必须使用语言支持的基元自己实现它们.

你应该使用内置的,因为它们真的是为了你的目的,因为它们已经被很多人调试和优化了很长时间.自己从头开始这样做可能会产生一种劣质的数据结构.

但是,如果你需要一些不能用作原语的东西,或者如果原语表现不够好,你就必须实现自己的类型.

指针管理等细节只是实现谈话,并没有真正限制语言本身的功能.

Answer 3

C/C++数据结构书籍只是试图教你各种结构背后的基本原理 - 他们通常不建议你通过构建自己的堆栈和列表来实际出去并重新发明轮子.

无论您使用的是Python,C++,C#,Java还是其他什么,您都应该首先考虑内置的数据结构.它们通常使用您必须自己使用的相同系统原语来实现,但具有经过试验和测试的优点.

只有当提供的数据结构不允许您完成所需的内容时,并且没有可供您使用的替代且可靠的库,您是否应该从头开始构建某些内容(或扩展所提供的内容).