前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >专栏 >Python中的collections

Python中的collections

作者头像
宅蓝三木
发布于 2024-10-09 13:18:19
发布于 2024-10-09 13:18:19
10100
代码可运行
举报
文章被收录于专栏:三木的博客三木的博客
运行总次数:0
代码可运行

Python 中,collections是一个非常有用的内置模块,它提供了一些高性能的数据类型,可以帮助你更高效地处理数据。

namedtuple

命名元组是一种可以为元组中的每个元素指定名称的数据类型。这使得代码更加可读,并且可以像访问对象属性一样访问元组的元素。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])
p = Point(1, 2)
print(p.x, p.y)

deque

双端队列是一种可以在两端进行高效插入和删除操作的数据结构。它比列表更适合用于实现队列和栈。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
from collections import deque

dq = deque([1, 2, 3])
dq.append(4)
dq.appendleft(0)
print(dq)

Counter

计数器是一种用于统计可哈希对象出现次数的数据类型。它可以方便地统计列表、字符串等数据中的元素出现次数。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
from collections import Counter

c = Counter('abracadabra')
print(c)

OrderedDict

有序字典是一种可以记住插入顺序的字典类型。在 Python 3.7 及以后的版本中,普通字典也已经可以记住插入顺序,但在之前的版本中,OrderedDict非常有用。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
from collections import OrderedDict

od = OrderedDict()
od['a'] = 1
od['b'] = 2
od['c'] = 3
print(od)

用OrderedDict实现LRU缓存算法

描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类:

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。
  • 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例:

输入

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

输出

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4

不用OrderedDict实现
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class ListNode:
    def __init__(self):
        self.value = None
        self.key = None
        self.next = None
        self.prev = None

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.nodeMap = {}

    def _putToHead(self, node):
        if node.prev is self.head:
            return
        node.next.prev = node.prev
        node.prev.next = node.next
        self.head.next.prev = node
        node.next = self.head.next
        node.prev = self.head
        self.head.next = node

    def get(self, key: int) -> int:
        if key in self.nodeMap:
            n = self.nodeMap[key]
            self._putToHead(n)
            return n.value
        return -1


    def put(self, key: int, value: int) -> None:
        if key in self.nodeMap:
            n = self.nodeMap[key]
            n.value = value
            self._putToHead(n)
            return
        n = ListNode()
        n.value = value
        n.key = key
        self.head.next.prev = n
        n.next = self.head.next
        n.prev = self.head
        self.head.next = n
        self.nodeMap[key] = n
        if len(self.nodeMap.keys()) > self.capacity:
            tailNode = self.tail.prev
            self.tail.prev = tailNode.prev
            tailNode.prev.next = tailNode.next
            if tailNode.key in self.nodeMap:
                del self.nodeMap[tailNode.key]
使用OrderedDict实现
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
import collections

