Cela fait partie d'un programme qui analyse les chances de poker, en particulier Texas Hold'em. J'ai un programme que je suis content, mais il a besoin de petites optimisations pour être parfaits.
J'utilise ce type (entre autres bien sûr): P>
for C1 := 0 to 51-4 do
if (C1<>P1) and (C1<>P2) then
for C2 := C1+1 to 51-3 do
if (C2<>P1) and (C2<>P2) then
for C3 := C2+1 to 51-2 do
if (C3<>P1) and (C3<>P2) then
for C4 := C3+1 to 51-1 do
if (C4<>P1) and (C4<>P2) then
for C5 := C4+1 to 51 do
if (C5<>P1) and (C5<>P2) then
begin
//This code will be executed 2 118 760 times
inc(ComboCounter[GetComboFromCards([P1,P2,C1,C2,C3,C4,C5])]);
end;
22 Réponses :
pour un très petit ensemble, Trier d'insertion peut généralement battre QuicksTort car il a très bas frais généraux.
wrt votre édition, si vous êtes déjà surtout en ordre de tri (5 derniers éléments sont déjà triés), le tri d'insertion est définitivement la voie à suivre. Dans un ensemble de données presque trié, il battra Quicksort à chaque fois, même pour les grands ensembles. (Surtout pour les grands ensembles! Ceci est le meilleur scénario du tri d'insertion et le pire des cas de Quicksort.)
Je ne sais pas comment vous mettez en œuvre cela, mais ce que vous pouviez faire est d'avoir un tableau de 52 au lieu de 7, et insérez simplement la carte dans son emplacement directement lorsque vous l'obtenez car il ne peut jamais y avoir de duplicate, de cette façon Vous n'avez jamais besoin de trier le tableau. Cela pourrait être plus rapide en fonction de son utilisation.
En fait, cela pourrait même être un éventail de bits, ce qui conviendrait à un entier unique 64 bits et consomme moins de mémoire.
Pas vraiment. Au lieu d'essayer de regarder à travers un tableau de 7 éléments, il examinera plutôt une matrice de 52 éléments. Idem pour les bits dans un seul entier.
@Pavel a été émis: Oui, cela signifierait regarder un tableau de 52 éléments - mais ce tableau ne devra jamais être trié, vous l'obtiendrez gratuitement. C'est pourquoi j'ai dit que pourrait être plus rapide en fonction de la manière dont le code est.
Éviter le tri peut être le meilleur moyen d'accélérer le programme.
(+1) juste pour être fantaisie. La mise en œuvre de la matrice d'arbre binaire pouvant être traversée dans l'ordre peut être utilisée. en.wikipedia.org/wiki/binary_tree
@Pavel a été diffusé, le stockant comme des bits ne fera pas le tri plus vite, mais il peut s'agir d'une meilleure représentation globale pour le programme. Les opérations de bits sont généralement beaucoup plus rapides que l'accès au réseau de 7 éléments et peuvent facilement s'intégrer dans des registres de processeur. - En fait, à la deuxième pensée, il peut faire le tri plus rapide car "Trouver le premier jeu" est implémenté de manière nativement mise en œuvre sur presque n'importe quel processeur, alors créant même la matrice de bit et la reconstruction de la matrice normale pourrait être très rapide.
En réalité, si vous devez trier les 7, c'est le moyen le plus rapide, en particulier si vous savez utiliser des masques bit-bit de reculez-collecte pour effectuer la ré-collecte (réduit l'ordre de numérisation de 52 à 7 + 7). Toutefois, si 5 sont déjà triés, le plus rapide est de trier les deux autres (O (2.5)) et de faire une fusion sur les deux listes (O (K * (5 + 2)) où K est généralement d'environ 4 ou 5.
Jetez un coup d'oeil à ceci:
http://fr.wikipedia.org/wiki/sorting_algorithme
Vous auriez besoin de choisir un qui aura un pire des cas stable ...
Une autre option pourrait être de garder le tableau trier tout le temps, de sorte qu'un ajout d'une carte maintiendrait la matrice triée automatiquement, de cette façon, vous pourriez passer au tri ...
Pour 7 éléments, il n'y a que peu d'options. Vous pouvez facilement écrire un générateur qui produit une méthode pour trier toutes les combinaisons possibles de 7 éléments. Quelque chose comme cette méthode pour 3 éléments: de la méthode de sécurité pour 7 éléments sera plus gros, mais ce n'est pas si difficile à générer.
"sera plus gros". Hmm. 3! est 6, 7! est 5040.
C'est pourquoi j'ai suggéré de le générer et de ne pas écrire manuellement :-) et il utilisera toujours un nombre minimum de comparaisons et d'opérations d'échange.
... ce sera très mauvais sur le cache du processeur.
Je ne connais pas grand chose à propos du cache d'instructions du processeur pour discuter :-), mais comme vous pouvez le constater, plus profondez-vous, plus de local les sauts sont (au moins en pseudocode ;-)), alors après peu de cache manque (peu de cache 'Branches), le repos devrait être déjà mis en cache. Mais cela dépend de la manière dont le code est compilé dans les instructions.
5040 est inférieur à 2 ^ 13, vous devez donc idéalement pouvoir trouver la bonne permutation avec 13 branches binaires. Et 5040 éléments doivent facilement s'intégrer dans le cache de la CPU moderne.
Qu'est-ce que JRL fait référence à un type de seau. Puisque vous avez un ensemble fini discret de valeurs possibles, vous pouvez déclarer 52 godets et laisser tomber chaque élément dans un seau dans O (1) heure. Par conséquent, Seau Seau est o (n). Sans la garantie d'un nombre fini d'éléments différents, le tri théorique le plus rapide est O (n journal n) que des choses comme la fusion trier une trace rapide sont. C'est juste un équilibre des scénarios les mieux et les pires cas.
mais longue réponse courte, utilisez le type de godet.
Comme je l'ai déjà noté, le type de seau n'est pas O (n), mais O (n + m), où M est le nombre de valeurs que les éléments de la matrice donnés peuvent avoir. Ce n'est pas applicable dans ce cas.
La performance asymptotique est totalement non pertinente pour la question, qui fixe n à 7.
Et si vous représentez vos godets en utilisant des bits, vous avez le même tri que certaines des autres réponses ici.
Utilisez min-sorte. Recherchez des éléments minimes et maximaux à la fois et placez-les dans une matrice résultante. Répéter trois fois. (EDIT: Non, je ne vais pas essayer de mesurer la vitesse théoriquement: _))
Si vous aimez la suggestion mentionnée ci-dessus pour conserver un tableau de 52 éléments qui maintient toujours votre tableau trié, vous pouvez également conserver une autre liste de 7 éléments qui feraient référence aux 7 éléments valides de la matrice 52 éléments. De cette façon, nous pouvons même éviter d'analyser le réseau de 52 éléments.
Je suppose que pour que cela soit vraiment efficace, nous aurions besoin d'avoir un type de structure de liste lié qui prend en charge les opérations: Insérez-laposition () et Supprimer () et être efficaces à cela.
Il n'y a que 5040 permutations de 7 éléments. Vous pouvez programmer une programmation générer un programme qui trouve celui représenté par votre contribution dans un nombre minimal de comparaisons. Ce sera un gros arbre de La partie délicate est de décider des 2 éléments à comparer dans un nœud interne particulier. Pour cela, vous devez prendre en compte les résultats des comparaisons dans les nœuds ancêtres de la racine du nœud particulier (par exemple Une fois que vous avez la permutation, il est trivial de le trier dans un ensemble minimal de swaps. si-alors-ele-ele , chacun comparant une paire de nœuds fixe, par exemple si (a [3] <= a [6]) .
a [0] <= a [1], pas un [2] <= a [7] ], a [2] <= A [5] ) et l'ensemble des permutations possibles qui satisfont aux comparaisons. Comparez la paire d'éléments qui séparent le réglé en parties égales aussi égales que possible (minimisez la taille de la plus grande partie).
Le code ci-dessous est proche de Optimal. Cela pourrait être amélioré en composant une liste à parcourir tout en faisant l'arbre, mais je suis hors de temps en ce moment. Bravo!
en pseudo code: C'est une application de Seau de godet , qui devrait généralement être plus rapide que l'une des sortes de comparaison qui ont été suggérées. Remarque: La deuxième partie pourrait également être mise en œuvre en itérant sur des bits sur le temps linéaire , mais en pratique, cela peut ne pas être plus rapide:
Il y a beaucoup de boucles dans les réponses. Compte tenu de son exigence de vitesse et de la taille minuscule du jeu de données, je ne ferais pas aucune boucle .
Je n'ai pas essayé mais je soupçonne que la meilleure réponse est une tresse de bulle entièrement déroulée. Cela gagnerait probablement probablement une bonne quantité d'avantage d'être fait en montage.
Je me demande si c'est la bonne approche, cependant. Comment allez-vous analyser une main de 7 cartes ?? Je pense que vous allez finir de la convertir à une autre représentation pour analyse de toute façon. Un réseau 4x13 ne serait-il pas une représentation plus utile? (Et cela rendrait le problème de tri moot, de toute façon.)
Considérant que les 5 derniers éléments sont toujours triés:
for i := 0 to 1 do begin
j := i;
x := array[j];
while (j+1 <= 6) and (array[j+1] < x) do begin
array[j] := array[j+1];
inc(j);
end;
array[j] := X;
end;
Bubble Tri est votre ami. D'autres sortes ont trop de codes aériens et ne conviennent pas à un petit nombre d'éléments
acclamations
Étant donné que les 5 derniers éléments sont déjà triés, le code peut être écrit juste pour repositionner les 2 premiers articles. Depuis que vous utilisez Pascal, j'ai écrit et testé un algorithme de tri qui peut exécuter 2 118 760 fois dans environ 62 millisecondes.
procedure SortT7Cards(var Cards: T7Cards);
const
CardsLength = Length(Cards);
var
I, J, V: Integer;
V1, V2: Integer;
begin
// Last 5 items will always be sorted, so we want to place the first two into
// the right location.
V1 := Cards[0];
V2 := Cards[1];
if V2 < V1 then
begin
I := V1;
V1 := V2;
V2 := I;
end;
J := 0;
I := 2;
while I < CardsLength do
begin
V := Cards[I];
if V1 < V then
begin
Cards[J] := V1;
Inc(J);
Break;
end;
Cards[J] := V;
Inc(J);
Inc(I);
end;
while I < CardsLength do
begin
V := Cards[I];
if V2 < V then
begin
Cards[J] := V2;
Break;
end;
Cards[J] := V;
Inc(J);
Inc(I);
end;
if J = (CardsLength - 2) then
begin
Cards[J] := V1;
Cards[J + 1] := V2;
end
else if J = (CardsLength - 1) then
begin
Cards[J] := V2;
end;
end;
Il s'agit de la méthode la plus rapide: puisque la liste des 5 cartes est déjà triée, trier la liste de deux cartes (un comparateur et une swap), puis fusionner les deux listes, qui est O (K * (5 + 2). . Dans ce cas (K) sera normalement 5: le test de boucle (1), le comparateur (2), la copie (3), l'incrément de liste d'entrée (4) et l'incrément de la liste de sortie (5). C'est 35 + 2.5. Jetez une initialisation en boucle et vous obtenez 41,5 déclarations, total.
Vous pouvez également dérouler les boucles qui vous sauveriez peut-être 8 déclarations ou exécution, mais faites toute la routine environ 4-5 fois plus longue pouvant vous gâcher avec votre Rapport sur le cache d'instructions.
donné P (0 à 2), C (0 à 5) et copier sur H (0 à 6)
avec c () déjà triché (ascendant): et note que cela est plus rapide que l'autre algorithme qui serait "le plus rapide" si vous deviez vraiment trier les 7 cartes : Utilisez un masque bit (52) pour planer et définir les 7 cartes dans cette plage de toutes les cartes de 52 possibles (le masque bit), puis numérisez le masque bit dans l'ordre à la recherche des 7 bits définis . Qui prend 60-120 déclarations au mieux (mais reste plus rapide que toute autre approche de tri).
supposer que vous avez besoin d'une gamme de cartes à la fin de celui-ci.
Carte des cartes d'origine aux bits dans un entier 64 bits (ou tout entier avec> = 52 bits).
Si Au cours de la mappage initial, le tableau est trié, ne le change pas.
partitionnez l'entier dans des grignotins - chacun correspondra à des valeurs 0x0 à 0xf.
Utilisez les nibiles en tant que index. sous-tableaux triés correspondants. Vous aurez besoin de 13 ensembles de 16 sous-tableaux (ou seulement 16 sous-tableaux et utilisez une deuxième indirection, ou faites le bit ops plutôt que de regarder la réponse à la réponse; ce qui est plus rapide variera par la plate-forme). < p> concaténer les sous-tableaux non vides dans le tableau final.
Vous pouvez utiliser plus grand que des piqûres si vous le souhaitez; Les octets donneraient 7 ensembles de 256 matrices et le rendraient plus probables que les matrices non vides nécessitent une concaténation.
Ceci suppose que les branches sont coûteuses et mises en cache accès à bon marché.
Je ne sais pas autant de choses sur le Texas Hold'em: Est-ce qu'il est important de ce que P1 et P2 sont, ou cela ne compte que si elles sont de même costume ou non? Si seulement costume (P1) == costume (P2) est important, vous pouvez séparer les deux cas, vous n'avez que 13x12 / 2 possibilités différentes pour P1 / P2, et vous pouvez facilement précalculer une table pour les deux cas.
Sinon, je suggérerais quelque chose comme ceci: (Il s'agit simplement d'une démonstration pour une carte P1, vous devrez étendre cela pour P2, mais je pense que c'est simple. Bien que ce sera beaucoup de taper ...)
De cette façon, le tri ne prend pas de temps du tout. Les permutations générées sont déjà commandées.
De loin la réponse la plus utile, même si cela ne traite pas de la question actuelle. En mettant en œuvre deux tables (une pour les combos de flush sur d'autres combos), prenant chacune environ 8 Mo de mémoire, la procédure s'est frayée sur environ 16 secondes à 3,5. Marche à suivre! Et la meilleure partie est que l'initialisation des tables était également très rapide, car je pourrais jeter des informations sur la poursuite. (Pour le curieux, les tables sont gpokercomboswithflush: matrice [0..12,0..12,0..12,0..12,0..12] de tpokercombo; gpokercomboswithoutflush: tableau [0..12,0 ..12,0..12,0..12,0..12] de tpokercombo;)
Avez-vous même essayé d'insertion de sorte?
@FogleBird: Si vous créez les combinaisons commandées en premier lieu, vous n'avez pas à trier du tout. Même l'insertion Trier ne peut pas battre O (0) ;-)
Voici votre type de base O (n). Je ne sais pas comment cela se compare aux autres. Il utilise des boucles déroulantes.
char card[7]; // the original table of 7 numbers in range 0..51 char table[52]; // workspace // clear the workspace memset(table, 0, sizeof(table)); // set the 7 bits corresponding to the 7 cards table[card[0]] = 1; table[card[1]] = 1; ... table[card[6]] = 1; // read the cards back out int j = 0; if (table[0]) card[j++] = 0; if (table[1]) card[j++] = 1; ... if (table[51]) card[j++] = 51;
Pour sept chiffres, l'algorithme le plus efficace qui existe en ce qui concerne le nombre de comparaisons est Ford-Johnson. En fait, Wikipedia Références Un papier, facilement trouvé sur Google, qui affirme Ford-Johnson's le meilleur pour jusqu'à 47 numéros. Malheureusement, les références à Ford-Johnson ne sont pas toutes seules à trouver, et l'algorithme utilise certaines structures de données complexes.
Il apparaît sur l'art de la programmation informatique, Volume 3, par Donald Knuth, si vous avez accès à cela livre. p>
Il y a un papier qui décrit FJ et une version plus efficace de la mémoire Ici . p>
En tout cas, en raison de la mémoire de mémoire de cet algorithme, je doute que cela vaut la peine d'être des entiers, car le coût de la comparaison de deux entiers est plutôt bon marché que au coût de l'allocation de mémoire et de manipuler des pointeurs. P>
Maintenant, vous avez mentionné que 5 cartes sont déjà triées et que vous avez juste besoin d'insérer deux. Vous pouvez le faire avec l'insertion Trier le plus efficacement comme ceci: p> Comment cela dépendra de la structure de données. Avec un tableau, vous échangerez chaque élément, alors placez P1 au 1er, P2 et 7ème (commandé haut à bas), puis échangez P1 en haut, puis p2 vers le bas. Avec une liste, il vous suffit de réparer les pointeurs, le cas échéant. P> Cependant, une fois de plus, en raison de la particularité de votre code, il est vraiment préférable que vous suivez Nikie suggestion et générer simplement les boucles pour toutes les boucles pour chaque variation de laquelle P1 et P2 peut apparaître dans la liste. P> Par exemple, Trier P1 et P2 afin que p1 Loop Po1 from 0 to 5
Loop Po2 from Po1 + 1 to 6
If (Po2 == 1) C1start := P2 + 1; C1end := 51 - 4
If (Po1 == 0 && Po2 == 2) C1start := P1+1; C1end := P2 - 1
If (Po1 == 0 && Po2 > 2) C1start := P1+1; C1end := 51 - 5
If (Po1 > 0) C1start := 0; C1end := 51 - 6
for C1 := C1start to C1end
// Repeat logic to compute C2start and C2end
// C2 can begin at C1+1, P1+1 or P2+1
// C2 can finish at P1-1, P2-1, 51 - 3, 51 - 4 or 51 -5
etc
Si vous recherchez une tranche très basse, une sorte optimale, vous devez créer un réseau de tri. Vous pouvez générer le code pour un réseau de 7 entiers à l'aide de l'algorithme Bose-Nelson.
Cela garantirait un nombre fixe de compage et un nombre égal de swaps dans le pire des cas.
Le code généré est laid, mais il est optimal.
Vos données sont dans un tableau de tri et je suppose que vous échangez le nouveau deux si nécessaire, donc aussi triés. une. Si vous voulez le garder en place, utilisez une forme de tri d'insertion; b. Si vous voulez avoir, le résultat dans un autre tableau fait une fusion en copiant.
avec les petits nombres, la côtelette binaire est surchargée et la hauteur ternaire est appropriée de toute façon: Une nouvelle carte va principalement être divisée en deux et trois, à savoir. 2 + 3 ou 3 + 2, Deux cartes dans des singles et des paires, par ex. 2 + 1 + 2.
Donc, l'approche la plus efficace de l'espace de temps pour placer la plus petite carte est de comparer avec un [1] (VIZ. Skip A [0]) puis recherchez la gauche ou la droite pour trouver la carte qu'il devrait remplacer, puis échanger. et déplacez-vous à droite (changeant plutôt que de bouillonner), comparant avec la plus grande nouvelle carte jusqu'à ce que vous trouviez où il va. Après cela, vous passerez en avant par TWO (deux cartes ont été insérées). Les variables tenant les nouvelles cartes (et les swaps) doivent être des registres.
L'approche de recherche serait plus rapide mais utilise plus de mémoire.
Utilisez un réseau de tri, comme dans ce code C ++: Utilisez la fonction ci-dessus si vous souhaitez transmettre un itérateur ou un pointeur et utiliser la fonction ci-dessous si vous souhaitez passer les sept arguments un par un. BTW, à l'aide de modèles permet aux compilateurs de générer un code vraiment optimisé, alors ne recevez pas la conduite du modèle code> sauf si vous voulez du code C (ou d'une autre langue du code). P> template<class T>
inline void sort7(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5, T& e6) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a) register auto data##a=e##a;
#define DD2(a,b) register auto data##a=e##a;register auto data##b=e##b;
#define CB1(a) e##a=data##a;
#define CB2(a,b) e##a=data##a;e##b=data##b;
DD2(1,2) SORT2(1,2)
DD2(3,4) SORT2(3,4)
DD2(5,6) SORT2(5,6)
DD1(0) SORT2(0,2)
SORT2(3,5)
SORT2(4,6)
SORT2(0,1)
SORT2(4,5)
SORT2(2,6) CB1(6)
SORT2(0,4)
SORT2(1,5)
SORT2(0,3) CB1(0)
SORT2(2,5) CB1(5)
SORT2(1,3) CB1(1)
SORT2(2,4) CB1(4)
SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}
Je dois me demander, pourquoi recherchez-vous le moyen le plus rapide de trier un tel ensemble? À cette échelle, même la tri de bulles va finir en moins d'une milaçonde sur à peu près tout CPU disponible.
Trier ou sélection d'insertion Trier.
Le commentaire de Mason Wheeler m'a fait éditer la question un peu. La routine où le tri a lieu sera appelé 2118760 fois, alors même si un tri ne prend qu'une milliseconde, la routine prendra en quelques secondes. Cette routine sera appelée 2652 fois pour analyser des chances pour toutes les combinaisons possibles à deux cartes.
Comme je l'ai appris, il y a un algorithme de tri entier très rapide. Voir cette question: Stackoverflow.com / Questions / 2352313 / ...
associé ici: Stackoverflow.com/Questtions/2786899/...