首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >从一个集合中查找最大最小的N个元素——Python heapq 堆数据结构

从一个集合中查找最大最小的N个元素——Python heapq 堆数据结构

作者头像
Linux云计算网络
发布2018-01-11 10:46:48
1.3K0
发布2018-01-11 10:46:48
举报
文章被收录于专栏:Linux云计算网络Linux云计算网络

Top N问题在搜索引擎、推荐系统领域应用很广, 如果用我们较为常见的语言,如C、C++、Java等,代码量至少也得五行,但是用Python的话,只用一个函数就能搞定,只需引入heapq(堆队列)这个数据结构即可。今天偶然看到这个库,特意记下之。

先看一个例子:

1 >>> import heapq
2 >>> nums = [1,8,2,23,7,-4,18,23,42,37,2]
3 >>> print heapq.nlargest(3, nums)
4 [42, 37, 23]
5 >>> 
6 >>> print heapq.nsmallest(3, nums)
7 [-4, 1, 2]

是不是很简洁? 我们具体来看一下具体的函数定义。heapq有很多函数,最为堆,队列,可想而知,也就是那些push,pop之类的操作,详细请看官方文档:https://docs.python.org/2/library/heapq.html,在这里,我们只看Top N的两个函数,其他函数在用到的时候查看文档就好了。

1)、heapq.nlargest(n, iterable[, key])

从迭代器对象iterable中返回前n个最大的元素列表,其中关键字参数key用于匹配是字典对象的iterable,用于更复杂的数据结构中。

2)、heapq.nsmallest(n, iterable[, key])

从迭代器对象iterable中返回前n个最小的元素列表,其中关键字参数key用于匹配是字典对象的iterable,用于更复杂的数据结构中。

关于第三个参数的应用,我们来看一个例子就明白了。

 1 >>> portfolio = [
 2     {'name': 'IBM', 'shares': 100, 'price': 91.1},
 3     {'name': 'AAPL', 'shares': 50, 'price': 543.22},
 4     {'name': 'FB', 'shares': 200, 'price': 21.09},
 5     {'name': 'HPQ', 'shares': 35, 'price': 31.75},
 6     {'name': 'YHOO', 'shares': 45, 'price': 16.35},
 7     {'name': 'ACME', 'shares': 75, 'price': 115.65}
 8 ]
 9 ... ... ... ... ... ... ... >>> 
10 >>> cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
11 >>> print cheap
12 [{'price': 16.35, 'name': 'YHOO', 'shares': 45}, {'price': 21.09, 'name': 'FB', 'shares': 200}, {'price': 31.75, 'name': 'HPQ', 'shares': 35}]
13 >>> expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])
14 >>> print expensive
15 [{'price': 543.22, 'name': 'AAPL', 'shares': 50}, {'price': 115.65, 'name': 'ACME', 'shares': 75}, {'price': 91.1, 'name': 'IBM', 'shares': 100}]
16 >>> 

从例子中可以看出,key匹配了portfolio中关键字为‘price’的一行。 到此为止,关于如何应用heapq来求Top N问题,相比通过上面的例子讲解,已经较为熟悉了。现在有几个需要注意的地方:

1)heapq.heapify(iterable):可以将一个列表转换成heapq

2)在Top N问题中,如果N=1,则直接用max(iterable)/min(iterable)即可。

3)如果N很大,接近集合元素,则为了提高效率,采用sort+切片的方式会更好,如:

求最大的N个元素:sorted(iterable, key=key, reverse=True)[:N]

求最小的N个元素:sorted(iterable, key=key)[:N]

1 >>> nums = [1,8,2,23,7,-4,18,23,42,37,2]
2 >>> max(nums)
3 42
4 >>> min(nums)
5 -4
6 >>> print sorted(nums, reverse=True)[:3]
7 [42, 37, 23]
8 >>> print sorted(nums)[:3]
9 [-4, 1, 2]
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2015-09-14 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档