Python中的高级数据结构详解

这篇文章主要介绍了Python中的高级数据结构详解,本文讲解了Collection、Array、Heapq、Bisect、Weakref、Copy以及Pprint这些数据结构的用法,需要的朋友可以参考下

Python中的高级数据结构详解

Python中的高级数据结构详解
数据结构
Python中的高级数据结构详解

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

Python中的高级数据结构详解
Python中的高级数据结构详解
Python中的高级数据结构详解

Python中的高级数据结构详解
这四种内置数据结构的用法很简单,而且网上有很多参考资料,因此本文不再讨论它们。
[En]

The use of the four built-in data structures is simple, and there are many references online, so they will not be discussed in this article.

Python中的高级数据结构详解

Python中的高级数据结构详解
1. Collections
Python中的高级数据结构详解

Python中的高级数据结构详解
collections模块包含了内建类型之外的一些有用的工具,例如Counter、defaultdict、OrderedDict、deque以及nametuple。其中Counter、deque以及defaultdict是最常用的类。
Python中的高级数据结构详解

Python中的高级数据结构详解
1.1 Counter()
Python中的高级数据结构详解

Python中的高级数据结构详解
如果你想统计一个单词在给定的序列中一共出现了多少次,诸如此类的操作就可以用到Counter。来看看如何统计一个list中出现的item次数:
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
from collections import Counter
Python中的高级数据结构详解

Python中的高级数据结构详解
li = [“Dog”, “Cat”, “Mouse”, 42, “Dog”, 42, “Cat”, “Dog”]
Python中的高级数据结构详解
a = Counter(li)
Python中的高级数据结构详解
print a # Counter({‘Dog’: 3, 42: 2, ‘Cat’: 2, ‘Mouse’: 1})
Python中的高级数据结构详解

Python中的高级数据结构详解
若要统计一个list中不同单词的数目,可以这么用:
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
from collections import Counter
Python中的高级数据结构详解

Python中的高级数据结构详解
li = [“Dog”, “Cat”, “Mouse”, 42, “Dog”, 42, “Cat”, “Dog”]
Python中的高级数据结构详解
a = Counter(li)
Python中的高级数据结构详解
print a # Counter({‘Dog’: 3, 42: 2, ‘Cat’: 2, ‘Mouse’: 1})
Python中的高级数据结构详解

Python中的高级数据结构详解
print len(set(li)) # 4
Python中的高级数据结构详解

Python中的高级数据结构详解
如果需要对结果进行分组,可以这么做:
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
from collections import Counter
Python中的高级数据结构详解

Python中的高级数据结构详解
li = [“Dog”, “Cat”, “Mouse”,”Dog”,”Cat”, “Dog”]
Python中的高级数据结构详解
a = Counter(li)
Python中的高级数据结构详解

Python中的高级数据结构详解
print a # Counter({‘Dog’: 3, ‘Cat’: 2, ‘Mouse’: 1})
Python中的高级数据结构详解

Python中的高级数据结构详解
print “{0} : {1}”.format(a.values(),a.keys()) # [1, 3, 2] : [‘Mouse’, ‘Dog’, ‘Cat’]
Python中的高级数据结构详解

Python中的高级数据结构详解
print(a.most_common(3)) # [(‘Dog’, 3), (‘Cat’, 2), (‘Mouse’, 1)]
Python中的高级数据结构详解

Python中的高级数据结构详解
下面的代码片段查找字符串中最常用的单词,并打印该单词出现的次数。
[En]

The following code snippet finds the most frequent word in a string and prints the number of times it appears.

Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
import re
Python中的高级数据结构详解
from collections import Counter
Python中的高级数据结构详解

