cmu15445 proj0

2021-02-07

misc

今天正式开始写project, 希望能够坚持下去.

作业地址: https://15445.courses.cs.cmu.edu/fall2020/project0/

proj目标

In this project, you will implement three classes: Matrix, RowMatrix, and RowMatrixOperations. These matrices are simple two-dimensional matrices that must support addition, matrix multiplication, and a simplified General Matrix Multiply (GEMM) operations.

1 安装骨架代码

按照链接来 https://github.com/cmu-db/bustub#cloning-this-repo

问题1: Permission denied (publickey).

这台电脑没有加到github, 本地ssh-keygen -t rsa -C "youremail@example.com", 然后加到github的 ssh设置部分

问题2: mirror这个repo的时候 [remote rejected] master -> master (shallow update not allowed)

原因 –depth clone, 解决方法: https://stackoverflow.com/questions/28983842/remote-rejected-shallow-update-not-allowed-after-changing-git-remote-url

问题3: sudo build_support/packages.sh 显示未支持的linux版本

阅读sh脚本发现, 只支持ubuntu18和20… 全部推倒重来, 先安装系统吧…
去清华下载https://mirrors.tuna.tsinghua.edu.cn/ubuntu-releases/18.04/

tips1: To speed up the build process, you can use multiple threads by passing the `-j` flag to make

例如: make -j 4

2 安装完成, 具体实现

总共要补全三个类: Matrix, RowMatrix, RowMatrixOperations;
说实话他这注释挺离谱的, 我搞半天最后猜着他的意思做的;
其实就是Matrix是实际一维存储元素的, 而RowMatrix是一个继承Matrix的行优先的二维数组, 而RowMatrixOperations则是对RowMatrix的操作, 矩阵相加, 矩阵相乘, 矩阵相乘相加;
1 matrix类:

template <typename T>
class Matrix {
 protected:
  // TODO(P0): Add implementation
  Matrix(int r, int c) : rows(r), cols(c) {
    linear = new int[r * c];
    for (int i = 0; i < r * c; ++i) {
      linear[i] = 0;
    }
  }

  // # of rows in the matrix
  int rows;
  // # of Columns in the matrix
  int cols;
  // Flattened array containing the elements of the matrix
  // TODO(P0) : Allocate the array in the constructor. Don't forget to free up
  // the array in the destructor.
  T *linear;

 public:
  // Return the # of rows in the matrix
  virtual int GetRows() = 0;

  // Return the # of columns in the matrix
  virtual int GetColumns() = 0;

  // Return the (i,j)th  matrix element
  virtual T GetElem(int i, int j) = 0;

  // Sets the (i,j)th  matrix element to val
  virtual void SetElem(int i, int j, T val) = 0;

  // Sets the matrix elements based on the array arr
  virtual void MatImport(T *arr) = 0;

  // TODO(P0): Add implementation
  virtual ~Matrix() {
    delete []linear;
  }
};

就在堆上申请个一维数组就可以了, 然后析构的时候记得delete [], 其余函数都是纯虚函数无需改动;

2 RowMatrix类:
观察该类, 给的是一个二维指针, 而且要我们指向Matrix中的一维数组, 因此我们给二维指针分配一组一维指针, 然后每个一维指针指向一维数组中的应该指向的位置(i* c);
特别注意一点: 使用父类的元素一定要加 this指针, 在clion上可以不加, 我一直没加, 今天make一直error, 应该编译环境的问题, 以后还是养成优秀习惯, 都加上.

template <typename T>
class RowMatrix : public Matrix<T> {
 public:
  // TODO(P0): Add implementation
  RowMatrix(int r, int c) : Matrix<T>(r, c) {
    // alloc 2d matrix
    data_ = new int *[r];
    for (int i = 0; i < r; ++i) {
      data_[i] = &(this->linear[i * c]);
    }
  }

  // TODO(P0): Add implementation
  int GetRows() override { return this->rows; }

  // TODO(P0): Add implementation
  int GetColumns() override { return this->cols; }

  // TODO(P0): Add implementation
  T GetElem(int i, int j) override { return data_[i][j]; }

  // TODO(P0): Add implementation
  void SetElem(int i, int j, T val) override {
    data_[i][j] = val;
  }

  // TODO(P0): Add implementation
  void MatImport(T *arr) override {
    for (int i = 0; i < this->rows; ++i) {
      for (int j = 0; j < this->cols; ++j) {
        data_[i][j] = arr[i * this->cols + j];
      }
    }
  }

