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

[閒聊] g++ 8.2.1 把 O(n) code 轉成 O(1)

看板C_and_CPP (C/C++)作者時間5年前 (2019/02/16 00:50), 編輯推噓21(21推 0噓 26→)
留言47則, 13人參與, 5年前最新討論串1/2 (看更多)
最近有個熱門的討論話題 就是計算費氏數列的複雜度到底是 O(1) 還是 O(n) 剛好我前幾天在看 wiki 嘗試 compiler 的一些東西的時候 https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8 也遇到一些有趣的 O(1) 還是 O(n) 的問題 覺得很有趣所以就分享上來 我也有把問題丟在 stackoverflow 上面問 沒想到上面的反應也蠻熱烈的 https://stackoverflow.com/questions/54686395 讓我不小心賺到了一些 reputation，大概比我回答十個問題還多 --- 不管複雜度是 O(1) 或是 O(n)，也不管 lookup table 到底要不要存在月球上 費氏數列遞迴的形式都是這條：F(x) = F(x-1) + F(x-2), F(1) = F(2) = 1 不過今天要討論的是一個更簡單的問題 F(x) = F(x-1)+1, F(0) = 0 學過中學以上歸納法的人類都能知道 F(x) = x 而學過 C++ 的人都可以把這個式子轉換變成程式碼 int Identity(int i) { if (i == 1) return 1; else return Identity(i-1)+1; } 上面的 wiki 說明了這個並不是有效的 tail recursion 形式 理論上應該不會變成 for loop 會產生 O(n) memory, O(n) runtime 的程式 （PS: 如果是 for loop，應該是 O(1), memory O(n) runtime） 為了驗證，我用了 gcc 8.2.1 編譯看看，結果大出意外 % g++ a.cpp -c -O2 && objdump -d a.o Disassembly of section .text: 0000000000000000 <_Z8Identityi>: 0: 89 f8 mov %edi,%eax 2: c3 ret Linux 下 x64 的第一個整數是 %edi，回傳值放在 %eax 等等，所以我以為 O(n) 的問題，真的可以在 O(1) 解出來嗎（誤） 難道 compiler 做了一些數學計算，推出 F(x) = x 了嗎 該不會在這個大 AI 時代，compiler 也要內建高中生等級的 super AI 了吧 該不會我下次升級到 gcc 9 的時候，我的 compiler 就會跑去當 Youtuber 了吧？！ --- Sorry 扯遠了，回歸正題 我一開始的想法是 1. gcc 知道了 negative i 會撞到 UB，因此可以隨便回傳任何值 （PS: negative i 不會變成 infinite loop 的 UB，而是 overflow） 2. positive i 的情形 gcc 經過了某些數學推導算出 F(x) = x 但是怎麼看都覺得太神奇，感覺不會有人實做這種東西 總之經過 stackoverflow 一番討論之後 看起來的結論如下 首先，當代的 gcc 不只可以化簡基本的 tail recursion 就連上面那個形式都可以（可以去看 stackoverflow 的一些討論） 雖然詳細上原理我不太明白，但是應該、大約、好像會變成這樣子 int Identity(int i) { int ans = 0; for (; i != 0; i--, ans++); return ans; } 接著我猜測這個形式對 compiler 來說應該比較好化簡了 因為這種 for loop 非常常見，應該有機會做某種化簡得到 F(x) = x 順帶一題，直接寫這個程式的話，gcc 是可以化簡 O(n) -> O(1) 的 如果 i != 0 改成 i >= 0 的話，gcc 會變成 return i > 0 ? i : 0; 真的很厲害 --- 另外 stackoverflow 裡面有人直接挖出 gcc code 來解釋 但是其實我不是 compiler 專家 所以我這篇主要還是單純分享一些我的觀察啦 如果這個版有人能做出更淺顯易懂，又更完整的解釋的話就太好了 謝謝大家～ -- Time waits for no one. ↑ (。Ａ。)ハァ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.89.176 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1550249453.A.382.html
推
02/16 06:33, 5年前 , 1F
你應該沒搞懂那個討論
02/16 06:33, 1F
→
02/16 06:33, 5年前 , 2F
O(1)是說費式數列有一個公式解
02/16 06:33, 2F
→
02/16 06:34, 5年前 , 3F
可是裡面有開根號 所以實務上並不是O(1)
02/16 06:34, 3F
→
02/16 06:34, 5年前 , 4F
開根號速度跟數字長度有關係
02/16 06:34, 4F
→
02/16 06:35, 5年前 , 5F
那個作者非常智障的嗆人time it 實際上就不是O(1)
02/16 06:35, 5F
→
02/16 06:36, 5年前 , 6F
那個人履歷蠻漂亮的 電機出身+待過微軟開發過VS前期
02/16 06:36, 6F
→
02/16 06:36, 5年前 , 7F
看他講話好像連基本的計算機原理和演算法數學都不懂
02/16 06:36, 7F
→
02/16 06:37, 5年前 , 8F
連我以前當助教的學生都可以電爆他了XD
02/16 06:37, 8F
推
02/16 06:41, 5年前 , 9F
講錯了 不是開根號 是次方問題
02/16 06:41, 9F
推
02/16 06:47, 5年前 , 10F
然後O(n)裡的n 一種是編碼長度 一種是input數量
02/16 06:47, 10F
→
02/16 06:49, 5年前 , 11F
因為是編碼長度問題 所以實際上是O(lgn)
02/16 06:49, 11F
推
02/16 06:52, 5年前 , 12F
不過說不定原作者是想表達C++有編譯時期運算技術
02/16 06:52, 12F
→
02/16 06:52, 5年前 , 13F
所以不管n多大C++都會在編譯時期算好
02/16 06:52, 13F
→
02/16 06:52, 5年前 , 14F
所以run-time是O(1)wwwwwwwwww
02/16 06:52, 14F
推
02/16 07:02, 5年前 , 15F
02/16 07:02, 15F
推
02/16 08:57, 5年前 , 16F
神奇給推！
02/16 08:57, 16F
→
02/16 08:57, 5年前 , 17F
已經跟地球月球時間無關 而是根本上錯誤
02/16 08:57, 17F
推
02/16 11:55, 5年前 , 18F
真有趣~~
02/16 11:55, 18F
推
02/16 12:44, 5年前 , 19F
Vtuber compiler XD
02/16 12:44, 19F
推
02/16 20:02, 5年前 , 20F
以編碼長度來看，也不會是O(lg n)
02/16 20:02, 20F
→
02/17 14:45, 5年前 , 21F
我是不是錯過了什麼新聞？ 求費氏數列的討論串 pAq
02/17 14:45, 21F
推
02/17 16:26, 5年前 , 22F
02/17 16:26, 22F
→
02/17 17:14, 5年前 , 23F
ㄟ 這是兩件事 1. O(logN) 是因為乘法有快速乘法logN
02/17 17:14, 23F
→
02/17 17:16, 5年前 , 24F
2. turing machine來看編碼長度確實是logN
02/17 17:16, 24F
→
02/17 17:17, 5年前 , 25F
然後巧合的是剛好這兩件事可以掛勾在一起
02/17 17:17, 25F
推
02/17 17:20, 5年前 , 26F
這個討論串居很無聊，居然這麼多人關注。
02/17 17:20, 26F
推
02/17 20:02, 5年前 , 27F
樓上的兩個 logN 是不同 N 吧?
02/17 20:02, 27F
→
02/17 20:02, 5年前 , 28F
你的"快速乘法"的 log N 的 N 是編碼長度
02/17 20:02, 28F
→
02/17 20:03, 5年前 , 29F
turing machine 編碼的 logN 的 N 是數值本身
02/17 20:03, 29F
推
02/17 20:19, 5年前 , 30F
Fabonacci(X) 這個是編碼長度logX 所以放在tap上是logX
02/17 20:19, 30F
→
02/17 20:20, 5年前 , 31F
然後公式解是一個const連乘X次
02/17 20:20, 31F
→
02/17 20:21, 5年前 , 32F
因為有快速乘法所以時間是logX
02/17 20:21, 32F
→
02/17 20:21, 5年前 , 33F
這題只是剛好快速乘法的行為跟二進為編碼直接有相關
02/17 20:21, 33F
推
02/17 20:24, 5年前 , 34F
1000 是四位數編碼 100是三位數編碼 10是兩位數編碼
02/17 20:24, 34F
→
02/17 20:24, 5年前 , 35F
放在tap上長度本來就是logN
02/17 20:24, 35F
推
02/17 21:32, 5年前 , 36F
所以正確來說編碼長度N的費氏數列時間複雜度O(N)
02/17 21:32, 36F
推
02/17 22:36, 5年前 , 37F
前面可能我表達不好 這個應該沒爭議了吧
02/17 22:36, 37F
推
02/18 02:33, 5年前 , 38F
O(N)次乘法, 但是乘法的時間不一定是O(1), 看你要怎
02/18 02:33, 38F
→
02/18 02:33, 5年前 , 39F
麼算
02/18 02:33, 39F
→
02/18 02:34, 5年前 , 40F
算出沒誤差的精確值至少是O(2^N), 因為答案本身就有
02/18 02:34, 40F
→
02/18 02:34, 5年前 , 41F
O(2^N)bit了
02/18 02:34, 41F
推
02/18 02:53, 5年前 , 42F
啊..修正一下, 底不確定是不是2, 但總之是指數級成長
02/18 02:53, 42F
→
02/18 03:13, 5年前 , 43F
怎麼推文都在回討論串？本文重心是編譯器優化遞迴f(i)成i吧
02/18 03:13, 43F
推
02/18 03:15, 5年前 , 44F
有趣給推
02/18 03:15, 44F
→
02/18 13:04, 5年前 , 45F
請問Higana，這是在哪個社團，那麼有趣 XD
02/18 13:04, 45F
推
02/18 14:42, 5年前 , 46F
樓上 Python台灣
02/18 14:42, 46F
推
02/20 01:44, 5年前 , 47F
是的 但該篇他老早就刪了 剩一些後續討論這樣
02/20 01:44, 47F
‣ 更多 johnjohnlin 的文章
文章代碼(AID): #1SPktjE2 (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 johnjohnlin 的文章
文章代碼(AID): #1SPktjE2 (C_and_CPP)