背景
题目:最近发现记忆化搜索真的很好用,于是在做力扣上记忆化搜索相关的题目时,用这种方法重做了一下买卖股票问题。
问题来源
在写递归代码的时候,我学习了一种匿名函数的写法,直接在函数体内写function<int(int, int)>dfs = [&](int day, int state)->int,从而用&一个字符捕获了外部所有参数,相当的方便,省的递归一个一个手动传参数~~(上次觉得什么东西很“方便”,还是在得知#include<bits/stdc++.h>是万能头文件的时候)~~ 。
然而,用这种方法写题居然超时了。试了一个prices.length()比较长(10的5次方)的测试用例,发现执行用时居然是使用外部递归函数的几十倍(28ms->884ms),前提是两者都使用了记忆化搜索存入了数组,逻辑完全一致
怀疑是匿名参数捕获参数问题
虽然参数是引用形式捕获,还是怀疑了一下
1.改成function<int(int, int)> dfs = [&dp, &prices](int day, int state) -> int,出现问题,因为是递归,需要调用自身。
2.改成 // 先声明dfs,此时还不给它赋值
std::function<int(int, int)> dfs;
dfs = [&dp, &prices, &dfs](int day, int state) -> int
修改完,发现用时还是很久,(当然了,因为所有的参数又被捕获进来了。。。)
模板类
然后想起来模板这种东西似乎是需要时间的,function也属于一种template,之前没有递归调用的时候不在意模板性能,现在写了这个题,感觉还是确实有影响。本来想用visual studio的性能分析工具调试一波,谁知道测试用例太长粘都粘不过来 = =。。即使粘过来了,修改cpp的时候又会卡死。。。
综合来看,可能是模板使用过程中,动态内存分配、间接层,甚至是可能的内联展开导致了这种情况的出现。