算法通过村第十五关-超大规模|黄金笔记|超大规模场景

2023-10-21 09:20

本文主要是介绍算法通过村第十五关-超大规模|黄金笔记|超大规模场景,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
  • 对20GB文件进行排序
  • 超大文本中搜索两个单词的最短距离
  • 从10亿数字中寻找小于100万个数字
  • 总结


前言


提示:你生命的前半辈子或许属于别人,活在别人的认为里。那把后半辈子还给自己,去追随你内在的声音。 --荣格

理解了前面的几个题目知乎,这里我们在看看在海量数据场景下的查询问题。

对20GB文件进行排序

题目要求:假设你有一个20GB的文件,每行一个字符串,请说明如何对这个文件进行排序?

分析:这里给出的大小是20GB,其实面试官在暗示我们不要将所有文件都装入内存里面,因此我们只有将文件划分成块,每块大小是xMB,x就是可用的内存大小,比如如果是1GB的块,那么我们就可以将文件分成20块。我们先对每块进行排序,然后再逐步合并。这时候我们可以使用两两并归,也可以使用堆排序的策略将其逐步合并成一个,相关的可以看以往章节介绍:

这种排序方式也称为外部排序。

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

题目要求:有一个超大文本文件,内部是很多单词组成的,现在给定两个单词,请你找出这两个单词在这个文本中的最小距离。你有办法在O(n)时间里完成搜索吗?方法的空间复杂度如何。

分析:这个题目咋看起来含简单,遍历一下,找到两个单词的位置w1和w2,然后比较一下就可以了,然而这里的w1可能存在多个位置,w2也一样。看下面的图:

在这里插入图片描述

这个时候如何找到最小的距离呢?

最直观的做法就是遍历数组words,对数组中的每个word1,遍历数组words找到每个word2并计算距离。该做法的最坏的时间复杂度为O(n^2),需要优化。

本题目少不了遍历一次数组,找到所有word1和word2出现的位置,但是为了方便比较,我们可以将其放入一个数组中。比如:

ListA:{1,2,3,5,9,34}
ListB:{4,8,12,56}
合并后
List:{1a,2a,3a,4b,5b,12b,34a,56b}

合并成一个之后更方便查找的数组,数字便是出现的位置,后面的一个元素表示元素是什么,然后一遍遍历,一遍比较就可以了。

但是对于超大文本,如果文本太大那么这个list可能会产生溢出,还需要继续观察,我们或发现其实不用单独构造list,从左到右遍历数组words当遍历到word1时,如果已经遍历的单词中存在word2,为了方便记录最短距离,应该取一个已经遍历到的word2所在的下标,计算和当前下边的距离。同理,当遍历到word2时,应该取最后一个已经遍历到的word1所在的下标,计算和当前下标的距离。

经过以上分析,我们可以遍历一次数组就可以得到最短距离,并且将复杂度降低到O(n)。用index1 和index2分别表示数组word已经遍历到单词的最后一个word1和word2下标。初始状态下index1和index2为-1.遍历数组word,当遇到word2时,执行以下操作:

  • 如果遇到word1,则将index1更新为当前下标;如果遇到word2,则将index2更新为当前下标。
  • 如果index1和index2都非负,则计算两个下标的距离|index1 - index 2|,并用该距离更新最短距离。

遍历结束之后就可以获取word1和word2的最短距离。

进阶问题如果再寻找的过程中这个文件会重复多次,而每次寻找的单词不同,则可以维护一个哈希表记录每个短促的下标列表。遍历一次文件,按照下标递增顺序得到每个单词再文件中出现的所有下标。寻找单词时,只需要得到两个单词的下标列表。使用双指针遍历下标链表,就可以得到两个单词的最短距离

从10亿数字中寻找小于100万个数字

题目要求:设计一个算法,给定一个10亿个数字,找出最小的100万的数字。假定计算机内存足够容纳10亿个数字。

分析:本题常见的做法有三种

  • 先对元素排序,然后去取出前100万个数字,该方法的时间复杂度为O(nlogn)。很明显这样做时间和空间的消耗很大
  • 采用选择排序,首先遍历10亿个数找最小,然后再遍历一遍找第二小…直到找到100万个。这种方式的时间复杂度(nm),执行10亿*100万次。实现难度高
  • 采用大顶堆来解决。推荐:算法通过村第十四关-堆|白银笔记|经典问题-CSDN博客 堆排序原理。

首先前提创建100万存储空间大顶堆,最大元素位于堆顶。

然后遍历整个序列,只要比堆顶元素小才可以放入堆中。并删除原堆的最大元素。之后继续遍历剩下的序列。直到最后剩下的之后100万个数字。

采用这一种遍历方式,只需要遍历一次10亿个数字,还可以接受。更新堆的代价是O(nlogn),也是勉强够用的。堆的占用空间是100万*4大约就是4MB的空间。也是不错的选择

如果数量没有这么大,上面的其他方法也不是不可以。

如果将10亿数字换成数据流,也可以采用堆的方式,而且对数据流来说,几乎能采用堆来做的。


总结

提示:超大数据排序;超大数据搜索问题;海量数据集遍历;超大规模数据流;堆的排序原理:


如果有帮助到你,请给题解点个赞和收藏,让更多的人看到 ~ ("▔□▔)/

如有不理解的地方,欢迎你在评论区给我留言,我都会逐一回复 ~

也欢迎你 关注我 ,喜欢交朋友,喜欢一起探讨问题。

在这里插入图片描述

这篇关于算法通过村第十五关-超大规模|黄金笔记|超大规模场景的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/253457

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Java中Runnable和Callable的区别和联系及使用场景

《Java中Runnable和Callable的区别和联系及使用场景》Java多线程有两个重要的接口,Runnable和Callable,分别提供一个run方法和call方法,二者是有较大差异的,本文... 目录一、Runnable使用场景二、Callable的使用场景三、关于Future和FutureTa

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

JavaScript中的reduce方法执行过程、使用场景及进阶用法

《JavaScript中的reduce方法执行过程、使用场景及进阶用法》:本文主要介绍JavaScript中的reduce方法执行过程、使用场景及进阶用法的相关资料,reduce是JavaScri... 目录1. 什么是reduce2. reduce语法2.1 语法2.2 参数说明3. reduce执行过程

JavaScript中的isTrusted属性及其应用场景详解

《JavaScript中的isTrusted属性及其应用场景详解》在现代Web开发中,JavaScript是构建交互式应用的核心语言,随着前端技术的不断发展,开发者需要处理越来越多的复杂场景,例如事件... 目录引言一、问题背景二、isTrusted 属性的来源与作用1. isTrusted 的定义2. 为

Python调用另一个py文件并传递参数常见的方法及其应用场景

《Python调用另一个py文件并传递参数常见的方法及其应用场景》:本文主要介绍在Python中调用另一个py文件并传递参数的几种常见方法,包括使用import语句、exec函数、subproce... 目录前言1. 使用import语句1.1 基本用法1.2 导入特定函数1.3 处理文件路径2. 使用ex