memset 遇到 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