算法與數(shù)據(jù)結(jié)構(gòu)25：資源限制類題目-創(chuàng)新互聯(lián)

算法與數(shù)據(jù)結(jié)構(gòu)25：資源限制類題目

• 資源限制技巧匯總
• 題目一
• 題目二
• 題目三
• 題目四
• 題目五
• 題目六
• 題目七

創(chuàng)新互聯(lián)長(zhǎng)期為近1000家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開(kāi)放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為涿州企業(yè)提供專業(yè)的成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站、成都外貿(mào)網(wǎng)站建設(shè)公司，涿州網(wǎng)站改版等技術(shù)服務(wù)。擁有10多年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開(kāi)發(fā)。資源限制技巧匯總

1、布隆過(guò)濾器用于集合的建立與查詢，并可以節(jié)省大量空間
2、一致性哈希解決數(shù)據(jù)服務(wù)器負(fù)載管理問(wèn)題
3、利用并查集結(jié)構(gòu)做島問(wèn)題的并行計(jì)算
4、哈希函數(shù)可以把數(shù)據(jù)按照種類均勻分流
5、位圖解決某一范圍上數(shù)字的出現(xiàn)情況，并可以節(jié)省大量空間
6、利用分段統(tǒng)計(jì)思想，并進(jìn)一步節(jié)省大量空間
7、利用堆、外排序來(lái)做多個(gè)處理單元的結(jié)果合并

題目一

32為無(wú)符號(hào)整數(shù)的范圍是0~4294967295，現(xiàn)在有一個(gè)正好包含40億個(gè)無(wú)符號(hào)整數(shù)的文件，可以使用最多1GB的內(nèi)存，怎么找到出現(xiàn)次數(shù)最多的數(shù)？
排序？不行，內(nèi)存只有1G，無(wú)法在內(nèi)存排序
1、假設(shè)1G內(nèi)存，使用hash表最多只能裝下1千萬(wàn)條記錄，那么40億除以1千萬(wàn)，等于400，準(zhǔn)備400個(gè)文件
2、然后每一個(gè)數(shù)，通過(guò)hash函數(shù)，算出一個(gè)hash值，模400，得到一個(gè)文件編號(hào)，該數(shù)發(fā)送到對(duì)應(yīng)文件
3、此時(shí)同一個(gè)數(shù)字，只會(huì)進(jìn)入一個(gè)文件，文件里面存的是該數(shù)字出現(xiàn)的次數(shù)
4、這樣就搞成了400個(gè)文件，此時(shí)每次加載一個(gè)文件，遍歷文件的每條記錄，抓出出現(xiàn)次數(shù)最多的
5、最后這400個(gè)出現(xiàn)次數(shù)最多的數(shù)PK一下，得出整體出現(xiàn)次數(shù)最多的數(shù)。
6、如果發(fā)現(xiàn)一個(gè)文件大小過(guò)大，在內(nèi)存還是裝不下，那么文件就搞500個(gè)、600個(gè)…

如果題目要求返回出現(xiàn)次數(shù)最多的所有數(shù)，那么就拿著這個(gè)次數(shù)，到每個(gè)文件中再找一遍，看有沒(méi)有出現(xiàn)這么多次的數(shù)，有的話就全部抓出來(lái)，返回。

題目二

32位無(wú)符號(hào)整數(shù)的范圍是0~4294967295，
現(xiàn)在有一個(gè)正好包含40億個(gè)無(wú)符號(hào)整數(shù)的文件，
所以在整個(gè)范圍中必然存在沒(méi)出現(xiàn)過(guò)的數(shù)。
可以使用最多1GB的內(nèi)存，怎么找到所有沒(méi)有出現(xiàn)過(guò)的數(shù)？
set去重統(tǒng)計(jì)？不行，內(nèi)存會(huì)爆掉。
使用位圖，8個(gè)bit才一個(gè)直接，那么就準(zhǔn)備4294967295bit長(zhǎng)度的位圖進(jìn)行統(tǒng)計(jì)。
如果實(shí)現(xiàn)bit數(shù)組？使用基礎(chǔ)類型拼，長(zhǎng)度為10的int數(shù)組，等于320bit長(zhǎng)度的bit數(shù)組，第i個(gè)bit就是arr[i / 32]這個(gè)數(shù)的第i%32位
那么這一位代表的數(shù)是否存在，就這樣計(jì)算：
int status = arr[i / 32] & (1<< (i%32)) != 0 ? 1 : 0;
如果status是1，那么就是存在，0就是不存在。

