1.数据结构和算法

数据结构和算法

将序列分解为单独的变量

任何序列都可以通过一个简单的赋值操作来分解为单独的变量,包括字典、集合、字符串、文件、迭代器和生成器

p =(4,5)

a,b=p

print(a)
print(b)

#4
#5

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

可以使用*表达式

>>> record = ["David","12334@qq.com","123456","456789"]
>>> name,email,*phone_number = record
>>> name
'David'
>>> email
'12334@qq.com'
>>> phone_number
['123456', '456789']
#拆分头部和尾部
>>> items =[1,2,3,4,5,6]
>>> head,*tail = items
>>> head
1
>>> tail
[2, 3, 4, 5, 6]
#指定一个单独的变量名丢弃没用的数据
>>> record = ("ACME",50,123.45,(12,18,2012))
>>> name,*_,(*_,year) =record
>>> name
'ACME'
>>> year
2012

保存最后N个元素

为了能够保存有限的历史记录,我们可以使用下面的代码

from collections import deque

def  search(lines,pattern,history=3):
    #创建一个保存历史记录的队列
    prevlines_lines= deque(maxlen=3)
    for line in lines:
        if pattern in line:
            #构造迭代器
            yield line,prevlines_lines
        prevlines_lines.append(line)

if __name__ == '__main__':
    with open("test.txt") as f:
        for line,prevlines in search(f,"hello",3):
            print("当前行:",line)
            print("历史记录:")
            for prevline in prevlines:
                print(prevline,end ="")
            print()

# 当前行: hello

# 历史记录:

# 当前行: hello,world

# 历史记录:
# hello

# 当前行: hello,siqu

# 历史记录:
# hello
# hello,world

# 当前行: hello,yunzhong
# 历史记录:
# hello
# hello,world
# hello,siqu

deque(maxlen=N)创建了一个长度为N的队列

>>> from collections import deque
#创建一个长度不固定的队列
>>> que = deque()
>>> que.append(1)
>>> que.append(2)
>>> que
deque([1, 2])
>>> que.appendleft(4)
>>> que
deque([4, 1, 2])
>>> que.pop()
2
>>> que
deque([4, 1])
>>> que.popleft()
4
>>> que
deque([1])

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

import heapq

nums =[2,34,11,3,54,6,76,23,4,5]

#找到最大的3个元素
print(heapq.nlargest(3,nums))

#找到最小的3个元素
print(heapq.nsmallest(3,nums))

portfolio=[
    {"name":"siqu","price":20},
    {"name":"xm","price":21},
    {"name":"xh","price":12},
    {"name":"xc","price":9}
]

#使用key来用于更加复杂的结构
print(heapq.nlargest(2,portfolio,key=lambda s:s["price"]))
print(heapq.nsmallest(2,portfolio,key=lambda s:s["price"]))

# [76, 54, 34]
# [2, 3, 4]
# [{'name': 'xm', 'price': 21}, {'name': 'siqu', 'price': 20}]
# [{'name': 'xc', 'price': 9}, {'name': 'xh', 'price': 12}]
#同集合当中的数目相比,N很小时
import heapq

nums =[23,45,65,45,78,123,476,3,12,435]

#将nums变成堆
heap =list(nums)
heapq.heapify(heap)

print(heap)

#堆总是返回最小的元素
print(heapq.heappop(heap))
print(heapq.heappop(heap))

# [3, 12, 65, 23, 78, 123, 476, 45, 45, 435]
# 3
# 12

实现优先级队列

创建一个队列,它能够以给定的优先级进行排序,且每次pop操作都会返回优先级最高的那个元素

import heapq
class PriorityQueue:
    def __init__(self):
        self._queue =[];
        self.index =0;
    def push(self,item,priority):
        heapq.heappush(self._queue,(-priority,self.index,item))
        self.index+=1
    def pop(self):
        return heapq.heappop(self._queue)[-1]

if __name__ == '__main__':
    q = PriorityQueue()

    q.push("siqu",1)
    q.push("xh",5)
    q.push("xw",2)
    q.push("yz",2)

    print(q.pop())
    print(q.pop())
    print(q.pop())
    print(q.pop())

# xh
# xw
# yz
# siqu
  • (-priority,self.index,item)的形式放入队列,弹出时,先比较优先级大小,在比较索引大小
  • 弹出优先级最大高的元素,如果优先级相同,则弹出最先进入队列的元素
  • priority加上负数,由于heappop每次都会弹出最小的元素
© 版权声明
THE END
喜欢就支持以下吧
点赞0
分享
评论 抢沙发
四曲的头像-四曲博客

昵称

取消
昵称表情代码图片