PTT數位生活區 / C_and_CPP (C/C++)

[閒聊] C++ LeetCode刷題的寫法

看板C_and_CPP (C/C++)作者 (大大)時間1年前 (2022/05/19 21:29), 編輯推噓15(16推 1噓 33→)
留言50則, 19人參與, 1年前最新討論串1/1
在解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://www.ptt.cc/bbs/C_and_CPP/M.1652966978.A.78D.html
→
05/19 21:57, 1年前 , 1F
pass by reference當然有差 不是只傳一個int 是vector
05/19 21:57, 1F
→
05/19 21:58, 1年前 , 2F
auto& -> vector<int>&
05/19 21:58, 2F
→
05/19 21:58, 1年前 , 3F
auto -> vector<int>
05/19 21:58, 3F
→
05/19 21:58, 1年前 , 4F
一個傳reference 沒啥開銷
05/19 21:58, 4F
→
05/19 21:58, 1年前 , 5F
我比較喜歡DIRS{0,1,0,-1,0} LEN=4
05/19 21:58, 5F
推
05/19 22:53, 1年前 , 6F
同樓上
05/19 22:53, 6F
推
05/20 00:21, 1年前 , 7F
我記得傳 reference 會造成沒辦法把值放到 register，導
05/20 00:21, 7F
→
05/20 00:21, 1年前 , 8F
致有時候 pass by value 反而會讓函數跑比較快
05/20 00:21, 8F
→
05/20 00:21, 1年前 , 9F
但這個 case 傳 ref 應該是比較好啦...
05/20 00:21, 9F
→
05/20 00:27, 1年前 , 10F
寫auto&&會更好,免得當dirs的容器變成vector<bool>
05/20 00:27, 10F
→
05/20 00:29, 1年前 , 11F
這種proxy class(會讓dereference得到一個暫時物件)
05/20 00:29, 11F
→
05/20 00:30, 1年前 , 12F
使得lvalue-reference無法bind to it.
05/20 00:30, 12F
推
05/20 02:25, 1年前 , 13F
plain struct可能就還好 你這是複製vector所以效能
05/20 02:25, 13F
→
05/20 02:25, 1年前 , 14F
影響比較大
05/20 02:25, 14F
推
05/20 05:53, 1年前 , 15F
沒改到就加 const
05/20 05:53, 15F
推
05/20 06:33, 1年前 , 16F
DIRS{0,1,0,-1,0} LEN=4 怎麼寫啊， len=5?
05/20 06:33, 16F
噓
05/20 09:00, 1年前 , 17F
這個不重要 重要的是你的演算法
05/20 09:00, 17F
→
05/20 09:01, 1年前 , 18F
而且compiler對於built-in type的東西有最佳化 pass by
05/20 09:01, 18F
→
05/20 09:01, 1年前 , 19F
value的效能會更好 但不重要 演算法不是要考語言特性
05/20 09:01, 19F
推
05/20 09:08, 1年前 , 20F
我都用 const auto &var
05/20 09:08, 20F
推
05/20 09:51, 1年前 , 21F
@peter98 說是這樣說，但刷 LeetCode 的人有高比例都不只
05/20 09:51, 21F
→
05/20 09:51, 1年前 , 22F
是為了測試演算法，多學一點語言特性都不會是壞事XD
05/20 09:51, 22F
→
05/20 09:52, 1年前 , 23F
而且這年頭演算法別說語言特性了，連硬體特性都要考慮，已
05/20 09:52, 23F
→
05/20 09:55, 1年前 , 24F
經不太純了XD
05/20 09:55, 24F
推
05/20 10:53, 1年前 , 25F
這個哪裡不重要 這是超級基本的C++特性
05/20 10:53, 25F
推
05/20 11:17, 1年前 , 26F
pass by value 效能會更好你確定這句話永遠為真？
05/20 11:17, 26F
推
05/20 13:30, 1年前 , 27F
int x = i + dir[d], y = j + dir[d + 1];
05/20 13:30, 27F
推
05/20 15:43, 1年前 , 28F
這讓我想到我某同事把其他語言寫的算法直接搬到c++
05/20 15:43, 28F
→
05/20 15:44, 1年前 , 29F
結果更慢就罵c++落伍又沒用 XD
05/20 15:44, 29F
推
05/20 21:58, 1年前 , 30F
高頻交易表示硬體才是問題
05/20 21:58, 30F
→
05/20 22:06, 1年前 , 31F
對語法熟、對編譯過程熟、對指令熟、對硬體特性熟，想
05/20 22:06, 31F
→
05/20 22:06, 1年前 , 32F
拼到極致單靠演算法是不夠的
05/20 22:06, 32F
→
05/20 22:09, 1年前 , 33F
寫嵌入式慢慢的 12MHz 可能還要精算每道指令的 cycle
05/20 22:09, 33F
→
05/20 22:09, 1年前 , 34F
數咧，哪有什麼哪個東西不重要這種說法
05/20 22:09, 34F
推
05/20 22:10, 1年前 , 35F
而且也可能是 leetcode 的問題，有時候會發生同一份 code
05/20 22:10, 35F
→
05/20 22:10, 1年前 , 36F
多 submit 幾次，每次跑出來效能都不一樣
05/20 22:10, 36F
推
05/20 22:17, 1年前 , 37F
啊我的意思是發生效能不如預期也可能是 lc 的鍋，雖然這
05/20 22:17, 37F
→
05/20 22:17, 1年前 , 38F
個 case 是因為 deep copying vectors 造成的
05/20 22:17, 38F
推
05/21 13:27, 1年前 , 39F
有人知道 constexpr等等compile time會不會算進作答時間嗎
05/21 13:27, 39F
→
05/21 15:39, 1年前 , 40F
應該不會 你拿meta programming玩一下No.509就知道了
05/21 15:39, 40F
推
05/21 16:24, 1年前 , 41F
不是template就不需要用auto&&了，因為你很清楚知
05/21 16:24, 41F
→
05/21 16:24, 1年前 , 42F
道操作的iterat
05/21 16:24, 42F
→
05/21 16:24, 1年前 , 43F
or dereference之後的型別是不是proxy，如果是prox
05/21 16:24, 43F
→
05/21 16:24, 1年前 , 44F
y還不如直接pa
05/21 16:24, 44F
→
05/21 16:24, 1年前 , 45F
ss by value享受compiler對build-in type有可能給
05/21 16:24, 45F
→
05/21 16:24, 1年前 , 46F
出的優化。寫te
05/21 16:24, 46F
→
05/21 16:24, 1年前 , 47F
mplate時你才會有考慮iterator dereference之後返
05/21 16:24, 47F
→
05/21 16:24, 1年前 , 48F
回值的各種可能
05/21 16:24, 48F
→
05/21 16:24, 1年前 , 49F
性問題。
05/21 16:24, 49F
→
05/21 22:28, 1年前 , 50F
dir這個用vector太浪費 建議直接用constexpr
05/21 22:28, 50F
‣ 更多 hunter73419 的文章
文章代碼(AID): #1YXaP2UD (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 hunter73419 的文章
文章代碼(AID): #1YXaP2UD (C_and_CPP)