ARTS--week 10 补打卡

steve_lee

关注

发布于: 2021 年 06 月 03 日

已经有好几周没打卡了，经历裁员，找工作，房子维权，家人去世一波慌乱，现在多数问题尘埃落定，终于又可以继续 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 倍。

本周分享的观点是如何判断代码的好坏，是和某 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

原文链接:【http://xie.infoq.cn/article/7a5d3e6f85d7d396961cf5f8b】。文章转载请联系作者。

steve_lee

关注

还未添加个人签名 2018.03.09 加入

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

发布

暂无评论

创作场景

ARTS--week 10 补打卡

Algorithm

题目链接

题目分析

代码实现

Review

Tips

Share

steve_lee

评论