大廠前端面試：：如何讓6000萬數(shù)據(jù)包和300萬數(shù)據(jù)包在僅50M內(nèi)存環(huán)境中求交集

由于最近疫情的影響，相信最近很多小伙伴都忙于線上辦公或者面試:sob:，筆者這里分享一道發(fā)生在大廠前端線上編程面試中的一道題目，

如何讓 6000 萬數(shù)據(jù)包和 300 萬數(shù)據(jù)包在僅 50M 內(nèi)存環(huán)境中求交集，請(qǐng)簡(jiǎn)單說出您解決這問題的思路

我們假設(shè)現(xiàn)在有兩份龐大的數(shù)據(jù)，而這兩份數(shù)據(jù)包的數(shù)據(jù)結(jié)構(gòu)均如下，仔細(xì)觀察里面的數(shù)據(jù)我們不難發(fā)現(xiàn)，里面有 QQ 號(hào)，地址和年齡，如題目的要求我們需要是求交集，所以我們暫時(shí)可以忽略地址和年齡，以 QQ 號(hào)作為唯一標(biāo)識(shí)：

<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 萬條數(shù)據(jù)
...</pre>

梳理了上面的數(shù)據(jù)包結(jié)構(gòu)之后，我們就得看看 50M 內(nèi)存是什么情況了，由于面試在線上進(jìn)行，只能短時(shí)間在本地測(cè)試下上面這個(gè)數(shù)據(jù)量在本地會(huì)占有有多大空間，那由于限于是場(chǎng)前端面試，所以筆者選用了 NodeJS 去制造這些龐大的數(shù)據(jù)了，當(dāng)時(shí)線上編寫的時(shí)候是沒注釋的，這里為了方便小伙伴理解，在寫這篇文章的時(shí)候我自覺加上了: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 {
// 檢查是否可以繼續(xù)寫入。
// 不要傳入回調(diào)，因?yàn)閷懭脒€沒有結(jié)束。
ok = writer.write(data);
}
} while (i > 0 && ok);
if (i > 0) {
// 被提前中止。
// 當(dāng)觸發(fā) 'drain' 事件時(shí)繼續(xù)寫入。
writer.once('drain', write);
}
}
// 初始化6000萬數(shù)據(jù)
let i = 600000;
write();
}

writeSixtyMillionTimes(writer)</pre>

首先在本地新建一份 data-60M.txt 文件，然后新建一份 data-60M.js 把上面代碼寫入并執(zhí)行，這里我最主要是使用了一個(gè)遞歸，由于當(dāng)時(shí)為了快速寫入文件測(cè)試大小，當(dāng)時(shí)模擬的 QQ 號(hào)，是使用 ${parseInt(Math.random() * 60000000)}\n 隨機(jī)數(shù)生成的，在實(shí)際測(cè)試表現(xiàn)中會(huì)有極小幾率重復(fù) QQ 號(hào)，但影響不大，實(shí)際影響最大的是當(dāng)你在生成 6000 萬數(shù)據(jù)的時(shí)候，電腦瘋狂運(yùn)作，運(yùn)氣不好的時(shí)候直接卡死，然后遠(yuǎn)程面試直接斷線。

這里筆者還是建議小伙伴在遠(yuǎn)程面試中手機(jī)隨時(shí)待命，當(dāng)電腦 GG 的時(shí)候還能聯(lián)系面試官搶救一下，經(jīng)過與電腦性能的多輪斗爭(zhēng)，和面試官尷尬重連的情況下，終于發(fā)現(xiàn)實(shí)際文件大小規(guī)律如下，這里為了方便小伙伴調(diào)試源代碼，我也把代碼傳到 Github 上，鏈接放在最后，只放了 6000 條數(shù)據(jù)，實(shí)際 300MB 實(shí)在是傳不上去了，小伙伴們可以下載源代碼自行測(cè)試，祈禱電腦能熬過去o(╥﹏╥)o：

