Python中的高级数据结构_程序人生

Python中的高级数据结构

admin

2023-07-31 00:48:14

0次

数据结构

数据结构的概念很好理解，就是用来将数据组织在一起的结构。换句话说，数据结构是用来存储一系列关联数据的东西。在Python中有四种内建的数据结构，分别是List、Tuple、Dictionary以及Set。大部分的应用程序不需要其他类型的数据结构，但若是真需要也有很多高级数据结构可供选择，例如Collection、Array、Heapq、Bisect、Weakref、Copy以及Pprint。本文将介绍这些数据结构的用法，看看它们是如何帮助我们的应用程序的。

关于四种内建数据结构的使用方法很简单，并且网上有很多参考资料，因此本文将不会讨论它们。

1. Collections

collections模块包含了内建类型之外的一些有用的工具，例如Counter、defaultdict、OrderedDict、deque以及nametuple。其中Counter、deque以及defaultdict是最常用的类。

1.1 Counter()

如果你想统计一个单词在给定的序列中一共出现了多少次，诸如此类的操作就可以用到Counter。来看看如何统计一个list中出现的item次数：

12345

from collections import Counter li = ["Dog", "Cat", "Mouse", 42, "Dog", 42, "Cat", "Dog"]a = Counter(li)print a # Counter({'Dog': 3, 42: 2, 'Cat': 2, 'Mouse': 1})

若要统计一个list中不同单词的数目，可以这么用：

1234567

from collections import Counter li = ["Dog", "Cat", "Mouse", 42, "Dog", 42, "Cat", "Dog"]a = Counter(li)print a # Counter({'Dog': 3, 42: 2, 'Cat': 2, 'Mouse': 1}) print len(set(li)) # 4

如果需要对结果进行分组，可以这么做：

12345678910

from collections import Counter li = ["Dog", "Cat", "Mouse","Dog","Cat", "Dog"]a = Counter(li) print a # Counter({'Dog': 3, 'Cat': 2, 'Mouse': 1}) print "{0} : {1}".format(a.values(),a.keys()) # [1, 3, 2] : ['Mouse', 'Dog', 'Cat'] print(a.most_common(3)) # [('Dog', 3), ('Cat', 2), ('Mouse', 1)]

以下的代码片段找出一个字符串中出现频率最高的单词，并打印其出现次数。

123456789101112131415161718192021222324252627282930313233343536

import refrom collections import Counter string = """ Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nunc ut elit id mi ultricies adipiscing. Nulla facilisi. Praesent pulvinar, sapien vel feugiat vestibulum, nulla dui pretium orci, non ultricies elit lacus quis ante. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Aliquam pretium ullamcorper urna quis iaculis. Etiam ac massa sed turpis tempor luctus. Curabitur sed nibh eu elit mollis congue. Praesent ipsum diam, consectetur vitae ornare a, aliquam a nunc. In id magna pellentesque tellus posuere adipiscing. Sed non mi metus, at lacinia augue. Sed magna nisi, ornare in mollis in, mollis sed nunc. Etiam at justo in leo congue mollis. Nullam in neque eget metus hendrerit scelerisque eu non enim. Ut malesuada lacus eu nulla bibendum id euismod urna sodales. """ words = re.findall(r'\\w+', string) #This finds words in the document lower_words = [word.lower() for word in words] #lower all the words word_counts = Counter(lower_words) #counts the number each time a word appearsprint word_counts # Counter({'elit': 5, 'sed': 5, 'in': 5, 'adipiscing': 4, 'mollis': 4, 'eu': 3, # 'id': 3, 'nunc': 3, 'consectetur': 3, 'non': 3, 'ipsum': 3, 'nulla': 3, 'pretium':# 2, 'lacus': 2, 'ornare': 2, 'at': 2, 'praesent': 2, 'quis': 2, 'sit': 2, 'congue': 2, 'amet': 2, # 'etiam': 2, 'urna': 2, 'a': 2, 'magna': 2, 'lorem': 2, 'aliquam': 2, 'ut': 2, 'ultricies': 2, 'mi': 2, # 'dolor': 2, 'metus': 2, 'ac': 1, 'bibendum': 1, 'posuere': 1, 'enim': 1, 'ante': 1, 'sodales': 1, 'tellus': 1,# 'vitae': 1, 'dui': 1, 'diam': 1, 'pellentesque': 1, 'massa': 1, 'vel': 1, 'nullam': 1, 'feugiat': 1, 'luctus': 1, # 'pulvinar': 1, 'iaculis': 1, 'hendrerit': 1, 'orci': 1, 'turpis': 1, 'nibh': 1, 'scelerisque': 1, 'ullamcorper': 1,# 'eget': 1, 'neque': 1, 'euismod': 1, 'curabitur': 1, 'leo': 1, 'sapien': 1, 'facilisi': 1, 'vestibulum': 1, 'nisi': 1, # 'justo': 1, 'augue': 1, 'tempor': 1, 'lacinia': 1, 'malesuada': 1})

1.2 Deque

Deque是一种由队列结构扩展而来的双端队列(double-ended queue)，队列元素能够在队列两端添加或删除。因此它还被称为头尾连接列表(head-tail linked list)，尽管叫这个名字的还有另一个特殊的数据结构实现。

Deque支持线程安全的，经过优化的append和pop操作，在队列两端的相关操作都能够达到近乎O(1)的时间复杂度。虽然list也支持类似的操作，但是它是对定长列表的操作表现很不错，而当遇到pop(0)和insert(0, v)这样既改变了列表的长度又改变其元素位置的操作时，其复杂度就变为O(n)了。

来看看相关的比较结果：

123456789101112131415161718192021222324252627282930313233343536373839404142434445

import timefrom collections import deque num = 100000 def append(c): for i in range(num): c.append(i) def appendleft(c): if isinstance(c, deque): for i in range(num): c.appendleft(i) else: for i in range(num): c.insert(0, i)def pop(c): for i in range(num): c.pop() def popleft(c): if isinstance(c, deque): for i in range(num): c.popleft() else: for i in range(num): c.pop(0) for container in [deque, list]: for operation in [append, appendleft, pop, popleft]: c = container(range(num)) start = time.time() operation(c) elapsed = time.time() –

上一篇：我不能胜任开发开源软件

下一篇：Pyston：Dropbox 正开发的开源 Python 解释器

Python中的高级数据结构

数据结构

1. Collections

1.1 Counter()

1.2 Deque

相关内容

热门资讯