CMU15-445_Project0

学习笔记 CMU15-445
CS
发布日期:   2025-03-19
更新日期:   2025-03-19
文章字数:   2k
阅读时长:   9 分
阅读次数:  

早在去年的年底就写完了CMU15-445的project0，但是当时写完有几十个Bug，陆陆续续改了一两天之后去忙别的事情了，就一直没有写完，github上找到了之前提交的新分支，准备重头看下题目然后继续快速的通过这个project0，个人认为这个Project0出得还是很有新意，和之前的什么字典树，前缀树之类的数据结构有较大区别，这是一个Probablistic data structure 一种概率数据结构。

Project Specification

项目官网

基础介绍

目的：Keeping track of the number of unique users accessing a website in a single day .

当对少数人访问的网站直接记录就好了，但是对有数十亿的用户来说要去重就非常的麻烦，所以就产生了HyperLogLog(HLL)这个概率数据结构，以极小的误差计算海量数据流种的唯一项目的数量，不显式存储唯一项目。

关键变量：

  • b : 哈希值二进制表示形式中的初始位数

  • m ：设定的桶数，m=2^b

  • p ：剩余的哈希位中最左端第一个1的位置

具体样例解释：

Consider a simple example of how this algorithm works using the string "A great database is a great life". First, the string is hashed to produce a hash value, which is then converted into its binary representation. From the hash value (binary form), b bits are extracted, starting from the most significant bit(MSB). The register value is calculated from the extracted bits. (by default each register has a value of 0).
考虑一个使用字符串 "A great database is a great life" .首先，对字符串进行哈希处理以生成哈希值，然后将其转换为其二进制表示形式。从哈希值（二进制形式）中提取 b 位，从最高有效位 （MSB） 开始。寄存器值是根据提取的 bits 计算得出的。（默认情况下，每个 register 的值为 0）。

From the remaining set of bits, the position of the leftmost 1 is obtained (MSB), i.e the number of leading zeros from left plus 1 (as given in the picture given below).
从剩余的一组位中，获得最左边的 1 的位置 （MSB），即从左边开始的前导零加 1 的数量（如下图所示）。

HLL

After this, using the b bits, the register value is calculated (which in the above case it’s 6). Hence, in register 6, max(register[6], p) will be stored.
在此之后，使用 b 位计算 register 值（在上述情况下为 6）。因此，在寄存器 6 中，将存储 max（register[6]， p）。

HLL

Another value in a set may have p = 2 in register 3, hence 2 will be stored in register 3.
一组中的另一个值可能在寄存器 3 中具有 p = 2，因此 2 将存储在寄存器 3 中。

HLL

Now, another element in a set has p = 2 in register 6. Hence, max(register[6], p) –> max(5, 2) will be stored in register 6.
现在，集合中的另一个元素在寄存器 6 中具有 p = 2。因此， max(register[6], p) –> max(5, 2) 将存储在寄存器 6 中。

HLL

Similarly, another element having p = 4 in register 3, max(register[3], p) –> max (2, 4) will be stored in register 3.
同样，寄存器 3 中 p = 4 的另一个元素 max(register[3], p) –> max (2, 4) 将存储在寄存器 3 中。

HLL

After all the elements in the set have been added, cardinality is calculated in the following manner.
添加集合中的所有元素后，按以下方式计算基数。

If there are total of m registers, then:
如果总共有 m 个 registers，则：

HLL

where constant = 0.79402 and R[j] is the value in register j and N = m.
其中 constant = 0.79402 和 R[j] 是寄存器 j 和 N = m 中的值。

文章中解释的很清楚，这里就不多赘述了，只明确几个点：

  • 一共的桶数为m，根据b个二进制数一共能得到2^b个组合得出的m，所以在概率上所有桶是等概率的获得数字、
  • 这个概率型数据结构的证明不属于本篇博文的讨论范围，故略过，教程中有Resources介绍其证明及实现HLL的博客。

Note

Task1将用最左边的1的位置作为p，Task2将使用最右边的连续零的个数作为p存储在寄存器中。

Instructions

Task1:实现基本的HLL数据结构

In hyperloglog.h, following functions have to be implemented:
在 hyperloglog.h 中，必须实现以下功能：

  • HyperLogLog(inital_bits): a constructor where a number of leading bits (b) is provided.
    HyperLogLog（inital_bits）：一个构造函数，其中提供了多个前导位 （b）。
  • GetCardinality(): returns the cardinality value of a given set
    GetCardinality（）：返回给定集的基数值
  • AddElem(val): computes and places the value in the register.
    AddElem（val）：计算值并将其放入寄存器中。
  • ComputeCardinality(): computes the cardinality based on the above formula.
    ComputeCardinality（）：根据上述公式计算基数。

