用python实现基本数据结构【02/4】

*说明

        如果需要用到这些知识却没有掌握,则会让人感到沮丧,也可能导致面试被拒。无论是花几天时间“突击”,还是利用零碎的时间持续学习,在数据结构上下点功夫都是值得的。那么Python 中有哪些数据结构呢?列表、字典、集合,还有……栈?Python 有栈吗?本系列文章将给出详细拼图。

第5章:Searching 和 Sorting

        排序和查找是最基础和频繁的操作,python内置了in操作符和bisect二分操作模块实现查找,内置了sorted方法来实现排序操作。二分和快排也是面试中经常考到的,本章讲的是基本的排序和查找。

def binary_search(sorted_seq, val):""" 实现标准库中的bisect.bisect_left """low = 0high = len(sorted_seq) - 1while low <= high:mid = (high + low) // 2if sorted_seq[mid] == val:return midelif val < sorted_seq[mid]:high = mid - 1else:low = mid + 1return lowdef bubble_sort(seq):  # O(n^2), n(n-1)/2 = 1/2(n^2 + n)n = len(seq)for i in range(n-1):for j in range(n-1-i):    # 这里之所以 n-1 还需要 减去 i 是因为每一轮冒泡最大的元素都会冒泡到最后,无需再比较if seq[j] > seq[j+1]:seq[j], seq[j+1] = seq[j+1], seq[j]def select_sort(seq):"""可以看作是冒泡的改进,每次找一个最小的元素交换,每一轮只需要交换一次"""n = len(seq)for i in range(n-1):min_idx = i    # assume the ith element is the smallestfor j in range(i+1, n):if seq[j] < seq[min_idx]:   # find the minist element indexmin_idx = jif min_idx != i:    # swapseq[i], seq[min_idx] = seq[min_idx], seq[i]def insertion_sort(seq):""" 每次挑选下一个元素插入已经排序的数组中,初始时已排序数组只有一个元素"""n = len(seq)for i in range(1, n):value = seq[i]    # save the value to be positioned# find the position where value fits in the ordered part of the listpos = iwhile pos > 0 and value < seq[pos-1]:# Shift the items to the right during the searchseq[pos] = seq[pos-1]pos -= 1seq[pos] = valuedef merge_sorted_list(listA, listB):""" 归并两个有序数组 """new_list = list()a = b = 0while a < len(listA) and b < len(listB):if listA[a] < listB[b]:new_list.append(listA[a])a += 1else:new_list.append(listB[b])b += 1while a < len(listA):new_list.append(listA[a])a += 1while b < len(listB):new_list.append(listB[b])b += 1return new_list

第6章: Linked Structure

        list是最常用的数据结构,但是list在中间增减元素的时候效率会很低,这时候linked list会更适合,缺点就是获取元素的平均时间复杂度变成了O(n)

# 单链表实现
class ListNode:def __init__(self, data):self.data = dataself.next = Nonedef travsersal(head, callback):curNode = headwhile curNode is not None:callback(curNode.data)curNode = curNode.nextdef unorderdSearch(head, target):curNode = headwhile curNode is not None and curNode.data != target:curNode = curNode.nextreturn curNode is not None# Given the head pointer, prepend an item to an unsorted linked list.
def prepend(head, item):newNode = ListNode(item)newNode.next = headhead = newNode# Given the head reference, remove a target from a linked list
def remove(head, target):predNode = NonecurNode = headwhile curNode is not None and curNode.data != target:# 寻找目标predNode = curNodecurNode = curNode.dataif curNode is not None:if curNode is head:head = curNode.nextelse:predNode.next = curNode.next

第7章:Stacks

        栈也是计算机里用得比较多的数据结构,栈是一种后进先出的数据结构,可以理解为往一个桶里放盘子,先放进去的会被压在地下,拿盘子的时候,后放的会被先拿出来。

class Stack:""" Stack ADT, using a python listStack()isEmpty()length()pop(): assert not emptypeek(): assert not empty, return top of non-empty stack without removing itpush(item)"""def __init__(self):self._items = list()def isEmpty(self):return len(self) == 0def __len__(self):return len(self._items)def peek(self):assert not self.isEmpty()return self._items[-1]def pop(self):assert not self.isEmpty()return self._items.pop()def push(self, item):self._items.append(item)class Stack:""" Stack ADT, use linked list使用list实现很简单,但是如果涉及大量push操作,list的空间不够时复杂度退化到O(n)而linked list可以保证最坏情况下仍是O(1)"""def __init__(self):self._top = None    # top节点, _StackNode or Noneself._size = 0    # intdef isEmpty(self):return self._top is Nonedef __len__(self):return self._sizedef peek(self):assert not self.isEmpty()return self._top.itemdef pop(self):assert not self.isEmpty()node = self._topself.top = self._top.nextself._size -= 1return node.itemdef _push(self, item):self._top = _StackNode(item, self._top)self._size += 1class _StackNode:def __init__(self, item, link):self.item = itemself.next = link

