4 ms·
Because 3459T is equivalent to 345T9 and 34T59 and all the other permutations. You need to either hash all the permutations (making your lookup table 5! times
by T-hawk 9y ago
Because 3459T is equivalent to 345T9 and 34T59 and all the other permutations.
You need to either hash all the permutations (making your lookup table 5! times bigger) or sort the hand by card value. It is faster to multiply the 5 prime factors in linear time rather than the N log N of sorting.
- deleted 9y ago[deleted]
- hervature 9y agoThat makes sense. I was making the assumption that hands are given in order. For example, when generating all hands, your inner loops only start at the current index of the parent loop.
- T-hawk 9y agoThe purpose isn't to generate the ranking list. The purpose is to evaluate hands. The list is a one-time cost however you make it, but evaluating the randomly dealt cards would have the ongoing cost of sorting every time if not for the prime-factors trick.
- hervature 9y agoYea, I guess I'm not convinced that the prime-factors is faster than sorting. Sure, linear time for prime multiplication, but you still have to look up the prime number in a lookup. The question comes down to what the coefficient is in front of N for prime factor method and in front of N log N for sorting. As N=5, the coefficient ratio is pretty small to still warrant using sorting. Also, using Radix sorting makes things even more fuzzy.