※ 引述《sealoe@kkcity.com.tw ()》之銘言：
: ※ 引述《DungeonFan》之銘言：
: > 這是多講的。
: > 如果拿同一個algorithm來實做，千萬不可小看那50%~的改善。
: > 真正的問題是..一般人別說algorithm，連程式本身的效率
: > 都不會。-_-
: 可以舉個例子嗎?
: 可以和 "課本" 內列出的演算法效率差很多的
: 我不要說50% 我只想問問 10%的有沒有
: 很多新演算法的改良處不過是常數的部份
: 你要是能夠提出如你所說的方法 我想IEEE一定有數篇你的大作
: 如果你說的會 不過是查查課本 照本宣科
: 那樣, 我只能說少以管窺天 多多學習才是比較重要的
他的意思是說, 同樣的 algorithm 以不同 coding 方式寫出來效率可能差很多.
隨便舉個例子, Discrete Cosine Trasform 講求的是最少的加法跟乘法.
縱使在 algorithm 上把加法跟乘法的數目壓到最低, 最重要的還是查表.
table-lookup 這種 coding 技巧在 algorithm 課本上是不會敎的.
還有一些是搞組語或 SIMD 時該知道的東西.
比如說 MOVQ 在 Pentium 4 上要 6 cycles, PSHUFW 只要 2cycles.
movq mm1, mm2 不如寫成 pshufw mm1, mm2, 0xe4
又如 MMX 上並沒有 PAVGB 這個兩點平均指令 (motion compensation 常用)
然而我們知道 (x + y + 1)>>1 = (x OR y) - (x XOR y)>>1, 因此
#define _m_pavgb_mmx(m1, m2) \
_m_psubb(_m_por(m1, m2), _m_psrlqi(_m_pand(_m_pxor(m1, m2), \
_mm_set1_pi8((char)0xfe)), 1))
這也是屬於 coding 技巧的一種, 程式寫久了有感覺才比較能想出這種東西.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.85.8.143