作者 | 梁唐
大家好,我是梁唐。
最近复习剑指offer的时候发现一个小问题,就是有些题目找不到来源。不知道来源就导致了,没有办法练习。有的时候我还会有一些奇思妙想,比如对题目做一些变形,甚至是自己搞一些原创题等等。
为了解决这个问题,老梁决定在本地搭建一个算法题的测试样例生成和测试工具。这样就可以在本地对算法进行测试了。
目前主要功能已经开发好了,虽然还比较简单,只能算是一个demo版本。但勉强能用,代码我已经开源在了github。点击「阅读原文」进行跳转。
整个项目大概分为三个功能,第一个功能当然是样例生成。
样例生成并不简单,因为不同的题目的题面不同,题面不同自然生成数据的算法也不同。这就意味着对于每道题的生成算法都要单独实现。
虽然数据生成的逻辑各不相同,但是运行的核心逻辑是一样的,都是生成数据再写入文件。只不过生成的逻辑各不相同,所以我们可以把样例的生成逻辑抽象出来放到派生类当中,而写入文件等一些核心逻辑在父类中实现。这样对于每道不同的题目,我们只需要关心数据生成逻辑即可,整个调用链路都是可以复用的。
我们先从最简单的结构开始看起,首先是Case
类,Case
类即测试样例,一个Case
的实例表示一个测试样例,它的定义如下:
class Case:
def __init__(self,*args, **kw):
raise NotImplementedError()
def output(self, data_path, result_path, idx):
raise NotImplementedError()
相当于我们定义了一个接口,并不会直接使用父类。Case
类当中只有两个函数,一个是初始化函数,一个是输出函数output
。
我们再来看一个它子类的例子,这道题是剑指offer第三题,在一个行列皆有序的二维数组当中寻找target是否存在。那么这个子类的构造函数当中实现的就是创建一个有序二维矩阵和target,output
则是将结果输入对应的文件。
class Case3(Case):
def __init__(self):
# 创建行列均有序的二维矩阵
n, m = random.randint(1, 100), random.randint(1, 100)
nums = sorted([random.randint(0, 100000000) for _ in range(n * m)])
arr = np.array(nums).reshape((n, m))
ans, k = 0, 0
if random.randint(0, 100) > 50:
ans = 1
x, y = random.randint(0, n-1), random.randint(0, m-1)
k = arr[x, y]
else:
while True:
k = random.randint(0, 100000000)
if k not in nums:
break
self.n, self.m, self.k, self.ans = n, m, k, ans
self.arr = arr
def output(self, data_path, result_path, idx):
# 将测试数据输入data_path,答案输入result_path
# idx为当前测试样例编号
with open(data_path, 'a+') as f:
f.write('{} {} {}\n'.format(self.n, self.m, self.k))
for i in range(self.n):
for j in range(self.m):
f.write('{} '.format(self.arr[i, j]))
f.write('\n')
with open(result_path, 'a+') as f:
f.write('case :{}\n'.format(idx + 1))
f.write(str(self.ans))
f.write('\n')
我们实现了样例的创建逻辑之后,为了将创建逻辑和生成逻辑解耦,我们把这个类本身当做参数传给样例构造的类Generate
。
class Generate:
def __init__(self, n, problem_id, Case):
# 将Case的实现子类以参数形式传入
self.n = n
self.problem_id = problem_id
self.output_path = os.path.join(output_path_base, '{}.txt'.format(problem_id))
self.result_path = os.path.join(result_path_base, '{}.txt'.format(problem_id))
self.cases = []
self.Case = Case
def generate(self):
for _ in range(self.n):
# 样例的具体生成逻辑都在Case类的初始化函数当中实现了
self.cases.append(self.Case())
def output(self):
# 生成输入的文件地址
if os.path.exists(self.output_path):
os.remove(self.output_path)
if os.path.exists(self.result_path):
os.remove(self.result_path)
f = open(self.output_path, 'w')
f.write('{}\n'.format(self.n))
f.close()
# 打印相关信息
for i in range(self.n):
print('generating case{}ing'.format(i))
self.cases[i].output(self.output_path, self.result_path, i)
f.close()
测试样例生成了之后,接下来要做的就是编写算法了。
我们采用最常规的C++来编写,由于测试样例已经输入了文件,当前我们就有两个选择。一个选择是在C++当中进行文件的处理操作,第二个选择是在以命令编译执行C++代码时以数据流的形式指定文件。
前者需要我们将对应的文件路径写在代码里,耦合性比较强,所以我选择了后者,在执行C++的时候做数据流的定向,如:
g++ xxx.cpp -o cur
./cur < input.txt > output.txt
既然如此,那么我们只需要在C++代码当中使用标准输入输出即可。使用标准输入输出之后,我们就可以随意玩耍了。不过为了代码看起来更加标准,我还是采用了LeetCode风格。即将算法执行逻辑以函数的形式实现,和数据处理的逻辑完全拆分开:
int tcase;
cin >> tcase;
for (int _i = 0 ; _i < tcase; _i++) {
int n, m, target;
cin >> n >> m >> target;
vector<vector<int>> mat(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> mat[i][j];
}
}
// 算法实现在findNumberIn2DArray 函数中
cout << findNumberIn2DArray(mat, target) << endl;
}
最后是校验的逻辑,其实校验的逻辑很简单,也就是把C++的输出结果和我们创建数据时候的正确答案进行比对。
使用Python的os
库,可以实现在Python当中调用shell
命令,完成一些比较复杂的功能。比如说调用g++
编译C++代码,并进行调用:
def get_cpp_result(code_path, bin_path, data_path, output_path):
# 编译
compile_st = os.system('g++ -std=c++17 -o {} {}'.format(bin_path, code_path))
if compile_st > 0:
print('compile error!')
delete_files(bin_path)
return [], False
os.system('mkdir cur')
# 运行
run_st = os.system('./{} < {} > {}'.format(bin_path, data_path, output_path))
if run_st > 0:
print('run time error!')
delete_files(bin_path)
os.system('rm -rf {}'.format(output_path))
return [], False
ret = []
with open(output_path, 'r') as f:
for l in f.readlines():
ret.append(l)
delete_files(bin_path)
return ret, True
最后, 当C++代码执行结束之后,再和我们生成数据时的正确答案进行比对。
在这个工具当中,为了简便,我直接使用的字符串比对。一般的结果直接当做字符串比对即可,有些特殊的题目可能需要special judge,也就是进行一些特殊的比对。比如有些题目的正确答案可能有多个, 任一输出一个即可,再比如有些题目输出的结果是一个浮点数,由于是浮点数所以没办法要求完全一致,一般都是给定精度,只要误差在这个范围内也算是正确等等。
不过special judge的逻辑相对复杂一些,目前还不支持,以后有需要用到了再完善。
这个项目是我心血来潮写的,毕竟还只是初版,有不完美或遗漏的地方在所难免。如果有什么疑问或者需求不妨给我留言,也欢迎大家开发新的功能给我提PR。