写点什么

ARTS--week 10 补打卡

用户头像
steve_lee
关注
发布于: 2021 年 06 月 03 日
ARTS--week 10 补打卡

已经有好几周没打卡了,经历裁员,找工作,房子维权,家人去世一波慌乱,现在多数问题尘埃落定,终于又可以继续 ARTS 了

Algorithm

题目链接

695. 岛屿的最大面积 - 力扣(LeetCode) (leetcode-cn.com)

题目分析

相当于找最大的联通域面积,可以用并查集的方法,也可以用深度优先搜索来做。下面介绍深度优先搜索的方法

对每个点进行遍历,看是是 1,以及是否被访问过,是 1 并且没被访问过,说明发现了一个新的岛屿,开始进行深度优先搜索。

对每个点四个方向进行遍历,并将返回结果进行加和,那么起始点返回的值就是当前岛屿的面积。

更新并保存一个最大值,最终返回即可

代码实现

class Solution {public:    int maxAreaOfIsland(vector<vector<int>>& grid) {        if(grid.size() == 0) return 0;        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));        vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};        int max_size = 0;         int curr_size = 0;        for(int i = 0; i < grid.size(); i++){            for(int j = 0; j < grid[0].size(); j++){                if(grid[i][j] == 1 && !visited[i][j]){                    curr_size = dfs(i, j, grid, visited,directions);                    if(curr_size > max_size){                        max_size = curr_size;                    }                }            }        }        return max_size;    }    inline bool in_map(int x, int y, int w, int h){        return x >=0 && x < w && y >= 0 && y < h;    }    int dfs(int i, int j, vector<vector<int>> &grid, vector<vector<bool>> &visited,           vector<pair<int, int>> &directions){        int count = 1;        visited[i][j] = true;        int h = grid.size();        int w = grid[0].size();                for(const auto& direction : directions){            int new_row = i + direction.first;            int new_col = j + direction.second;            if(!in_map(new_row, new_col, h, w)){                continue;            }            if(grid[new_row][new_col] == 0 || visited[new_row][new_col] ){                continue;            }            count += dfs(new_row, new_col, grid, visited, directions);        }        //visited[i][j] = false;        return count;    }}; 
复制代码



Review

A Simple Makefile Tutorial (colby.edu), 找到了新工作,又要开始写 C++,重新温习下 makefile 写法。

这篇文章介绍了简单的多文件 makefile 的写法,对于一些简单场景,应该能够充分覆盖,也是学习下一步的关键,假设有三个文件, 两个.c 文件,一个头文件,简单代码如下


可以通过 gcc 来进行编译,命令如下

gcc -o hellomake hellomake.c hellofunc.c -I.
复制代码

其中 -I. 来保证在当前目录下寻找所需头文件。这种方法的缺点很明显,1. 每次都需要重新输入;2.对一个文件的更改就需要编译所有相关文件。三个文件当然没问题,但是工程量大了之后,这样的方法就会很浪费时间。

先从最简单例子开始

makefile1:

hellomake: hellomake.c hellofunc.c	gcc -o hellomake hellomake.c hellofunc.c -I.
复制代码

第一行声明了目标文件和源文件,通过冒号分隔,第二行就是普通 gcc 编译命令。注意:gcc 前面一定要有一个空格。 此时,仅需要 make 命令即可完成编译链接,不用每次重新输入命令行。

下面看一个稍微进阶的版本

makefile2

CC=gccCFLAGS=-I.
hellomake: hellomake.o hellofunc.o $(CC) -o hellomake hellomake.o hellofunc.o
复制代码

这个版本定义了两个常量, CC 和 CFLAGS, 是用来告诉 make 如何编译.c 文件的。CC 指定编译器名称,CFLAGS 是用来传递编译参数的,这样可以避免多行的时候重复输入。功能和特性和 makefile1 一样,只是增加两个常量。

上述两个格式的 makefile 对于小型项目比较合适,但是不能做到一点,关于 include file 的依赖关系。以上面图例子为例,如果 hellomake.h 发生了变更,但是 hellofunc.c 不变,那么编译器不会重新编译.c 文件,但是事实上,需要对.c 文件重新编译。

如何解决这个问题呢?我们需要告诉 make 程序,.c 文件依赖于某个.h 文件。要做到这一点,可以添加一个规则到 makefile, 如下所示

CC=gccCFLAGS=-I.DEPS = hellomake.h
%.o: %.c $(DEPS) $(CC) -c -o $@ $< $(CFLAGS)
hellomake: hellomake.o hellofunc.o $(CC) -o hellomake hellomake.o hellofunc.o
复制代码

第三行添加了一个宏,DEPS, dependences 的缩写,是所有.c 文件依赖的.h 文件名。第 5-6 行定义了依赖规则, 所有以.o 结尾的文件依赖于所有.c 结尾的文件并也依赖于 DEPS 里面定义的.h 文件集合。第六行指明如果要生成.o 文件,需要编译所有的 c 文件。

-c 表示生成目标文件;

-o $@ 表示将生产的文件放到第五行:冒号的左侧

$< 表示 DEPS 里面的第一项,即 hellomake.h

$(CFLAG S)的定义同上面相同

两个特殊的宏:

$@表示冒号左边的内容

$^表示冒号右边的内容

通过这两个宏,makefile3 可以改写为如下形式

makefile4

CC=gccCFLAGS=-I.DEPS = hellomake.hOBJ = hellomake.o hellofunc.o 
%.o: %.c $(DEPS) $(CC) -c -o $@ $< $(CFLAGS)
hellomake: $(OBJ) $(CC) -o $@ $^ $(CFLAGS)
复制代码

在这里,引入了一个新的常量,OBJ,表示编译的目标

一个正常的工程项目要有几个分类,如将头文件放到 include 里面,.c 文件放到 src 里面,依赖库的.so 文件放到 lib 里面,代码的格式应该是这样

makefile5

IDIR =../includeCC=gccCFLAGS=-I$(IDIR)
ODIR=objLDIR =../lib
LIBS=-lm
_DEPS = hellomake.hDEPS = $(patsubst %,$(IDIR)/%,$(_DEPS))
_OBJ = hellomake.o hellofunc.o OBJ = $(patsubst %,$(ODIR)/%,$(_OBJ))

$(ODIR)/%.o: %.c $(DEPS) $(CC) -c -o $@ $< $(CFLAGS)
hellomake: $(OBJ) $(CC) -o $@ $^ $(CFLAGS) $(LIBS)
.PHONY: clean
clean: rm -f $(ODIR)/*.o *~ core $(INCDIR)/*~
复制代码


这些知识对于中小型项目应该 ok 了,如果还有其他内容,就需要参考官方手册,GNU make


Tips

在机器学习任务中,如果 python 写的一些后处理程序过慢(到达小时级别甚至天级别), 如果优化代码本身无法达到预期速度,可能最快的方式是编写一个 cpp 程序,然后打包成为 so 文件,作新的 module 来调用。因为 python 的判断条件都要进行安全检查,会严重影响性能。昨天通过实践,一些 pytorch tensor 操作,需要频繁 if 语句的,当将这个小代码块转化为 cpp 之后,性能可以提高 10-100 倍。

Share

本周分享的观点是如何判断代码的好坏,是和某 AI 头部公司 CTO 聊的时候谈到的观点,如何判断代码质量的好坏,比如自己带了团队,进行代码审查,那么这个时候,怎么告诉新人,哪些代码是好的,好在哪里,哪些代码是坏的,坏在哪里呢?其实主要就是依赖于设计模式的几个原则,这样子讲起来就方便很多,类似 MBA 的案例,大家有了业界共识,那么沟通起来会方便很多,设计模式的一个原则和我理解的意思,具体如下

  • 单一职责原则 (Single Responsibility Principle):一个类只负责一个职责

  • 开放-关闭原则 (Open-Closed Principle):软件实体 (类、模块、函数等等) 应该是可以被扩展的,但是不可被修改

  • 里氏替换原则 (Liskov Substitution Principle):子类可以扩展父类的功能,但不能改变父类原有的功能

  • 依赖倒转原则 (Dependence Inversion Principle):高层模块不应该依赖低层模块,二者都应该于抽象。进一步说,抽象不应该依赖于细节,细节应该依赖于抽象。面向接口编程

  • 接口隔离原则 (Interface Segregation Principle):客户端不应该依赖它不需要的接口;一个类对另一个类的依赖应该建立在最小的接口上。

  • 迪米特法则(Law Of Demeter):迪米特法则又称为 最少知道原则,它表示一个对象应该对其它对象保持最少的了解。通俗来说就是,只与直接的朋友通信

  • 组合/聚合复用原则 (Composite/Aggregate Reuse Principle):,也就是在实际开发设计中,尽量使用组合/聚合,不要使用类继承。

发布于: 2021 年 06 月 03 日阅读数: 12
用户头像

steve_lee

关注

还未添加个人签名 2018.03.09 加入

努力做全栈程序员,将AI应用于实处

评论

发布
暂无评论
ARTS--week 10 补打卡