1.查找最大或最小的N个元素
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] # 可以接受关键字参数,用于更复杂的数据结构 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'])
讨论, 堆数据结构里heap[0]永远是最小的元素,剩余最小的通过heapq.heappop()得到,时间复杂度是O(log N).查找最小的三个可以写成
heapq.heappop(heap)
heapq.heappop(heap)
heapq.heappop(heap)
==>当查找的元素个数相对比较小的时候,nlargest()和nsmallest比较合适.
==>仅查找最大值或最小值, min()和max()函数会更快
==>如果查找的数量跟集合本身差不多大,应该先排序,再使用切片操作sorted(items)[:N]和sorted(items)[-N:]
2.元祖是可以比较大小的
a = (1, 2, 'dandy')
b = (10, 4, 'sam')
c = (1, 3, 'tom')
d = (1, 2, 'dandy1') print(a < b) # True
print(a < c) # True
print(a < d) # True
元祖会按照第一个元素,第二个元素的顺序进行比较大小.
那列表呢?
a = [1, 2]
b = [1, 3]
c = [2, 3]
print(a < b) # True
print(a < c) # True
元祖的混合数据比较呢?
class Foo:
def __init__(self, a):
self.a = a a = (1, 2, [3, 4])
b = (1, 2, [4, 5])
c = (1, Foo(1))
print(a > b) # False
print(a > c)
Traceback (most recent call last):
File "/home/dandy/Documents/charm/cookbook/1算法和数据结构/13test.py", line 32, in <module>
print(a > c)
TypeError: '>' not supported between instances of 'int' and 'Foo'
上面的扩展跳跃性有点强,直接从常用的数据结构扩展到了对象的比较.可以发现报错了,报错内容为Foo类没有实现比较运算符.在一个类内,比较运算符的实现是依赖__lt__, __eq__, __gt__这三个内置函数的,分别对应'<', '==', '>'.在上面的比较内
1.解析a > c
2.比较a和c的第一个元素,a[0] > c[0], 结果是相等,跳到下一个元素
3.比较a和c的第二个元素,a[1] > c[1],此时c[1]是一个实例,以c[1]为中心的话,可以看做foo(1) < a[1],Foo没有实现__lt__这个内置方法.
大结局:只要对象实现上述的三种比较方法__lt__, __eq__, __gt__就可以进行比较大小了,python的对象确实也是这么做的. 很多都是c实现的,__lt__, __eq__, __gt__相当于留给开发人员的外部接口,可以重写或者定义其内置方法.
class Foo:
def __init__(self, a):
self.a = a def __lt__(self, other):
return self.a > other a = (1, 2, [3, 4])
b = (1, 2, [4, 5])
c = (1, Foo(1))
print(a > b) # False
print(a > c) # False
3.字典的默认值
# pairs是一组新增数据,需要按照key,加入到字典d对应的字段的列表内
pairs = {'a': 1, 'b': 2, 'c': 3} d = {} for key, value in pairs:
if key not in d:
d[key] = []
d[key].append(value)
可以用字典的setdefault方法来解决:
pairs = {'a': 1, 'b': 2, 'c': 3}
d = {}
for key, value in pairs:
d.setdefault(key, []).append(value)
这样就会方便很多,但还是有点别扭,因为每次调用都要创建一个新的初始值的实例.引入内置的defaultdict,在字典对象申明的时候直接定义好value的对象
d = defaultdict(list) for key, value in pairs:
d[key].append(value)
4.字典比较大小
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')
排序输出
prices_sorted = sorted(zip(prices.values(), prices.keys()))
# prices_sorted is [(10.75, 'FB'), (37.2, 'HPQ'),
# (45.23, 'ACME'), (205.55, 'IBM'),
# (612.78, 'AAPL')]
讨论通常的做法
min(prices.values()) # Returns 10.75
max(prices.values()) # Returns 612.78 min(prices, key=lambda k: prices[k]) # Returns 'FB'
max(prices, key=lambda k: prices[k]) # Returns 'AAPL' # 上面的方式不能输出完整的键值对 min_value = prices[min(prices, key=lambda k: prices[k])]
# 需要进行2次查找操作,时间复杂度高