數(shù)據(jù)量 內(nèi)存占用
6000條數(shù)據(jù)(Git版本) >=30KB
6000萬條數(shù)據(jù)(實(shí)際版本) >=300MB
300條數(shù)據(jù)(Git版本 >=15KB
300萬條數(shù)據(jù)(實(shí)際版本) >=15MB
image

到了這個(gè)地方，筆者漸漸地看出這個(gè)問題的坑點(diǎn)可能在那里了，6000 萬條數(shù)據(jù)在測(cè)試文件中大小大概在 300MB 左右，而 300 萬條數(shù)據(jù)大小大概在 15 MB，在 50MB 的內(nèi)存限制下，我們可以把 300 萬條約 15MB 的數(shù)據(jù)完全放入內(nèi)存中，剩余大概 35MB 空間是不允許我們完全放入 6000 萬條約 300MB 的數(shù)據(jù)，所以我們需要把數(shù)據(jù)切割成10塊左右，大概每塊控制在 30MB ，然后分別讀取出來跟內(nèi)存中的 300 萬條數(shù)據(jù)進(jìn)行比對(duì)并求出交集，50MB 情況也太極端苛刻了，難道是手機(jī)并且還是老人機(jī)嗎，我也不敢問啊o(╥﹏╥)o

在思考上面這一連串的邏輯時(shí)候，為了不耽誤面試官寶貴的時(shí)間，邊想邊隨手建立好下面幾份文件和文件夾，好梳理代碼，給自己思考時(shí)間和回旋的余地，以下是我當(dāng)時(shí)臨時(shí)的目錄結(jié)構(gòu)。

  • database

    • data-3M.txt - 模擬的3百萬數(shù)據(jù)包
    • data-60M.txt - 模擬的6千萬數(shù)據(jù)包

  • library

    • data-3M.js - 處理3百萬數(shù)據(jù)包的邏輯
    • data-60M.js - 處理6千萬數(shù)據(jù)包的邏輯
    • intersect.js - 處理數(shù)據(jù)包的交集
    • create-60M.js - 生成大數(shù)據(jù)的文件

  • result.txt 最終數(shù)據(jù)包的交集結(jié)果

  • index.js 主邏輯文件

在不急不慢的分類好目錄結(jié)構(gòu)之后，總得再弄點(diǎn)代碼給面試官瞧瞧吧o(╥﹏╥)o，不能讓人家空等啊

image

當(dāng)然既然是面試用 NodeJS 第三方模塊解決也不夠好，當(dāng)時(shí)是先屢一下用什么原生模塊實(shí)現(xiàn)比較好，要滿足上面這些要求，想到這里能使用到的原生 Node 內(nèi)置模塊關(guān)鍵有如下兩個(gè)：

  • fs - 文件系統(tǒng)
  • readline - 逐行讀取

fs.createReadStream(path[, options]) 方法中，其中 options 可以包括 start 和 end 值，以從文件中讀取一定范圍的字節(jié)而不是整個(gè)文件。 start 和 end 都包含在內(nèi)并從 0 開始計(jì)數(shù)，這種是方法方便我們分段讀取 6000 萬條數(shù)據(jù)。當(dāng)時(shí)快速寫了一個(gè)示例去驗(yàn)證，從一個(gè)大小為 100 個(gè)字節(jié)的文件中讀取最后 10 個(gè)字節(jié)：

<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>

經(jīng)過短暫的測(cè)試，發(fā)現(xiàn)這個(gè)方案可行，心理淡定了一點(diǎn)。

image

起碼這個(gè)備用方案起碼可以給自己留點(diǎn)操作空間，但當(dāng)時(shí)討論到的是下面這種方案：

fs.createReadStream() 提供 highWaterMark 選項(xiàng)，它允許我們將以大小等于 highWaterMark選項(xiàng)的塊讀取流， highWaterMark 的默認(rèn)值為: 64 * 1024(即64KB)，我們可以根據(jù)需要進(jìn)行調(diào)整，當(dāng)內(nèi)部的可讀緩沖的總大小達(dá)到 highWaterMark 設(shè)置的閾值時(shí)，流會(huì)暫時(shí)停止從底層資源讀取數(shù)據(jù)，直到當(dāng)前緩沖的數(shù)據(jù)被消費(fèi)，我們就可以觸發(fā) readline.pause() 暫停流，處理完之后繼續(xù)觸發(fā) readline.resume() 恢復(fù)流，然后不斷重復(fù)以上步驟，將 6000 萬數(shù)據(jù)分別處理完。

readline 模塊提供了一個(gè)接口，用于一次一行地讀取可讀流中的數(shù)據(jù)。 它可以使用以下方式訪問，并且我們的數(shù)據(jù)包，每條數(shù)據(jù)之間是使用 \n、\r 或 \r\n 隔開，所以這樣方便我們使用 readline.on('line', (input) => {}) 來接受每一行數(shù)據(jù)包的字符串。

這里自我感覺有些丟分項(xiàng)，是當(dāng)時(shí)忘記了 fs.createReadStream 里面一些配置項(xiàng)，在現(xiàn)場(chǎng)臨時(shí)翻閱 NodeJS 的官方 API 文檔，這里非常感謝當(dāng)時(shí)面試官的理解( ▽ )

image

下面，我們就要寫最關(guān)鍵的代碼了，就是如何處理那 6000 萬條數(shù)據(jù)，打開剛才新建好的 data-60M.js 文件，該文件就是用于專門處理 6000 萬數(shù)據(jù)的，我們使用 readline 和 createReadStream 兩者配合，將數(shù)據(jù)按一定條數(shù)分別緩存在內(nèi)存中，這里代碼正如上面提到，由于提交的代碼不適合太大(Git傳上去太慢)，所以把數(shù)據(jù)量減少到 6000 條，那么分成 10 份的話，每份緩存就需要讀 600 條左右，讀完每份數(shù)據(jù)之后調(diào)用 intersect 函數(shù)求交集，并存入硬盤 result.txt 文件中，然后釋放內(nèi)存：

<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;">// 寫入結(jié)果
const writeResult = (element) => {
appendFile('./result.txt', ${element}\n, (err) => {
err ? () => console.log('寫入成功') : () => console.log('寫入失敗');
})
}</pre>

這里最關(guān)鍵是要定義一個(gè)空的容器 lineCount 來存放每段數(shù)據(jù)，并且使用 if (lineCount === 6000) {} 語句判斷內(nèi)存超過限制的空間后做釋放內(nèi)存的處理：

<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條數(shù)據(jù)流
input: createReadStream('./database/data60M.txt', {
// 節(jié)流閥
highWaterMark: 50
}),
// 處理分隔符
crlfDelay: Infinity
});
// 緩存次數(shù)
let lineCount = 0;
// 緩存容器
let rawData = [];
// 逐行讀取
rl.on('line', (line) => {
rawData.push(line);
lineCount++;
// 限制每一次讀取6000條數(shù)據(jù)，分十次讀取
if (lineCount === 6000) {
// 釋放內(nèi)存
// ...
}
);
rl.on('close', () => {
resolve('結(jié)束');
})
})
}</pre>

