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

  • 原创
  • Madman
  • /
  • 2018-06-12 17:08
  • /
  • 0
  • 340 次阅读

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
未经允许不得转载: LIFE & SHARE - 王颜公子 » 查找最大或最小的N个元素

分享

作者

作者头像

Madman

如果博文内容有误或其它任何问题,欢迎留言评论,我会尽快回复; 或者通过QQ、微信等联系我

0 条评论

暂时还没有评论.

发表评论前请先登录