Python中的高级数据结构详解
string = “”” Lorem ipsum dolor sit amet, consectetur
Python中的高级数据结构详解
adipiscing elit. Nunc ut elit id mi ultricies
Python中的高级数据结构详解
adipiscing. Nulla facilisi. Praesent pulvinar,
Python中的高级数据结构详解
sapien vel feugiat vestibulum, nulla dui pretium orci,
Python中的高级数据结构详解
non ultricies elit lacus quis ante. Lorem ipsum dolor
Python中的高级数据结构详解
sit amet, consectetur adipiscing elit. Aliquam
Python中的高级数据结构详解
pretium ullamcorper urna quis iaculis. Etiam ac massa
Python中的高级数据结构详解
sed turpis tempor luctus. Curabitur sed nibh eu elit
Python中的高级数据结构详解
mollis congue. Praesent ipsum diam, consectetur vitae
Python中的高级数据结构详解
ornare a, aliquam a nunc. In id magna pellentesque
Python中的高级数据结构详解
tellus posuere adipiscing. Sed non mi metus, at lacinia
Python中的高级数据结构详解
augue. Sed magna nisi, ornare in mollis in, mollis
Python中的高级数据结构详解
sed nunc. Etiam at justo in leo congue mollis.
Python中的高级数据结构详解

Python中的高级数据结构详解
Nullam in neque eget metus hendrerit scelerisque
Python中的高级数据结构详解
eu non enim. Ut malesuada lacus eu nulla bibendum
Python中的高级数据结构详解
id euismod urna sodales. “””
Python中的高级数据结构详解

Python中的高级数据结构详解
words = re.findall(r’\w ‘, string) #This finds words in the document
Python中的高级数据结构详解

Python中的高级数据结构详解
lower_words = [word.lower() for word in words] #lower all the words
Python中的高级数据结构详解

Python中的高级数据结构详解
word_counts = Counter(lower_words) #counts the number each time a word appears
Python中的高级数据结构详解
print word_counts
Python中的高级数据结构详解

Python中的高级数据结构详解

Counter({‘elit’: 5, ‘sed’: 5, ‘in’: 5, ‘adipiscing’: 4, ‘mollis’: 4, ‘eu’: 3,

Python中的高级数据结构详解

‘id’: 3, ‘nunc’: 3, ‘consectetur’: 3, ‘non’: 3, ‘ipsum’: 3, ‘nulla’: 3, ‘pretium’:

Python中的高级数据结构详解

2, ‘lacus’: 2, ‘ornare’: 2, ‘at’: 2, ‘praesent’: 2, ‘quis’: 2, ‘sit’: 2, ‘congue’: 2, ‘amet’: 2,

Python中的高级数据结构详解

‘etiam’: 2, ‘urna’: 2, ‘a’: 2, ‘magna’: 2, ‘lorem’: 2, ‘aliquam’: 2, ‘ut’: 2, ‘ultricies’: 2, ‘mi’: 2,

Python中的高级数据结构详解

‘dolor’: 2, ‘metus’: 2, ‘ac’: 1, ‘bibendum’: 1, ‘posuere’: 1, ‘enim’: 1, ‘ante’: 1, ‘sodales’: 1, ‘tellus’: 1,

Python中的高级数据结构详解

‘vitae’: 1, ‘dui’: 1, ‘diam’: 1, ‘pellentesque’: 1, ‘massa’: 1, ‘vel’: 1, ‘nullam’: 1, ‘feugiat’: 1, ‘luctus’: 1,

Python中的高级数据结构详解

‘pulvinar’: 1, ‘iaculis’: 1, ‘hendrerit’: 1, ‘orci’: 1, ‘turpis’: 1, ‘nibh’: 1, ‘scelerisque’: 1, ‘ullamcorper’: 1,

Python中的高级数据结构详解

‘eget’: 1, ‘neque’: 1, ‘euismod’: 1, ‘curabitur’: 1, ‘leo’: 1, ‘sapien’: 1, ‘facilisi’: 1, ‘vestibulum’: 1, ‘nisi’: 1,

Python中的高级数据结构详解

‘justo’: 1, ‘augue’: 1, ‘tempor’: 1, ‘lacinia’: 1, ‘malesuada’: 1})

Python中的高级数据结构详解

Python中的高级数据结构详解
1.2 Deque
Python中的高级数据结构详解

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

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

Python中的高级数据结构详解
来看看相关的比较结果:
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
import time
Python中的高级数据结构详解
from collections import deque
Python中的高级数据结构详解

Python中的高级数据结构详解
num = 100000
Python中的高级数据结构详解

Python中的高级数据结构详解
def append(c):
Python中的高级数据结构详解
for i in range(num):
Python中的高级数据结构详解
c.append(i)
Python中的高级数据结构详解

Python中的高级数据结构详解
def appendleft(c):
Python中的高级数据结构详解
if isinstance(c, deque):
Python中的高级数据结构详解
for i in range(num):
Python中的高级数据结构详解
c.appendleft(i)
Python中的高级数据结构详解
else:
Python中的高级数据结构详解
for i in range(num):
Python中的高级数据结构详解
c.insert(0, i)
Python中的高级数据结构详解
def pop(c):
Python中的高级数据结构详解
for i in range(num):
Python中的高级数据结构详解
c.pop()
Python中的高级数据结构详解

Python中的高级数据结构详解
def popleft(c):
Python中的高级数据结构详解
if isinstance(c, deque):
Python中的高级数据结构详解
for i in range(num):
Python中的高级数据结构详解
c.popleft()
Python中的高级数据结构详解
else:
Python中的高级数据结构详解
for i in range(num):
Python中的高级数据结构详解
c.pop(0)
Python中的高级数据结构详解

Python中的高级数据结构详解
for container in [deque, list]:
Python中的高级数据结构详解
for operation in [append, appendleft, pop, popleft]:
Python中的高级数据结构详解
c = container(range(num))
Python中的高级数据结构详解
start = time.time()
Python中的高级数据结构详解
operation(c)
Python中的高级数据结构详解
elapsed = time.time() – start
Python中的高级数据结构详解
print “Completed {0}/{1} in {2} seconds: {3} ops/sec”.format(
Python中的高级数据结构详解
container.name, operation.name, elapsed, num / elapsed)
Python中的高级数据结构详解

Python中的高级数据结构详解

Completed deque/append in 0.0250000953674 seconds: 3999984.74127 ops/sec

Python中的高级数据结构详解

Completed deque/appendleft in 0.0199999809265 seconds: 5000004.76838 ops/sec

Python中的高级数据结构详解

Completed deque/pop in 0.0209999084473 seconds: 4761925.52225 ops/sec

Python中的高级数据结构详解

Completed deque/popleft in 0.0199999809265 seconds: 5000004.76838 ops/sec

Python中的高级数据结构详解

Completed list/append in 0.0220000743866 seconds: 4545439.17637 ops/sec

Python中的高级数据结构详解

Completed list/appendleft in 21.3209998608 seconds: 4690.21155917 ops/sec

Python中的高级数据结构详解

Completed list/pop in 0.0240001678467 seconds: 4166637.52682 ops/sec

Python中的高级数据结构详解

Completed list/popleft in 4.01799988747 seconds: 24888.0046791 ops/sec

Python中的高级数据结构详解

Python中的高级数据结构详解
另一个例子是执行基本的队列操作:
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
from collections import deque
Python中的高级数据结构详解
q = deque(range(5))
Python中的高级数据结构详解
q.append(5)
Python中的高级数据结构详解
q.appendleft(6)
Python中的高级数据结构详解
print q
Python中的高级数据结构详解
print q.pop()
Python中的高级数据结构详解
print q.popleft()
Python中的高级数据结构详解
print q.rotate(3)
Python中的高级数据结构详解
print q
Python中的高级数据结构详解
print q.rotate(-1)
Python中的高级数据结构详解
print q
Python中的高级数据结构详解

Python中的高级数据结构详解

deque([6, 0, 1, 2, 3, 4, 5])

Python中的高级数据结构详解

5

Python中的高级数据结构详解

6

Python中的高级数据结构详解

None

Python中的高级数据结构详解

deque([2, 3, 4, 0, 1])

Python中的高级数据结构详解

None

Python中的高级数据结构详解

deque([3, 4, 0, 1, 2])

Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
译者注:rotate是队列的旋转操作,Right rotate(正参数)是将右端的元素移动到左端,而Left rotate(负参数)则相反。
Python中的高级数据结构详解

