作者hunter73419 (大大)
看板C_and_CPP
标题[闲聊] C++ LeetCode刷题的写法
时间Thu May 19 21:29:36 2022
在解LeetCode上面关於DP or BFS/DFS的时候常会用到下面几行code
vector<vector<int>> dirs{{0,-1}, {0,1}, {1,0}, {-1,0}};
func()
{
for(auto& dir: dirs)
{
int nr = r + dir[0];
int nc = c + dir[1];
}
}
for那一行有时候想说没改到dir得值，就直接写成for(auto dir: dirs)
没想到leetcode算效能的时候结果差很多
我试过有时候从70%掉到10%
甚至超过时间submit failed
这两种写法真的有差这麽多吗?
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.163.224.17 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1652966978.A.78D.html
1F：→ wulouise: pass by reference当然有差 不是只传一个int 是vector 05/19 21:57
2F：→ lingege321: auto& -> vector<int>& 05/19 21:58
3F：→ lingege321: auto -> vector<int> 05/19 21:58
4F：→ lingege321: 一个传reference 没啥开销 05/19 21:58
5F：→ wulouise: 我比较喜欢DIRS{0,1,0,-1,0} LEN=4 05/19 21:58
6F：推 LawlietDo: 同楼上 05/19 22:53
7F：推 CoNsTaR: 我记得传 reference 会造成没办法把值放到 register，导 05/20 00:21
8F：→ CoNsTaR: 致有时候 pass by value 反而会让函数跑比较快 05/20 00:21
9F：→ CoNsTaR: 但这个 case 传 ref 应该是比较好啦... 05/20 00:21
10F：→ jack7775kimo: 写auto&&会更好,免得当dirs的容器变成vector<bool> 05/20 00:27
11F：→ jack7775kimo: 这种proxy class(会让dereference得到一个暂时物件) 05/20 00:29
12F：→ jack7775kimo: 使得lvalue-reference无法bind to it. 05/20 00:30
13F：推 harryooooooo: plain struct可能就还好 你这是复制vector所以效能 05/20 02:25
14F：→ harryooooooo: 影响比较大 05/20 02:25
15F：推 NciscalA: 没改到就加 const 05/20 05:53
16F：推 bjk: DIRS{0,1,0,-1,0} LEN=4 怎麽写啊， len=5? 05/20 06:33
17F：嘘 peter98: 这个不重要 重要的是你的演算法 05/20 09:00
18F：→ peter98: 而且compiler对於built-in type的东西有最佳化 pass by 05/20 09:01
19F：→ peter98: value的效能会更好 但不重要 演算法不是要考语言特性 05/20 09:01
20F：推 alan23273850: 我都用 const auto &var 05/20 09:08
21F：推 ddavid: @peter98 说是这样说，但刷 LeetCode 的人有高比例都不只 05/20 09:51
22F：→ ddavid: 是为了测试演算法，多学一点语言特性都不会是坏事XD 05/20 09:51
23F：→ ddavid: 而且这年头演算法别说语言特性了，连硬体特性都要考虑，已 05/20 09:52
24F：→ ddavid: 经不太纯了XD 05/20 09:55
25F：推 chchwy: 这个哪里不重要 这是超级基本的C++特性 05/20 10:53
26F：推 chchwy: pass by value 效能会更好你确定这句话永远为真？ 05/20 11:17
27F：推 bjk: int x = i + dir[d], y = j + dir[d + 1]; 05/20 13:30
28F：推 ctrlbreak: 这让我想到我某同事把其他语言写的算法直接搬到c++ 05/20 15:43
29F：→ ctrlbreak: 结果更慢就骂c++落伍又没用 XD 05/20 15:44
30F：推 newking761: 高频交易表示硬体才是问题 05/20 21:58
31F：→ Lipraxde: 对语法熟、对编译过程熟、对指令熟、对硬体特性熟，想 05/20 22:06
32F：→ Lipraxde: 拼到极致单靠演算法是不够的 05/20 22:06
33F：→ Lipraxde: 写嵌入式慢慢的 12MHz 可能还要精算每道指令的 cycle 05/20 22:09
34F：→ Lipraxde: 数咧，哪有什麽哪个东西不重要这种说法 05/20 22:09
35F：推 CoNsTaR: 而且也可能是 leetcode 的问题，有时候会发生同一份 code 05/20 22:10
36F：→ CoNsTaR: 多 submit 几次，每次跑出来效能都不一样 05/20 22:10
37F：推 CoNsTaR: 啊我的意思是发生效能不如预期也可能是 lc 的锅，虽然这 05/20 22:17
38F：→ CoNsTaR: 个 case 是因为 deep copying vectors 造成的 05/20 22:17
39F：推 SFGEX: 有人知道 constexpr等等compile time会不会算进作答时间吗 05/21 13:27
40F：→ sarafciel: 应该不会 你拿meta programming玩一下No.509就知道了 05/21 15:39
41F：推 OnlyRD: 不是template就不需要用auto&&了，因为你很清楚知 05/21 16:24
42F：→ OnlyRD: 道操作的iterat 05/21 16:24
43F：→ OnlyRD: or dereference之後的型别是不是proxy，如果是prox 05/21 16:24
44F：→ OnlyRD: y还不如直接pa 05/21 16:24
45F：→ OnlyRD: ss by value享受compiler对build-in type有可能给 05/21 16:24
46F：→ OnlyRD: 出的优化。写te 05/21 16:24
47F：→ OnlyRD: mplate时你才会有考虑iterator dereference之後返 05/21 16:24
48F：→ OnlyRD: 回值的各种可能 05/21 16:24
49F：→ OnlyRD: 性问题。 05/21 16:24
50F：→ EricTCartman: dir这个用vector太浪费 建议直接用constexpr 05/21 22:28
51F：推 deangood01: 纯粹是lc 那个时间变化很大而已 你同一份多传几次 不 05/26 14:53
52F：→ deangood01: 同月份传 结果可能出乎你意料 05/26 14:53