12 ms·

I think it should be noted here that this only ranks garbage hands and flushes. Quad 2's is certainly worth more than 3 Ace's yet 2^4 < 41^3. Edit: I missed >

I think it should be noted here that this only ranks garbage hands and flushes. Quad 2's is certainly worth more than 3 Ace's yet 2^4 < 41^3. Edit: I missed >>> rank them against each other in a lookup table I'm just confused about the prime factors thing now. Why not just hash the hand itself? "3459To" where o stands for off suit?

gopalv 9y ago
> Why not just hash the hand itself? "3459To" where o stands for off suit? Permutable hashes - you could just sort them and hash again, but the prime multiply hashing is pretty neat way of mapping all items in any order to the same hash code.
- _asummers 9y ago
  Exactly. Leverages the fundamental theorem of arithmetic, that the product of primes is unique modulo permutations.
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 ago
  That 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 ago
    The 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 ago
      Yea, 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.

gopalv 9y ago

> Why not just hash the hand itself? "3459To" where o stands for off suit? Permutable hashes - you could just sort them and hash again, but the prime multiply hashing is pretty neat way of mapping all items in any order to the same hash code.

_asummers 9y ago
Exactly. Leverages the fundamental theorem of arithmetic, that the product of primes is unique modulo permutations.

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 ago
That 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 ago
  The 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 ago
    Yea, 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.