『Python CookBook』読書ノート-データ構造とアルゴリズム(一)

1.シーケンスLを、n(n<=len(l))個の個別変数を含むように分割する
使用法

data = ['ACME', 50, 90, (2017, 3, 8)]
name, shares, price, date = data
print(name, date)
name, _, _, (year, *_) = data    #               
print(name, year)

ACME (2017, 3, 8)
ACME 2017

説明
分解操作では、いくつかの値を破棄する必要がある場合があります.通常、一般的に使用できない変数名を選択して、これらの破棄する要素を表すことができます.例えば、'','','ign(ignored)', 'ign'.この*式の構文は、未知または任意の長さの反復可能なオブジェクトを分解する場合に特に役立ちます.
例

#                  
def drop_first_last(grades):
    first, *middle, last = grades
    return avg(middle)

#     
def sum(items):
    head, *tail = items
    return head + sum(tail) if tail else head

2.heapqモジュールで最大または最小のN個の要素を探す
使用法

import heapq
import random

nums = random.sample(range(-20, 50), 10) #  range(-20, 50)     10   
print(nums)
print(heapq.nlargest(3, nums))
print(heapq.nsmallest(3, nums))

dict_nums = [dict.fromkeys('a', i) for i in nums]
print(dict_nums)
print(heapq.nlargest(3, dict_nums, key=lambda s: s['a'])) #       key，                
print(heapq.nsmallest(3, dict_nums, key=lambda s: s['a']))

heap = list(nums)
heapq.heapify(heap) #  nums         
print(heap)
print(heapq.heappop(heap)) # heap[0]        ，heappop       ，             
print(heapq.heappop(heap))

[-1, 43, 16, 47, 31, -11, 4, 49, 13, 28]
[49, 47, 43]
[-11, -1, 4]
[{'a': -1}, {'a': 43}, {'a': 16}, {'a': 47}, {'a': 31}, {'a': -11}, {'a': 4}, {'a': 49}, {'a': 13}, {'a': 28}]
[{'a': 49}, {'a': 47}, {'a': 43}]
[{'a': -11}, {'a': -1}, {'a': 4}]
[-11, 13, -1, 43, 28, 16, 4, 49, 47, 31]
-11
-1

説明

スタックの最も重要な特性はheap[0]が常に最小であるその要素

である.

探している要素の数が相対的に小さい場合、nlargest()とnsmallest()が適用されます.nlargest()とnsmallest()の実際の実装は、それらを適用する方法によって異なります.例えば、Nが集合している場合、

が先にソートされます.

最小または最大の要素を簡単に見つけるだけであれば、min()およびmax()を用いて

を適切にする.

Nと集合自体の大きさの差が少ない場合、通常より速い方法は、集合を並べ替えてからスライス操作

を行うことである.
3.優先順位キューの実装
に質問
与えられた優先度で要素をソートできるキューを実装し、pop操作のたびに最も優先度の高い要素を返します.
ソリューション

import heapq

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]
    
pq = PriorityQueue()
pq.push('jlan', 5)
pq.push('hua', 2)
pq.push('lann', 4)
pq.push('bob', 1)
pq.push('han', 3)
print(pq._queue)
print(pq.pop())
print(pq._queue)
print(pq.pop())

[(-5, 0, 'jlan'), (-3, 4, 'han'), (-4, 2, 'lann'), (-1, 3, 'bob'), (-2, 1, 'hua')]
jlan
[(-4, 2, 'lann'), (-3, 4, 'han'), (-2, 1, 'hua'), (-1, 3, 'bob')]
lann

説明(詳細はP 10参照)

このスキームの核心はheapqモジュールの使用にある.heappush()とheapppop()はそれぞれ_Queueでの挿入と削除は、リスト内の最初の要素の優先度が最も低いことを保証します.heapppop()は常に「最小」要素を返すので、キューが正しい要素をポップアップできる鍵です.

このコードでは、キューはメタグループ(-priority,index,item)の形で構成され、priorityが負の値をとるのは、キューが優先度で高いものから最後までソートできるようにするため(通常、スタックは小さいものから大きいものまでソートされる)、スタックを構築するときに-priorityでソートされ、priorityが同じ場合にindexでソートされる.

変数indexの役割は、同じ優先度を有する要素を適切な順序(エンキュー順序)で配列することである.

辞書アクション

キーを複数の値にマッピングする

from collections import defaultdict

d = defaultdict(list)
d['a'].append(1)
d['a'].append(2)
print(d)

defaultdict(, {'a': [1, 2]})

秩序辞書collectionsを使用する.OrderedDictは辞書の順序を保つことができ、OrderedDictの内部には双方向チェーンテーブルが維持され、要素が加えられた順序に基づいてキーの位置が並べられます.OrderedDictの大きさは普通の辞書の2倍以上です.

辞書で最大値、最小値などを求める操作

を行う.

prices = {
    'apple': 2,
    'banada': 3,
    'orange': 1,
    'peach': 4
}

#            ，     ，    
min(prices) #   'apple'
max(prices) #   'peach'

#    dict.values()    
min(prices.values()) #    1
max(prices.values()) #    4

min(prices, key=lambda x: prices[x]) #   'orange'
max(prices, key=lambda x: prices[x]) #   'peach'

#          ，              
min(zip(prices.values(), prices.keys())) #   (1, 'orange')
max(zip(prices.values(), prices.keys())) #   (4, 'orange')
# zip()        ，          
#   (value, key)     ，          value，     key    

(4, 'peach')

辞書で同じ点を探す

#              （       ）
a = {'x': 1, 'y': 2, 'z': 3}
b = {'w': 11, 'y': 2, 'z': 13}

# a b    
a.keys() & b.keys() #    {'y', 'z'}

#  a     b   
a.keys() - b.keys() #    {'x'}

# a b    {key: value}
a.items() & b.items() #    {('y', 2)}

{('y', 2)}