您现在的位置是:首页 > 正文

海量数据处理思想 + 一些例题

2024-04-01 00:59:12阅读 2

海量数据,顾名思义就是数据量太大,内存里装不下,基本思路就是分治,借助一些合适的数据结构;下来看一下具体的例子

一、bit-map:使用bit数组来表示元素是否存在,这样只需要存储比特位即可;

1、如果有40亿个QQ,如何存储
首先我们需要清楚,如果有40亿个QQ号,假设每个QQ号用一个int类型存储,则大约需要16G的空间,所以如果不做任何处理直接存储,缺点是空间消耗比较大,并且也有可能导致内存不够的问题。在这里,我们存储的目的主要是用于查询,所以我们可以使用位图存储某一个QQ存在与否的二值信息。对于每一个二值信息,我们可以用一个bit位保存,这样,40亿个QQ号的存储空间我们可以减少32倍,即只需要消耗大概500M的空间。
2、给定100亿个整数,设计算法找到只出现一次的整数
采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。还有一种办法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。

二、堆:这种适合topk问题,

特别适合topN问题,内存中一下子无法加载所有的数据集,此时可以先读取海量数据中前面的K个数,建立数据集为K的小根堆,然后依次往堆结构中读取数字,调整堆,使其保持小顶堆,最后得到topk的最大数。
3、上千万或上亿数据(有重复),统计其中出现次数最多的钱N个数据。
  上千万或上亿的数据,现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了,可以用第2题提到的堆机制完成。

三、hash映射进行分治,然后归并

hash映射通过key-value模型,就会把海量数据变少,然后分段处理,接着再进行归并,
4、给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?
遍历文件a,对每个url求取hash(url)%1000,根据所取得的值将url分别存储到1000个小文件中。这样每个小文件的大约为300M。接着再遍历文件b,采取和a相同的方式将url分别存储到1000小文件,这样处理后,所有可能相同的url都在对应的小文件(a0vsb0,a1vsb1,…,a999vsb999)中,不对应的小文件不可能有相同的url。所以逐个比较各个小文件中的url,然后归并就可以了;
 
5、有一个log文件,提取出访问百度次数最多的那个IP,
再详细介绍下此方案:首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法,比如模1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map进行频率统计,然后再找出频率最大的几个)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。==
6、怎么在海量数据中找出重复次数最多的一个?
先做hash,然后求模映射为小文件,求出每个小文件中重复次数最多的一个,并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求。

四、hash统计:以特征为key统计

五、trie树:适合字符串类的查找:如把500万个单词中大量的重复单词去掉,

六、布隆过滤器

可以用于判重,此方法存在一定的误差,但是比较高效。方法是利用多种不同的hash方法对数据集做hash运算,将对应的结果为key,值为1,然后判断一个新数在不在这个数据集中,则用相同的n中hash方法进行计算,如果全为1则认为在,任何一个不为1,则认为不在。

网站文章

  • kafka可视化工具kafka tool

    kafka可视化工具kafka tool

    kafka tool官网下载地址http://www.kafkatool.com/download.html连接zookeeper服务地址其中message信息乱码,解决方案如下:1、点击tools—settings—选择topics中将key message设置为string2、选择指定的topic中properties将key message设置为string ...

    2024-04-01 00:59:05
  • Java中httpClient中三种超时设置

    本文章给大家介绍一下关于Java中httpClient中的三种超时设置小结 在Apache的HttpClient包中,有三个设置超时的地方:/* 从连接池中取连接的超时时间*/ ConnManagerParams.setTimeout(params, 1000); /*连接超时*/ HttpConnectionParams.setConnectionTimeout(params, 2000)

    2024-04-01 00:58:41
  • 从微服务开始 vs 不从微服务开始

    从微服务开始 vs 不从微服务开始

    本文的题目看似自相矛盾,实则不然。 我想讲两个故事。一个是不从微服务开始,一个是从微服务开始。我认为,通过观察事物的两面,我们将对微服务的实际好处有更多的了解。 闲话少叙,言归正题。 不从微服务开始 ...

    2024-04-01 00:58:33
  • python引用另一个py的函数

    引用test.py的函数testafrom test import testatesta() 或者import testtest.testa()

    2024-04-01 00:58:26
  • VSCode 联合调试Python/C++

    VSCode 联合调试Python/C++

    本文选择Vscode实现Python/C++代码的联合调试,一是它跨平台,二是通过插件支持多语言代码编辑以及调试。在尝试ptvsd调试器失败后换用gdb调试器做讲解。

    2024-04-01 00:58:03
  • 《机器学习高频面试题详解》4.4:模型融合:Bagging

    机械工程师岗,18K x (14-16)薪,七成是基本工资,三成绩效,公积金12%,每月交通补助600元,每日餐补大约20元,试用期半年,试用期内工资80%,宿。三方违约金是一个月工资,但是我现在没有...

    2024-04-01 00:57:57
  • 计算机毕业设计/课程设计开题报告系列-基于JavaWeb的学生选课系统开题报告

    计算机毕业设计/课程设计开题报告系列-基于JavaWeb的学生选课系统开题报告

    本项目是一款基于JavaWeb的学生选课系统,主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的 Java 学习者。

    2024-04-01 00:57:51
  • 为什么要用反射创建对象_为什么几乎所有的Java框架都要用到反射机制,她的魅力在哪里?...

    为什么要用反射创建对象_为什么几乎所有的Java框架都要用到反射机制,她的魅力在哪里?...

    说起Java的反射机制,大家应该不陌生吧,她是Java语言多态的一种体现。但是在面试过程中,我发现很多人都只是停留在听说过的层面,并没有知其所以然,今天我们就来探讨下。大部分人最早接触的反射代码,是J...

    2024-04-01 00:57:43
  • RESTful 规范

    1. 基本概念     REST全称是Representational State Transfer,中文意思是表征性状态转移。指的是一组架构约束条件和原则。如果一个架构符合REST的约束条件和原则,...

    2024-04-01 00:57:17
  • Python中运算符优先级的顺序

    Python中运算符优先级的顺序

    目录(一)引言(二)运算符分类(三)关于三种运算符的优先级列表 在任何语言中运算符都有优先级一说,那在Python中我们常见的运算符优先级又是如何呢,本文我将展开聊聊这个话题 此处我将列出常见运算符,大致分为算数符(比如加减乘除),关系符(比如大于小于等于)以及逻辑符(与非或)......

    2024-04-01 00:57:08