memset Gets TLE#
const int N = 1e8 + 10;
int a[N];
int main()
{
int t; cin >> t;
while (t--) {
memset(a, 0, sizeof a);
...
}
}
memset 函数会将整个数组进行填充，但遇到多组数据的情况，每次都对 a 填充一次，显然会 TLE
解决思路可以有两种：
- 弃用全局变量
弃用全局变量带来最大的困难是函数之间变量传递的问题，一般函数可以添加一个参数，但对于 dfs 来说较为不便，考虑使用
lambda进行 dfs 的实现。 - 弃用
memset换成fill()或assign()只要将不必要操作省去，操作次数在合理的范围内满足需要即可
笔者个人倾向抛弃全局变量的写法。为实现我们这一操作，对一般函数，我们采用引用传递。下面简析 recursive lambda 的写法：
lambda 递归#
使用 self -- 最快#
auto dfs1 = [&](auto &self, int u, int p) -> int {
int ret = 1;
for(auto v : adj[u]) {
if(v != p)
ret += self(self, v, u);
}
return ret;
};
利用 self 指代表达式自身，给 auto 的推导指明了方向，同时采用引用避免拷贝。
使用 std::function<> -- 最简便#
该模板类用于包装可以调用的任何类型的可调用对象（callable object），包括函数指针、函数对象、成员函数指针、Lambda 表达式等等
#include <functional>
#include <iostream>
void foo(int x) {
std::cout << "foo(" << x << ")" << std::endl;
}
int main() {
std::function<void(int)> f1 = foo;
f1(42);
std::function<void()> f2 = []() { std::cout << "lambda" << std::endl; };
f2();
struct Bar {
void operator()(int x) const {
std::cout << "Bar::operator()(" << x << ")" << std::endl;
}
};
std::function<void(int)> f3 = Bar();
f3(123);
return 0;
}
原理在于向该类内部传入函数。但大量递归，新开大量 std::function<> 存在较大开销。
approach:
function<int(int, int)> dfs2 = [&](int u, int p) {
int ret = 1;
for(auto v : adj[u]) {
if(v != p) {
ret += dfs2(v, u);
}
}
return ret;
};
Benchmark#
int main() {
int n; cin >> n;
vector<vector<int>> adj(n);
for(int i = 0; i < n - 1; i++) adj[i].push_back(i + 1);
auto dfs1 = [&](auto &self, int u, int p) -> int {
int ret = 1;
for(auto v : adj[u]) {
if(v != p)
ret += self(self, v, u);
}
return ret;
};
function<int(int, int)> dfs2 = [&](int u, int p) {
int ret = 1;
for(auto v : adj[u]) {
if(v != p) {
ret += dfs2(v, u);
}
}
return ret;
};
cout << fixed << setprecision(10);
auto start = clock();
int res1 = dfs1(dfs1, 0, -1);
cout << res1 << '\n';
cout << "Passing self: " << (double) (clock() - start) / CLOCKS_PER_SEC << '\n';
start = clock();
int res2 = dfs2(0, -1);
cout << res2 << '\n';
cout << "std::function: " << (double) (clock() - start) / CLOCKS_PER_SEC << '\n';
assert(res1 == res2);
return 0;
}
/* ---- results ---- */
n = 1e5
Passing self: 0.0000000000
std::function: 0.0180000000
n = 1e6
Passing self: 0.0310000000
std::function: 0.0780000000
n = 2e6
Passing self: 0.0620000000
std::function: 0.1750000000