Python cookbook(数据结构与算法)找到最大或最小的N个元素实现方法示例

本文实例讲述了python找到最大或最小的N个元素实现方法。分享给大家供大家参考,具体如下:

问题:想在某个集合中找出最大或最小的N个元素

解决方案:heapq模块中的nlargest()nsmallest()两个函数正是我们需要的。

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

这两个函数接受一个参数key,允许其工作在更复杂的数据结构之上:

# example.py
#
# Example of using heapq to find the N smallest or largest items
import heapq
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'])
print(cheap)
print(expensive)
Python 3.4.0 (v3.4.0:04f714765c13, Mar 16 2014, 19:24:06) [MSC v.1600 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>>
[{'name': 'YHOO', 'price': 16.35, 'shares': 45}, {'name': 'FB', 'price': 21.09, 'shares': 200}, {'name': 'HPQ', 'price': 31.75, 'shares': 35}]
[{'name': 'AAPL', 'price': 543.22, 'shares': 50}, {'name': 'ACME', 'price': 115.65, 'shares': 75}, {'name': 'IBM', 'price': 91.1, 'shares': 100}]
>>>

如果正在寻找的最大或最小的N个元素,且相比于集合中元素的数量,N很小时,下面的函数性能更好。

这些函数首先会在底层将数据转化为列表,且元素会以堆的顺序排列。

>>> import heapq
>>> nums=[1,8,2,23,7,-4,18,23,42,37,2]
>>> heap=list(nums)
>>> heap
[1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
>>> heapq.heapify(heap) #heapify()参数必须是list,此函数将list变成堆,实时操作。从而能够在任何情况下使用堆的函数。
>>> heap
[-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]
>>> heapq.heappop(heap)#如下是为了找到第3小的元素
-4
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
2
>>>

堆(heap)最重要的特性就是heap[0]总是最小的元素。可通过heapq.heappop()轻松找到最小值,这个操作的复杂度为O(logN),N代表堆得大小。

总结:

1、当要找的元素数量相对较小时,函数nlargest()nsmallest()才最适用。
2、若只是想找到最小和最大值(N=1)时,使用min()和max()会更快。
3、若N和集合本身的大小差不多,更快的方法是先对集合排序再进行切片操作(例如使用sorted(items)[:N]sorted(items)[-N:]
4、heapq.heappush(heap, item):将item压入到堆数组heap中。如果不进行此步操作,后面的heappop()失效;
heapq.heappop(heap):从堆数组heap中取出最小的值,并返回。
heapq.heapify(list):参数必须是list,此函数将list变成堆,实时操作。从而能够在任何情况下使用堆的函数。
heapq.heappushpop(heap, item):是上述heappush和heappop的合体,同时完成两者的功能.注意:相当于先操作了heappush(heap,item),然后操作heappop(heap)
heapreplace(heap, item):是heappop(heap)和heappush(heap,item)的联合操作。注意,与heappushpop(heap,item)的区别在于,顺序不同,这里是先进行删除,后压入堆
heap,merge(*iterables)

>>> h=[]   #定义一个list
>>> from heapq import * #引入heapq模块
>>> h
[]
>>> heappush(h,5)  #向堆中依次增加数值
>>> heappush(h,2)
>>> heappush(h,3)
>>> heappush(h,9)
>>> h    #h的值
[2, 5, 3, 9]
>>> heappop(h)   #从h中删除最小的,并返回该值
2
>>> h
[3, 5, 9]
>>> h.append(1)   #注意,如果不是压入堆中,而是通过append追加一个数值
>>> h    #堆的函数并不能操作这个增加的数值,或者说它堆对来讲是不存在的
[3, 5, 9, 1]
>>> heappop(h)   #从h中能够找到的最小值是3,而不是1
3
>>> heappush(h,2)  #这时,不仅将2压入到堆内,而且1也进入了堆。
>>> h
[1, 2, 9, 5]
>>> heappop(h)   #操作对象已经包含了1
1
>>> h
[1, 2, 9, 5]
>>> heappop(h)
1
>>> heappushpop(h,4)  #增加4同时删除最小值2并返回该最小值,与下列操作等同:
2    #heappush(h,4),heappop(h)
>>> h
[4, 5, 9]
>>> a=[3,6,1]
>>> heapify(a)   #将a变成堆之后,可以对其操作
>>> heappop(a)
1
>>> b=[4,2,5]   #b不是堆,如果对其进行操作,显示结果如下
>>> heappop(b)   #按照顺序,删除第一个数值并返回,不会从中挑选出最小的
4
>>> heapify(b)   #变成堆之后,再操作
>>> heappop(b)
2
>>> a=[]
>>> heapreplace(a,3)  #如果list空,则报错
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: index out of range
>>> heappush(a,3)
>>> a
[3]
>>> heapreplace(a,2)  #先执行删除(heappop(a)->3),再执行加入(heappush(a,2))
3
>>> a
[2]
>>> heappush(a,5)
>>> heappush(a,9)
>>> heappush(a,4)
>>> a
[2, 4, 9, 5]
>>> heapreplace(a,6)  #先从堆a中找出最小值并返回,然后加入6
2
>>> a
[4, 5, 9, 6]
>>> heapreplace(a,1)  #1是后来加入的,在1加入之前,a中的最小值是4
4
>>> a
[1, 5, 9, 6]
>>> a=[2,4,6]
>>> b=[1,3,5]
>>> c=merge(a,b)
>>> list(c)
[1, 2, 3, 4, 5, 6]

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

您可能感兴趣的文章:

  • Python cookbook(数据结构与算法)保存最后N个元素的方法
  • Python cookbook(数据结构与算法)从任意长度的可迭代对象中分解元素操作示例
  • Python cookbook(数据结构与算法)将序列分解为单独变量的方法
  • 利用Python找出序列中出现最多的元素示例代码
  • Python找出list中最常出现元素的方法
  • python查找第k小元素代码分享
  • Python实现的数据结构与算法之链表详解
  • Python实现的数据结构与算法之快速排序详解
  • Python实现的数据结构与算法之队列详解
  • Python实现的数据结构与算法之基本搜索详解
  • Python数据结构与算法之图结构(Graph)实例分析
(0)

相关推荐

  • Python数据结构与算法之图结构(Graph)实例分析

    本文实例讲述了Python数据结构与算法之图结构(Graph).分享给大家供大家参考,具体如下: 图结构(Graph)--算法学中最强大的框架之一.树结构只是图的一种特殊情况. 如果我们可将自己的工作诠释成一个图问题的话,那么该问题至少已经接近解决方案了.而我们我们的问题实例可以用树结构(tree)来诠释,那么我们基本上已经拥有了一个真正有效的解决方案了. 邻接表及加权邻接字典 对于图结构的实现来说,最直观的方式之一就是使用邻接列表.基本上就是针对每个节点设置一个邻接列表.下面我们来实现一个最简

  • python查找第k小元素代码分享

    复制代码 代码如下: # -*- coding: utf-8 -*- from random import randintfrom math import ceil, floor def _partition(A, l, r, i):    """以A[i]为主元划分数组A[l..r],使得:    A[l..m-1] <= A[m] < A[m+1..r]    """    A[i], A[r] = A[r], A[i] # i交

  • Python实现的数据结构与算法之队列详解

    本文实例讲述了Python实现的数据结构与算法之队列.分享给大家供大家参考.具体分析如下: 一.概述 队列(Queue)是一种先进先出(FIFO)的线性数据结构,插入操作在队尾(rear)进行,删除操作在队首(front)进行. 二.ADT 队列ADT(抽象数据类型)一般提供以下接口: ① Queue() 创建队列 ② enqueue(item) 向队尾插入项 ③ dequeue() 返回队首的项,并从队列中删除该项 ④ empty() 判断队列是否为空 ⑤ size() 返回队列中项的个数 队

  • Python实现的数据结构与算法之快速排序详解

    本文实例讲述了Python实现的数据结构与算法之快速排序.分享给大家供大家参考.具体分析如下: 一.概述 快速排序(quick sort)是一种分治排序算法.该算法首先 选取 一个划分元素(partition element,有时又称为pivot):接着重排列表将其 划分 为三个部分:left(小于划分元素pivot的部分).划分元素pivot.right(大于划分元素pivot的部分),此时,划分元素pivot已经在列表的最终位置上:然后分别对left和right两个部分进行 递归排序. 其中

  • 利用Python找出序列中出现最多的元素示例代码

    前言 Python包含6种内置的序列:列表.元组.字符串 .Unicode字符串.buffer对象.xrange对象.在序列中的每个元素都有自己的编号.列表与元组的区别在于,列表是可以修改,而组元不可修改.理论上几乎所有情况下元组都可以用列表来代替.有个例外是但元组作为字典的键时,在这种情况下,因为键不可修改,所以就不能使用列表. 我们在一些统计工作或者分析过程中,有事会遇到要统计一个序列中出现最多次的元素,比如一段英文中,查询出现最多的词是什么,及每个词出现的次数.一遍的做法为,将每个此作为k

  • Python实现的数据结构与算法之基本搜索详解

    本文实例讲述了Python实现的数据结构与算法之基本搜索.分享给大家供大家参考.具体分析如下: 一.顺序搜索 顺序搜索 是最简单直观的搜索方法:从列表开头到末尾,逐个比较待搜索项与列表中的项,直到找到目标项(搜索成功)或者 超出搜索范围 (搜索失败). 根据列表中的项是否按顺序排列,可以将列表分为 无序列表 和 有序列表.对于 无序列表,超出搜索范围 是指越过列表的末尾:对于 有序列表,超过搜索范围 是指进入列表中大于目标项的区域(发生在目标项小于列表末尾项时)或者指越过列表的末尾(发生在目标项

  • Python找出list中最常出现元素的方法

    本文实例讲述了Python找出list中最常出现元素的方法.分享给大家供大家参考,具体如下: 假设一个list中保存着各种元素,需要统计每个元素出现的个数,并打印出最常出现的前三个元素分别是什么.list如下: 复制代码 代码如下: word_list =["is","you","are","I","am","OK","is","OK","

  • Python cookbook(数据结构与算法)保存最后N个元素的方法

    本文实例讲述了Python保存最后N个元素的方法.分享给大家供大家参考,具体如下: 问题:希望在迭代或是其他形式的处理过程中对最后几项记录做一个有限的历史记录统计 解决方案:选择collections.deque. 如下的代码对一系列文本行做简单的文本匹配操作,当发现有匹配时就输出当前的匹配行以及最后检查过的N行文本: from collections import deque def search(lines, pattern, history=5): previous_lines = deq

  • Python cookbook(数据结构与算法)从任意长度的可迭代对象中分解元素操作示例

    本文实例讲述了python从任意长度的可迭代对象中分解元素操作.分享给大家供大家参考,具体如下: 从某个可迭代对象中分解出N个元素,但是可迭代对象的长度可能超过N,会出现"分解值过多"的异常: 使用"*表达式"来解决该问题: Python 3.4.3 (v3.4.3:9b73f1c3e601, Feb 24 2015, 22:43:06) [MSC v.1600 32 bit (Intel)] on win32 Type "copyright",

  • Python cookbook(数据结构与算法)将序列分解为单独变量的方法

    本文实例讲述了Python cookbook(数据结构与算法)将序列分解为单独变量的方法.分享给大家供大家参考,具体如下: 如果对象是可迭代的(任何序列),则可以进行分解操作,包括元组.列表.字符串.文件.迭代器以及生成器,可通过简单的一个赋值操作分解为单独的变量. 唯一要求:变量的总数和序列相吻合,否则将出错: Python 2.7.11 (v2.7.11:6d1b6a68f775, Dec 5 2015, 20:32:19) [MSC v.1500 32 bit (Intel)] on wi

  • Python实现的数据结构与算法之链表详解

    本文实例讲述了Python实现的数据结构与算法之链表.分享给大家供大家参考.具体分析如下: 一.概述 链表(linked list)是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接. 根据结构的不同,链表可以分为单向链表.单向循环链表.双向链表.双向循环链表等.其中,单向链表和单向循环链表的结构如下图所示: 二.ADT 这里只考虑单向循环链表ADT,其他类型的链表ADT大同小异.单向循环链表ADT(抽象数据类型)一般提供以下接口: ① SinCycLin

随机推荐