ZXAlgorithm - JZ海量數(shù)據(jù)處理算法

https://www.jiuzhang.com/tutorial/big-data-interview-questions
https://www.lintcode.com/ladder/47/

包括哪些方面？
算法：外排序，mapreduce，非精確算法，概率算法，hash算法
數(shù)據(jù)結(jié)構(gòu)：hash table，堆，布隆過濾器，位圖

C1 最高頻K項(xiàng)問題

主要講了什么?
找出一個(gè)大文件或者數(shù)據(jù)流中出現(xiàn)頻率最高的K項(xiàng)，由是否需要精確和是離線還是在線決定

K Closest Points
https://www.lintcode.com/problem/k-closest-points/description?_from=ladder&&fromId=47
https://www.lintcode.com/problem/k-closest-points/discuss?_from=ladder&&fromId=47

離線算法：

使用快排的算法，但是要掃兩遍，無法滿足數(shù)據(jù)流的算法
使用快選（基于快排的思路）O（N）
https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/60306/Python-different-solutions-with-comments-(bubble-sort-selection-sort-heap-sort-and-quick-sort).
基于堆 O(klogN)
LintCode 練習(xí)地址
https://www.lintcode.com/problem/top-k-largest-numbers/discuss
https://www.jiuzhang.com/solution/top-k-largest-numbers/#tag-highlight-lang-python

從最大K項(xiàng)到最高頻K
先用Hash去存（key, frequency），然后用上面的最小堆的算法

在線算法：

LintCode 練習(xí)地址

最高頻K項(xiàng)
https://www.jiuzhang.com/tutorial/big-data-interview-questions/229
一邊計(jì)數(shù)一邊比較TopK
一個(gè)dict計(jì)數(shù)器，一個(gè)heap(里面存的是(key, count))（最小棧）
取topK，直接把這個(gè)heap給變成list
加入新的值，先變dict計(jì)數(shù)器，然后如果在heap里面，更新數(shù)組，否則判斷有沒有滿，沒有滿也放進(jìn)去，最后判斷新的值是不是比最小棧里面的top（即最小值）大，如果大的話放進(jìn)去

C2 Bloom filter

節(jié)省空間，但是存在FP問題

  • 包含兩個(gè)部分
    1.k個(gè)完全獨(dú)立的hash 函數(shù)，magic number設(shè)置為31，37，41等等
    magic number不能設(shè)置的太?。ㄔ黾优鲎玻螅ㄓ?jì)算效率低），不是合數(shù)（每一個(gè)大于1的整數(shù)若不是質(zhì)數(shù)，就會是合數(shù)
    ）
    2.一個(gè)很大的數(shù)組
  • 分為兩種
    標(biāo)準(zhǔn)型：HashSet
    計(jì)數(shù)型：HashMap

標(biāo)準(zhǔn)型

boolean數(shù)組，k個(gè)哈希值，k個(gè)有false，肯定沒有
如果4個(gè)hash函數(shù)，數(shù)組長度和要存的個(gè)數(shù)40：1

計(jì)數(shù)型

int數(shù)組，k個(gè)哈希值，k個(gè)存的最小為預(yù)估次數(shù)比實(shí)際的數(shù)要大

C3 外排序算法

https://www.cnblogs.com/LUO77/p/5838206.html
大文件分割為小文件，各個(gè)歸并排序
https://leetcode.com/problems/merge-k-sorted-lists/
https://github.com/corvasto/Python-SS

C4 概率類的大數(shù)據(jù)問題

如何在數(shù)據(jù)流中等概率取出M個(gè)元素
等概率挑出文件中的一行
先選出1行，剩下的每次能替代的概率是1/k
等概率的挑選Google搜索記錄日志中的一百萬條中文搜索記錄
M是出現(xiàn)過了多少條中文記錄，N是需要多少條中文記錄
如果buffer不滿先寫進(jìn)去，如果滿了，以N/M的概率隨機(jī)替換原來的
random.randint(1, M) <= N

C5 其他和題目

題目：
http://www.lintcode.com/ladder/47/

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

相關(guān)閱讀更多精彩內(nèi)容

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