The Fastest way to sort 3 values
Yesterday I was surfing the web looking for some optimized C++ code to sort 3 numbers. Here is an excerpt from the first page returned by Google.
The problem of sorting 3 numbers can be described as follow
| a < b | a < c | b < c | a < b < c here, sorted!!! |
| a < c <= b here, sorted | |||
| c <= a < b here, sorted!!! | |||
| b < c | a < c | b <= a < c here, sorted!!! | |
| b < c <= a here, sorted!!! | |||
| c <= b <= a here, sorted!!! | |||
A binary tree is used to reach the solution.
This leads to the following code:
! ------------------------------------------------------- ! This program reads in three INTEGERs and displays them ! in ascending order. ! ------------------------------------------------------- PROGRAM Order IMPLICIT NONE INTEGER :: a, b, c READ(*,*) a, b, c IF (a < b) THEN ! a < b here IF (a < c) THEN ! a < c : a the smallest IF (b < c) THEN ! b < c : a < b < c WRITE(*,*) a, b, c ELSE ! c <= b : a < c <= b WRITE(*,*) a, c, b END IF ELSE ! a >= c : c <= a < b WRITE(*,*) c, a, b END IF ELSE ! b <= a here IF (b < c) THEN ! b < c : b the smallest IF (a < c) THEN ! a < c : b <= a < c WRITE(*,*) b, a, c ELSE ! a >= c : b < c <= a WRITE(*,*) b, c, a END IF ELSE ! c <= b : c <= b <= a WRITE(*,*) c, b, a END IF END IF END PROGRAM Order
Another guy suggested that this solution is too complicated and proposed:
int a, b, c; #define swap(x, y) do {int tmp; tmp = x; x = y; y = tmp; } while (0) if (b < a) swap(b, a); if (c < b) swap(c, b); if (b < a) swap(b, a);
This can also be easly extended to 4 numbers :
if (b < a) swap(b, a); if (c < b) swap(c, b); if (d < c) swap(d, c); if (b < a) swap(b, a); if (c < b) swap(c, b); if (b < a) swap(b, a);
This program is nothing less than bubble sort. It can be generated with the following program:
main() for (i = 0; i < n - 1; i++) for (j = 0; j < n - 1 - i; j++) printf("if (%c < %c) swap(%c, %c);\n", 'a' + j + 1, 'a' + j, 'a' + j + 1, 'a' + j); }
This code may be easier to write but it is slower, I have compared the easy solution (with swaps form bubble sort) with the more complicated one that uses a binary tree.
Sorting 10′000′000 3 numbers buckets took 187ms with the bubble sort, 158mswith binary tree. I coded a in place version of a 3 numbers sort function.
Here is the fastest code I know to sort in place 3 numbers:
void sort3(double * a) { double temp; if (a[0]<a[1]){ if (a[0]<a[2]){ if (a[1]<a[2]){ // 012 } else { // 021 temp=a[0]; a[1]=a[2]; a[2]=a[1]; a[0]=temp; } } else { // 201 temp=a[0]; a[0]=a[2]; a[2]=a[1]; a[1]=temp; } } else { if (a[0]<a[2]){ // 102 temp=a[0]; a[0]=a[1]; a[1]=temp; } else { if (a[1]<a[2]){ // 120 temp=a[0]; a[0]=a[1]; a[1]=a[2]; a[2]=temp; } else { // 210 temp=a[0]; a[0]=a[2]; a[2]=temp; } } } }
Notice that there is no swap macros. Swaps are optimized avoiding to copy the temp value when is not necessary. So now I have to propose you some interesting challenge.
Can this be called the “QuickestSort algorithm” ?
Can you find or code something faster? Let me know.
And can you figure out what is the fastest way to sort 4 numbers?
keep in touch with blog and you will see how.
Popularity: 2% [?]
Poker Predictor: a Free Texas Hold’em Odds and Probability Computer
Contents
The finest poker brains on your side!
In real life poker games many factors affects the game. A good poker player has to study facial expression, breath frequency, hands movements etc. In online games you have no opponent to look in the eyes, the math behind poker takes a leading role to gain an edge against others players. To become a good online poker player you have to know at least some basic poker theory.
First of all I want to say something about the relationship between math and poker. Poker is a cards game, this means luck counts, you wont win all the matches if you know all the odds and if you are a great bluffer. To win, you also have to be a little luck and, fortunately, poker is still an human game, experience and skills are important too.
But what is important is to acquire a good gaming style that allows you to play correctly every time. It does not mind if you play correctly and you still loose. You may loose this game but you’ll see that on a large numbers of matches the edge you have against your opponent will turn into money.
Now how to acquire a mathematically correct good gaming style?
There are two options:
- You can study all the odds, read a thousand of poker game theory, make some quite complex calculations in your head each time a card falls on the table.
- You can Download Poker Predictor
What can Poker Predictor Do
Texas holdem poker is about:
- 2+5 cards each player
- 52 total number of cards
- 1326 starting hand configurations
- 207025 distinct head-to-head match ups
- 1712304 possible boards
- 690900 hands configurations with a single opponent
- over 6.22 e26 with 9 opponents
- ……………..
All of them are in Poker Predictor
Poker Predictor is a tool to calculate poker games probabilities from whatever cards configuration. Probability are computed with random cards permutation, they are not the exact ones but the high simulations numbers ensure the error to be less than 1%.
Thanks to his strong computational engine, It can simulate 100′000 10 players Texas hold’em games in a matters of 0.3 seconds, so it is actually a real time tool, very useful for on line games, especially with high level players. It is possible to choose both players and opponents cards.
Although a little rough in the graphics (I am not a software developer, neither a programmer, just an engineer with poker passion) Poker predictor is a powerful tool, I am myself using it.
Parameters computed by poker predictor
OnLine Help for Poker Predictor
Downloads
Release History:
| Poker Predictor v1.0
(24/02/2010) Download for Win 32 |
|
| Poker Predictor v1.1
(09/03/2010) Download for Windows
|
|
This version is completely free. You can remove the ads on them with a 5 euros contribution to the project:
donations will be used to enlarge this utility
Poker Predictor was developed for Matlab at the beginning here you can find the matlab version: Matlab version of Poker Predictor
Poker predictor is always under development. Any question/suggestion? giaccariluigi@msn.com
Popularity: 5% [?]
Poker Predictor: How to Use it
Contents
This page is some kind of poker predictor online help. Here you can find discussions about its game parameters. Suggestions are greatly appreciated, Poker Predictor is always under development.
Please go to Poker Predictor: How to Use it to view the survey
Profit
Each poker hand is just like an investment: you can loose the money you invest or you can make more money out of them. We need a parameter to know whether our cards are supposed to be a good investments or not.
Profit express the gain of money, or chips, you are expecting from the game. Basically are worth playing pre -flop cards with positive profit. This in the hypothesis you go to river all the hands. Obviously this is untrue. So you have to act like a “smart” player: if the game is very hard, full of rising players, you can play all hands with 10% (as example) profit, so you have more chance to “resist” to your opponents shoots. On the others side, if you meet soft players that always fold, even with low raises, you can play cards with negative profit (for example-10%)
Profit also take into account number of players,folds, Odds. For example folds decrease profit, since there will be less money on the pot. This may seems strange but it is true, folds increase your winning chance but actually decrease your capability to earn money.
Consider Profit is an instantaneous parameter which depends on the current cards configuration. There is also the profit of the entire game considering previous moves, but calculating this requires the history of the game and it is not supported.
Player and opponent higher rank
I suppose this need no explanation.
Winning chance
Probability to win after river. Notice that the probability suppose you go on until river card falls.
Tie chance
probability to tie after river.
Odds
the odds bookmakers would give to your game. When is odds useful? First of all, odds take into account both winning and tie chance. Ties are considered only partially because in that case the pot is divided among all the winners.
If the game is completely random, odds equal the number of players, this means every players has the same winning chance. So if odds overcomes players number this means your cards are worse than usual. On the other side if your odds is lower than the number of players your cards are good.
Odds are generally more useful than the winning chance. Let’s make an example: you have 30% of winning. Is that good?
The right answer id I don’t know, it depends on the number of players. If there are only two players 30% is bad winning chance but if we are 12 players of course is good. How do I find the limit? what is the number of players for which 30% winning is a good chance?
Well, you don’t have to get tired everytime on this computation, you can bypass them just by looking the odds number: is lower than the player number than is good, is higher than is bad. Odds and winning chance are just two different ways to estimate how strong are your cards.
If you have zero winning chance your odds equals infinity, bookmakers will pay a lot of money in case you win, but this just because you can not win. If odd equals one you are sure to win. The lower is the Odds the higher are you’re winning chance.
MaxBet/Pot
This is the answer to question call/fold when an opponent make raise. This is max bet, compared with the pot, you can do remaining in the mathematical correctness of the game. This means that if you can afford to bet the 30% of the pot you can call any raise which respect this condition. If this parameter overlaps 100% you can bet all the pot, you have more than 50% of winning and you are (theoretically) allowed to go all in, it is you or your opponent. Generally listening to this data carefully lead to run too much risk, the all in in poker may be without return !
What I suggest is to find to find a good feeling with the values of this parameter that fits your gaming style.
Consider that the pot you see when you call may increase during the game, this can not be calculated by the program, expert players must also consider this factor.
Any questions, suggestions?
Popularity: 3% [?]
GLTree Pro Version: a fast nearest neighbour library for Matlab and C++
Filed under: Algorithms, Computational Geometry, Geometry, Graphics
Contents
Introduction
The nearest neighbor search problem arises in numerous fields of application, including:
- Pattern recognition – in particular for optical character recognition
- Statistical classification- see k-nearest neighbor algorithm
- Computer vision
- Databases – e.g. content-based image retrieval
- Coding theory – see maximum likelihood decoding
- Data compression – see MPEG-2 standard
- Recommendation systems
- Internet marketing - see contextual advertising and behavioral targeting
- DNA sequencing
- Spell checking - suggesting correct spelling
- Plagiarism detection
- Contact searching algorithms in FEA
- Similarity scores for predicting career paths of professional athletes.
- Cluster analysis – assignment of a set of observations into subsets (called clusters) so that observations in the same cluster are similar in some sense, usually based on Euclidean distance
The algorithm
The reason that pushed me to develop this algorithm was the need of more speed in nearest neighbors search. The first implementation of GLTree was coded in the September 2008, and a first, rough, but very fast version was uploaded on Matlab File Exchange as C++ code to compile into MEX file in November. These version are still available and open-source:
After using this library for about a year I released the potential and I decided to make a step further. In this page a faster and low memory version is proposed. Many more functions have been developed like: a nearest neighbour filter radius search and a cuboid search and many more can be developed.
Perfomances
This are the timings for a NNGraph in 2D and 3D on my 2.4Ghz laptop. Test is run on uniform randomly points in 0-1 range. Given a set of N random points, for each one finds his nearest neighbour.
START NNGraph Test: 2D NNGraph of 10 points took: 0.0001 s NNGraph of 100 points took: 0.0001 s NNGraph of 1000 points took: 0.0004 s NNGraph of 10000 points took: 0.0039 s NNGraph of 100000 points took: 0.0629 s NNGraph of 1000000 points took: 1.1897 s 3D NNGraph of 10 points took: 0.0014 s NNGraph of 100 points took: 0.0001 s NNGraph of 1000 points took: 0.0007 s NNGraph of 10000 points took: 0.0075 s NNGraph of 100000 points took: 0.1219 s NNGraph of 1000000 points took: 2.4760 s TEST SUCCESFULLY COMPLETED !!!
You can run this test by downloading the demo version (linux and win32):
Download GLTreePro Demo
For very sparse data, like logspace data, GLTree becomes slower. It may be convenient using others algorithm. For more see this post:
A comparison of GLTree with Kd-Tree and Bd-Tree
Release
- 15/02/2010 GLTreePro_v1.0
Matlab
This release includes the following MEX files:
- 2D
- K-Nearest Neighbor Search
- K-Nearest Neighbour Graph
- Nearest Neighbour Filter
- Radius Search
- Cuboid Search
- BuildTree
- DeleteTree
- 3D
- K-Nearest Neighbor Search
- K-Nearest Neigbour Graph
- Nearest Neighbour Filter
- Radius Search
- Cuboid Search
- BuildTree
- DeleteTree
We support Win32 and Linux platform. Source code is currently not supported. The package includes all the MEX files plus .m files for the help command.
| Version | Minimum Support amount |
| 2D | 10 euro |
| 3D | 10 euro |
| 2D&3D | 15 euro |
or on the following bank account:
| Name | Luigi Giaccari |
| IBAN | IT 07 E05550 77710 000000483947 |
Please e-mail at: giaccariluigi@msn.com after the donation. You will soon receive the latest version of the GLTree library and all following updates.
C++
Under Construction. You need it? tell me and I may speed up the development.
Examples
See the examples for 2D:
Popularity: 2% [?]
GLTree Matlab Example: Nearest Neighbor Filter Function
Filed under: Algorithms, Computational Geometry, Optimization
KNNSearch2D query a GL-tree for k nearest neighbor(kNN)
SYNTAX
[cutdist,ndel,idel]=KNNFilter2D(p,ptrtree,’r',r);% radius mode
[cutdist,ndel,idel]=KNNFilter2D(p,ptrtree,’f',f);% consolidator mode
INPUT PARAMETERS
- p: [2xN] double array coordinates of reference points
- ptrtree: a pointer to the previously constructed GLtree.Warning if the pointer is incorrect it will cause a crash, there is no way to check this in the mex routine, you have to check it in your script.
- ‘r’ or ‘f’: string. Specify the RADIUS mode or the CONSOLIDATOR mode.
- r or f: double parameter for the mode.
OUTPUT PARAMETERS
- cutdist: in the dataset no couple of points will be closer than cutdist. In the radius mode cutdist==radius.
- ndel: number of points removed from the tree
- iddel: ids of points removed from the tree
GENERAL INFORMATIONS
- -RADIUS mode: if 2 points are closer than r only one will survive.
- -CONSOLIDATOR mode: the nearest neighbour graph is computed and the mean distance between points is evaluated. The cutdistance is set to meandist/f.
- -points removed form the tree are not physically deleted (memory deaollocated), they are just skipped during search.
For question, suggestion, bug reports
giaccariluigi@msn.com
Author: Luigi Giaccari
N=300;%reference points Cuboid=[.2 ,.5 ,.2 ,.5 ]'; p=rand(N,2);%reference points fprintf('RANDOM POINTS GENERATED\n\n') fprintf('BUILDING THE DATA STRUCTURE:\n') tic ptrtree=BuildGLTree2D(p'); fprintf('\tGLTree built in %4.4f s\n\treturned pointer %4.0f:\n\n',toc,ptrtree); fprintf('START FILTER:\n') tic [idc]=CuboidSearch2D(p',Cuboid,ptrtree); fprintf('\t %4.0f Points found in range\n\n',length(idc)); fprintf('DELETING THE TREE\n\n') DeleteGLTree2D(ptrtree); fprintf('TEST SUCCESFULLY COMPLETED !!!\n\n') %plot the NNG figure(1) title('Cuboid Search','fontsize',14); axis equal hold on x=[Cuboid(1),Cuboid(1),Cuboid(2),Cuboid(2),Cuboid(1)]; y=[Cuboid(3),Cuboid(4),Cuboid(4),Cuboid(3),Cuboid(3)]; h1=plot(p(:,1),p(:,2),'g.'); h2=plot(x,y,'b-'); h3=plot(p(idc,1),p(idc,2),'r.'); legend([h1,h2,h3],'Reference points','Cuboid','Inside points');
RESULTS
Points inside the cut radius are found
And deleted..
Go to main post
Popularity: 2% [?]
Translator
By N2H Follow Us
Video Posts
-
