Terms & Conditions

Internet Magazine

Non–US new players
Get five 2+2 books

Order Books
Book Translations

Expand All   Collapse All

Forum Archives

## The 2+2 Forums

Before using this Forum, please refer to the Terms and Conditions (Last modified: 2/26/2006)

Be sure to read the   Two Plus Two Internet Magazine

This is an archive. The main forums are here

These forums are read only.

 You are not logged in. [Login] Main Index · Search · Classified Ads New user · Who's Online · FAQ · Calendar

Internet Gambling >> Software
 Previous Index Next Flat

jukofyork
Carpal \'Tunnel

Reged: 09/16/04
Posts: 2551
Loc: Leeds, UK.
Re: 279Mill a second.....
12/28/06 05:25 PM

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;

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);

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

 Post Extras

Extra information
0 registered and 30 anonymous users are browsing this forum.

Moderator:  SamIAm, Mike Haven

Forum Permissions
You cannot start new topics
You cannot reply to topics
HTML is disabled
UBBCode is enabled

Rating: