大厂前端面试：：如何让6000万数据包和300万数据包在仅50M内存环境中求交集

由于最近疫情的影响，相信最近很多小伙伴都忙于线上办公或者面试:sob:，笔者这里分享一道发生在大厂前端线上编程面试中的一道题目，

如何让 6000 万数据包和 300 万数据包在仅 50M 内存环境中求交集，请简单说出您解决这问题的思路

我们假设现在有两份庞大的数据，而这两份数据包的数据结构均如下，仔细观察里面的数据我们不难发现，里面有 QQ 号，地址和年龄，如题目的要求我们需要是求交集，所以我们暂时可以忽略地址和年龄，以 QQ 号作为唯一标识：

<pre class="prettyprint hljs less" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; word-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;">QQ:40645253 地址：xxx 年龄：xxx
QQ:49844525 地址：xxx 年龄：xxx
QQ:51053984 地址：xxx 年龄：xxx
QQ:15692967 地址：xxx 年龄：xxx
QQ:39211026 地址：xxx 年龄：xxx
// 以下省略 6000 万条数据
...</pre>

梳理了上面的数据包结构之后，我们就得看看 50M 内存是什么情况了，由于面试在线上进行，只能短时间在本地测试下上面这个数据量在本地会占有有多大空间，那由于限于是场前端面试，所以笔者选用了 NodeJS 去制造这些庞大的数据了，当时线上编写的时候是没注释的，这里为了方便小伙伴理解，在写这篇文章的时候我自觉加上了:grin:

<pre class="prettyprint hljs javascript" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; word-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;">const fs = require("fs");
const path = require('path');
const writer = fs.createWriteStream(path.resolve(__dirname, 'data-60M.txt'), { highWaterMark: 1 });

const writeSixtyMillionTimes = (writer) => {
const write = () => {
let data = Buffer.from(${parseInt(Math.random() * 60000000)}\n)
let ok = true;
do {
i--;
if (i === 0) {
// 最后一次写入。
writer.write(data);
} else {
// 检查是否可以继续写入。
// 不要传入回调，因为写入还没有结束。
ok = writer.write(data);
}
} while (i > 0 && ok);
if (i > 0) {
// 被提前中止。
// 当触发 'drain' 事件时继续写入。
writer.once('drain', write);
}
}
// 初始化6000万数据
let i = 600000;
write();
}

writeSixtyMillionTimes(writer)</pre>

首先在本地新建一份 data-60M.txt 文件，然后新建一份 data-60M.js 把上面代码写入并执行，这里我最主要是使用了一个递归，由于当时为了快速写入文件测试大小，当时模拟的 QQ 号，是使用 ${parseInt(Math.random() * 60000000)}\n 随机数生成的，在实际测试表现中会有极小几率重复 QQ 号，但影响不大，实际影响最大的是当你在生成 6000 万数据的时候，电脑疯狂运作，运气不好的时候直接卡死，然后远程面试直接断线。

这里笔者还是建议小伙伴在远程面试中手机随时待命，当电脑 GG 的时候还能联系面试官抢救一下，经过与电脑性能的多轮斗争，和面试官尴尬重连的情况下，终于发现实际文件大小规律如下，这里为了方便小伙伴调试源代码，我也把代码传到 Github 上，链接放在最后，只放了 6000 条数据，实际 300MB 实在是传不上去了，小伙伴们可以下载源代码自行测试，祈祷电脑能熬过去o(╥﹏╥)o：