【進(jìn)階】
內(nèi)存限制3KB，但是只用找到以沒(méi)出現(xiàn)過(guò)的數(shù)即可。
3KB大約能存下750個(gè)整形，那么準(zhǔn)備一個(gè)離750最近的2的某次方，得到512，那么申請(qǐng)512長(zhǎng)度的數(shù)組
此時(shí)可以把0~4294967295均分為512份（512個(gè)文件），每一份負(fù)責(zé)負(fù)責(zé)的范圍的長(zhǎng)度是8388608
這樣，肯定在每個(gè)范圍上存儲(chǔ)數(shù)不滿8388608的情況，找到這個(gè)不滿的范圍，再分512份，再找不滿的小范圍，再分512份…，幾次過(guò)后就能找到?jīng)]出現(xiàn)過(guò)的1個(gè)數(shù)。

【進(jìn)階】
內(nèi)存中只能申請(qǐng)有限幾個(gè)遍歷，但是只用找到以沒(méi)出現(xiàn)過(guò)的數(shù)即可。
申請(qǐng)兩個(gè)遍歷L和R，對(duì)0~4294967295進(jìn)行二分（兩個(gè)文件）
統(tǒng)計(jì)兩邊出現(xiàn)的數(shù)的個(gè)數(shù)
其中有一邊肯定不滿，再對(duì)不滿的一邊進(jìn)行二分，還是用兩個(gè)變量L、R統(tǒng)計(jì)兩邊范圍出現(xiàn)的數(shù)的個(gè)數(shù)
如此不斷二分，最終會(huì)找到?jīng)]出現(xiàn)過(guò)的1個(gè)數(shù)

題目三

有一個(gè)包含100億個(gè)URL的大文件，假設(shè)每個(gè)URL占用64B，
請(qǐng)找出其中所有重復(fù)的URL
如果允許失誤率，使用布隆過(guò)濾器
如果不允許，使用hash分流，分到不同小文件，看小文件是否有重復(fù)的。

【補(bǔ)充】
某搜索公司一天的用戶搜索詞匯是海量的（百億數(shù)據(jù)量），
請(qǐng)?jiān)O(shè)計(jì)一種求出每天人們Top100詞匯的可行辦法。

題目四

32為無(wú)符號(hào)整數(shù)的范圍是0~4294967295，
現(xiàn)在有40億個(gè)無(wú)符號(hào)整數(shù)，
可以使用最多1GB內(nèi)存，
找出所有出現(xiàn)了兩次的數(shù)。

用兩個(gè)bit位表示一個(gè)數(shù)出現(xiàn)的次數(shù)，比如那0bit為何1bit為表示0這個(gè)數(shù)出現(xiàn)的次數(shù)，00表示出現(xiàn)0次，01表示出現(xiàn)1次，10，表示出現(xiàn)兩次，11表示出現(xiàn)3次或以上。
這樣1個(gè)byte表示4個(gè)數(shù)。
但是4294967295除以4，超過(guò)了1G，那就繼續(xù)用上面分段統(tǒng)計(jì)的辦法。
也就是：位圖 + 分段統(tǒng)計(jì)，先統(tǒng)計(jì)前面一半（0~2^31）出現(xiàn)兩次的數(shù)，在統(tǒng)計(jì)后面一半的

題目五

32位無(wú)符號(hào)整數(shù)的范圍是0~4294967295，
現(xiàn)在有40億個(gè)無(wú)符號(hào)整數(shù)
可以使用最多3KB的內(nèi)存，怎么找到這40億個(gè)整數(shù)的中位數(shù)？