Python中的高级数据结构详解
1.3 Defaultdict
Python中的高级数据结构详解

Python中的高级数据结构详解
这个类型除了在处理不存在的键的操作之外与普通的字典完全相同。当查找一个不存在的键操作发生时,它的default_factory会被调用,提供一个默认的值,并且将这对键值存储下来。其他的参数同普通的字典方法dict()一致,一个defaultdict的实例同内建dict一样拥有同样地操作。
Python中的高级数据结构详解

Python中的高级数据结构详解
defaultdict对象在当你希望使用它存放追踪数据的时候很有用。举个例子,假定你希望追踪一个单词在字符串中的位置,那么你可以这么做:
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
from collections import defaultdict
Python中的高级数据结构详解

Python中的高级数据结构详解
s = “the quick brown fox jumps over the lazy dog”
Python中的高级数据结构详解

Python中的高级数据结构详解
words = s.split()
Python中的高级数据结构详解
location = defaultdict(list)
Python中的高级数据结构详解
for m, n in enumerate(words):
Python中的高级数据结构详解
location[n].append(m)
Python中的高级数据结构详解

Python中的高级数据结构详解
print location
Python中的高级数据结构详解

Python中的高级数据结构详解

defaultdict(, {‘brown’: [2], ‘lazy’: [7], ‘over’: [5], ‘fox’: [3],

Python中的高级数据结构详解

‘dog’: [8], ‘quick’: [1], ‘the’: [0, 6], ‘jumps’: [4]})

Python中的高级数据结构详解

Python中的高级数据结构详解
是选择lists或sets与defaultdict搭配取决于你的目的,使用list能够保存你插入元素的顺序,而使用set则不关心元素插入顺序,它会帮助消除重复元素。
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
from collections import defaultdict
Python中的高级数据结构详解

Python中的高级数据结构详解
s = “the quick brown fox jumps over the lazy dog”
Python中的高级数据结构详解

Python中的高级数据结构详解
words = s.split()
Python中的高级数据结构详解
location = defaultdict(set)
Python中的高级数据结构详解
for m, n in enumerate(words):
Python中的高级数据结构详解
location[n].add(m)
Python中的高级数据结构详解

Python中的高级数据结构详解
print location
Python中的高级数据结构详解

Python中的高级数据结构详解

defaultdict(, {‘brown’: set([2]), ‘lazy’: set([7]),

Python中的高级数据结构详解

‘over’: set([5]), ‘fox’: set([3]), ‘dog’: set([8]), ‘quick’: set([1]),

Python中的高级数据结构详解

‘the’: set([0, 6]), ‘jumps’: set([4])})

Python中的高级数据结构详解

Python中的高级数据结构详解
另一种创建multidict的方法:
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
s = “the quick brown fox jumps over the lazy dog”
Python中的高级数据结构详解
d = {}
Python中的高级数据结构详解
words = s.split()
Python中的高级数据结构详解

Python中的高级数据结构详解
for key, value in enumerate(words):
Python中的高级数据结构详解
d.setdefault(key, []).append(value)
Python中的高级数据结构详解
print d
Python中的高级数据结构详解

Python中的高级数据结构详解

{0: [‘the’], 1: [‘quick’], 2: [‘brown’], 3: [‘fox’], 4: [‘jumps’], 5: [‘over’], 6: [‘the’], 7: [‘lazy’], 8: [‘dog’]}

Python中的高级数据结构详解

Python中的高级数据结构详解
一个更复杂的例子:
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
class Example(dict):
Python中的高级数据结构详解
def getitem(self, item):
Python中的高级数据结构详解
try:
Python中的高级数据结构详解
return dict.getitem(self, item)
Python中的高级数据结构详解
except KeyError:
Python中的高级数据结构详解
value = self[item] = type(self)()
Python中的高级数据结构详解
return value
Python中的高级数据结构详解

Python中的高级数据结构详解
a = Example()
Python中的高级数据结构详解

