Python的内置数据结构

日常编程，只要涉及对数据的操作就离不开数据结构，无论是自己实现的优化还是直接使用编程语言自带的数据结构。Python、Go、Java都以库或语言内置的形式提供强大的数据结构。本文分享Python的数据结构的用法和技巧。通常情况下编程语言自带的数据结构性能都很好，经得起考验，通常使用它而不是自己实现，除非出于某种场景的优化或通过再写而满足特定需求。

Python内置丰富的数据结构，在日常编程时一般不用自己重复造轮子，当然，为了满足丰富的场景需求，复杂的数据结构还是需要自己实现的，比如Flask Web框架中的HTTP工具werkzeug就实现了很多自己的数据结构以方便使用。Python实现的数据结构除了数据结构本身外，还要让其显得Pythonic。比如：实现一个容器或序列数据结构Seq，在Pythonic的方式是通过len(Seq)取得数据结构的长度，而不是通过Seq.length()等方式。这和Java很不同！今天总结Python的数据结构，以及谈谈如何实现Pythonic的数据结构。

Python数据结构的特点

Python数据结构有几个特点，包括约定的特殊方法框架（典型的方法包括__len__），内置的数据结构支持推导式，迭代器和生成器等。下面一一讲述。

特殊方法

Python的特殊方法可以看做是Python类型系统的框架，该框架定义了获取特殊值的方法名，例如：

• __len__ 获取对象长度

• __hash__ 获取可哈希对象的哈希值

• __contains__ item in container操作的实现

• __setitem__ 切片操作

• __gt__ 对象大小比较，还有其它用于比较的特殊方法

等等。要让Python实现的数据结构更Pythonic，需要充分利用特殊方法的优势。接下来会讲到。

这些特殊方法统一了Python类型系统中获取相关属性和相关操作的实现。这样的好处是，不管什么类型，我们要获取某一属性或操作都可以使用内置函数激活。

推导式

Python内置的数据结构都支持推导式。

• list

>>> numbers = [num for num in range(1, 11) if num % 2 == 0]
>>> numbers
[2, 4, 6, 8, 10]
>>> pb = [(c, f) for c in range(1, 14) for f in 'ABCD']
>>> pb
[(1, 'A'), (1, 'B'), (1, 'C'), (1, 'D'), (2, 'A'), (2, 'B'), (2, 'C'), (2, 'D'), (3, 'A'), (3, 'B'), (3, 'C'), (3, 'D'), (4, 'A'), (4, 'B'), (4, 'C'), (4, 'D'), (5, 'A'), (5, 'B'), (5, 'C'), (5, 'D'), (6, 'A'), (6, 'B'), (6, 'C'), (6, 'D'), (7, 'A'), (7, 'B'), (7, 'C'), (7, 'D'), (8, 'A'), (8, 'B'), (8, 'C'), (8, 'D'), (9, 'A'), (9, 'B'), (9, 'C'), (9, 'D'), (10, 'A'), (10, 'B'), (10, 'C'), (10, 'D'), (11, 'A'), (11, 'B'), (11, 'C'), (11, 'D'), (12, 'A'), (12, 'B'), (12, 'C'), (12, 'D'), (13, 'A'), (13, 'B'), (13, 'C'), (13, 'D')]

• tuple

元组的推导式返回生成器。

>>> i = (n for n in range(1, 11) if n % 2 == 0)
>>> i
<generator object <genexpr> at 0x00000178D3163410>
>>> type(i)
<class 'generator'>
>>> list(i)
[2, 4, 6, 8, 10]

• dict

>>> d = {i: j for i, j in zip('123', 'abc')}
>>> d
{'1': 'a', '3': 'c', '2': 'b'}
>>> 

• set

>>> numbers = {num for num in range(1, 11) if num % 2 == 0}
>>> numbers
{8, 2, 10, 4, 6}
>>> 

这就是推导式的基本用法，在复杂的场景下，可以通过嵌套使用上面的推导式以方便解决问题。但要考虑简便和可读性的平衡。

内建实现和库实现