第8章:Queues

队列也是经常使用的数据结构,比如发送消息等,celery可以使用redis提供的list实现消息队列。 本章我们用list和linked list来实现队列和优先级队列。

class Queue:""" Queue ADT, use list。list实现,简单但是push和pop效率最差是O(n)Queue()isEmpty()length()enqueue(item)dequeue()"""def __init__(self):self._qList = list()def isEmpty(self):return len(self) == 0def __len__(self):return len(self._qList)def enquue(self, item):self._qList.append(item)def dequeue(self):assert not self.isEmpty()return self._qList.pop(0)from array import Array    # Array那一章实现的Array ADT
class Queue:"""circular Array ,通过头尾指针实现。list内置append和pop复杂度会退化,使用环数组实现可以使得入队出队操作时间复杂度为O(1),缺点是数组长度需要固定。"""def __init__(self, maxSize):self._count = 0self._front = 0self._back = maxSize - 1self._qArray = Array(maxSize)def isEmpty(self):return self._count == 0def isFull(self):return self._count == len(self._qArray)def __len__(self):return len(self._count)def enqueue(self, item):assert not self.isFull()maxSize = len(self._qArray)self._back = (self._back + 1) % maxSize     # 移动尾指针self._qArray[self._back] = itemself._count += 1def dequeue(self):assert not self.isFull()item = self._qArray[self._front]maxSize = len(self._qArray)self._front = (self._front + 1) % maxSizeself._count -= 1return itemclass _QueueNode:def __init__(self, item):self.item = itemclass Queue:""" Queue ADT, linked list 实现。为了改进环型数组有最大数量的限制,改用带有头尾节点的linked list实现。"""def __init__(self):self._qhead = Noneself._qtail = Noneself._qsize = 0def isEmpty(self):return self._qhead is Nonedef __len__(self):return self._countdef enqueue(self, item):node = _QueueNode(item)    # 创建新的节点并用尾节点指向他if self.isEmpty():self._qhead = nodeelse:self._qtail.next = nodeself._qtail = nodeself._qcount += 1def dequeue(self):assert not self.isEmpty(), 'Can not dequeue from an empty queue'node = self._qheadif self._qhead is self._qtail:self._qtail = Noneself._qhead = self._qhead.next    # 前移头节点self._count -= 1return node.itemclass UnboundedPriorityQueue:""" PriorityQueue ADT: 给每个item加上优先级p,高优先级先dequeue分为两种:- bounded PriorityQueue: 限制优先级在一个区间[0...p)- unbounded PriorityQueue: 不限制优先级PriorityQueue()BPriorityQueue(numLevels): create a bounded PriorityQueue with priority in range[0, numLevels-1]isEmpty()length()enqueue(item, priority): 如果是bounded PriorityQueue, priority必须在区间内dequeue(): 最高优先级的出队,同优先级的按照FIFO顺序- 两种实现方式:1.入队的时候都是到队尾,出队操作找到最高优先级的出队,出队操作O(n)2.始终维持队列有序,每次入队都找到该插入的位置,出队操作是O(1)(注意如果用list实现list.append和pop操作复杂度会因内存分配退化)"""from collections import namedtuple_PriorityQEntry = namedtuple('_PriorityQEntry', 'item, priority')# 采用方式1,用内置list实现unbounded PriorityQueuedef __init__(self):self._qlist = list()def isEmpty(self):return len(self) == 0def __len__(self):return len(self._qlist)def enqueue(self, item, priority):entry = UnboundedPriorityQueue._PriorityQEntry(item, priority)self._qlist.append(entry)def deque(self):assert not self.isEmpty(), 'can not deque from an empty queue'highest = self._qlist[0].priorityfor i in range(len(self)):    # 出队操作O(n),遍历找到最高优先级if self._qlist[i].priority < highest:highest = self._qlist[i].priorityentry = self._qlist.pop(highest)return entry.itemclass BoundedPriorityQueue:""" BoundedPriorityQueue ADT,用linked list实现。上一个地方提到了 BoundedPriorityQueue但是为什么需要 BoundedPriorityQueue呢? BoundedPriorityQueue 的优先级限制在[0, maxPriority-1]对于 UnboundedPriorityQueue,出队操作由于要遍历寻找优先级最高的item,所以平均是O(n)的操作,但是对于 BoundedPriorityQueue,用队列数组实现可以达到常量时间,用空间换时间。比如要弹出一个元素,直接找到第一个非空队列弹出 元素就可以了。(小数字代表高优先级,先出队)qlist[0] -> ["white"][1][2] -> ["black", "green"][3] -> ["purple", "yellow"]"""# Implementation of the bounded Priority Queue ADT using an array of ## queues in which the queues are implemented using a linked list.from array import Array    #  第二章定义的ADTdef __init__(self, numLevels):self._qSize = 0self._qLevels = Array(numLevels)for i in range(numLevels):self._qLevels[i] = Queue()    # 上一节讲到用linked list实现的Queuedef isEmpty(self):return len(self) == 0def __len__(self):return len(self._qSize)def enqueue(self, item, priority):assert priority >= 0 and priority < len(self._qLevels), 'invalid priority'self._qLevel[priority].enquue(item)    # 直接找到 priority 对应的槽入队def deque(self):assert not self.isEmpty(), 'can not deque from an empty queue'i = 0p = len(self._qLevels)while i < p and not self._qLevels[i].isEmpty():    # 找到第一个非空队列i += 1return self._qLevels[i].dequeue()

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/127143.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【白话机器学习系列】白话梯度下降

