Python中的高級數(shù)據(jù)結(jié)構(gòu)詳解
數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)的概念很好理解，就是用來將數(shù)據(jù)組織在一起的結(jié)構(gòu)。換句話說，數(shù)據(jù)結(jié)構(gòu)是用來存儲一系列關(guān)聯(lián)數(shù)據(jù)的東西。在Python中有四種內(nèi)建的數(shù)據(jù)結(jié)構(gòu)，分別是List、Tuple、Dictionary以及Set。大部分的應(yīng)用程序不需要其他類型的數(shù)據(jù)結(jié)構(gòu)，但若是真需要也有很多高級數(shù)據(jù)結(jié)構(gòu)可供選擇，例如Collection、Array、Heapq、Bisect、Weakref、Copy以及Pprint。本文將介紹這些數(shù)據(jù)結(jié)構(gòu)的用法，看看它們是如何幫助我們的應(yīng)用程序的。
關(guān)于四種內(nèi)建數(shù)據(jù)結(jié)構(gòu)的使用方法很簡單，并且網(wǎng)上有很多參考資料，因此本文將不會討論它們。
1. Collections
collections模塊包含了內(nèi)建類型之外的一些有用的工具，例如Counter、defaultdict、OrderedDict、deque以及nametuple。其中Counter、deque以及defaultdict是最常用的類。
1.1 Counter()
如果你想統(tǒng)計(jì)一個(gè)單詞在給定的序列中一共出現(xiàn)了多少次，諸如此類的操作就可以用到Counter。來看看如何統(tǒng)計(jì)一個(gè)list中出現(xiàn)的item次數(shù)：
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})
若要統(tǒng)計(jì)一個(gè)list中不同單詞的數(shù)目，可以這么用：
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
如果需要對結(jié)果進(jìn)行分組，可以這么做：
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)]
以下的代碼片段找出一個(gè)字符串中出現(xiàn)頻率最高的單詞，并打印其出現(xiàn)次數(shù)。
import re
from 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 appears
print 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是一種由隊(duì)列結(jié)構(gòu)擴(kuò)展而來的雙端隊(duì)列(double-ended queue)，隊(duì)列元素能夠在隊(duì)列兩端添加或刪除。因此它還被稱為頭尾連接列表(head-tail linked list)，盡管叫這個(gè)名字的還有另一個(gè)特殊的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。
Deque支持線程安全的，經(jīng)過優(yōu)化的append和pop操作，在隊(duì)列兩端的相關(guān)操作都能夠達(dá)到近乎O(1)的時(shí)間復(fù)雜度。雖然list也支持類似的操作，但是它是對定長列表的操作表現(xiàn)很不錯(cuò)，而當(dāng)遇到pop(0)和insert(0, v)這樣既改變了列表的長度又改變其元素位置的操作時(shí)，其復(fù)雜度就變?yōu)镺(n)了。
來看看相關(guān)的比較結(jié)果：
import time
from 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() - start
print "Completed {0}/{1} in {2} seconds: {3} ops/sec".format(
container.__name__, operation.__name__, elapsed, num / elapsed)
# Completed deque/append in 0.0250000953674 seconds: 3999984.74127 ops/sec
# Completed deque/appendleft in 0.0199999809265 seconds: 5000004.76838 ops/sec
# Completed deque/pop in 0.0209999084473 seconds: 4761925.52225 ops/sec
# Completed deque/popleft in 0.0199999809265 seconds: 5000004.76838 ops/sec
# Completed list/append in 0.0220000743866 seconds: 4545439.17637 ops/sec
# Completed list/appendleft in 21.3209998608 seconds: 4690.21155917 ops/sec
# Completed list/pop in 0.0240001678467 seconds: 4166637.52682 ops/sec
# Completed list/popleft in 4.01799988747 seconds: 24888.0046791 ops/sec
另一個(gè)例子是執(zhí)行基本的隊(duì)列操作：
from collections import deque
q = deque(range(5))
q.append(5)
q.appendleft(6)
print q
print q.pop()
print q.popleft()
print q.rotate(3)
print q
print q.rotate(-1)
print q
# deque([6, 0, 1, 2, 3, 4, 5])
# 5
# 6
# None
# deque([2, 3, 4, 0, 1])
# None
# deque([3, 4, 0, 1, 2])
譯者注:rotate是隊(duì)列的旋轉(zhuǎn)操作，Right rotate(正參數(shù))是將右端的元素移動到左端，而Left rotate(負(fù)參數(shù))則相反。
1.3 Defaultdict
這個(gè)類型除了在處理不存在的鍵的操作之外與普通的字典完全相同。當(dāng)查找一個(gè)不存在的鍵操作發(fā)生時(shí)，它的default_factory會被調(diào)用，提供一個(gè)默認(rèn)的值，并且將這對鍵值存儲下來。其他的參數(shù)同普通的字典方法dict()一致，一個(gè)defaultdict的實(shí)例同內(nèi)建dict一樣擁有同樣地操作。
defaultdict對象在當(dāng)你希望使用它存放追蹤數(shù)據(jù)的時(shí)候很有用。舉個(gè)例子，假定你希望追蹤一個(gè)單詞在字符串中的位置，那么你可以這么做：
from collections import defaultdict
s = "the quick brown fox jumps over the lazy dog"
words = s.split()
location = defaultdict(list)
for m, n in enumerate(words):
location[n].append(m)
print location
# defaultdict(<type 'list'>, {'brown': [2], 'lazy': [7], 'over': [5], 'fox': [3],
# 'dog': [8], 'quick': [1], 'the': [0, 6], 'jumps': [4]})
是選擇lists或sets與defaultdict搭配取決于你的目的，使用list能夠保存你插入元素的順序，而使用set則不關(guān)心元素插入順序，它會幫助消除重復(fù)元素。
from collections import defaultdict
s = "the quick brown fox jumps over the lazy dog"
words = s.split()
location = defaultdict(set)
for m, n in enumerate(words):
location[n].add(m)
print location
# defaultdict(<type 'set'>, {'brown': set([2]), 'lazy': set([7]),
# 'over': set([5]), 'fox': set([3]), 'dog': set([8]), 'quick': set([1]),
# 'the': set([0, 6]), 'jumps': set([4])})
另一種創(chuàng)建multidict的方法：
s = "the quick brown fox jumps over the lazy dog"
d = {}
words = s.split()
for key, value in enumerate(words):
d.setdefault(key, []).append(value)
print d
# {0: ['the'], 1: ['quick'], 2: ['brown'], 3: ['fox'], 4: ['jumps'], 5: ['over'], 6: ['the'], 7: ['lazy'], 8: ['dog']}
一個(gè)更復(fù)雜的例子：
class Example(dict):
def __getitem__(self, item):
try:
return dict.__getitem__(self, item)
except KeyError:
value = self[item] = type(self)()
return value
a = Example()
a[1][2][3] = 4
a[1][3][3] = 5
a[1][2]['test'] = 6
print a # {1: {2: {'test': 6, 3: 4}, 3: {3: 5}}}
2. Array
array模塊定義了一個(gè)很像list的新對象類型，不同之處在于它限定了這個(gè)類型只能裝一種類型的元素。array元素的類型是在創(chuàng)建并使用的時(shí)候確定的。
如果你的程序需要優(yōu)化內(nèi)存的使用，并且你確定你希望在list中存儲的數(shù)據(jù)都是同樣類型的，那么使用array模塊很合適。舉個(gè)例子，如果需要存儲一千萬個(gè)整數(shù)，如果用list，那么你至少需要160MB的存儲空間，然而如果使用array，你只需要40MB。但雖然說能夠節(jié)省空間，array上幾乎沒有什么基本操作能夠比在list上更快。
在使用array進(jìn)行計(jì)算的時(shí)候，需要特別注意那些創(chuàng)建list的操作。例如，使用列表推導(dǎo)式(list comprehension)的時(shí)候，會將array整個(gè)轉(zhuǎn)換為list，使得存儲空間膨脹。一個(gè)可行的替代方案是使用生成器表達(dá)式創(chuàng)建新的array。看代碼：
import array
a = array.array("i", [1,2,3,4,5])
b = array.array(a.typecode, (2*x for x in a))
因?yàn)槭褂胊rray是為了節(jié)省空間，所以更傾向于使用in-place操作。一種更高效的方法是使用enumerate：
import array
a = array.array("i", [1,2,3,4,5])
for i, x in enumerate(a):
a[i] = 2*x
對于較大的array，這種in-place修改能夠比用生成器創(chuàng)建一個(gè)新的array至少提升15%的速度。
那么什么時(shí)候使用array呢？是當(dāng)你在考慮計(jì)算的因素之外，還需要得到一個(gè)像C語言里一樣統(tǒng)一元素類型的數(shù)組時(shí)。
import array
from timeit import Timer
def arraytest():
a = array.array("i", [1, 2, 3, 4, 5])
b = array.array(a.typecode, (2 * x for x in a))
def enumeratetest():
a = array.array("i", [1, 2, 3, 4, 5])
for i, x in enumerate(a):
a[i] = 2 * x
if __name__=='__main__':
m = Timer("arraytest()", "from __main__ import arraytest")
n = Timer("enumeratetest()", "from __main__ import enumeratetest")
print m.timeit() # 5.22479210582
print n.timeit() # 4.34367196717
3.Heapq
heapq模塊使用一個(gè)用堆實(shí)現(xiàn)的優(yōu)先級隊(duì)列。堆是一種簡單的有序列表，并且置入了堆的相關(guān)規(guī)則。
堆是一種樹形的數(shù)據(jù)結(jié)構(gòu)，樹上的子節(jié)點(diǎn)與父節(jié)點(diǎn)之間存在順序關(guān)系。二叉堆(binary heap)能夠用一個(gè)經(jīng)過組織的列表或數(shù)組結(jié)構(gòu)來標(biāo)識，在這種結(jié)構(gòu)中，元素N的子節(jié)點(diǎn)的序號為2*N+1和2*N+2(下標(biāo)始于0)。簡單來說，這個(gè)模塊中的所有函數(shù)都假設(shè)序列是有序的，所以序列中的第一個(gè)元素(seq[0])是最小的，序列的其他部分構(gòu)成一個(gè)二叉樹，并且seq[i]節(jié)點(diǎn)的子節(jié)點(diǎn)分別為seq[2*i+1]以及seq[2*i+2]。當(dāng)對序列進(jìn)行修改時(shí)，相關(guān)函數(shù)總是確保子節(jié)點(diǎn)大于等于父節(jié)點(diǎn)。
import heapq
heap = []
for value in [20, 10, 30, 50, 40]:
heapq.heappush(heap, value)
while heap:
print heapq.heappop(heap)
heapq模塊有兩個(gè)函數(shù)nlargest()和nsmallest()，顧名思義，讓我們來看看它們的用法。
import heapq
nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
print(heapq.nlargest(3, nums)) # Prints [42, 37, 23]
print(heapq.nsmallest(3, nums)) # Prints [-4, 1, 2]
兩個(gè)函數(shù)也能夠通過一個(gè)鍵參數(shù)使用更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，例如：
import heapq
portfolio = [
{'name': 'IBM', 'shares': 100, 'price': 91.1},
{'name': 'AAPL', 'shares': 50, 'price': 543.22},
{'name': 'FB', 'shares': 200, 'price': 21.09},
{'name': 'HPQ', 'shares': 35, 'price': 31.75},
{'name': 'YHOO', 'shares': 45, 'price': 16.35},
{'name': 'ACME', 'shares': 75, 'price': 115.65}
]
cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])
print cheap
# [{'price': 16.35, 'name': 'YHOO', 'shares': 45},
# {'price': 21.09, 'name': 'FB', 'shares': 200}, {'price': 31.75, 'name': 'HPQ', 'shares': 35}]
print expensive
# [{'price': 543.22, 'name': 'AAPL', 'shares': 50}, {'price': 115.65, 'name': 'ACME',
# 'shares': 75}, {'price': 91.1, 'name': 'IBM', 'shares': 100}]
來看看如何實(shí)現(xiàn)一個(gè)根據(jù)給定優(yōu)先級進(jìn)行排序，并且每次pop操作都返回優(yōu)先級最高的元素的隊(duì)列例子。
import heapq
class Item:
def __init__(self, name):
self.name = name
def __repr__(self):
return 'Item({!r})'.format(self.name)
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
heapq.heappush(self._queue, (-priority, self._index, item))
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1]
q = PriorityQueue()
q.push(Item('foo'), 1)
q.push(Item('bar'), 5)
q.push(Item('spam'), 4)
q.push(Item('grok'), 1)
print q.pop() # Item('bar')
print q.pop() # Item('spam')
print q.pop() # Item('foo')
print q.pop() # Item('grok')
4. Bisect
bisect模塊能夠提供保持list元素序列的支持。它使用了二分法完成大部分的工作。它在向一個(gè)list插入元素的同時(shí)維持list是有序的。在某些情況下，這比重復(fù)的對一個(gè)list進(jìn)行排序更為高效，并且對于一個(gè)較大的list來說，對每步操作維持其有序也比對其排序要高效。
假設(shè)你有一個(gè)range集合：
a = [(0, 100), (150, 220), (500, 1000)]
如果我想添加一個(gè)range (250, 400)，我可能會這么做：
import bisect
a = [(0, 100), (150, 220), (500, 1000)]
bisect.insort_right(a, (250,400))
print a # [(0, 100), (150, 220), (250, 400), (500, 1000)]
我們可以使用bisect()函數(shù)來尋找插入點(diǎn)：
import bisect
a = [(0, 100), (150, 220), (500, 1000)]
bisect.insort_right(a, (250,400))
bisect.insort_right(a, (399, 450))
print a # [(0, 100), (150, 220), (250, 400), (500, 1000)]
print bisect.bisect(a, (550, 1200)) # 5
bisect(sequence, item) => index 返回元素應(yīng)該的插入點(diǎn)，但序列并不被修改。
import bisect
a = [(0, 100), (150, 220), (500, 1000)]
bisect.insort_right(a, (250,400))
bisect.insort_right(a, (399, 450))
print a # [(0, 100), (150, 220), (250, 400), (500, 1000)]
print bisect.bisect(a, (550, 1200)) # 5
bisect.insort_right(a, (550, 1200))
print a # [(0, 100), (150, 220), (250, 400), (399, 450), (500, 1000), (550, 1200)]
新元素被插入到第5的位置。
5. Weakref
weakref模塊能夠幫助我們創(chuàng)建Python引用，卻不會阻止對象的銷毀操作。這一節(jié)包含了weak reference的基本用法，并且引入一個(gè)代理類。
在開始之前，我們需要明白什么是strong reference。strong reference是一個(gè)對對象的引用次數(shù)、生命周期以及銷毀時(shí)機(jī)產(chǎn)生影響的指針。strong reference如你所見，就是當(dāng)你將一個(gè)對象賦值給一個(gè)變量的時(shí)候產(chǎn)生的：
>>> a = [1,2,3]
>>> b = a
在這種情況下，這個(gè)列表有兩個(gè)strong reference，分別是a和b。在這兩個(gè)引用都被釋放之前，這個(gè)list不會被銷毀。
class Foo(object):
def __init__(self):
self.obj = None
print 'created'
def __del__(self):
print 'destroyed'
def show(self):
print self.obj
def store(self, obj):
self.obj = obj
a = Foo() # created
b = a
del a
del b # destroyed
Weak reference則是對對象的引用計(jì)數(shù)器不會產(chǎn)生影響。當(dāng)一個(gè)對象存在weak reference時(shí)，并不會影響對象的撤銷。這就說，如果一個(gè)對象僅剩下weak reference，那么它將會被銷毀。
你可以使用weakref.ref函數(shù)來創(chuàng)建對象的weak reference。這個(gè)函數(shù)調(diào)用需要將一個(gè)strong reference作為第一個(gè)參數(shù)傳給函數(shù)，并且返回一個(gè)weak reference。
>>> import weakref
>>> a = Foo()
created
>>> b = weakref.ref(a)
>>> b
一個(gè)臨時(shí)的strong reference可以從weak reference中創(chuàng)建，即是下例中的b()：
>>> a == b()
True
>>> b().show()
None
請注意當(dāng)我們刪除strong reference的時(shí)候，對象將立即被銷毀。
>>> del a
destroyed
如果試圖在對象被摧毀之后通過weak reference使用對象，則會返回None：
>>> b() is None
True
若是使用weakref.proxy，就能提供相對于weakref.ref更透明的可選操作。同樣是使用一個(gè)strong reference作為第一個(gè)參數(shù)并且返回一個(gè)weak reference，proxy更像是一個(gè)strong reference，但當(dāng)對象不存在時(shí)會拋出異常。
>>> a = Foo()
created
>>> b = weakref.proxy(a)
>>> b.store('fish')
>>> b.show()
fish
>>> del a
destroyed
>>> b.show()
Traceback (most recent call last):
File "", line 1, in ?
ReferenceError: weakly-referenced object no longer exists
完整的例子：
引用計(jì)數(shù)器是由Python的垃圾回收器使用的，當(dāng)一個(gè)對象的應(yīng)用計(jì)數(shù)器變?yōu)?，則其將會被垃圾回收器回收。
最好將weak reference用于開銷較大的對象，或避免循環(huán)引用(雖然垃圾回收器經(jīng)常干這種事情)。
import weakref
import gc
class MyObject(object):
def my_method(self):
print 'my_method was called!'
obj = MyObject()
r = weakref.ref(obj)
gc.collect()
assert r() is obj #r() allows you to access the object referenced: it's there.
obj = 1 #Let's change what obj references to
gc.collect()
assert r() is None #There is no object left: it was gc'ed.
提示：只有l(wèi)ibrary模塊中定義的class instances、functions、methods、sets、frozen sets、files、generators、type objects和certain object types(例如sockets、arrays和regular expression patterns)支持weakref。內(nèi)建函數(shù)以及大部分內(nèi)建類型如lists、dictionaries、strings和numbers則不支持。
6. Copy()
通過shallow或deep copy語法提供復(fù)制對象的函數(shù)操作。
shallow和deep copying的不同之處在于對于混合型對象的操作(混合對象是包含了其他類型對象的對象，例如list或其他類實(shí)例)。
1.對于shallow copy而言，它創(chuàng)建一個(gè)新的混合對象，并且將原對象中其他對象的引用插入新對象。
2.對于deep copy而言，它創(chuàng)建一個(gè)新的對象，并且遞歸地復(fù)制源對象中的其他對象并插入新的對象中。
普通的賦值操作知識簡單的將心變量指向源對象。
import copy
a = [1,2,3]
b = [4,5]
c = [a,b]
# Normal Assignment
d = c
print id(c) == id(d) # True - d is the same object as c
print id(c[0]) == id(d[0]) # True - d[0] is the same object as c[0]
# Shallow Copy
d = copy.copy(c)
print id(c) == id(d) # False - d is now a new object
print id(c[0]) == id(d[0]) # True - d[0] is the same object as c[0]
# Deep Copy
d = copy.deepcopy(c)
print id(c) == id(d) # False - d is now a new object
print id(c[0]) == id(d[0]) # False - d[0] is now a new object
shallow copy (copy())操作創(chuàng)建一個(gè)新的容器，其包含的引用指向原對象中的對象。
deep copy (deepcopy())創(chuàng)建的對象包含的引用指向復(fù)制出來的新對象。
復(fù)雜的例子：
假定我有兩個(gè)類，名為Manager和Graph，每個(gè)Graph包含了一個(gè)指向其manager的引用，而每個(gè)Manager有一個(gè)指向其管理的Graph的集合，現(xiàn)在我們有兩個(gè)任務(wù)需要完成：
1) 復(fù)制一個(gè)graph實(shí)例，使用deepcopy，但其manager指向?yàn)樵璯raph的manager。
2) 復(fù)制一個(gè)manager，完全創(chuàng)建新manager，但拷貝原有的所有g(shù)raph。
import weakref, copy
class Graph(object):
def __init__(self, manager=None):
self.manager = None if manager is None else weakref.ref(manager)
def __deepcopy__(self, memodict):
manager = self.manager()
return Graph(memodict.get(id(manager), manager))
class Manager(object):
def __init__(self, graphs=[]):
self.graphs = graphs
for g in self.graphs:
g.manager = weakref.ref(self)
a = Manager([Graph(), Graph()])
b = copy.deepcopy(a)
if [g.manager() is b for g in b.graphs]:
print True # True
if copy.deepcopy(a.graphs[0]).manager() is a:
print True # True
7. Pprint()
Pprint模塊能夠提供比較優(yōu)雅的數(shù)據(jù)結(jié)構(gòu)打印方式，如果你需要打印一個(gè)結(jié)構(gòu)較為復(fù)雜，層次較深的字典或是JSON對象時(shí)，使用Pprint能夠提供較好的打印結(jié)果。
假定你需要打印一個(gè)矩陣，當(dāng)使用普通的print時(shí)，你只能打印出普通的列表，不過如果使用pprint，你就能打出漂亮的矩陣結(jié)構(gòu)
如果
import pprint
matrix = [ [1,2,3], [4,5,6], [7,8,9] ]
a = pprint.PrettyPrinter(width=20)
a.pprint(matrix)
# [[1, 2, 3],
# [4, 5, 6],
# [7, 8, 9]]
額外的知識
一些基本的數(shù)據(jù)結(jié)構(gòu)
1. 單鏈鏈表
class Node:
def __init__(self):
self.data = None
self.nextNode = None
def set_and_return_Next(self):
self.nextNode = Node()
return self.nextNode
def getNext(self):
return self.nextNode
def getData(self):
return self.data
def setData(self, d):
self.data = d
class LinkedList:
def buildList(self, array):
self.head = Node()
self.head.setData(array[0])
self.temp = self.head
for i in array[1:]:
self.temp = self.temp.set_and_return_Next()
self.temp.setData(i)
self.tail = self.temp
return self.head
def printList(self):
tempNode = self.head
while(tempNode!=self.tail):
print(tempNode.getData())
tempNode = tempNode.getNext()
print(self.tail.getData())
myArray = [3, 5, 4, 6, 2, 6, 7, 8, 9, 10, 21]
myList = LinkedList()
myList.buildList(myArray)
myList.printList()
2. 用Python實(shí)現(xiàn)的普林姆算法
譯者注：普林姆算法(Prims Algorithm)是圖論中，在加權(quán)連通圖中搜索最小生成樹的算法。
from collections import defaultdict
from heapq import heapify, heappop, heappush
def prim( nodes, edges ):
conn = defaultdict( list )
for n1,n2,c in edges:
conn[ n1 ].append( (c, n1, n2) )
conn[ n2 ].append( (c, n2, n1) )
mst = []
used = set( nodes[ 0 ] )
usable_edges = conn[ nodes[0] ][:]
heapify( usable_edges )
while usable_edges:
cost, n1, n2 = heappop( usable_edges )
if n2 not in used:
used.add( n2 )
mst.append( ( n1, n2, cost ) )
for e in conn[ n2 ]:
if e[ 2 ] not in used:
heappush( usable_edges, e )
return mst
#test
nodes = list("ABCDEFG")
edges = [ ("A", "B", 7), ("A", "D", 5),
("B", "C", 8), ("B", "D", 9), ("B", "E", 7),
("C", "E", 5),
("D", "E", 15), ("D", "F", 6),
("E", "F", 8), ("E", "G", 9),
("F", "G", 11)]
print "prim:", prim( nodes, edges )
總結(jié)
如果想了解更多地?cái)?shù)據(jù)結(jié)構(gòu)信息請參閱相關(guān)文檔。謝謝閱讀。
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹的建立實(shí)例
- Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之鏈表詳解
- Python中列表、字典、元組、集合數(shù)據(jù)結(jié)構(gòu)整理
- python數(shù)據(jù)結(jié)構(gòu)之圖深度優(yōu)先和廣度優(yōu)先實(shí)例詳解
- python實(shí)現(xiàn)bitmap數(shù)據(jù)結(jié)構(gòu)詳解
- python數(shù)據(jù)結(jié)構(gòu)樹和二叉樹簡介
- Python實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)與算法之隊(duì)列詳解
- Python中3種內(nèi)建數(shù)據(jù)結(jié)構(gòu)：列表、元組和字典
- C++數(shù)據(jù)結(jié)構(gòu)與算法之哈夫曼樹的實(shí)現(xiàn)方法
- 圖文詳解JAVA實(shí)現(xiàn)哈夫曼樹
- Python數(shù)據(jù)結(jié)構(gòu)之哈夫曼樹定義與使用方法示例
相關(guān)文章
解決python調(diào)用自己文件函數(shù)/執(zhí)行函數(shù)找不到包問題
這篇文章主要介紹了解決python調(diào)用自己文件函數(shù)/執(zhí)行函數(shù)找不到包問題，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-06-06
Python實(shí)現(xiàn)發(fā)送郵件到自己郵箱
在日常開發(fā)中，我們經(jīng)常需要監(jiān)控應(yīng)用程序的狀態(tài)，及時(shí)發(fā)現(xiàn)問題并采取措施解決。而通過郵件發(fā)送報(bào)警信息則是一種常見的實(shí)現(xiàn)方式。本文就來介紹一下Python實(shí)現(xiàn)發(fā)送郵件到自己郵箱的方法2023-04-04
wheel是新的Python的disribution，用于替代Python傳統(tǒng)的egg文件。目前有超過一半的庫文件有對應(yīng)的wheel文件，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2022-09-09
python每次處理固定個(gè)數(shù)的字符的方法總結(jié)
使用python每次處理固定個(gè)數(shù)的字符，很多情況下都會遇到。本文對可能的方法做下總結(jié)，供各位朋友學(xué)習(xí)參考2013-01-01
大家好，本篇文章主要講的是用Python生成會跳舞的美女，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
Python中非常實(shí)用的一些功能和函數(shù)分享
這篇文章主要介紹了Python中非常實(shí)用的一些功能和函數(shù)分享,本文講解了帶任意數(shù)量參數(shù)的函數(shù)、使用Glob()查找文件、調(diào)試、生成唯一ID等內(nèi)容,需要的朋友可以參考下2015-02-02
解決python遞歸函數(shù)及遞歸次數(shù)受到限制的問題
這篇文章主要介紹了解決python遞歸函數(shù)及遞歸次數(shù)受到限制的問題，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-06-06
這篇文章主要介紹了Python字符串的修改方法實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-12-12
基于OpenCV4.2實(shí)現(xiàn)單目標(biāo)跟蹤
這篇文章主要介紹了如何和何時(shí)使用OpenCV 4.2中可用的8種不同的跟蹤器- BOOSTING, MIL, KCF, TLD, MEDIANFLOW, GOTURN, MOSSE和CSRT，并用他們實(shí)現(xiàn)單目標(biāo)跟蹤，需要的可以參考一下2022-03-03
python格式化輸出format()函數(shù)常見用法和格式選項(xiàng)
這篇文章主要介紹了python格式化輸出format()函數(shù)常見用法和格式選項(xiàng)的相關(guān)資料,format方法是一種強(qiáng)大的字符串格式化工具,它允許你將變量或表達(dá)式插入到字符串中,并根據(jù)需要進(jìn)行格式化,需要的朋友可以參考下2025-03-03