Logo - LIFE & SHARE - 王颜公子
Loading... RSS

查找最大或最小的N个元素

  • 原创
  • Madman
  • /
  • /
  • 0
  • 6644 次阅读

Synopsis: 如果只想查找最小或最大的元素的话（N=1），请使用 min() 或 max() 函数；如果 N 的大小和容器大小接近的时候，通常先排序这个容器然后再使用切片操作会更快点（ sorted(items)[:N] 或者是 sorted(items)[-N:] ）；当要查找的元素个数相对比较小的时候（N大于1，且N小于容器元素数量），使用 heapq 模块中的 nsmallest() 和 nlargest() 函数是最合适的。需要在正确场合使用函数 nlargest() 和 nsmallest() 才能发挥它们的优势 （如果 N 快接近容器大小了，那么使用排序操作会更好些）

1. N=1时

如果只想查找最小或最大的元素的话，请使用min()或max()函数：

In [1]: nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]

In [2]: min(nums)
Out[2]: -4

In [3]: max(nums)
Out[3]: 42

这两个函数也支持指定key=func来实现自定义的排序：

In [1]: 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}
   ...: ]

In [2]: max(portfolio)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-2-5f0359b97ec9> in <module>()
----> 1 max(portfolio)

TypeError: '>' not supported between instances of 'dict' and 'dict'

In [3]: max(portfolio, key=lambda x: x['price'])
Out[3]: {'name': 'AAPL', 'shares': 50, 'price': 543.22}

In [4]: min(portfolio, key=lambda x: x['price'])
Out[4]: {'name': 'YHOO', 'shares': 45, 'price': 16.35}

2. N接近容器的总大小时

这个时候最优的方案是，先排序这个容器，然后使用切片操作会更快点：

In [1]: nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]

In [2]: sorted(nums)[:8]
Out[2]: [-4, 1, 2, 2, 7, 8, 18, 23]

In [3]: sorted(nums)[-8:]
Out[3]: [2, 7, 8, 18, 23, 23, 37, 42]

In [4]: 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}
   ...: ]

In [5]: sorted(portfolio, key=lambda x: x['price'])[:4]
Out[5]: 
[{'name': 'YHOO', 'shares': 45, 'price': 16.35},
 {'name': 'FB', 'shares': 200, 'price': 21.09},
 {'name': 'HPQ', 'shares': 35, 'price': 31.75},
 {'name': 'IBM', 'shares': 100, 'price': 91.1}]

In [6]: sorted(portfolio, key=lambda x: x['price'])[-4:]
Out[6]: 
[{'name': 'HPQ', 'shares': 35, 'price': 31.75},
 {'name': 'IBM', 'shares': 100, 'price': 91.1},
 {'name': 'ACME', 'shares': 75, 'price': 115.65},
 {'name': 'AAPL', 'shares': 50, 'price': 543.22}]

3. 其它情况

当要查找的元素个数相对比较小的时候（N大于1，且N小于容器元素数量），使用heapq模块中的nsmallest()和nlargest()函数是最合适的：

In [1]: import heapq

In [2]: nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]

In [3]: heapq.nlargest(3, nums)
Out[3]: [42, 37, 23]

In [4]: heapq.nsmallest(3, nums)
Out[4]: [-4, 1, 2]

In [5]: 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}
   ...: ]

In [6]: heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
Out[6]: 
[{'name': 'YHOO', 'shares': 45, 'price': 16.35},
 {'name': 'FB', 'shares': 200, 'price': 21.09},
 {'name': 'HPQ', 'shares': 35, 'price': 31.75}]

In [7]: heapq.nlargest(3, portfolio, key=lambda s: s['price'])
Out[7]: 
[{'name': 'AAPL', 'shares': 50, 'price': 543.22},
 {'name': 'ACME', 'shares': 75, 'price': 115.65},
 {'name': 'IBM', 'shares': 100, 'price': 91.1}]

在底层实现里面，首先会先将容器数据进行堆排序后放入一个列表中：

In [1]: import heapq

In [2]: nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]

In [3]: heap = list(nums)

In [4]: heapq.heapify(heap)

In [5]: heap
Out[5]: [-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]  # 第一个元素是最小的

堆数据结构最重要的特征是heap[0]永远是最小的元素，并且剩余的元素可以很容易的通过调用heapq.heappop()方法得到， 该方法会先将第一个元素弹出来，然后用下一个最小的元素来取代被弹出元素（这种操作时间复杂度仅仅是O(log N)，N 是堆大小）。 比如，如果想要查找最小的 3 个元素，你可以这样做：

In [6]: heapq.heappop(heap)
Out[6]: -4

In [7]: heapq.heappop(heap)
Out[7]: 1

In [8]: heapq.heappop(heap)
Out[8]: 2
分类: 数据结构与算法
标签: heapq max min nlargest nsmallest 切片 sorted
未经允许不得转载: LIFE & SHARE - 王颜公子 » 查找最大或最小的N个元素

分享

相关推荐

作者

作者头像

Madman

如需 Linux / Python 相关问题付费解答，请按如下方式联系我

0 条评论

暂时还没有评论.

专题系列

热门文章

归档

随机文章

热门标签

文章目录