題目介紹

這是題目原文。
注意：在拉取項目的時候需要注意拉取2024fall的Tag，本人血淚教訓！

本題是關于HyperLogLog的具體實現，其介紹可以看這個視頻進行了解。簡單來說HyperLogLog可以在一個非常小的固定內存下（一般為十幾KB）非常快速地估算出大量數據的唯一元素數量，并且其可以分別對多個數據庫獨立估算，還不會損失精度。

比如要統計訪問網站的唯一用戶數，如果用精確算法，需要對數據庫中的所有數據進行比對，這會占用非常大的內存且非常耗時，尤其是在分布式存儲的情況下。但我們在絕大多數的時候并不需要一個精確的值，因此可以使用HLL對其進行估算（雖說是估算，但其誤差也非常小）。

這道題主要檢查了學生的C++基礎，以及對C++項目的開發和調試能力。

文章末尾有本人的項目代碼地址，文章內容主要講述思路和一些細節不會出現代碼，大家各取所需。

Task#1

Task#1是實現基本的HLL算法。

所需修改的文件目錄為：
src/include/primer/hyperloglog.h
src/primer/hyperloglog.cpp

測試文件的目錄為：
test/primer/hyperloglog_test.cpp

原始代碼中已經給出了一些變量和方法的定義及實現，需要我們進行完善和補全。

hyperloglog.h中的變量部分給出了最終的結果cardinality_和計算常量CONSTANT，缺少了題目中所提及的b、m、p，b和p可以設置為uint8_t類型的參數，因為其值的范圍在0到63之間，m可以設置為uint8_t的數組，原因同上。

• CalculateHash()：將傳入的值轉換為哈希值的方法。
• GetCardinality()：返回最終結果。

hyperloglog.cpp是該算法主要的函數實現。以下是各個方法的簡介：

• HyperLogLog(inital_bits)：構造函數，需要我們根據傳入的b初始化我們內部的b和m。
• AddElem(val)：計算出傳入值的p并將其存在m中（最主要方法）。
• ComputeCardinality()：根據公式計算最終結果。
• ComputeBinary()：將哈希值轉換為64位二進制流。
• PositionOfLeftmostOne()：計算出p值（二進制流中最左側 1 的位置）。

我這里添加了一個函數GetBucketValue()，用來計算p應該存在m的哪個位置中。

接下來我會大概說一下我的解答中每個方法的實現。

HyperLogLog(inital_bits)

根據傳入的b初始化我們內部的b和m。需要對b的值進行判斷，看是否是小于0的值，如果小于0則直接return，否則對我們內部的b進行賦值。同時需要根據b重新設置我們m的大小。
注意： 如果將b設置為size_t或者unit_t類型，需要注意其數值不會小于0，容易因此產生bug。

ComputeBinary()

可以直接使用std::bitsize<64>()方法，將傳入的哈希值轉換為64位二進制流。需注意，這里轉換后的值第0位是低位，第63位是高位，不要搞反了。

GetBucketValue()

我們需要從后往前獲取b位二進制流的內容，計算這個二進制數在十進制下是幾。可以通過位操作符<<進行計算。

PositionOfLeftmostOne()

由于Task#1是計算高位1的位置，高位的前b位又被用來計算插入位置。所以我們需要從第63 - b位開始，從高到低查找二進制流第一個1的位置。

AddElem(val)

有了前面幾個方法，這個方法實現起來就比較簡單了。分別調用前面的幾個方法，得到參數的哈希值、64位二進制流、插入m的位置、高位1的位置p，就只需將當前p和m上的值比較一下大小，將大的存入就可以了。

ComputeCardinality()

根據公式計算最終結果，可以先算出分母的總數，再計算整個公式，可以使用static_cast<size_t>()方法保留結果的整數部分。進行冪計算時可以使用1.0 / std::pow(2, num)進行計算。

Task#2

要求我們實現HyperLogLog算法的密集布局，整體與Task#1類似，不過這里是從低位開始計算0的數量，并且如果數量超過15，需要將其拆分成高3位和低4位分別進行存儲。

所需修改的文件目錄為：
src/include/primer/hyperloglog_presto.h
src/primer/hyperloglog_presto.cpp

hyperloglog_presto.h文件多出了dense_bucket_和overflow_bucket_兩個參數，前者和前面的m基本相同，后者是在發生溢出時存儲高3位的桶。

整體思路沒有什么變化，只有以下幾點需要變化：

1. PositionOfLeftmostOne()方法需要改為從低到高計算0的個數。
2. 獲取到0的個數p后，需將其拆分為高3位和低4位。可以使用與操作符&進行處理。
3. 在對比p和插入位置的值，以及計算最終結果時，要將dense_bucket_和overflow_bucket_中相應位置的值進行合并，轉換為十進制進行比較。轉換為十進制可以使用to_ulong()方法，合并操作可以使用或操作符｜。

測試

先將test/primer/hyperloglog_test.cpp中的測試函數第二個參數的DIABLE_去掉。

mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Debug ..
make -j$(nproc) hyperloglog_test
./test/hyperloglog_test

正常應該如圖所示：

提交

cd ..
mkdir build_rel && cd build_rel
cmake -DCMAKE_BUILD_TYPE=Release ..
make -j$(nproc)
make format
make check-clang-tidy-p0
make submit-p0

如果有格式問題clang-tidy會報錯。我這里本地沒有報錯，但是提交到平臺上就會報格式錯誤，可能是工具版本的問題。

執行完成后會在根目錄生成一個壓縮包，上傳該壓縮包等待平臺打分。

正常如圖所示：

代碼地址：https://github.com/GCW-kuku/bustub