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

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

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

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

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

題目一

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

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

題目二

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

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

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

題目三

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

【補充】
某搜索公司一天的用戶搜索詞匯是海量的（百億數(shù)據(jù)量），
請設(shè)計一種求出每天人們Top100詞匯的可行辦法。

題目四

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

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

題目五

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

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

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

題目六

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

現(xiàn)在不看5G內(nèi)存，假設(shè)內(nèi)存嚴重不足，只能存幾條記錄
那么準備一個堆，大根堆，只存3條記錄，存的是數(shù)字和出現(xiàn)的次數(shù)
申請1個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
…
文件遍歷完了，堆中就記錄了整個文件中前3小的數(shù)，出現(xiàn)的次數(shù)
假設(shè)是
1 =>1000
3 =>2000
5 =>1000
然后在10G的文件中，數(shù)字1寫1000次，數(shù)字3寫2000次，數(shù)字5寫1000次

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

題目七

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

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

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

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

廣告

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