7 Card Hand Evaluators

[jukofyork]

[ QUOTE ]
I'll be honest guys, I'm incredibly dissapointed! I thought I had something near optimum, but I must be missing something obvious! My meak 15 million per second is not much compared to your dozens of millions!

Anyway, incase any of you are interested, this is the best way to sort 7 cards. Please note, this sort algorithm I wrote beats all the classic sorting algorithms (quick sort, merge, insertion, std::Sort). It's basically a precomputed LUT for a pigeonhole sort.

// Represent the hand
sevenCardHand = ((__int64)1 << c1) | ((__int64)1 << c2) | ((__int64)1 << c3) | ((__int64)1 << c4) | ((__int64)1 << c5) | ((__int64)1 << c6) | ((__int64)1 << c7);

// Split 64 bit int into 4 chunks of 16 bits
firstChunk = (sevenCardHand & 0xFFFF);
secondChunk = (sevenCardHand & 0xFFFF0000) >> 16;
thirdChunk = (sevenCardHand & 0xFFFF00000000) >> 32;
fourthChunk = (sevenCardHand & 0xFFFF000000000000) >> 48;

// Reset pointer to sorted hand array
sortedPointer = 0;

// Retrieve records
numToLoop = intToIndexArr_L1[firstChunk][0];
for(anotherCounter = 1; anotherCounter < numToLoop; anotherCounter++)
sortedHand[sortedPointer++] = intToIndexArr_L1[firstChunk][anotherCounter];

numToLoop = intToIndexArr_L1[secondChunk][0];
for(anotherCounter = 1; anotherCounter < numToLoop; anotherCounter++)
sortedHand[sortedPointer++] = intToIndexArr_L1[secondChunk][anotherCounter] + 16;

numToLoop = intToIndexArr_L1[thirdChunk][0];
for(anotherCounter = 1; anotherCounter < numToLoop; anotherCounter++)
sortedHand[sortedPointer++] = intToIndexArr_L1[thirdChunk][anotherCounter] + 32;

numToLoop = intToIndexArr_L1[fourthChunk][0];
for(anotherCounter = 1; anotherCounter < numToLoop; anotherCounter++)
sortedHand[sortedPointer++] = intToIndexArr_L1[fourthChunk][anotherCounter] + 48;

[/ QUOTE ]
There seems to be alot of dereferences and increments in the above method (ie: even though pigeonhole sort is O(n) there are alot of constant factors to be added for such a small n...).

Have you compared it to a hard compiled Sorting Network, eg:

[ QUOTE ]
Network for N=7, using Bose-Nelson Algorithm:
SWAP(1, 2);
SWAP(0, 2);
SWAP(0, 1);
SWAP(3, 4);
SWAP(5, 6);
SWAP(3, 5);
SWAP(4, 6);
SWAP(4, 5);
SWAP(0, 4);
SWAP(0, 3);
SWAP(1, 5);
SWAP(2, 6);
SWAP(2, 5);
SWAP(1, 3);
SWAP(2, 4);
SWAP(2, 3);


[/ QUOTE ]

Even though it takes 16 compare and swap operations, it can actually be done in 6 parallel steps (ie: it's depth) and a modern compiler should be able to get close to this by utilizing CPU pipelines. Overall, for very small n I've always found them to be the most efficient sort in terms of CPU cycles.

Juk [img]/images/graemlins/smile.gif[/img]