Python中的高级数据结构详解
a[1][2][3] = 4
Python中的高级数据结构详解
a[1][3][3] = 5
Python中的高级数据结构详解
a[1][2][‘test’] = 6
Python中的高级数据结构详解

Python中的高级数据结构详解
print a # {1: {2: {‘test’: 6, 3: 4}, 3: {3: 5}}}
Python中的高级数据结构详解

Python中的高级数据结构详解
2. Array
Python中的高级数据结构详解
array模块定义了一个很像list的新对象类型,不同之处在于它限定了这个类型只能装一种类型的元素。array元素的类型是在创建并使用的时候确定的。
Python中的高级数据结构详解

Python中的高级数据结构详解
如果你的程序需要优化内存的使用,并且你确定你希望在list中存储的数据都是同样类型的,那么使用array模块很合适。举个例子,如果需要存储一千万个整数,如果用list,那么你至少需要160MB的存储空间,然而如果使用array,你只需要40MB。但虽然说能够节省空间,array上几乎没有什么基本操作能够比在list上更快。
Python中的高级数据结构详解

Python中的高级数据结构详解
在使用array进行计算的时候,需要特别注意那些创建list的操作。例如,使用列表推导式(list comprehension)的时候,会将array整个转换为list,使得存储空间膨胀。一个可行的替代方案是使用生成器表达式创建新的array。看代码:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
import array
Python中的高级数据结构详解

Python中的高级数据结构详解
a = array.array(“i”, [1,2,3,4,5])
Python中的高级数据结构详解
b = array.array(a.typecode, (2*x for x in a))
Python中的高级数据结构详解

Python中的高级数据结构详解
因为使用array是为了节省空间,所以更倾向于使用in-place操作。一种更高效的方法是使用enumerate:
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
import array
Python中的高级数据结构详解

Python中的高级数据结构详解
a = array.array(“i”, [1,2,3,4,5])
Python中的高级数据结构详解
for i, x in enumerate(a):
Python中的高级数据结构详解
a[i] = 2*x
Python中的高级数据结构详解

Python中的高级数据结构详解
对于较大的array,这种in-place修改能够比用生成器创建一个新的array至少提升15%的速度。
Python中的高级数据结构详解

Python中的高级数据结构详解
那么什么时候使用array呢?是当你在考虑计算的因素之外,还需要得到一个像C语言里一样统一元素类型的数组时。
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
import array
Python中的高级数据结构详解
from timeit import Timer
Python中的高级数据结构详解

Python中的高级数据结构详解
def arraytest():
Python中的高级数据结构详解
a = array.array(“i”, [1, 2, 3, 4, 5])
Python中的高级数据结构详解
b = array.array(a.typecode, (2 * x for x in a))
Python中的高级数据结构详解

Python中的高级数据结构详解
def enumeratetest():
Python中的高级数据结构详解
a = array.array(“i”, [1, 2, 3, 4, 5])
Python中的高级数据结构详解
for i, x in enumerate(a):
Python中的高级数据结构详解
a[i] = 2 * x
Python中的高级数据结构详解

Python中的高级数据结构详解
if name==’main‘:
Python中的高级数据结构详解
m = Timer(“arraytest()”, “from main import arraytest”)
Python中的高级数据结构详解
n = Timer(“enumeratetest()”, “from main import enumeratetest”)
Python中的高级数据结构详解

Python中的高级数据结构详解
print m.timeit() # 5.22479210582
Python中的高级数据结构详解
print n.timeit() # 4.34367196717
Python中的高级数据结构详解

Python中的高级数据结构详解
3.Heapq
Python中的高级数据结构详解

Python中的高级数据结构详解
heapq模块使用一个用堆实现的优先级队列。堆是一种简单的有序列表,并且置入了堆的相关规则。
Python中的高级数据结构详解

Python中的高级数据结构详解
堆是一种树形的数据结构,树上的子节点与父节点之间存在顺序关系。二叉堆(binary heap)能够用一个经过组织的列表或数组结构来标识,在这种结构中,元素N的子节点的序号为2N 1和2N 2(下标始于0)。简单来说,这个模块中的所有函数都假设序列是有序的,所以序列中的第一个元素(seq[0])是最小的,序列的其他部分构成一个二叉树,并且seq[i]节点的子节点分别为seq[2i 1]以及seq[2i 2]。当对序列进行修改时,相关函数总是确保子节点大于等于父节点。
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
import heapq
Python中的高级数据结构详解

