作者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