算法通关村第十五关—继续研究超大规模数据场景的问题(黄金)

  继续研究超大规模数据场景的问题

一、对20GB文件进行排序

 题目要求:假设你有一个20GB的文件,每行一个字符串,请说明如何对这个文件进行排序?
 分析:这里给出大小是20GB,其实面试官就在暗示你不要将所有的文件都装入到内存里,因此我们只能将文件划分成一些块,每块大小是xMB,x就是可用内存的大小,例如1GB一块,那我们就可以将文件分为20块。我们先对每块进行排序,然后再逐步合并。这时候我们可以使用两两归并,也可以使用堆排序策略将其逐步合并成一个。相关方法我们在《查找》一章的堆排部分有介绍。这种排序方式也称为外部排序。

二、超大文本中搜索两个单词的最短距离

 题目要求:有个超大文本文件,内部是很多单词组成的,现在给定两个单词,请你找出这两个单词在这个文件中的最小距离,也就是像个几个单词。你有办法在O()时间里完成搜索操作吗?方法的空间复杂度如何。
 分析:这个题咋看很简单,遍历一下,找到这两个单词w1和w2的位置然后比较一下就可以了,然而这里的w1可能在很多位置出现,而w2也会在很多位置出现,如下图:
image.png
 这时候如何比较寻找哪两个是最小距离呢?
 最直观的做法是遍历数组words,对于数组中的每个word1,遍历数组words找到每个word2并计算距离。该做法在最坏情况下的时间复杂度是O(n^2),需要优化。
 本题我们少不了遍历一次数组,找到所有word1和word2出现的位置,但是为了方便比较,我们可以将其放到一个数组里,例如:

l1stA:{1,2,9,15,25}
listB:{4,10,19}
合并成
list:{1a,2a,4b,9a,10b,15a,19b,25a}

 合并成一个之后更方便查找,数字表示出现的位置,后面一个元素表示元素是什么。然后一边遍历一边比较就可以了。
 但是对于超大文本,如果文本太大那这个ist可能溢出。如果继续观察,我们会发现其实不用单独构造ist,从左到右遍历数组words,当遍历到word1时,如果已经遍历的单词中存在word2,为了计算最短距离,应该取最后一个已经遍历到的word2所在的下标,计算和当前下标的距离。同理,当遍历到word2时,应该取最后一个已经遍历到的word1所在的下标,计算和当前下标的距离。
 基于上述分析,可以遍历数组一次得到最短距离,将时间复杂度降低到O(n)。用index1和index2分别表示数组words已经遍历的单词中的最后一个word1的下标和最后一个word2的下标,初始时index1=index2=-1。遍历数组words,当遇到word2时,执行如下操作:
1.如果遇到word1,则将index1更新为当前下标;如果遇到word2,则将index2更新为当前下标。
2.如果index1和index22都非负,则计算两个下标的距离|index1-index2|,并用该距离更新最短距离。
遍历结束之后即可得到word1和word2的最短距离。
 进阶问题如果寻找过程在这个文件中会重复多次,而每次寻找的单词不同,则可以维护一个哈希表记录每个单词的下标列表。遍历一次文件,按照下标递增顺序得到每个单词在文件中出现的所有下标。在寻找单词时,只要得到两个单词的下标列表,使用双指针遍历两个下标链表,即可得到两个单词的最短距离。

三、从10亿数字中寻找最小的100万个数字

 题目要求:设计一个算法,给定一个10亿个数字,找出最小的100万的数字。假定计算机内存足以容纳全部10亿个数字。
 本题有三种常用的方法,一种是先排序所有元素,然后取出前100万个数,该方法的时间复杂度为O(nlogn)。很明显对于10亿级别的数据,这么做时间和空间代价太高。
 第二种方式是采用选择排序的方式,首先遍历10亿个数字找最小,然后再遍历一次找第二小,然后再一次找第三小,直到找到第100万个。很明显这种方式的时间代价是O(m)也就是要执行10亿100万次,这个效率一般的服务器都达不到。
 第三种方式,采用大顶堆来解决,堆的原理在《查找》一章专门介绍过,方法思想是一致的,都是“查小用大堆,查大用小堆”。
 首先,为前100万个数字创建一个大顶堆,最大元素位于堆顶。然后,遍历整个序列,只有比堆顶元素小的才允许插入堆中,并删除原堆的最大元素。之后继续遍历剩下的数字,最后剩下的就是最小的100万个。
 采用这种方式,只需要遍历一次10亿个数字,还可以接受。更新堆的代价是O(nlogn),也勉强能够接受。堆占用的空间是100万
4,大约为4MB左右的空间就够了,2因此也能接收。如果数据量没有这么大,也是可以直接使用这三种方式的。如果将10亿数字换成流数据,也可以使用堆来找,而且对于流数据,几乎只能用堆来做。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【ROS2】使用C++实现简单的发布订阅方

1 构建自定义数据类型 1、自定义消息类型Student 1.1 创建base_interfaces_demo包 1.2 创建Student.msg文件 string name int32 age float64 height 1.2 在cmakeLists.txt中增加如下语句 #增加自定义消息类型的依赖 find_package(rosidl_default_generators REQUIRED) # 为…

Pytorch基础知识点复习

文章目录 并行计算单卡训练多卡训练单机多卡DP多机多卡DDPDP 与 DDP 的优缺点 PyTorch的主要组成模块Pytorch的主要组成模块包括那些呢?Dataset和DataLoader的作用是什么,我们如何构建自己的Dataset和DataLoader?神经网络的一般构造方法&…

机器学习~从入门到精通(三)梯度下降法

一、梯度下降法 # 梯度下降不是一种算法,是一种最优化方法 # 上节课讲解的梯度下降的案例 是一个简单的一元二次方程 # 最简单的线性回归:只有一个特征的线性回归,有两个theta # 二、在多元线性回归中使用梯度下降求解 三、### R…

泊松流生成模型简介

一、说明 泊松流生成模型 (PFGM) 是一种新型的生成深度学习模型,与扩散模型类似,其灵感来自物理学。在这本简单易懂的指南中了解 PFGM 背后的理论以及如何使用它们生成图像。 生成式人工智能模型在过去几年中取得了长足的进步。受物理启发的扩散…

使用pygame实现简单的烟花效果

import pygame import sys import random import math# 初始化 Pygame pygame.init()# 设置窗口大小 width, height 800, 600 screen pygame.display.set_mode((width, height)) pygame.display.set_caption("Fireworks Explosion")# 定义颜色 black (0, 0, 0) wh…

BLDC 电机和 PMSM 的结构区别

BLDC 电机和 PMSM 的结构类似,其永磁体均置于转子,并被定义为同步电机。在同步电机中,转子与定子磁场同步,即转子的旋转速度与定子磁场相同。它们的主要区别在于其反电动势(反 EMF)的形状。电机在旋转时充当…

MySQL进阶篇(五) 锁

一、概述 锁是计算机协调多个进程或线程并发访问某一资源的机制。在数据库中,除传统的计算资源(CPU、RAM、I/O)的争用以外,数据也是一种供许多用户共享的资源。如何保证数据并发访问的一致性、有效性是所有数据库必须解决的一个问…

基于JavaWeb的酒店管理系统