像dict、list、set这些数据结构及其方法的底层实现都是使用C语言，内置于Python的解析器中，即使没有标准库也可以使用，可以从源码看到它们的具体实现。这样的数据结构称为内建实现。数据结构如果来自标准库，例如collections.defaultdict，称为库实现。需要注意的是，有些库看似是库实现，实质是C实现，例如array模块就是C语言实现，而array.array的底层也是C语言。

>>> array
<module 'array' (built-in)>
>>> collections
<module 'collections' from '~\\lib\\collections\\__init__.py'>
>>> 

迭代器和生成器

• 什么是迭代器？

• 什么是生成器？

Python内置的所有数据结构都可以迭代。用户自定义数据结构也可以通过实现迭代器协议（实现__iter__和__next__方法 ）实现迭代操作。生成器是实现yield语法的函数。

内建数据结构

str、bytes、bytearray、array.array、tuple、list、dict、memoryview、set、frozenset、代理数据结构ProxyTypes。

• str
• bytes
• bytearray
• array.array
• tuple
• list
• dict
• memoryview
• set
• frozenset
• 代理数据结构ProxyTypes

来自collections库的数据结构

collections模块中常用的数据结构有：deque, defaultdict, namedtuple, UserDict, UserList, UserString, Counter, OrderedDict, ChainMap, ByteString 。

view类：MappingView, KeysView, ItemsView, ValuesView

其他的类：Awaitable, Coroutine, AsyncIterable, AsyncIterator, Hashable, Iterable, Iterator, Generator, Sized, Container, Callable, Set, MutableSet, Mapping, MutableMapping, Sequence, MutableSequence 都是抽象类。

collections.abc包括了自定义数据机构的抽象基类。collections的类都是具体可用的。

• namedtuple

namedtuple的使用在交互式下

>>> Person = collections.namedtuple('Person', 'age sex job name')
>>> Person
<class '__main__.Person'>
>>> p = Person(21, 1, 'Enginer', 'allen')
>>> p
Person(age=21, sex=1, job='Enginer', name='allen')
>>> print(p.age)
21
>>> print(p.name)
allen
>>> p._asdict()
OrderedDict([('age', 21), ('sex', 1), ('job', 'Enginer'), ('name', 'allen')])
>>> p._make((22, 0, "Teacher", "gopher"))
Person(age=22, sex=0, job='Teacher', name='gopher')
>>> 

对于一些简单的类，没有方法，只有属性，可以使用namedtuple来代替。这样可以节省空间。

class Person:
      def __init__(self, name, sex, job, age):
          self.name = name
        self.sex = sex
        self.job = job
        self.age = age
        
# 替代方案
Person = collections.namedtuple('Person', 'age sex job name')

类维护属性需要使用字典，而namedtuple并不需要，这就是节省空间的原因所在。

• defaultdict

defaultdict用于指定当键为空时，创建默认值的类型。

一个具体的例子：根据文件的哈希值归类文件（实际就是找出相同的文件）

import collections

def find_same_files(files):
    filemap = collections.defaultdict(list)
    for file in files:
        hash = sum_hash(file)
        filemap[hash].append(file)
    return filemap

• deque

deque是双端队列，兼容list对象的所有方法，同时添加常见的方法：’extendleft’, ‘maxlen’, ‘popleft’, ‘appendleft’, ‘rotate’。

>>> from collections import deque
>>> d = deque(maxlen=5)
>>> d
deque([], maxlen=5)
>>> d.append(2)
>>> d
deque([2], maxlen=5)
>>> d.appendleft(1)
>>> d
deque([1, 2], maxlen=5)
>>> d.extend([3, 4, 5])
>>> d
deque([1, 2, 3, 4, 5], maxlen=5)
>>> d.append(6)
>>> d
deque([2, 3, 4, 5, 6], maxlen=5)
>>> d.rotate(3)
>>> d
deque([4, 5, 6, 2, 3], maxlen=5)
>>> d.rotate(-3)
>>> d
deque([2, 3, 4, 5, 6], maxlen=5)
>>> 

