作者of (開心的過每一天~)
看板EE_DSnP
標題[請益] hash function
時間Mon Jun 29 23:29:07 2009
雖然放暑假了 不過我還是很好奇
我用的hash function是
key = add_bddl ^ (add_bddr>>2) + level
我改成上面那個之後效能比我原本用的
key = 800*add_bddl +1000*add_bddr + 500*level
整整快了一倍
連cache一起改了之後就變成四倍了@@
可是跟老師的一比較之後就一整個輸很大~~~
我查了一下似乎是當hash function可以讓hash幾乎成為cache時會達到最佳化
也就是投影片說的最平均分配的hash
不知道老師是用了什麼祕方可以讓BDD跑這麼快呢@@?
還是有人寫出比老師快的可以分享一下嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.33.163
1F：推 ric2k1:你有用 -O3 嗎.... XD 06/29 23:37
2F：推 ptt6161180:.....||| 06/29 23:51
3F：→ ptt6161180:開外掛啦= = 06/29 23:51
4F：→ of:呃...我是有想到要用O3拉...只是我沒有想到老師的有用orz 06/29 23:53
5F：→ of:難怪我dfs跟rdfs跑不出來... 06/29 23:53
6F：→ of:不過我還是很好奇 到底有沒有什麼解最佳hash function的方法 06/29 23:54
7F：推 suzuki1207:好奇+1 我直接相加起來再shift... 06/29 23:57
8F：推 Peter034:我用(_left<<3) + (_right) + _level 跟老師速度幾乎相同 06/30 01:10
9F：→ of:看來O3才是真正的速度關鍵阿= =+ 06/30 01:57