人工智能與大資料面試指南——算法與資料結構：大資料量算法

分類目錄：​​《人工智能與大資料面試指南》總目錄​​

《人工智能與大資料領域面試指南》系列下的内容會持續更新，有需要的讀者可以收藏文章，以及時擷取文章的最新内容。

大資料量算法面試一般考查海量資料上的存儲、處理、操作，一般考點隻有兩個：

• 資料量過大導緻無法在較短時間内解決，需要設計一個時間複雜度較低的算法
• 資料量過大導緻無法一次性載入記憶體，需要設計合适的資料結構來實作在記憶體中存儲，或者使用外存解決問題

各種資料類型占用的存儲空間

1個位元組（byte）等于8個比特（bit），其中：

• 比特/位（bit）：計算機中存儲資料的最小機關，指二進制數中的一個位數，其值為0或1
• 位元組（byte, B）：位元組是計算機存儲容量的基本機關，1個位元組由8位二進制數組成（1Byte＝1B=8bit）。在計算機内部，一個位元組可以表示一個資料，也可以表示一個英文字母，兩個位元組可以表示一個漢字。

一般在常見的程式設計語言中有如下8中資料類型：

• 整型​

  ​byte​

  ​​：取值範圍為，占用1個位元組
• 整型​

  ​short​

  ​​：取值範圍為，占用2個位元組
• 整型​

  ​int​

  ​​：取值範圍為，占用4個位元組
• 整型​

  ​long​

  ​​：取值範圍為，占用4個位元組
• 單精度浮點型​

  ​float​

  ​：占用4個位元組
• 浮點型​

  ​double​

  ​：占用8個位元組
• 布爾型​

  ​boolean​

  ​​：邏輯上​

  ​boolean​

  ​​類型隻占1bit，但是虛拟機底層對​

  ​boolean​

  ​​值進行操作實際使用的是​

  ​int​

  ​​類型，操作​

  ​boolean​

  ​​數組則使用​

  ​byte​

  ​類型
• 文本型​

  ​char​

  ​​：存儲範圍為​

  ​\u0000​

  ​​~​

  ​\uFFFF​

  ​​，占用2個位元組，若采用​

  ​unicode​

  ​編碼，則其前128位元組編碼與ASCII相容

可以看出​

​byte​

​​類型和​

​short​

​​類型的取值範圍比較小，而​

​long​

​​類型的取值範圍又過大，占用的空間多，是以在程式設計實踐中​

​int​

​​類型的使用較多。在通常情況下，如果JAVA中出現了一個整數數字比如：35，那麼這個數字就是​

​int​

​​類型的，如果我們希望它是​

​byte​

​​類型的，可以在資料後加上大寫的​

​B​

​​，如：​

​35B​

​​，表示它是​

​byte​

​​類型的，同樣的​

​35S​

​​表示​

​short​

​​類型，​

​35L​

​​表示​

​long​

​​類型的，表示​

​int​

​​類型可以什麼都不加。同時，之是以是2的7、15、31次方是因為其包含了正負整數，​

​byte​

​​類型、​

​short​

​​類型、​

​int​

​​類型、​

​long​

​​類型包含的實際數量總數為、、和。

單精度浮點型​

​float​

​類型占用4個位元組（32位）存儲空間的單精度值。單精度在一些處理器上比雙精度更快而且隻占用雙精度一半的空間，但是當值很大或很小的時候，它将變得不精确。當你需要小數部分并且對精度的要求不高時，單精度浮點型的變量是有用的。單精度浮點型​

​float​

​​類型的單精度值占用4個位元組的空間，包括1個符号位、一個8位二進制指數和一個23 位尾數，共32位。由于尾數的高順序位始終為 1，是以它不是以數字形式存儲的。而​

​double​

​​類型比​

​float​

​​類型存儲範圍更大，精度更高，是以通常的浮點型的資料在不聲明的情況下都是​

​double​

​​型的，如果要表示一個資料是​

​float​

​​型的，可以在資料後面加上​

​F​

​。浮點型的資料是不能完全精确的，是以有的時候在計算的時候可能會在小數點最後幾位出現浮動，這是正常的。

在Python中，整數是變長的，無法精确控制記憶體，若需精确控制記憶體需使用C/C++、JAVA等語言。對于Python中的字元串，相同長度的字元串占用的存儲空間和編碼方式也有關系。

