[問題] For迴圈 和 array 執行速度問題

看板C_and_CPP作者 (SaoAn)時間14年前 (2010/10/23 14:44), 編輯推噓13(13043)
留言56則, 18人參與, 最新討論串1/4 (看更多)
大家好 小弟我有些觀念不是很清楚想請教大家 1. for(i=0;i<m;i++) for(j=0;j<n;j++) { //do something } 2. for(i=0;i<m*n;i++) { //do something } 有個同學跟我說2跑的會比1快,請問這是為什麼呢? 不是都是跑了m*n次? 另外還有個類似的問題 3. for(i=0;i<m;i++) for(j=0;j<n;j++) { array_2D[i][j]=some operation; } 4. for(i=0;i<m;i++) for(j=0;j<n;j++) { array_1D[i*m+j]=some operation; } 那個同學又跟我說4比3快,但是大小一樣,只有2D跟1D的差別,請問他說的是對的嗎? 我原以為速度上1=2, 3=4, 但是被他這麼一說我有點被搞混了 煩請各位解答 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 24.161.183.254

10/23 22:46, , 1F
你同學是超人嗎?居然可以測到誰快誰慢>"<
10/23 22:46, 1F

10/23 22:51, , 2F
其實這不是很重要,別太瞧不起編譯器的最佳化了....XDD
10/23 22:51, 2F

10/23 22:53, , 3F
3跟4可以選時,用4會被同事公幹。
10/23 22:53, 3F

10/23 22:54, , 4F
3和4一樣 = =
10/23 22:54, 4F

10/23 22:55, , 5F
比這沒意義 big O都一樣 沒差~ 把你的演算法學好比較重要
10/23 22:55, 5F

10/23 23:04, , 6F
你同學想讓你以為他很厲害
10/23 23:04, 6F

10/23 23:09, , 7F
我一直以為是2跟4會比較慢耶,因為有多做乘法??
10/23 23:09, 7F

10/23 23:12, , 8F
我也覺得24比較快~
10/23 23:12, 8F

10/23 23:13, , 9F
不過編譯器最佳化應該差不多太多吧
10/23 23:13, 9F

10/23 23:20, , 10F
如果m、n的值在編譯時期已知, 那麼兩個可以說一樣快,
10/23 23:20, 10F

10/23 23:20, , 11F
直接寫程式測量一下時間,一定比聽別人說正確
10/23 23:20, 11F

10/23 23:21, , 12F
在迴圈的執行過程 m、n的值如果有變動到, 那麼第二個
10/23 23:21, 12F

10/23 23:22, , 13F
個迴圈每次都做乘法我猜是會比較慢, 因為想不到例子來
10/23 23:22, 13F

10/23 23:23, , 14F
測...XD 不過現在這個時代, 你應該先把程式碼寫的愈清
10/23 23:23, 14F

10/23 23:23, , 15F
楚愈好, 這樣要加速才有辦法改得快又不改錯
10/23 23:23, 15F

10/23 23:24, , 16F
我覺得寫程式先求快的人根本是...
10/23 23:24, 16F

10/23 23:31, , 17F
基本上2的確會比1快 這是computer architecture的議題
10/23 23:31, 17F

10/23 23:32, , 18F
4也會比3快
10/23 23:32, 18F

10/23 23:40, , 19F
2比1快吧 我覺得寫的時候 有新增 呼叫副函式跟大量計算
10/23 23:40, 19F

10/23 23:41, , 20F
的時候 寫兩個迴圈的速度整個就差很多
10/23 23:41, 20F

10/23 23:44, , 21F
m、n 的值改變沒辦法做cache, 2 還有辦法比較快?
10/23 23:44, 21F

10/23 23:45, , 22F
1,2的明顯差別是會少了一個判斷 不過差距會很大嗎?
10/23 23:45, 22F

10/23 23:51, , 23F
loop裡設 null, vc2008 2010 測十次,結果會飄耶..
10/23 23:51, 23F

10/23 23:51, , 24F
有時1比較快,有時2比較快,有時一樣快.GetTickCount測
10/23 23:51, 24F

10/23 23:55, , 25F
眾說紛紜 冏 越來越糊塗了
10/23 23:55, 25F

10/23 23:59, , 26F
其實這真的不是一個很重要的問題
10/23 23:59, 26F

10/24 00:02, , 27F
同樓上, 你應該花時間在其他層面
10/24 00:02, 27F

10/24 00:05, , 28F
目前為止沒聽說過在Windows跑得哪個套裝軟體,是靠改這個
10/24 00:05, 28F

10/24 00:05, , 29F
來最佳化改善速度的...從這你就知道這又多不重要
10/24 00:05, 29F

10/24 00:05, , 30F
...這有多不重要
10/24 00:05, 30F

10/24 00:10, , 31F
好吧 感謝各位
10/24 00:10, 31F

10/24 00:26, , 33F
真的想了解,看編譯器編出來的組語長怎樣,一切真相大白
10/24 00:26, 33F

10/24 00:30, , 34F
不過指令數量也不代表執行時間 因此也很難講...XD
10/24 00:30, 34F

10/24 00:30, , 35F
不過跑一個迴圈多幾行組語指令,當迴圈執行的內容很多時
10/24 00:30, 35F

10/24 00:31, , 36F
這幾行的影響完全可以忽略掉
10/24 00:31, 36F

10/24 00:38, , 37F
樓上說的簡單講就是複雜度的意義...
10/24 00:38, 37F

10/24 00:41, , 38F
這使我想到安德定理..(使常出現部份變快 XD)
10/24 00:41, 38F

10/24 00:42, , 39F
測不準原理
10/24 00:42, 39F

10/24 00:48, , 40F
大部份程式花時間的都是迴圈內容,而不是i<x i++這些
10/24 00:48, 40F

10/24 00:52, , 41F
大部份程式都花時間在Message Loop
10/24 00:52, 41F

10/24 00:53, , 42F
可是我覺得 while(cin>>line) count++; 不是耶
10/24 00:53, 42F

10/24 00:55, , 43F
我只知道,程式設計師大部份時間花在上網
10/24 00:55, 43F

10/24 00:56, , 44F
大部份宅男花時間的都是動漫內容,而不是____這些
10/24 00:56, 44F

10/24 00:57, , 45F
我認為大部分時間都在寫文件...文件真的很靠北
10/24 00:57, 45F

10/24 01:55, , 46F
james 是對的,這些差異有可能被 compiler 吸收掉 XD
10/24 01:55, 46F

10/24 02:17, , 47F
Those're correct for some observations. However, as a
10/24 02:17, 47F

10/24 02:19, , 48F
language, effectiveness is not primitive in C syntax.
10/24 02:19, 48F

10/24 02:20, , 49F
In general, it's useless when analyzing algorithms.
10/24 02:20, 49F

10/24 08:57, , 50F
你可以用loop-unroll消掉一些jmp
10/24 08:57, 50F

10/24 13:31, , 51F
complier會做好一切~~gcc太強了~
10/24 13:31, 51F

10/24 14:48, , 52F
有聽過一種講法,編譯沒優化情況下,case #1表示有很多子迴圈
10/24 14:48, 52F

10/24 14:50, , 53F
會讓作業系統用分頁處理,多作一點分頁的命中判斷.而且因此
10/24 14:50, 53F

10/24 14:51, , 54F
如果寫column-major的迴圈,又會比現在row-major更耗時.
10/24 14:51, 54F

10/24 15:30, , 55F
branch predictor
10/24 15:30, 55F

10/25 16:16, , 56F
推樓上 越多分支判斷會比較慢
10/25 16:16, 56F
文章代碼(AID): #1CmlJMLk (C_and_CPP)
討論串 (同標題文章)
文章代碼(AID): #1CmlJMLk (C_and_CPP)