数据量 内存占用
6000条数据(Git版本) >=30KB
6000万条数据(实际版本) >=300MB
300条数据(Git版本 >=15KB
300万条数据(实际版本) >=15MB
image

到了这个地方，笔者渐渐地看出这个问题的坑点可能在那里了，6000 万条数据在测试文件中大小大概在 300MB 左右，而 300 万条数据大小大概在 15 MB，在 50MB 的内存限制下，我们可以把 300 万条约 15MB 的数据完全放入内存中，剩余大概 35MB 空间是不允许我们完全放入 6000 万条约 300MB 的数据，所以我们需要把数据切割成10块左右，大概每块控制在 30MB ，然后分别读取出来跟内存中的 300 万条数据进行比对并求出交集，50MB 情况也太极端苛刻了，难道是手机并且还是老人机吗，我也不敢问啊o(╥﹏╥)o

在思考上面这一连串的逻辑时候，为了不耽误面试官宝贵的时间，边想边随手建立好下面几份文件和文件夹，好梳理代码，给自己思考时间和回旋的余地，以下是我当时临时的目录结构。

  • database

    • data-3M.txt - 模拟的3百万数据包
    • data-60M.txt - 模拟的6千万数据包

  • library

    • data-3M.js - 处理3百万数据包的逻辑
    • data-60M.js - 处理6千万数据包的逻辑
    • intersect.js - 处理数据包的交集
    • create-60M.js - 生成大数据的文件

  • result.txt 最终数据包的交集结果

  • index.js 主逻辑文件

在不急不慢的分类好目录结构之后，总得再弄点代码给面试官瞧瞧吧o(╥﹏╥)o，不能让人家空等啊

image

当然既然是面试用 NodeJS 第三方模块解决也不够好，当时是先屡一下用什么原生模块实现比较好，要满足上面这些要求，想到这里能使用到的原生 Node 内置模块关键有如下两个：

  • fs - 文件系统
  • readline - 逐行读取

fs.createReadStream(path[, options]) 方法中，其中 options 可以包括 start 和 end 值，以从文件中读取一定范围的字节而不是整个文件。 start 和 end 都包含在内并从 0 开始计数，这种是方法方便我们分段读取 6000 万条数据。当时快速写了一个示例去验证，从一个大小为 100 个字节的文件中读取最后 10 个字节：

<pre class="hljs less" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 0.75em; font-size: 14px; line-height: 1.5em; word-break: break-all; word-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;">fs.createReadStream('data-60M.txt', { start: 90, end: 99 });</pre>

经过短暂的测试，发现这个方案可行，心理淡定了一点。

image

起码这个备用方案起码可以给自己留点操作空间，但当时讨论到的是下面这种方案：

fs.createReadStream() 提供 highWaterMark 选项，它允许我们将以大小等于 highWaterMark选项的块读取流， highWaterMark 的默认值为: 64 * 1024(即64KB)，我们可以根据需要进行调整，当内部的可读缓冲的总大小达到 highWaterMark 设置的阈值时，流会暂时停止从底层资源读取数据，直到当前缓冲的数据被消费，我们就可以触发 readline.pause() 暂停流，处理完之后继续触发 readline.resume() 恢复流，然后不断重复以上步骤，将 6000 万数据分别处理完。

readline 模块提供了一个接口，用于一次一行地读取可读流中的数据。 它可以使用以下方式访问，并且我们的数据包，每条数据之间是使用 \n、\r 或 \r\n 隔开，所以这样方便我们使用 readline.on('line', (input) => {}) 来接受每一行数据包的字符串。

这里自我感觉有些丢分项，是当时忘记了 fs.createReadStream 里面一些配置项，在现场临时翻阅 NodeJS 的官方 API 文档，这里非常感谢当时面试官的理解( ▽ )

image

下面，我们就要写最关键的代码了，就是如何处理那 6000 万条数据，打开刚才新建好的 data-60M.js 文件，该文件就是用于专门处理 6000 万数据的，我们使用 readline 和 createReadStream 两者配合，将数据按一定条数分别缓存在内存中，这里代码正如上面提到，由于提交的代码不适合太大(Git传上去太慢)，所以把数据量减少到 6000 条，那么分成 10 份的话，每份缓存就需要读 600 条左右，读完每份数据之后调用 intersect 函数求交集，并存入硬盘 result.txt 文件中，然后释放内存：

<pre class="prettyprint hljs javascript" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; word-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;">// 写入结果
const writeResult = (element) => {
appendFile('./result.txt', ${element}\n, (err) => {
err ? () => console.log('写入成功') : () => console.log('写入失败');
})
}</pre>

这里最关键是要定义一个空的容器 lineCount 来存放每段数据，并且使用 if (lineCount === 6000) {} 语句判断内存超过限制的空间后做释放内存的处理：

<pre class="prettyprint hljs javascript" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; word-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;">const { createReadStream, appendFile } = require('fs');
const readline = require('readline');
const intersect = require('./intersect');

module.exports = (smallData) => {
return new Promise((resolve) => {
const rl = readline.createInterface({
// 6000条数据流
input: createReadStream('./database/data60M.txt', {
// 节流阀
highWaterMark: 50
}),
// 处理分隔符
crlfDelay: Infinity
});
// 缓存次数
let lineCount = 0;
// 缓存容器
let rawData = [];
// 逐行读取
rl.on('line', (line) => {
rawData.push(line);
lineCount++;
// 限制每一次读取6000条数据，分十次读取
if (lineCount === 6000) {
// 释放内存
// ...
}
);
rl.on('close', () => {
resolve('结束');
})
})
}</pre>

释放内存后前需要使用 rl.pause() 暂停流，然后做两步逻辑:

  • 求交集结果
  • 写入每段交集结果到硬盘

然后需要使用 rl.resume() 重启流：

<pre class="prettyprint hljs javascript" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; word-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;">if (lineCount === 6000) {
// 暂停流
rl.pause();
// 获取交集
let intersectResult = intersect(rawData, smallData);
// 遍历交集并写入结果
intersectResult.forEach(element => {
writeResult(element)
});
// 释放缓存
rawData = null;
intersectResult = null;
rawData = [];
// 重置读取次数
lineCount = 0;
// 重启流
rl.resume();
}</pre>

上面这个过程实际非常耗时和缓慢，这里建议就是在代码长时间运行的时候不要冷落了面试官o(╥﹏╥)o

image

在处理完上面 6 千万数据之后，就剩下 3百万份的了，这里的数据由于是3百万，所以可以把全部数据放入内存，我们在 data-3M.js 写入以下代码，这里用 Promise 封装，方便在外部配合 async 和 await 使用：

<pre class="prettyprint hljs coffeescript" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; word-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;">const fs = require('fs');
const readline = require('readline');
module.exports = () => {
return new Promise((resolve) => {
const rl = readline.createInterface({
input: fs.createReadStream('./database/data-3M.txt'),
crlfDelay: Infinity
});
let check = [];
rl.on('line', (line) => {
check.push(line);
});
rl.on('close', () => {
resolve(check)
})
})
}</pre>

然后就是交集了，在 intersect.js 代码中写入一下代码，这里简单的使用 Set 和 filter 方法来求交集：

<pre class="prettyprint hljs javascript" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; word-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;">// 交集方法
module.exports = (a, b) => {
return a.filter(x => new Set(b).has(x));
}</pre>

分别把上面两份处理关键数据在 index.js 逻辑引入，然后执行逻辑，就可以乖乖地等待面试官的检阅和指导了：

<pre class="prettyprint hljs javascript" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; word-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;">const data3M = require('./library/data-3M');
const data60M = require('./library/data-60M');
(async () => {
let smallData = await data3M();
let result = await data60M(smallData);
console.log(result);
})();</pre>

image

这里附上源代码地址方便小伙伴测试： https://github.com/Wscats/intersect

也使用以下命令运行测试，运行成功后结果会在 result.txt 中展现结果：

<pre class="prettyprint hljs dockerfile" style="padding: 0.5em; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; color: rgb(68, 68, 68); border-radius: 4px; display: block; margin: 0px 0px 1.5em; font-size: 14px; line-height: 1.5em; word-break: break-all; word-wrap: break-word; white-space: pre; background-color: rgb(246, 246, 246); border: none; overflow-x: auto; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;">git clone https://github.com/Wscats/intersect

运行

npm start

查看结果

npm run dev # 生成新的大数据
npm run build</pre>

有想了解更多的朋友可以；

一、搜索QQ群，前端学习交流群：1093606290

二、https://jq.qq.com/?_wv=1027&k=MlDBtuEG

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,921评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,635评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,393评论 0赞 338
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,836评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,833评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,685评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,043评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,694评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 42,671评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,670评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,779评论 1赞 332
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,424评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,027评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,984评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,214评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,108评论 2赞 351
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,517评论 2赞 343