Along with it, you can implement helper functions to implement the above (can add more as per requirement):
除此之外，您还可以实现辅助函数来实现上述内容（可以根据要求添加更多）：

  • ComputeBinary(hash_t hash): It computes a binary of a given hash value. The hash value should be converted to a 64 bit binary stream (otherwise tests may fail).
    ComputeBinary（hash_t hash）：计算给定哈希值的二进制文件。哈希值应转换为 64 位二进制流（否则测试可能会失败）。
  • PositionOfLeftmostOne(....): it computes the position of the leftmost 1.
    PositionOfLeftmostOne（....）：它计算最左边的 1 的位置。

For calculating hash, you can use the given function:
要计算哈希值，您可以使用给定的函数：

  • CalculateHash(...) - to calculate hash
    CalculateHash（...）- 计算哈希

Please refer to the std::bitset library for storing in binary representation. When a value is obtained in decimal, convert into a greatest integer less than or equal to the decmial. Refer std::floor for more details.
请参考 std：：bitset 库以二进制表示形式存储。当获得以十进制为单位的值时，转换为小于或等于十进制的最大整数。有关更多详细信息，请参阅 std：：floor

可以简单的发现，这几个函数的最终作用就是读取字符串，转换哈希串，转化成二进制字符串，按位处理，存入vector，所以可以轻易的写出代码：

在这里只展示hyperLogLog.cpp

基本代码

#include "primer/hyperloglog.h"

namespace bustub {

/** @brief Parameterized constructor. */
template <typename KeyType>
HyperLogLog<KeyType>::HyperLogLog(int16_t n_bits) : cardinality_(0) {
  if (n_bits < 1 || n_bits > 64) {
    throw std::invalid_argument("n_bits must be between 1 and 64");
  }
  this->n_bits = n_bits;
 //   BITSET_CAPACITY = n_bits;//应该是不能改这个的
  
  this->registers_=std::vector<uint64_t>(1<<n_bits,0);
  bitset_=std::bitset<BITSET_CAPACITY>(0);
}

/**
 * @brief Function that computes binary.
 *
 * @param[in] hash
 * @returns binary of a given hash
 */
template <typename KeyType>
auto HyperLogLog<KeyType>::ComputeBinary(const hash_t &hash) const -> std::bitset<BITSET_CAPACITY> {
  /** @TODO(student) Implement this function! */
 return  std::bitset<BITSET_CAPACITY>(hash);
 
}

/**
 * @brief Function that computes leading zeros.
 *
 * @param[in] bset - binary values of a given bitset
 * @returns leading zeros of given binary set
 */
template <typename KeyType>
auto HyperLogLog<KeyType>::PositionOfLeftmostOne(const std::bitset<BITSET_CAPACITY> &bset) const -> uint64_t {
  /** @TODO(student) Implement this function! */
  for (uint64_t i = static_cast<uint64_t>(BITSET_CAPACITY-(uint16_t)n_bits-1); i >1; i--) {//bset.test是从最右边开始遍历
    if (bset.test(i)) {
      return (BITSET_CAPACITY-(uint16_t)n_bits) - i;
    }
  }
  return 0; 
}

/**
 * @brief Adds a value into the HyperLogLog.
 *
 * @param[in] val - value that's added into hyperloglog
 */
template <typename KeyType>
auto HyperLogLog<KeyType>::AddElem(KeyType val) -> void {
  /*
  数出前面几个b然后把他变成寄存器的位置，然后数出1的位置然后塞进去
  */
 bitset_=std::bitset<BITSET_CAPACITY>(0);
 bitset_=ComputeBinary(CalculateHash(val));
 uint64_t decimal_value=0;
 for(uint64_t i=0;i<n_bits;i++){//计算桶的序号数
   uint64_t bit_index =BITSET_CAPACITY-n_bits+i;
   if(bitset_.test(bit_index)){
     decimal_value+=(1ull <<(i));//左移i位
   }
 }
 uint64_t positionlt_value = PositionOfLeftmostOne(bitset_);//计算除去桶左边第一个1的位置
  if(registers_[decimal_value]<positionlt_value){
    registers_[decimal_value]=positionlt_value;
  /** @TODO(student) Implement this function! */
  }
}

/**
 * @brief Function that computes cardinality.
 */
template <typename KeyType>
auto HyperLogLog<KeyType>::ComputeCardinality() -> void {
  for(int i=0;i<(1<<n_bits);i++){
  middle_pow_sum+=std::pow(2,-registers_[i]);
  }
  middle_pow_sum=(1.0*CONSTANT*(1<<n_bits)*(1<<n_bits))/middle_pow_sum;
  cardinality_=(uint64_t)floor(middle_pow_sum);//向下取整
  

  // /** @TODO(student) Implement this function! */
}

template class HyperLogLog<int64_t>;
template class HyperLogLog<std::string>;

}  // namespace bustub

全面报错

发现一个测试点都没过，于是开始漫长的debug，因为不知道怎么debug高效，只能修改测试样例，看输出符不符合，现在还在尝试，可能之后用gdb来debug，虽然之前用过

文章作者: Vitus Apollo
文章链接: http://vitus213.github.io/2025/03/19/CMU15_445_Project0/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Vitus Apollo !
学习笔记 CMU15-445
赏
  目录