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

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

相关文章

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

SpringBoot应用中出现的Full GC问题的场景与解决

《SpringBoot应用中出现的FullGC问题的场景与解决》这篇文章主要为大家详细介绍了SpringBoot应用中出现的FullGC问题的场景与解决方法,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录Full GC的原理与触发条件原理触发条件对Spring Boot应用的影响示例代码优化建议结论F

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

SpringBoot条件注解核心作用与使用场景详解

《SpringBoot条件注解核心作用与使用场景详解》SpringBoot的条件注解为开发者提供了强大的动态配置能力,理解其原理和适用场景是构建灵活、可扩展应用的关键,本文将系统梳理所有常用的条件注... 目录引言一、条件注解的核心机制二、SpringBoot内置条件注解详解1、@ConditionalOn

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle

利用Python快速搭建Markdown笔记发布系统

《利用Python快速搭建Markdown笔记发布系统》这篇文章主要为大家详细介绍了使用Python生态的成熟工具,在30分钟内搭建一个支持Markdown渲染、分类标签、全文搜索的私有化知识发布系统... 目录引言:为什么要自建知识博客一、技术选型:极简主义开发栈二、系统架构设计三、核心代码实现(分步解析

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

kotlin中const 和val的区别及使用场景分析

《kotlin中const和val的区别及使用场景分析》在Kotlin中,const和val都是用来声明常量的,但它们的使用场景和功能有所不同,下面给大家介绍kotlin中const和val的区别,... 目录kotlin中const 和val的区别1. val:2. const:二 代码示例1 Java

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

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