  // TODO(P0): Add implementation
  ~RowMatrix() override {
    delete []data_;
  }

 private:
  // 2D array containing the elements of the matrix in row-major format
  // TODO(P0): Allocate the array of row pointers in the constructor. Use these pointers
  // to point to corresponding elements of the 'linear' array.
  // Don't forget to free up the array in the destructor.
  T **data_;
};

3 RowMatrixOperations 类:
注意智能指针的使用(把它当作不需要delete的指针使用即可)
乘法直接naive实现, O(n^3), 没有使用strassen算法, 没必要.
最后gemm啥的直接调用前两个函数就可以.

template <typename T>
class RowMatrixOperations {
 public:
  // Compute (mat1 + mat2) and return the result.
  // Return nullptr if dimensions mismatch for input matrices.
  static std::unique_ptr<RowMatrix<T>> AddMatrices(std::unique_ptr<RowMatrix<T>> mat1,
                                                   std::unique_ptr<RowMatrix<T>> mat2) {
    // TODO(P0): Add code
    // check size
    if (mat1->GetRows() != mat2->GetRows() || mat1->GetColumns() != mat2->GetColumns()) {
      return std::unique_ptr<RowMatrix<T>>(nullptr);
    }
    // add
    int rows = mat1->GetRows();
    int cols = mat1->GetColumns();
    std::unique_ptr<RowMatrix<T>> resMat = std::make_unique<RowMatrix<T>>(rows, cols);
    for (int i = 0; i < rows; ++i) {
      for (int j = 0; j < cols; ++j) {
        resMat->SetElem(i, j, mat1->GetElem(i, j) + mat2->GetElem(i, j));
      }
    }
    return resMat;
  }

  // Compute matrix multiplication (mat1 * mat2) and return the result.
  // Return nullptr if dimensions mismatch for input matrices.
  static std::unique_ptr<RowMatrix<T>> MultiplyMatrices(std::unique_ptr<RowMatrix<T>> mat1,
                                                        std::unique_ptr<RowMatrix<T>> mat2) {
    // TODO(P0): Add code
    // check size
    if (mat1->GetColumns() != mat2->GetRows()) {
      return std::unique_ptr<RowMatrix<T>>(nullptr);
    }
    // mul
    int rows = mat1->GetRows();
    int cols = mat2->GetColumns();
    std::unique_ptr<RowMatrix<T>> resMat = std::make_unique<RowMatrix<T>>(rows, cols);
    for (int i = 0; i < rows; ++i) {
      for (int j = 0; j < cols; ++j) {
	int tmp = 0;
        for (int k = 0; k < mat1->GetColumns(); ++k) {
	  tmp += mat1->GetElem(i, k) * mat2->GetElem(k, j);
	}
	resMat->SetElem(i, j, tmp);
      }
    }
    return resMat;
  }

  // Simplified GEMM (general matrix multiply) operation
  // Compute (matA * matB + matC). Return nullptr if dimensions mismatch for input matrices
  static std::unique_ptr<RowMatrix<T>> GemmMatrices(std::unique_ptr<RowMatrix<T>> matA,
                                                    std::unique_ptr<RowMatrix<T>> matB,
                                                    std::unique_ptr<RowMatrix<T>> matC) {
    // TODO(P0): Add code
    // check size
    std::unique_ptr<RowMatrix<T>> mulMat = MultiplyMatrices(matA, matB);
    if (!mulMat) return mulMat;
    std::unique_ptr<RowMatrix<T>> resMat = AddMatrices(mulMat, matC);
    return resMat;
  }
};

学到的vim指令

ctrl + f forward, 向下翻页;
ctrl + b backward, 向上翻页;
i, 进入insert模式;
esc, 进入命令模式;
:wq, 保存并退出;
:q: 退出(无修改的时候可以正常退出);
:!q: 不保存退出, 慎用!!! 想要丢弃修改可以用git来帮忙;

总结

今天晚上没玩鬼谷八荒来写proj, 一定要保佑年后拿个好offer啊!!!
这是这门课的前置proj, 如果做不出来就要强制退课, 总体有新意, 挺简单的;
注重template的使用;
注重智能指针的使用;
this指针多用;
编码规范化, 养成good coding style;
测试通过结果: