美文网首页
Python数据结构和算法

Python数据结构和算法

作者: Echocipher | 来源:发表于2019-01-10 11:35 被阅读0次

将序列分解为单独变量

我们有一个N个元素的元组或者序列,想要分解为N个单独的变量

解决方案:任何序列或者可迭代的对象(包括字符串,文件,迭代器以及生成器)都要通过一个简单的赋值操作来分解为单独的变量,要求是变量的总数和结构要与序列吻合。

Python 3.7.2 (tags/v3.7.2:9a3ffc0492, Dec 23 2018, 23:09:28) [MSC v.1916 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> p = (4,5)
>>> x,y = p
>>> x
4
>>> y
5

从任意长度的可迭代对象中分解元素

上面我们说过可以通过赋值操作来分解单独的变量,但是要求变量总数与结构要与序列吻合,如果需要从某个可迭代对象中分解出N个元素,但是可迭代的对象长度超过N的时候就会导致如下异常:

Python 3.7.2 (tags/v3.7.2:9a3ffc0492, Dec 23 2018, 23:09:28) [MSC v.1916 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> p = (1,2,3)
>>> x,y = p
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: too many values to unpack (expected 2)

解决方案:利用*表达式,可以处理分解位置或者任意长度的可迭代对象,或者在迭代一个变长的元组序列,以及结合某些特定的字符串处理操作,比如拆分操作。

Python 3.7.2 (tags/v3.7.2:9a3ffc0492, Dec 23 2018, 23:09:28) [MSC v.1916 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> *headdata,current=[10,3,2,6,8,5] #*修饰的变量位于列表第一个位置,轻松分别头部和尾部
>>> headdata
[10, 3, 2, 6, 8]
>>> current
5
>>> record=('dave','dave@example.com','773-555-1212','847-555-1212')
>>> name,email,*phone_numbers=record#*修饰的变量位于列表最后一个位置
>>> name
'dave'
>>> email
'dave@example.com'
>>> phone_numbers
['773-555-1212', '847-555-1212']
>>> line='nobody:*:-2:-3:Unpriviledged User:/var/empty:/usr/bin/false'
>>> uname,*fields,homedir,sh=line.split(':') #*修饰的变量位于中间位置,且与字符串处理操作相结合
>>> uname
'nobody'
>>> homedir
'/var/empty'
>>> sh
'/usr/bin/false'
>>> fields
['*', '-2', '-3', 'Unpriviledged User']

保存最后N个元素

deque(maxlen=N)创建一个固定长度的队列,当有新的记录加入而队列已经满时,会自动移除老的记录(队列更加优雅和快速),如果不指定队列的大小,就会得到一个无界限的队列。

Python 3.7.2 (tags/v3.7.2:9a3ffc0492, Dec 23 2018, 23:09:28) [MSC v.1916 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> from collections import deque
>>> q = deque(maxlen=3)
>>> q.append(1)
>>> q.append(2)
>>> q.append(3)
>>> q
deque([1, 2, 3], maxlen=3)
>>> q.append(4)
>>> q
deque([2, 3, 4], maxlen=3)

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

可以用最大(最小)堆。假设现在要找N个最大的元素,则首先把前N个元素入堆,并形成最小堆(堆顶元素为最小元素),下面每次有新元素来都和堆顶元素比较,如果小于等于堆顶元素则抛弃,否则删除堆顶元素并将新元素入堆,并维持堆序。如此下去直到遍历所有元素。heapq模块中的nlargest()和nsmallest()两个函数正好可以实现我们的需求。

Python 3.7.2 (tags/v3.7.2:9a3ffc0492, Dec 23 2018, 23:09:28) [MSC v.1916 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import heapq
>>> nums = [1,2,3,4,5,6,7,8,9]
>>> print(heapq.nlargest(3,nums))
[9, 8, 7]
>>> print(heapq.nsmallest(3,nums))
[1, 2, 3]

如果同集合中元素总数目相比,N很小,那么下面的函数可以提供更好的性能,首先会在底层将数据转换成列表,且元素会以堆的顺序排列。

Python 3.7.2 (tags/v3.7.2:9a3ffc0492, Dec 23 2018, 23:09:28) [MSC v.1916 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> nums = [1,5,3,-6,33,44,67]
>>> import heapq
>>> heap = list(nums)
>>> heapq.heapify(heap)
>>> heap
[-6, 1, 3, 5, 33, 44, 67]

如果N与集合本身的大小差不多,通常更快的方法是先对集合排序,再切片,这两个函数实际实现会跟使用它们的方法不同,会做一些优化,比如N大小与集合相近的时候,会采用排序的方法。

在字典中将键映射到多个值上

通常可以使用集合或者列表来实现:

d = {
    'a' : [1, 2, 3],
    'b' : [4, 5],  
}
 
e = {
    'a' : [1, 2, 3],
    'b' : [4, 5],  
}

为了能更方便的创建字典,可以使用defaultdict:

Python 3.7.2 (tags/v3.7.2:9a3ffc0492, Dec 23 2018, 23:09:28) [MSC v.1916 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> d['a'].append(1)
>>> d['a'].append(2)
>>> d['b'].append(4)
>>> print(d)
defaultdict(<class 'list'>, {'a': [1, 2], 'b': [4]})

创建一键多值的字典很容易,但是如果试着对第一个值初始化的时候,就会变得杂乱:

d = {}
for key, value in pairs:
    if key not in d:
        d[key] = []
    d[key].append(value)

使用defaultdict后代码会清晰很多:

d = defaultdict(list)
for key, value in pairs:
    d[key].append(value)

参考来源:

  1. 《Python Cookbook》

相关文章

  • 个人 Python 书单

    入门: Beginning Python 数据结构: Python 数据结构 算法: Python 算法教程

  • 10.数据结构和算法 初识

    1、数据结构与算法(Python) 数据结构和算法是什么?答曰:兵法! 1.1算法的概念 算法是计算机处理信息的本...

  • python数据结构与算法总结

    python常用的数据结构与算法就分享到此处,本月涉及数据结构与算法的内容有如下文章: 《数据结构和算法对pyth...

  • python学习资料

    算法:Python中数据结构和算法的最小例子https://github.com/keon/algorithms?...

  • 数据结构和算法(六)

    1. Python 内置数据结构和算法 使用过哪些内置的常用的算法和数据结构 sorted:排序 dict、lis...

  • 数据结构和算法对python意味着什么?

    数据结构和算法对于python而言是他的灵魂;程序是数据结构加上算法来实现的,对于任何一门编程语言都离不开数据结构...

  • 数据结构与算法基本概念

    数据结构与算法 本文包括: 算法概念 时间复杂度 大 O 记法 数据结构概念 Python 内置类型的效率 算法的...

  • Python语言进阶

    Python语言进阶 数据结构和算法 算法:解决问题的方法和步骤 评价算法的好坏:渐近时间复杂度和渐近空间复杂度。...

  • 首位交易循环机制(TTCM)的Python实现

    Xc.LiFeb.2016 算法原理 首位交易循环机制的算法,略。 Python实现 学校和学生的数据结构 学校 ...

  • python面试算法

    python内置数据结构算法常考 常用的内置算法和数据结构 sorted排序函数 dict/list/set/tu...

网友评论

      本文标题:Python数据结构和算法

      本文链接:https://www.haomeiwen.com/subject/husorqtx.html