8.Python 3のデータ構造

Pythonのより多くのデータ構造

集合(set)

ヒープ

双方向キュー(double-ended queue)

Pythonに内蔵されているデータ型では、tuple、string、list、dictの4つの従来のデータ型が基本的に十分ですが、柔軟で効率的ではありません.可変データ型はlistとdictの2種類しかなく、dictのキー値に対応する表現も堅苦しいため、listに基づいてset、heap、dequeなどの高度に失われたデータ構造が派生している(もちろん機能もさらに細分化されている).
8.1. 集合set
重複要素がなく、インデックスを使用してアクセスできないデータ構造ですよ.集合操作(Intersection、並union、差difference、対称差symmetric_difference)をサポートします.不適切な比喩で、集合は大きな缶です.

とlistの関係.set(lst)リストをsetに変換する.list(st)setをlistオブジェクトに変換します.

要素の添加:add(st,value)

要素の削除(remove,指定要素)とポップアップ(pop,最小要素)

8.2ヒープheap
pythonのスタックは、ある順序で並べられたデータ構造(バケツにたとえられ、最も軽い果物が一番上に漂っている)です.要素を追加すると自動的にソートされ、要素を削除しても自動的にソートされます.加算値はlst.append().sort()に相当する、読み出し値はlst[0]に相当する.簡単に言えばheap=list+sort

とlistの関係.Heapは特殊なソートのlist(heapはツリーベースのソート)であり、heapify(lst)によってlistをheapに強制的に変換することができる(ただし、ソートされていないのは、後のheapqモジュールの関数で操作できるだけである)

heapデータ構造のオブジェクトが存在しないため、通常のスタック(heap)の操作は、パラメータ伝達関数(listのすべての操作であり、スタックheapは使用可能であり、ソート構造を破壊するだけである)としてheapを使用する必要がある.

>>> from heapq import *
>>> from _heapq import heappop
>>> heap =[] # an empty list, is also a heap
>>> for i in range(10):
...     heappush(heap,10-i) #  push a value
... 
>>> print(heap)
[1, 2, 5, 4, 3, 9, 6, 10, 7, 8]
>>> heappop(heap)          # pop the minimal value
1
>>> print(heap)
[2, 3, 5, 4, 8, 9, 6, 10, 7]
>>> heapreplace(heap,6.5) # pop at first, and push another value
2
>>> print(heap)
[3, 4, 5, 6.5, 8, 9, 6, 10, 7]
>>> type(heap) # heap is a list in the implementation

より多くの操作、最大(小さい)n個の値

>>> heap
[3, 4, 5, 6.5, 8, 9, 6, 10, 7]
>>> nlargest(3,heap) #         
[10, 9, 8]
>>> nsmallest(2,heap)#      n  
[3, 4]
>>> heap                    #    inplace  ，heap  
[3, 4, 5, 6.5, 8, 9, 6, 10, 7]

8.3両端キュー(double-ended queue)
私はパイプ操作と理解しています.両側に栓をしてもいいし、両側に取り出すこともできます.リストのように真ん中から値を取るのは、もちろんできます(もしあなたがそうしたいなら、これはqueueの主な職責ではありません).

>>> from collections import deque
>>> q = deque(list(range(6)))
>>> print(q)
deque([0, 1, 2, 3, 4, 5])
>>> q.append('x') 
>>> q.appendleft('-1')
>>> print(q)
deque(['-1', 0, 1, 2, 3, 4, 5, 'x'])
>>> print(q.pop())
x
>>> print(q.popleft())
-1
>>> print(q)
deque([0, 1, 2, 3, 4, 5])
>>> q.rotate(3)
>>> print(q)
deque([3, 4, 5, 0, 1, 2])
>>> q.rotate(-1)
>>> print(q)
deque([4, 5, 0, 1, 2, 3])
>>> type(q)

>>> q[2] = 10
>>> print(q)
deque([4, 5, 10, 1, 2, 3])

セクション

listの様々な不足に対してset,heap,dequeの3つの新しいデータ構造を提案した.

setは重複データを効果的に取り除くことができ、同じセットの論理操作演算を提供している(多く使われているが、自分でリストで実現するのは面倒なことだ).

heapはlistデータを動的に更新したときに並べ替え結果を速やかに与えることができ、すなわちpushのときのデータの配置位置は大きさによって判定される.

dequeの内在的な実装はlistであり、操作の利便性を除いて(これで十分で、さもなくば純粋なcの天下はpythonを必要としない)、私は特別な優位性を発見しなかった.