白话梯度下降 梯度下降是机器学习中最常见的优化算法之一。理解它的基本实现是理解所有基于它构建的高级优化算法的基础。 文章目录 优化算法一维梯度下降均方误差梯度下降什么是均方误差单权重双权重三权重三个以上权重 矩阵求导结论 优化算法 在机器学习中&#xff0c;优化是…

ChatGPT实战与私有化大模型落地

文章目录 大模型现状baseline底座选择数据构造迁移方法评价思考 领域大模型训练技巧Tokenizer分布式深度学习数据并行管道并行向量并行分布式框架——Megatron-LM分布式深度学习框架——Colossal-AI分布式深度学习框架——DeepSpeedP-tuning 微调 资源消耗模型推理加速模型推理…

Python批处理(一)提取txt中数据存入excel

Python批处理&#xff08;一&#xff09;提取txt中数据存入excel 问题描述 现从冠层分析软件中保存了叶面积指数分析的结果&#xff0c;然而软件保存格式为txt&#xff0c;且在不同的文件夹中&#xff0c;每个文件夹的txt文件数量不固定&#xff0c;但是txt文件格式固定。现需…

C#__多线程之任务和连续任务

/// <summary> /// /// 任务&#xff1a;System.Threading.Tasks&#xff08;异步编程的一种实现方式&#xff09; /// 表应完成某个单元工作。这个工作可以在单独的线程中运行&#xff0c;也可以以同步方式启动一个任务。 /// /// 连续任务&#…

thinkphp6-简简单单地开发接口

目录 1.前言TP6简介 2.项目目录3.运行项目运行命令访问规则 4.model db使用db连接配置model编写及调用调用接口 5.返回json格式 1.前言 基于上篇文章环境搭建后&#xff0c;便开始简单学习上手开发接口…记录重要的过程&#xff01; Windows-试用phpthink发现原来可这样快速搭…

如何使用SQL SERVER的OpenQuery

如何使用SQL SERVER的OpenQuery 一、OpenQuery使用说明二、 OpenQuery语法2.1 参数说明2.2注解 三、示例3.1 执行 SELECT 传递查询3.2 执行 UPDATE 传递查询3.3 执行 INSERT传递查询3.4 执行 DELETE 传递查询 一、OpenQuery使用说明 在指定的链接服务器上执行指定的传递查询。 …

电工什么是电动势

什么是电动势&#xff1f;及电源电动势计算公式与方向确定 前面我们讲到在基本电路中的电流和电压的基础知识&#xff0c;而本文要讲的电动势和电压是一个很类似的概念。那么什么是电动势&#xff1f;电源电动势的计算公式是什么&#xff1f;它的方向如何确定及与电压有什么区…

轻量容器引擎Docker基础使用

轻量容器引擎Docker Docker是什么 Docker 是一个开源项目&#xff0c;诞生于 2013 年初&#xff0c;最初是 dotCloud 公司内部的一个业余项目。 它基于 Google 公司推出的 Go 语言实现&#xff0c;项目后来加入了 Linux 基金会&#xff0c;遵从了 Apache 2.0 协议&#xff0c;…

【Redis】深入探索 Redis 的数据类型 —— 哈希表 hash

