***
9091 ワード
第1章データ構造とアルゴリズム:1.1シーケンスを個別の変数コアポイントに分解する:任意のシーケンスまたは反復可能なオブジェクト、メタグループtuple、リストリストリストだけでなく、文字列string、ファイル、反復器iterator、ジェネレータgeneratorも含まれ、簡単な付与操作で単一の変数に分解することができる.次のようになります.
さらに複雑なもの:
要素の数は互いに一致しなければなりません.そうしないと、エラーが発生します.
*特定の値を破棄する方法:pythonでは対応する構文は提供されていませんが、使用できない変数名を選択することで実現できます.
例:
1.2任意の長さの反復可能オブジェクトから要素のコアポイントを分解します.反復可能オブジェクトの長さが必要な分解要素の数を超えると、*式が役立ちます.
最も簡単な例を挙げます.
破棄する値の変数名を指定する場合は、'''を追加することで、複数の値を同時に破棄できます.
1.3最後のN個の要素のコアポイントを保存する:from collections import deque、deque([maxlen=N])は最大長Nのキューを作成することができ(記録された要素がNを超えると、最も古いレコードを削除する)、長さを指定しないと、境界のないキューが得られ、両端で追加とポップアップ操作を実行することができる.例1:
リストヘッダから要素を挿入または除去する複雑さはO(N)であり、キューの両端に要素を追加またはポップアップする複雑さはO(1)であることに注意してください.
1.4最大または最小のN個の要素の核心点を見つける:本章では4つの比較サイズの時の解題構想を提供した:1最小または最大の要素(N=1)を見つけたいだけなら、min()とmax()を使うともっと速くなる.2 Nと集合自体の大きさの差がそれほど大きくない場合、通常はソート・スライス結合方式がより速く、すなわちsorted(items)[:N]またはsorted(items)[-N:]を用いる.3探している要素の数が比較的小さい場合、nlargest()とnsmallest()が最も適する(パラメータkeyも許容できる):heapq.nlargest(N,list,key = lambda s: s[’ ']);④Nは集合中の要素の総数目よりはるかに小さいので、データをリストに変換してからheapqを使用する.heapify()はリストを線形時間でスタックに変換する、heap[0]は常に最小の要素であり、heapq.heapppop()は、最初の要素(最小)をポップアップします.例1:
例2:
1.5優先順位キューを実現するコアポイント:heapq.heappush(スタック、value)は、与えられた優先度で要素をソートします.本の例を通して、関連操作を解析しましょう.例1:
本の中の実例と元組の対比に関する説明については、私はもう余計なことを言わない.いくつかのheapqモジュールの方法を添付します:heapq.Heapeplace(heap,item):item要素を追加し、heapの最小要素を返します.heapq.heappushpop(heap,item):item要素を追加し、heapの最小要素heapq._を返します.heappop_max(heap):heapの最大値heapqを返します.merge(複数の秩序シーケンス、key:None、reverse:False):秩序シーケンスをマージして反復し、heapq.merge()の反復的性質は、提供されるすべてのシーケンスに対して一度に読み込まないことを意味する.これは、非常に長いシーケンスを処理するのに使用できますが、オーバーヘッドは非常に小さいことを意味します.
1.6ディクショナリで複数の値にキーをマッピングする:コアポイント:1つのキーの多値ディクショナリを作成すると、リストまたはコレクションを使用してこれらの値を保存できます.リストは入力順序を維持し、コレクションは重複要素を除去できます(ただし、順序が乱されます).
方法:1 from collections import defaultdict、defaultdictは最初の値を自動的に初期化し、要素の追加に注目します.
例1:
②通常辞書を作成し、setdefaultを呼び出します.
例2:
この方法では、setdefaultを呼び出すたびに、初期値の新しいインスタンス-空のリスト[]が作成されます.
例3:
1.7ディクショナリを秩序化するコアポイント:from collections import OrderedDict、ディクショナリを反復すると、要素の初期追加の順序に厳格に従いますが、欠点も明らかです.それは、OrderedDictの内部で双方向チェーンテーブルが維持されているため、通常のディクショナリの2倍以上の大きさなので、使用前にメリットとデメリットを測定する必要があります.
例1
1.8辞書に関する計算問題の核心点:辞書内のデータの最大値の最小値を要求する場合、通常zip()を利用して辞書のキーと値を反転すれば求めることができ、データをソートする必要がある場合はsorted()に協力することができる.
例1
*zip()は反復器で作成され、コンテンツは1回しか消費されません.
zip()を使用しない場合は、答えを得るには少なくとも2つのステップが必要です.
1.9同じポイントのコアポイントを2つの辞書で探します.辞書のキー(keys()、items()メソッドを含む)は、パラレルセット、交差、および差セットなどの一般的な集合操作をサポートします.ただし、辞書の値は必ずしも一意ではないため、集合操作は直接サポートされません(集合に移行してから操作できます).
例1:
これらのタイプの操作は、辞書の内容を変更またはフィルタリングするためにも使用できます.次のようになります.
1.10繰り返しをシーケンスから削除し、要素間の順序を維持
コアポイント:1シーケンスの値はハッシュ可能で、コレクションとジェネレータを使用して解決できます.
例1:
*returnとyieldの違い:returnは結果を返した後に関数の実行を終了し、yieldは関数をジェネレータにし、ジェネレータは毎回1つの値(yield文)を生成し、関数は凍結され、起動された後に1つの値を生成するので、yieldはreturnよりも速く、空間を節約します.
例2:
この例では、オブジェクトのフィールドまたは属性に基づいて重複項目を除去し、匿名関数によってハッシュ可能なタイプを取得します.
1.11スライスの名前付けコアポイント:コードにハードコーディングされたインデックス値が多数ある場合、その可読性とメンテナンス性は必ず低下し、内蔵slice()関数を使用してスライスオブジェクトを作成し、スライス操作を許可する場所で使用できます.
例1:
sliceスライスとindices(size)メソッドを組み合わせると、インデックス操作でIndexErrorエラーが発生することを防止できます.
ここでsizeはslice(start,end,step)のend,new_に相当するend = min(end,size)
s = 'Hello'
a,b,c,d,e =s
print(a) # 'H'
print(b) # 'e'
さらに複雑なもの:
data = ['ACME',50,91.1,(2012,12,21)] #
name, shares ,price, date = data #
print(date) # (2012,12,21)
# ：
name,shares,price,(year,month,day) = data
print(month) # 12
要素の数は互いに一致しなければなりません.そうしないと、エラーが発生します.
p = [4,5]
x,y,z = p #ValueError: need more than 2 values to unpack
*特定の値を破棄する方法:pythonでは対応する構文は提供されていませんが、使用できない変数名を選択することで実現できます.
例:
data = ['ACME',50,91.1,(2012,12,21)]
_, shares, price, _ = data
print(shares) #50
print(price) #91.1
1.2任意の長さの反復可能オブジェクトから要素のコアポイントを分解します.反復可能オブジェクトの長さが必要な分解要素の数を超えると、*式が役立ちます.
最も簡単な例を挙げます.
s = 'HelloWorld'
a,b,*c,d = s
print(a) #'H'
print(c) #['l', 'l', 'o', 'W', 'o', 'r', 'l']
破棄する値の変数名を指定する場合は、'''を追加することで、複数の値を同時に破棄できます.
record = ['ACME',50,123.45,(12,18,2012)]
name, *_ , (*_, year) = record
print(name) # 'ACME'
print(year) # 2012
1.3最後のN個の要素のコアポイントを保存する:from collections import deque、deque([maxlen=N])は最大長Nのキューを作成することができ(記録された要素がNを超えると、最も古いレコードを削除する)、長さを指定しないと、境界のないキューが得られ、両端で追加とポップアップ操作を実行することができる.例1:
from collections import deque
q = deque(maxlen=3)
q.append(1)
q.append(2)
q.append(3)
print(q)# deque([1,2,3],maxlen=3)
q.append(4)
print(q)# deque([2,3,4],maxlen=3)
q.appendleft(1)
print(q)#deque([3,4,1], maxlen=3)
q.popleft(3) # 3( 3)
リストヘッダから要素を挿入または除去する複雑さはO(N)であり、キューの両端に要素を追加またはポップアップする複雑さはO(1)であることに注意してください.
1.4最大または最小のN個の要素の核心点を見つける:本章では4つの比較サイズの時の解題構想を提供した:1最小または最大の要素(N=1)を見つけたいだけなら、min()とmax()を使うともっと速くなる.2 Nと集合自体の大きさの差がそれほど大きくない場合、通常はソート・スライス結合方式がより速く、すなわちsorted(items)[:N]またはsorted(items)[-N:]を用いる.3探している要素の数が比較的小さい場合、nlargest()とnsmallest()が最も適する(パラメータkeyも許容できる):heapq.nlargest(N,list,key = lambda s: s[’ ']);④Nは集合中の要素の総数目よりはるかに小さいので、データをリストに変換してからheapqを使用する.heapify()はリストを線形時間でスタックに変換する、heap[0]は常に最小の要素であり、heapq.heapppop()は、最初の要素(最小)をポップアップします.例1:
import heapq
data = [
{'name':'Tom','age':18,'salary':4000},
{'name':'Jimmy','age':25,'salary':10000},
{'name':'Jane','age':33,'salary':40000},
{'name':'Ferrando','age':30,'salary':32000},
]
print(heapq.nlargest(2,data, key = lambda s: s['salary']))
#[{'name': 'Jane', 'age': 33, 'salary': 40000}, {'name': 'Ferrando', 'age': 30, 'salary': 32000}]
例2:
import heapq
data = [1,3,5,9,7,4,6,12,-1,-13]
heap = list(data)
heapq.heapify(heap)
print(heap[0]) # -13
print(heapq.heappop(heap))# -13
print(heapq.heappop(heap))# -1
1.5優先順位キューを実現するコアポイント:heapq.heappush(スタック、value)は、与えられた優先度で要素をソートします.本の例を通して、関連操作を解析しましょう.例1:
import heapq
class PriorityQueue: #
def __init__(self):
self._queue = [] #
self._index = 0
def push(self,item,priority):
heaqp.heappush(self._queue,(-priority, self._index, item))#value
self._index += 1 # ，
def pop(self):
return heapq.heappop(self._queue)[-1]
class Item:
def __init__(self,name):
self.name = name
def __repr__(self):
return 'Item({!r})'.format(self.name) # !r format ， 。
#__repr__ 。
q = PriroityQueue()
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')# priority 。
print(q.pop())# Item('spam')
print(q.pop())# Item('foo')# grok ， grok ，
print(q.pop())# Item('grok')
本の中の実例と元組の対比に関する説明については、私はもう余計なことを言わない.いくつかのheapqモジュールの方法を添付します:heapq.Heapeplace(heap,item):item要素を追加し、heapの最小要素を返します.heapq.heappushpop(heap,item):item要素を追加し、heapの最小要素heapq._を返します.heappop_max(heap):heapの最大値heapqを返します.merge(複数の秩序シーケンス、key:None、reverse:False):秩序シーケンスをマージして反復し、heapq.merge()の反復的性質は、提供されるすべてのシーケンスに対して一度に読み込まないことを意味する.これは、非常に長いシーケンスを処理するのに使用できますが、オーバーヘッドは非常に小さいことを意味します.
1.6ディクショナリで複数の値にキーをマッピングする:コアポイント:1つのキーの多値ディクショナリを作成すると、リストまたはコレクションを使用してこれらの値を保存できます.リストは入力順序を維持し、コレクションは重複要素を除去できます(ただし、順序が乱されます).
方法:1 from collections import defaultdict、defaultdictは最初の値を自動的に初期化し、要素の追加に注目します.
例1:
d= defaultdict(list)
d['a'].append(1)
d['a'].append(2)
d['a'].append(4)
print(d) # defaultdict(, {'a': [1, 2, 4]})
②通常辞書を作成し、setdefaultを呼び出します.
例2:
d = {}
d.setdefault('a',[]).append(1)
d.setdefault('a',[]).append(2)
d.setdefault('b',[]).append(3)
print(d) # {'a': [1, 2], 'b': [3]}
この方法では、setdefaultを呼び出すたびに、初期値の新しいインスタンス-空のリスト[]が作成されます.
例3:
data = [('p',1),('p',2),('p',3)]
d = defaultdict(list)
for key,value in data:
d[key].append(value)
print(d)#defaultdict(, {'p': [1, 2, 3]})
1.7ディクショナリを秩序化するコアポイント:from collections import OrderedDict、ディクショナリを反復すると、要素の初期追加の順序に厳格に従いますが、欠点も明らかです.それは、OrderedDictの内部で双方向チェーンテーブルが維持されているため、通常のディクショナリの2倍以上の大きさなので、使用前にメリットとデメリットを測定する必要があります.
例1
from collections import OrderedDict
d = OrderedDict()
d['foo'] = 1
d['bar'] = 2
d['spam'] = 3
d['grok'] = 4
for key in d:
print(key,d[key])#foo 1 bar 2 spam 3 grok 4
1.8辞書に関する計算問題の核心点:辞書内のデータの最大値の最小値を要求する場合、通常zip()を利用して辞書のキーと値を反転すれば求めることができ、データをソートする必要がある場合はsorted()に協力することができる.
例1
prices = {
'ACME': 45.23,
'AAPL':612.78,
'IBM':205.55,
'HPQ':37.20,
'FB':10.75
}
min_price = min(zip(prices.values(),prices.keys())) # min_price is{10.75,'FB'}
max_price = max(zip(prices.values(),prices.keys()))#max_price is {612.78,'AAPL'}
price_sorted = sorted(zip(prices.values,prices.keys()))
#price_sorted is [(10.75, 'FB'),..., (612.78, 'AAPL')]
*zip()は反復器で作成され、コンテンツは1回しか消費されません.
zip()を使用しない場合は、答えを得るには少なくとも2つのステップが必要です.
min_name = min(prices, lambda k : prices[k])#min_price 'FB'
print(min_name, prices[min_name])#'FB',10.75
1.9同じポイントのコアポイントを2つの辞書で探します.辞書のキー(keys()、items()メソッドを含む)は、パラレルセット、交差、および差セットなどの一般的な集合操作をサポートします.ただし、辞書の値は必ずしも一意ではないため、集合操作は直接サポートされません(集合に移行してから操作できます).
例1:
a = {
'x': 1,
'y': 2,
'z': 3
}
b = {
'x':11,
'y': 2,
'w': 10
}
print(a.keys() & b.keys()) #{'x','y'}
print(a.keys() - b.keys()) #{'z'}
print(a.keys()|b.keys())#{'w', 'z', 'y', 'x'}
print(a.items() & b.items())# {('y',2)}
これらのタイプの操作は、辞書の内容を変更またはフィルタリングするためにも使用できます.次のようになります.
c = {key:a[key] for key in a.keys() -{'z','w'}}
print(c) # {'x':1,'y':2}
1.10繰り返しをシーケンスから削除し、要素間の順序を維持
コアポイント:1シーケンスの値はハッシュ可能で、コレクションとジェネレータを使用して解決できます.
例1:
def dedupe(items):
seen = set()
for item in items:
if item not in seen:# seen ，
yield item
seen.add(item)
a = [1,5,2,1,9,1,5,10]
b = list(dedupe(a))
print(b)#[1, 5, 2, 9, 10]
*returnとyieldの違い:returnは結果を返した後に関数の実行を終了し、yieldは関数をジェネレータにし、ジェネレータは毎回1つの値(yield文)を生成し、関数は凍結され、起動された後に1つの値を生成するので、yieldはreturnよりも速く、空間を節約します.
② （ ） ：
例2:
def dedupe(items,key=None):
seen = set()
for item in items:
val = item if key is None else key(item)
if val not in seen:
yield item
seen.add(val)
a = [{'x':1,'y':2},{'x':1,'y':3},{'x':1,'y':2},{'x':2,'y':4}]
print(list(dedupe(a, key = lambda d: (d['x'],d['y']))))
#[{'x':1,'y':2},{'x':1,'y':3},{'x':2,'y':4}]
print(list(dedupe(a, key = lambda d: d['x'])))
#[{'x':1,'y':2},{'x':2,'y':4}]
この例では、オブジェクトのフィールドまたは属性に基づいて重複項目を除去し、匿名関数によってハッシュ可能なタイプを取得します.
1.11スライスの名前付けコアポイント:コードにハードコーディングされたインデックス値が多数ある場合、その可読性とメンテナンス性は必ず低下し、内蔵slice()関数を使用してスライスオブジェクトを作成し、スライス操作を許可する場所で使用できます.
例1:
items = [0,1,2,3,4,5,6]
a = slice(2,4)
print(items[2:4]) #[2,3]
print(items[a])#[2,3]
sliceスライスとindices(size)メソッドを組み合わせると、インデックス操作でIndexErrorエラーが発生することを防止できます.
print(a.indices(3)) # (2,3,1)
print(a.indices(100))#(2,3,1)
ここでsizeはslice(start,end,step)のend,new_に相当するend = min(end,size)