基于JavaWeb的酒店管理系统 文章目录 基于JavaWeb的酒店管理系统系统介绍技术选型成果展示源码获取账号地址及其他说明 系统介绍 基于JavaWeb的酒店管理系统是为酒店打造的管理平台,其主要功能有管理员登陆、客房预订、客房入住、房间管理、数据查询(预订单查询、入…

ros2 基础学习 15- URDF:机器人建模方法

URDF:机器人建模方法 ROS是机器人操作系统,当然要给机器人使用啦,不过在使用之前,还得让ROS认识下我们使用的机器人,如何把一个机器人介绍给ROS呢? 为此,ROS专门提供了一种机器人建模方法——…

数据结构.线性表(2)

一、模板 例子: a: b: 二、基本操作的实现 (1)初始化 (2)销毁和清空 (3)求长度和判断是否为空 (4)取值 (5)查找 (6)插入 &…

【rust/bevy】从game template开始

目录 说在前面步骤进入3D控制方块问题 说在前面 操作系统:win11rust版本:rustc 1.77.0-nightlybevy版本:0.12 步骤 rust安装 这里 windows下建议使用msvc版本bevy安装 这里clone代码git clone https://github.com/NiklasEi/bevy_game_templa…

Jetpack Flow 、Room 初学者学习记录

学习使用响应式Flow操作数据,记录自己学习的过程。 ContactViewModel 是一个 ViewModel,它依赖于一个Room操作接口 ContactDao ,访问对象来获取联系人数据。它使用了 StateFlow 来处理状态的变化和数据的更新。ViewModels 通常用于管理应用的…

emc防护原理

emc原理 emc设计的根本是对于干扰电流的阻塞和疏导。通过阻抗变化来实现对于特定频率的电流的防护。 emc设计 在485等信号线emc实验中,一般使用8us/20us的脉冲波形进行浪涌信号线实验即可。在特殊场景(军品)会使用到更高等级的浪涌实验&am…

在illustrator中按大小尺寸选择物体 <脚本 018>

在Illustrator中我们可以依据对象的属性 如:填充颜色、描边颜色或描边宽度来选择相同属性的对象,但是Illustrator中没有根据不同大小尺寸来选择对象的功能,下面介绍的就是根据大小尺寸选择对象的脚本。 1、下面是当前画板中的所有对象&#…

Linux远程登陆协议ssh

目录 一、SSH服务 1. ssh基础 2. 原理 3. 服务端配置 3.1 常用配置项 3.2 具体操作 3.2.1 修改默认端口号 3.2.2 禁止root用户登录 3.2.3 白名单列表 3.2.4 黑名单列表 3.2.5 使用秘钥对及免交互验证登录 3.2.6 免交互式登录 一、SSH服务 1. ssh基础 SSH&…

【嘿,“怪”回来了】半年未见,好久不见。新年伊始,共赴新约。

您的阅读概要: 故事的开头总是极尽温柔,故事会一直温柔……半年未见,好久不见新年伊始,共赴新约忙碌的敲代码也不要忘了浪漫呀 故事的开头总是极尽温柔,故事会一直温柔…… ✨【自我介绍】:你好&#xff0c…

【数据库】间隙锁Gap Lock

什么是间隙锁 间隙锁(Gap Lock):间隙锁是(RR级别下)一个在索引记录之间的间隙上的锁,可以是两个索引记录之间,也可能是第一个索引记录之前或最后一个索引之后的空间。间隙锁(Gap Lo…

【数据结构与算法】之数组系列-20240115

这里写目录标题 一、599. 两个列表的最小索引总和二、724. 寻找数组的中心下标三、面试题 16.11. 跳水板四、35. 搜索插入位置 一、599. 两个列表的最小索引总和 简单 假设 Andy 和 Doris 想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表&#xff0c…

vue项目之.env文件.env.dev、test、pro

.env文件是vue运行项目时的环境配置文件。 .env: 全局默认配置文件,所有环境(开发、测试、生产等)均会加载并合并该文件 .env.development(开发环境默认命名) 开发环境的配置,文件名默认为.env.development,如果需要改名也是可以的&#xf…

记录误删除docker中极狐gitlab容器恢复过程

如题一次误操作导致删除了docker中极狐gitlab容器恢复过程 情况说明 创建容器时,我是用的是极狐官网推荐安装的步骤,具体按照官网步骤走就行 sudo docker run --detach \--hostname gitlab.example.com \--publish 443:443 --publish 80:80 --publish …