文章目录 前言一、hash 类型相关命令1.1 HSET 和 HSETNX1.2 HGET 和 HMGET1.3 HKEYS、HVALS 和 HGETALL1.4 HEXISTS 和 HDEL1.5 HLEN1.6 HINCRBY 和 HINCRBYFLOAT1.7 哈希相关命令总结 二、hash 类型内部编码三、hash 类型的应用场景四、原生&#xff0c;序列化&#xff0c;哈希…

Android相机-架构3

目录 引言 1. Android相机的整体架构 2. 相机 HAL 2.1 AIDL相机HAL 2.2 相机 HAL3 功能 3. HAL子系统 3.1 请求 3.2 HAL和相机子系统 3.2.1 相机的管道 3.2.2 使用 Android Camera API 的步骤 3.2.3 HAL 操作摘要 3.3 启动和预期操作顺序 3.3.1 枚举、打开相机设备…

C语言课程作业

本科期间c语言课程作业代码整理&#xff1a; Josephus链表实现 Josephus 层序遍历树 二叉树的恢复 哈夫曼树 链表的合并 中缀表达式 链接&#xff1a;https://pan.baidu.com/s/1Q7d-LONauNLi7nJS_h0jtw?pwdswit 提取码&#xff1a;swit

《TCP/IP网络编程》阅读笔记--进程间通信

目录 1--进程间通信 2--pipe()函数 3--代码实例 3-1--pipe1.c 3-2--pipe2.c 3-3--pipe3.c 3-4--保存信息的回声服务器端 1--进程间通信 为了实现进程间通信&#xff0c;使得两个不同的进程间可以交换数据&#xff0c;操作系统必须提供两个进程可以同时访问的内存空间&am…

MySQL之MHA高可用配置及故障切换

目录 一、MHA概念 1、MHA的组成 2、MHA的特点 3、主从复制有多少种复制方法 二、搭建MySqlMHA部署 1&#xff0e;Master、Slave1、Slave2 节点上安装 mysql 2&#xff0e;修改 Master、Slave1、Slave2 节点的 Mysql主配置文件/etc/my.cnf 3. 配置 mysql 一主两从 4、安…

关于el-input和el-select宽度不一致问题解决

1. 情景一 单列布局 对于上图这种情况&#xff0c;只需要给el-select加上style"width: 100%"即可&#xff0c;如下&#xff1a; <el-select v-model"fjForm.region" placeholder"请选择阀门类型" style"width: 100%"><el-o…

【轻量化网络】MobileNet系列

MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications, CVPR2017 论文&#xff1a;https://arxiv.org/abs/1704.04861 代码&#xff1a; 解读&#xff1a;【图像分类】2017-MobileNetV1 CVPR_說詤榢的博客-CSDN博客 MobileNetV2: Inverted …

如何使用PySide2将designer设计的ui文件加载到Python类上鼠标拖拽显示路径

应用场景&#xff1a; designer快速设计好UI文件后&#xff0c;需要增加一些特别的界面功能&#xff0c;如文件拖拽显示文件路径功能。 方法如下&#xff1a; from PySide2.QtWidgets import QApplication, QMainWindow from PySide2.QtUiTools import loadUiTypeUi_MainWindo…

Java中wait和notify详解

线程的调度是无序的&#xff0c;随机的&#xff0c;但是也是有一定的需求场景&#xff0c;希望能够有序执行&#xff0c;join算是一种控制顺序的方式&#xff08;功能有限&#xff09;——》一个线程执行完&#xff0c;才能执行另一个线程&#xff01; 本文主要讲解的&#xf…

【工具使用】Dependency Walker使用

一&#xff0c;简介 在工作过程中常常会遇到编译的dll库运行不正常的情况&#xff0c;那就需要确认dll库是否编译正常&#xff0c;即是否将函数编译到dll中去。今天介绍一种查看dll库中函数定义的工具——Dependency walker。 二&#xff0c;软件介绍 Dependency Walker是一…

CSS3技巧36:backdrop-filter 背景滤镜

CSS3 有 filter 滤镜属性&#xff0c;能给内容&#xff0c;尤其是图片&#xff0c;添加各种滤镜效果。 filter 滤镜详见博文&#xff1a;CSS3中强大的filter(滤镜)属性_css3滤镜_stones4zd的博客-CSDN博客 后续&#xff0c;CSS3 又新增了 backdrop-filter 背景滤镜。 backdr…

源码剖析:Elasticsearch 段合并调度及优化手段

1、背景 经常看到集群的merge限流耗时比较高&#xff0c;所以想分析其原因、造成的影响、以及反思merge的一些优化手段。 比如下图中测试集群相关监控截图&#xff1a; 可是从磁盘的写入来看&#xff0c;并不高&#xff1a; 那么目前的情况带来哪些影响&#xff1f; 资源利用率…