deque既可以当做栈（LIFO）使用，也可以当做队列（FIFO）使用。当在编写功能代码时需要这两种数据结构，优先使用deque或通过它做扩展。

演示下它的使用。

• Counter

  Counter是一个基数统计类，常用于简单的基数统计。Counter调用后返回一个字典对象，包括常规的字典方法，另外还有most_common方法，返回出现频率最高的基数和统计频次。可以输入一个整形参数n，表示返回前n个最常出现的统计频次。下面是交互式下演示：

  >>> from collections import Counter
  >>> s = 'The ORM is in contrast to the SQLAlchemy Expression Language, upon which the ORM is constructed. '
  >>> c = Counter(s)
  >>> c
  Counter({' ': 16, 'e': 7, 't': 7, 'n': 6, 's': 6, 'h': 6, 'i': 5, 'c': 5, 'o': 5, 'a': 3, 'u': 3, 'r': 3, 'M': 2, 'L': 2, 'p': 2, 'R': 2, 'g': 2, 'O': 2, 'S': 1, 'T': 1, 'x': 1, 'l': 1, '.': 1, ',': 1, 'd': 1, 'Q': 1, 'A': 1, 'E': 1, 'y': 1, 'm': 1, 'w': 1})
  >>> c.most_common(2)
  [(' ', 16), ('e', 7)]
  >>> c.most_common(1)
  [(' ', 16)]

• OrderedDict

• ChainMap

• UserDict、UserList、UserString

用于多进程的queue

• multiprocessing.Queue

• multiprocessing.SimpleQueue

• multiprocessing.JoinableQueue

用于线程并发的queue

• queue.Queue

• queue.PriorityQueue

• queue.LifoQueue

用于协程并发的queue

• asyncio.Queue

• asyncio.PriorityQueue

• asyncio.LifoQueue

弱引用数据结构

• weakref.WeakKeyDictionary

• weakref.WeakValueDictionary

• weakref.WeakSet

自定义数据结构

本部分综合上述的内容实现一个LRUCache。

class LRUCache(collections.MutableMapping):
    """This class is not thread safe"""

    def __init__(self, timeout=60, close_callback=None, *args, **kwargs):
        self.timeout = timeout
        self.close_callback = close_callback
        self._store = {}
        self._time_to_keys = collections.defaultdict(list)
        self._keys_to_last_time = {}
        self._last_visits = collections.deque()
        self._closed_values = set()
        self.update(dict(*args, **kwargs))  # use the free update to set keys

    def __getitem__(self, key):
        # O(1)
        t = time.time()
        self._keys_to_last_time[key] = t
        self._time_to_keys[t].append(key)
        self._last_visits.append(t)
        return self._store[key]

    def __setitem__(self, key, value):
        # O(1)
        t = time.time()
        self._keys_to_last_time[key] = t
        self._store[key] = value
        self._time_to_keys[t].append(key)
        self._last_visits.append(t)

    def __delitem__(self, key):
        # O(1)
        del self._store[key]
        del self._keys_to_last_time[key]

    def __iter__(self):
        return iter(self._store)

    def __len__(self):
        return len(self._store)

    def sweep(self):
        # O(m)
        now = time.time()
        c = 0
        while len(self._last_visits) > 0:
            least = self._last_visits[0]
            if now - least <= self.timeout:
                break
            if self.close_callback is not None:
                for key in self._time_to_keys[least]:
                    if key in self._store:
                        if now - self._keys_to_last_time[key] > self.timeout:
                            value = self._store[key]
                            if value not in self._closed_values:
                                self.close_callback(value)
                                self._closed_values.add(value)
            for key in self._time_to_keys[least]:
                self._last_visits.popleft()
                if key in self._store:
                    if now - self._keys_to_last_time[key] > self.timeout:
                        del self._store[key]
                        del self._keys_to_last_time[key]
                        c += 1
            del self._time_to_keys[least]
        if c:
            self._closed_values.clear()
            logging.debug('%d keys swept' % c)

总结

转载请包括本文地址：https://allenwind.github.io/blog/5004
更多文章请参考：https://allenwind.github.io/blog/archives/