bfprt？不行，內(nèi)存會(huì)爆掉。

3KB大約能存下750個(gè)整形，那么準(zhǔn)備一個(gè)離750最近的2的某次方，得到512，那么申請(qǐng)512長(zhǎng)度的數(shù)組arr。
此時(shí)可以把0~4294967295均分為512份（512個(gè)文件），每一份負(fù)責(zé)負(fù)責(zé)的范圍的長(zhǎng)度是8388608。
數(shù)組arr中每一個(gè)數(shù)統(tǒng)計(jì)自己范圍內(nèi)出現(xiàn)的數(shù)的個(gè)數(shù)。
中位數(shù)是第20億個(gè)數(shù)，那么看數(shù)組arr累加到大于等于20億，是數(shù)組arr中的第幾個(gè)數(shù)。
假設(shè)arr[129]沖動(dòng)了20億，那么中位數(shù)一定在第129號(hào)文件。
然后以相同的方法，對(duì)129號(hào)文件分512份，數(shù)組arr統(tǒng)計(jì)每一份中出現(xiàn)的數(shù)的個(gè)數(shù)…循環(huán)往復(fù)，最終找到中位數(shù)。

題目六

32位無(wú)符號(hào)整數(shù)的范圍是0~4294967295，
有一個(gè)10G大小的文件，每一行都裝著這種類型的數(shù)字，
整個(gè)文件是無(wú)序的，給你5G的空間，
請(qǐng)你輸出一個(gè)10G大小的文件，就是原文件所有數(shù)字排序的結(jié)果。

現(xiàn)在不看5G內(nèi)存，假設(shè)內(nèi)存嚴(yán)重不足，只能存幾條記錄
那么準(zhǔn)備一個(gè)堆，大根堆，只存3條記錄，存的是數(shù)字和出現(xiàn)的次數(shù)
申請(qǐng)1個(gè)10G的文件，用于存放結(jié)果

遍歷文件，在堆中記錄數(shù)字以及該數(shù)出現(xiàn)的次數(shù)：
假設(shè)遍歷到3，記錄 3 =>1，表示3出現(xiàn)1次
再遍歷到3，記錄 3 =>2，表示3出現(xiàn)2次
遍歷到9，記錄 9 =>1
遍歷到7，記錄 7 =>1
遍歷到8，堆滿了，彈出 9 =>1，記錄8 =>1
遍歷到6，堆滿了，彈出 8 =>1，記錄6 =>1
…
文件遍歷完了，堆中就記錄了整個(gè)文件中前3小的數(shù)，出現(xiàn)的次數(shù)
假設(shè)是
1 =>1000
3 =>2000
5 =>1000
然后在10G的文件中，數(shù)字1寫(xiě)1000次，數(shù)字3寫(xiě)2000次，數(shù)字5寫(xiě)1000次

然后用1個(gè)遍歷記錄5，表示上一次遍歷到的大的數(shù)
再搞一遍這個(gè)遍歷，在堆中記錄數(shù)字以及該數(shù)出現(xiàn)的次數(shù)，但是小于等于5的數(shù)字不再記錄
…
這樣一直搞，直至所有的數(shù)都統(tǒng)計(jì)完（某一次循環(huán)，堆沒(méi)放滿），10G排序號(hào)的文件返回。

題目七

一個(gè)大文件，返回里面出現(xiàn)的數(shù)的前100名。
解法：分成不同的小文件，通過(guò)hash分流把數(shù)字分發(fā)到不同文件，每個(gè)文件統(tǒng)計(jì)Top100，然后在內(nèi)存做歸并排序。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：算法與數(shù)據(jù)結(jié)構(gòu)25：資源限制類題目-創(chuàng)新互聯(lián)
轉(zhuǎn)載源于：http://muchs.cn/article16/cecegg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊(cè)、微信小程序、商城網(wǎng)站、網(wǎng)站設(shè)計(jì)公司、網(wǎng)站設(shè)計(jì)、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)