Python中的高级数据结构详解
heap = []
Python中的高级数据结构详解

Python中的高级数据结构详解
for value in [20, 10, 30, 50, 40]:
Python中的高级数据结构详解
heapq.heappush(heap, value)
Python中的高级数据结构详解

Python中的高级数据结构详解
while heap:
Python中的高级数据结构详解
print heapq.heappop(heap)
Python中的高级数据结构详解

Python中的高级数据结构详解
heapq模块有两个函数nlargest()和nsmallest(),顾名思义,让我们来看看它们的用法。
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
import heapq
Python中的高级数据结构详解

Python中的高级数据结构详解
nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
Python中的高级数据结构详解
print(heapq.nlargest(3, nums)) # Prints [42, 37, 23]
Python中的高级数据结构详解
print(heapq.nsmallest(3, nums)) # Prints [-4, 1, 2]
Python中的高级数据结构详解

Python中的高级数据结构详解
两个函数也能够通过一个键参数使用更为复杂的数据结构,例如:
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
import heapq
Python中的高级数据结构详解

Python中的高级数据结构详解
portfolio = [
Python中的高级数据结构详解
{‘name’: ‘IBM’, ‘shares’: 100, ‘price’: 91.1},
Python中的高级数据结构详解
{‘name’: ‘AAPL’, ‘shares’: 50, ‘price’: 543.22},
Python中的高级数据结构详解
{‘name’: ‘FB’, ‘shares’: 200, ‘price’: 21.09},
Python中的高级数据结构详解
{‘name’: ‘HPQ’, ‘shares’: 35, ‘price’: 31.75},
Python中的高级数据结构详解
{‘name’: ‘YHOO’, ‘shares’: 45, ‘price’: 16.35},
Python中的高级数据结构详解
{‘name’: ‘ACME’, ‘shares’: 75, ‘price’: 115.65}
Python中的高级数据结构详解
]
Python中的高级数据结构详解
cheap = heapq.nsmallest(3, portfolio, key=lambda s: s[‘price’])
Python中的高级数据结构详解
expensive = heapq.nlargest(3, portfolio, key=lambda s: s[‘price’])
Python中的高级数据结构详解

Python中的高级数据结构详解
print cheap
Python中的高级数据结构详解

Python中的高级数据结构详解

[{‘price’: 16.35, ‘name’: ‘YHOO’, ‘shares’: 45},

Python中的高级数据结构详解

{‘price’: 21.09, ‘name’: ‘FB’, ‘shares’: 200}, {‘price’: 31.75, ‘name’: ‘HPQ’, ‘shares’: 35}]

Python中的高级数据结构详解

Python中的高级数据结构详解
print expensive
Python中的高级数据结构详解

Python中的高级数据结构详解

[{‘price’: 543.22, ‘name’: ‘AAPL’, ‘shares’: 50}, {‘price’: 115.65, ‘name’: ‘ACME’,

Python中的高级数据结构详解

‘shares’: 75}, {‘price’: 91.1, ‘name’: ‘IBM’, ‘shares’: 100}]

Python中的高级数据结构详解

Python中的高级数据结构详解
来看看如何实现一个根据给定优先级进行排序,并且每次pop操作都返回优先级最高的元素的队列例子。
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
import heapq
Python中的高级数据结构详解

Python中的高级数据结构详解
class Item:
Python中的高级数据结构详解
def init(self, name):
Python中的高级数据结构详解
self.name = name
Python中的高级数据结构详解

Python中的高级数据结构详解
def repr(self):
Python中的高级数据结构详解
return ‘Item({!r})’.format(self.name)
Python中的高级数据结构详解

Python中的高级数据结构详解
class PriorityQueue:
Python中的高级数据结构详解
def init(self):
Python中的高级数据结构详解
self._queue = []
Python中的高级数据结构详解
self._index = 0
Python中的高级数据结构详解

