Depending on what you are trying to do, great speed improvements can be achieved by "entropic sampling"/"importance sampling", where mircocanonical phase states are visited with a propability, which is inverse proportional to the density of states. There is a large literature on this topic, for example:
http://en.wikipedia.org/wiki/Importance_sampling http://www.cms.tuwien.ac.at/media/pdf/publications/PRE_71_066705_2005.pdf http://hrma.physics.sjtu.edu.cn/SimulationPhysics/PRL02050.pdf
Olaf