class LRUCache(collections.OrderedDict):

    def __init__(self, capacity: int):
        super().__init__()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key in self:
            self.move_to_end(key)
            return self[key]
        return -1


    def put(self, key: int, value: int) -> None:
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last=False)
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-09-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
经典算法之链表篇(三)
ma布
2024/10/21
910
经典算法之链表篇(三)
lru_cache分析
在计算机软件领域,缓存(Cache)指的是将部分数据存储在内存中,以便下次能够更快地访问这些数据,这也是一个典型的用空间换时间的例子。一般用于缓存的内存空间是固定的,当有更多的数据需要缓存的时候,需要将已缓存的部分数据清除后再将新的缓存数据放进去。需要清除哪些数据,就涉及到了缓存置换的策略,LRU(Least Recently Used,最近最少使用)是很常见的一个,也是 Python 中提供的缓存置换策略。
Yerik
2021/08/22
6210
☆打卡算法☆LeetCode 146. LRU 缓存 算法解析
请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类:
恬静的小魔龙
2022/08/07
2910
☆打卡算法☆LeetCode 146. LRU 缓存 算法解析
Python 算法基础篇:链表和双向链表的实现与应用
链表和双向链表是常用的线性数据结构,它们在算法和程序设计中有着广泛的应用。本篇博客将重点介绍链表和双向链表的原理、实现以及它们在不同场景下的应用。我们将使用 Python 来演示链表和双向链表的实现,并通过实例展示每一行代码的运行过程。
小蓝枣
2023/07/25
7730
【python刷题】LRU
LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最少使用的页面予以淘汰。 我们需要记住以下几点就行了:这里以队列为例
西西嘛呦
2021/02/02
5060
146. LRU 缓存机制
要在O(1)时间复杂度完成这两种操作,我们想到的使用HashMap来进行操作,而且参考LRUCache的特性,需要对元素进行移动或者删除,首选的是双向链表。
用户7447819
2021/07/23
2880
LRU算法原理解析
LRU是Least Recently Used的缩写,即最近最少使用,常用于页面置换算法,是为虚拟页式存储管理服务的。
py3study
2020/01/15
1.4K0
Leetcode No.146 LRU 缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类:
week
2021/11/29
3120
数据结构界的“六脉神剑”:数组、链表、哈希表、栈、队列、树的终极解析与实战演练
在编程的世界里,数据结构是构建高效算法的基石。它们就像是武侠小说中的武功秘籍,掌握了它们,就能在代码的江湖中游刃有余。今天,我们就来深入探讨数据结构界的“六脉神剑”——数组、链表、哈希表、栈、队列和树。这六种数据结构,每一种都有其独特的运行原理和应用场景,它们是编程高手的必备技能。
疯狂的KK
2024/05/06
2540
数据结构界的“六脉神剑”:数组、链表、哈希表、栈、队列、树的终极解析与实战演练
实现 LRU 缓存算法
LRU 算法全称是最近最少使用算法(Least Recently Use),是一种简单的缓存策略。顾名思义,LRU 算法会选出最近最少使用的数据进行淘汰。
Se7en258
2022/06/24
9810
实现 LRU 缓存算法
淘汰算法-LRU
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
用户9778128
2022/05/26
6310
LRU算法简介
LRU(Least Recently Used)算法是一种缓存淘汰算法,常用于缓存系统中,通过保留最近使用的数据而淘汰最久未使用的数据,以提高缓存的命中率。LRU算法的核心思想是基于时间局部性原理:最近访问的数据在未来会被再次访问。
孟斯特
2024/01/28
6280
LRU算法简介
js实现 LRU 算法
方式一:map实现 class LRU { constructor(size) { this.size = size; this.cache = new Map(); } get(key) { if (this.cache.has(key)) { const value = this.cache.get(key); this.cache.delete(key); t
蓓蕾心晴
2022/09/24
1.3K0
Python后端技术栈(二)
Darkness cannot drive out darkness; only light can do that. Hate cannot drive out hate; only love can do that.
小闫同学啊
2019/07/18
1.7K0
Python后端技术栈(二)
Design - 460. LFU Cache
Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.
ppxai
2020/09/23
4170
【LeetCode】146. LRU 缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类:
韩旭051
2021/01/07
4480
146. LRU 缓存机制
什么是LRU? 很多时候尤其以前内存比较值钱的时候,我们空间比较宝贵,不会很大,那么就存在了重点数据和非重点数据,我们要在内存不够的时候有限保存重点数据淘汰非重点数据;LRU也就是说我们认为最近使用过的数据应该是重点数据,很久都没用过的数据应该是非重点数据,内存满了就优先删那些很久没用过的数据。 有哪些应用场景呢? 1.手机上划显示的任务列表,都是按照最近打开顺序排列的 2.redis的lru淘汰策略 思路: 1.利用linkedhashmap实现lru,因为其本身就存在lru策略,只需要
名字是乱打的
2021/12/23
2310
146. LRU 缓存机制
十道腾讯算法真题解析!
大家好,我是捡田螺的小男孩。收集了腾讯常考的十道算法题(真题)。在金三银四,希望对大家有帮助呀。
捡田螺的小男孩
2022/04/06
8780
十道腾讯算法真题解析!
Leetcode模块训练2
1. 两数之和(1)# 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1: 输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。 示例 2: 输入:nums = [3,2
素履coder
2022/11/16
3240
实现LRU算法
计算机的缓存容量有限,如果缓存满了就要删除一些内容给新的内容腾出位置,而删除哪些内容,就有不同的策略,LRU算法是其中一种策略。
Defu Li
2020/09/08
8560
相关推荐
经典算法之链表篇(三)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文