Python中的高级数据结构详解
def push(self, item, priority):
Python中的高级数据结构详解
heapq.heappush(self._queue, (-priority, self._index, item))
Python中的高级数据结构详解
self._index = 1
Python中的高级数据结构详解

Python中的高级数据结构详解
def pop(self):
Python中的高级数据结构详解
return heapq.heappop(self._queue)[-1]
Python中的高级数据结构详解

Python中的高级数据结构详解
q = PriorityQueue()
Python中的高级数据结构详解
q.push(Item(‘foo’), 1)
Python中的高级数据结构详解
q.push(Item(‘bar’), 5)
Python中的高级数据结构详解
q.push(Item(‘spam’), 4)
Python中的高级数据结构详解
q.push(Item(‘grok’), 1)
Python中的高级数据结构详解

Python中的高级数据结构详解
print q.pop() # Item(‘bar’)
Python中的高级数据结构详解
print q.pop() # Item(‘spam’)
Python中的高级数据结构详解
print q.pop() # Item(‘foo’)
Python中的高级数据结构详解
print q.pop() # Item(‘grok’)
Python中的高级数据结构详解

Python中的高级数据结构详解
4. Bisect
Python中的高级数据结构详解

Python中的高级数据结构详解
bisect模块能够提供保持list元素序列的支持。它使用了二分法完成大部分的工作。它在向一个list插入元素的同时维持list是有序的。在某些情况下,这比重复的对一个list进行排序更为高效,并且对于一个较大的list来说,对每步操作维持其有序也比对其排序要高效。
Python中的高级数据结构详解

Python中的高级数据结构详解
假设你有一个range集合:
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
a = [(0, 100), (150, 220), (500, 1000)]
Python中的高级数据结构详解

Python中的高级数据结构详解
如果我想添加一个range (250, 400),我可能会这么做:
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
import bisect
Python中的高级数据结构详解

Python中的高级数据结构详解
a = [(0, 100), (150, 220), (500, 1000)]
Python中的高级数据结构详解

Python中的高级数据结构详解
bisect.insort_right(a, (250,400))
Python中的高级数据结构详解

Python中的高级数据结构详解
print a # [(0, 100), (150, 220), (250, 400), (500, 1000)]
Python中的高级数据结构详解

Python中的高级数据结构详解
我们可以使用bisect()函数来寻找插入点:
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
import bisect
Python中的高级数据结构详解

Python中的高级数据结构详解
a = [(0, 100), (150, 220), (500, 1000)]
Python中的高级数据结构详解

Python中的高级数据结构详解
bisect.insort_right(a, (250,400))
Python中的高级数据结构详解
bisect.insort_right(a, (399, 450))
Python中的高级数据结构详解
print a # [(0, 100), (150, 220), (250, 400), (500, 1000)]
Python中的高级数据结构详解

Python中的高级数据结构详解
print bisect.bisect(a, (550, 1200)) # 5
Python中的高级数据结构详解

Python中的高级数据结构详解
bisect(sequence, item) => index 返回元素应该的插入点,但序列并不被修改。
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
import bisect
Python中的高级数据结构详解

Python中的高级数据结构详解
a = [(0, 100), (150, 220), (500, 1000)]
Python中的高级数据结构详解

Python中的高级数据结构详解
bisect.insort_right(a, (250,400))
Python中的高级数据结构详解
bisect.insort_right(a, (399, 450))
Python中的高级数据结构详解
print a # [(0, 100), (150, 220), (250, 400), (500, 1000)]
Python中的高级数据结构详解

Python中的高级数据结构详解
print bisect.bisect(a, (550, 1200)) # 5
Python中的高级数据结构详解
bisect.insort_right(a, (550, 1200))
Python中的高级数据结构详解
print a # [(0, 100), (150, 220), (250, 400), (399, 450), (500, 1000), (550, 1200)]
Python中的高级数据结构详解

Python中的高级数据结构详解
新元素被插入到第5的位置。
Python中的高级数据结构详解