釋放內(nèi)存后前需要使用 rl.pause() 暫停流，然后做兩步邏輯:

  • 求交集結(jié)果
  • 寫入每段交集結(jié)果到硬盤

然后需要使用 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);
// 遍歷交集并寫入結(jié)果
intersectResult.forEach(element => {
writeResult(element)
});
// 釋放緩存
rawData = null;
intersectResult = null;
rawData = [];
// 重置讀取次數(shù)
lineCount = 0;
// 重啟流
rl.resume();
}</pre>

上面這個(gè)過程實(shí)際非常耗時(shí)和緩慢，這里建議就是在代碼長時(shí)間運(yùn)行的時(shí)候不要冷落了面試官o(╥﹏╥)o

image

在處理完上面 6 千萬數(shù)據(jù)之后，就剩下 3百萬份的了，這里的數(shù)據(jù)由于是3百萬，所以可以把全部數(shù)據(jù)放入內(nèi)存，我們?cè)?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 代碼中寫入一下代碼，這里簡(jiǎn)單的使用 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>

分別把上面兩份處理關(guān)鍵數(shù)據(jù)在 index.js 邏輯引入，然后執(zhí)行邏輯，就可以乖乖地等待面試官的檢閱和指導(dǎo)了：

<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

這里附上源代碼地址方便小伙伴測(cè)試： https://github.com/Wscats/intersect

也使用以下命令運(yùn)行測(cè)試，運(yùn)行成功后結(jié)果會(huì)在 result.txt 中展現(xiàn)結(jié)果：

<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

運(yùn)行

npm start

查看結(jié)果

npm run dev # 生成新的大數(shù)據(jù)
npm run build</pre>

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

一、搜索QQ群，前端學(xué)習(xí)交流群：1093606290

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

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容