兩個大檔案A和B，每一行存儲的都是一個字元串，找出其中在兩個檔案中都出現過的字元串

對于随機不定長的字元串：哈希

• 根據給定記憶體需求或其他限制，确定需要劃分的小檔案數量（代碼裡的​​

  ​num_split​

  ​）
• 周遊檔案，對檔案的每一行做Hash運算，根據Hash值将該行資料映射到小檔案中，的滿足：，若劃分結束後發現存在子檔案仍然超過記憶體限制，可以通過增大解決
• 周遊檔案，對檔案的每一行做Hash運算，根據Hash值及讀取檔案并判斷是否在中，由于不同字元串可能産生相同Hash值，故在Hash值相同的情況下還需要判斷字元串是否相同（可将檔案的每行字元串的Hash值作為key，字元串本身或字元串行索引作為value存入小檔案中），若Hash值不同則可以斷定字元串不在檔案中

import json

def contrast_file(fileA_path, fileB_path, num_split):
    result = []
    
    for i in range(num_split):
        with open('fileA_%s.json' % i,'w') as f:
            json.dump({}, f, ensure_ascii=False)     # ensure_ascii=False可以使得中文正常輸出

    with open(fileA_path) as f:
        for line in f:
            line = line.replace('\n', '')
            hash_line = hash(line)
            ind = hash_line % num_split
            with open('fileA_%s.json' % ind,'r+') as fileA_ind:
                dict_fileA_ind = json.load(fileA_ind)
            with open('fileA_%s.json' % ind,'w+') as fileA_ind:
                if hash_line in dict_fileA_ind:
                    dict_fileA_ind[hash_line].append(line)
                else:
                    dict_fileA_ind[hash_line] = [line]
                json.dump(dict_fileA_ind, fileA_ind, ensure_ascii=False)
                
    with open(fileB_path) as f:
        for line in f:
            line = line.replace('\n', '')
            hash_line = hash(line)
            ind = hash_line % num_split
            with open('fileA_%s.json' % ind,'r+') as fileA_ind:
                dict_fileA_ind = json.load(fileA_ind)
                hash_line = str(hash_line)
                if hash_line in dict_fileA_ind:
                    list_hash_line = dict_fileA_ind[hash_line]
                    if line in list_hash_line:
                        result.append(line)
    
    return result      

對于固定格式的字元串，如電話号碼、QQ号等：Trie樹

• 周遊檔案的字元串依次寫入Trie樹
• 周遊檔案判斷字元串是否存在于Trie樹

對于重複字元串較多的情況，可先用​

​set()​

​去重

參考文章：

· ​​​《位圖（BitMap）》​​​ · ​​《布隆過濾器（Bloom Filter）》​​

10億個未排序的正整數，其中隻有1個數重複出現過，要在的時間裡面找出這個數，且記憶體要盡可能少

方法一：BitMap（适用于最大的正整數較小的情況）

當最大的正整數較小時，可以使用BitMap，即将10億個正整數轉換到一個BitMap中，并将其所有位設定為0，然後開始周遊這10億個整數，每周遊一個，則對應到位圖中相應的位置設定1。當記憶體為1G時，1G=1024MB=1048576KB=1073741824B=8589934592bits。換言之當10億個正整數中的最大數小于8589934592時，使用BitMap理論上使用的記憶體小于1GB。在周遊整個數組插入BItMap的過程中，若出現任意一個正整數的位上已經為1，則該正整數為重複出現的數字，

方法二：字典樹（字首樹、Trie樹）

若最大的正整數不确定時，可以使用字典樹。由于每個正整數的位數可能不同，是以在整數的末尾需要加上某個符号來表示結束，若在周遊數組建構字典樹的時候，某個正整數的最後一位寫入字典樹後，節點上連接配接了一個結束符号，則說明改正整數重複出現過。

方法三：歸并排序

• 建立為外排序所用的記憶體緩沖區，并根據它們的記憶體大小将輸入檔案劃分為若幹段，然後用某種有效的内排序方法對各段進行排序，這些經過排序的段叫做初始歸并段或初始順串，當它們生成後就被寫到硬碟中
• 仿照内排序中所介紹過的歸并樹模式，把第一個階段生成的初始歸并段加以歸并，一趟趟地擴大歸并段和減少歸并段個數，直到最後歸并成一個大歸并段（有序檔案）為止。