Python中的高级数据结构详解
5. Weakref
Python中的高级数据结构详解

Python中的高级数据结构详解
weakref模块能够帮助我们创建Python引用,却不会阻止对象的销毁操作。这一节包含了weak reference的基本用法,并且引入一个代理类。
Python中的高级数据结构详解

Python中的高级数据结构详解
在开始之前,我们需要明白什么是strong reference。strong reference是一个对对象的引用次数、生命周期以及销毁时机产生影响的指针。strong reference如你所见,就是当你将一个对象赋值给一个变量的时候产生的:
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解

a = [1,2,3]

Python中的高级数据结构详解
b = a
Python中的高级数据结构详解

Python中的高级数据结构详解
在这种情况下,这个列表有两个strong reference,分别是a和b。在这两个引用都被释放之前,这个list不会被销毁。
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解
class Foo(object):
Python中的高级数据结构详解
def init(self):
Python中的高级数据结构详解
self.obj = None
Python中的高级数据结构详解
print ‘created’
Python中的高级数据结构详解

Python中的高级数据结构详解
def del(self):
Python中的高级数据结构详解
print ‘destroyed’
Python中的高级数据结构详解

Python中的高级数据结构详解
def show(self):
Python中的高级数据结构详解
print self.obj
Python中的高级数据结构详解

Python中的高级数据结构详解
def store(self, obj):
Python中的高级数据结构详解
self.obj = obj
Python中的高级数据结构详解

Python中的高级数据结构详解
a = Foo() # created
Python中的高级数据结构详解
b = a
Python中的高级数据结构详解
del a
Python中的高级数据结构详解
del b # destroyed
Python中的高级数据结构详解

Python中的高级数据结构详解
Weak reference则是对对象的引用计数器不会产生影响。当一个对象存在weak reference时,并不会影响对象的撤销。这就说,如果一个对象仅剩下weak reference,那么它将会被销毁。
Python中的高级数据结构详解

Python中的高级数据结构详解
你可以使用weakref.ref函数来创建对象的weak reference。这个函数调用需要将一个strong reference作为第一个参数传给函数,并且返回一个weak reference。
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解

import weakref

Python中的高级数据结构详解
a = Foo()
Python中的高级数据结构详解
created
Python中的高级数据结构详解
b = weakref.ref(a)
Python中的高级数据结构详解
b
Python中的高级数据结构详解

Python中的高级数据结构详解
一个临时的strong reference可以从weak reference中创建,即是下例中的b():
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解

a == b()

Python中的高级数据结构详解
True
Python中的高级数据结构详解
b().show()
Python中的高级数据结构详解
None
Python中的高级数据结构详解

Python中的高级数据结构详解
请注意当我们删除strong reference的时候,对象将立即被销毁。
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解

del a

Python中的高级数据结构详解
destroyed
Python中的高级数据结构详解

Python中的高级数据结构详解
如果试图在对象被摧毁之后通过weak reference使用对象,则会返回None:
Python中的高级数据结构详解

Python中的高级数据结构详解
代码如下:
Python中的高级数据结构详解

Python中的高级数据结构详解

Python中的高级数据结构详解

b() is None

Python中的高级数据结构详解
True
Python中的高级数据结构详解

Python中的高级数据结构详解
若是使用weakref.proxy,就能提供相对于weakref.ref更透明的可选操作。同样是使用一个strong reference作为第一个参数并且返回一个weak reference,proxy更像是一个strong reference,但当对象不存在时会抛出异常。

Original: https://www.cnblogs.com/amengduo/p/9586224.html
Author: 刘小子
Title: Python中的高级数据结构详解

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/9824/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

免费咨询
免费咨询
扫码关注
扫码关注
联系站长

站长Johngo!

大数据和算法重度研究者!

持续产出大数据、算法、LeetCode干货,以及业界好资源!

2022012703491714

微信来撩,免费咨询:xiaozhu_tec

分享本页
返回顶部
最近整理资源【免费获取】:   👉 程序员最新必读书单  | 👏 互联网各方向面试题下载 | ✌️计算机核心资源汇总