Che è più veloce - la cernita o moltiplicazione di una piccola serie di elementi?

Question

di Cactus Kev Poker Hand Evaluator , ho notato le seguenti dichiarazioni:

In un primo momento, ho pensato che avrei potuto sempre semplicemente sorta la mano prima di passarlo al valutatore; ma l'ordinamento richiede tempo, e non volevo sprecare eventuali cicli di CPU di smistamento mani. Avevo bisogno di un metodo che non importava quale ordine i cinque carte sono state date come.
...
Dopo un sacco di pensiero, ho avuto un lampo di genio di utilizzare numeri primi. Vorrei assegnare un valore numero primo per ciascuno dei tredici ranghi della carta ... La bellezza di questo sistema è che se si moltiplicano i valori principali del rango di ogni carta in mano, si ottiene un prodotto unico, indipendentemente dall'ordine delle cinque carte.
...
Dal momento che la moltiplicazione è uno dei calcoli più veloci di un computer può fare, abbiamo rasato centinaia di millisecondi al largo nostro tempo erano siamo stati costretti a ordinare ogni mano prima della valutazione.

Non ho difficoltà a credere questo.

Cactus Kev rappresenta ogni scheda come intero di 4 byte, e valuta le mani chiamando eval_5cards( int c1, int c2, int c3, int c4, int c5 ). Possiamo rappresentare carte come un byte, e una mano di poker come una matrice 5 byte. Ordinamento questo array 5 byte per ottenere una mano unica deve essere abbastanza veloce. E 'più veloce del suo approccio?

Che cosa succede se osserviamo i suoi rappresentanza (carte come integer a 4 byte)? Può Ordinamento di un array di 5 interi essere più veloce di loro moltiplicare? Se no, che tipo di ottimizzazioni di basso livello può essere fatto per rendere l'ordinamento di un piccolo numero di elementi più veloce?

Grazie!

buone risposte a tutti; Sto lavorando su analisi comparativa delle prestazioni di smistamento vs moltiplicazione, per ottenere alcune statistiche sulle prestazioni duro.

Answer 1

L'ordinamento non è intrinsecamente più difficile di moltiplicare i numeri. Sulla carta, sono circa lo stesso, ed è anche bisogno di un algoritmo di moltiplicazione sofisticata per rendere grande la moltiplicazione competitivo con grande sorta. Inoltre, quando l'algoritmo di moltiplicazione proposta è fattibile, è possibile utilizzare anche bucket sort, che è asintoticamente più veloce.

Tuttavia, una mano di poker non è un problema asintotico. E 'solo 5 carte e lui si preoccupa solo di uno dei 13 valori numerici della scheda. Anche se la moltiplicazione è complicata in linea di principio, in pratica si è implementato in microcodice ed è incredibilmente veloce. Quello che sta facendo lavori.

Ora, se siete interessati nella questione teorica, v'è anche una soluzione con aggiunta piuttosto che la moltiplicazione. Ci può essere solo 4 carte di qualsiasi valore uno, così si potrebbe altrettanto bene assegnare i valori 1,5,25, ..., 5 ^ 12 e aggiungerli. Si adatta ancora a 32 bit aritmetica. Ci sono anche altre soluzioni per addizione based con altre proprietà matematiche. Ma in realtà non importa, perché l'aritmetica a microprogramma è molto più veloce di qualsiasi altra cosa che il computer sta facendo.

Answer 2

Naturalmente dipende molto dalla CPU del computer, ma una tipica CPU Intel (ad esempio Core 2 Duo) possono moltiplicare due numeri a 32 bit all'interno di cicli di clock della CPU 3. Per un algoritmo di ordinamento per battere che, l'algoritmo deve essere più veloce di 3 * 4 = 12 cicli di CPU, che è un vincolo molto stretto. Nessuno degli algoritmi di ordinamento standard, può farlo in meno di 12 cicli di sicuro. Solo il confronto di due numeri avrà un ciclo della CPU, il ramo condizionato il risultato sarà anche prendere un ciclo di CPU e tutto quello che fate allora sarà almeno prendere un ciclo della CPU (scambiando due carte saranno effettivamente prendere almeno 4 cicli di CPU). Così moltiplicando vittorie.

Naturalmente questo non sta prendendo la latenza in considerazione per recuperare il valore della carta da 1 ° o 2 ° livello della cache o forse anche di memoria; tuttavia, questa latenza si applica a entrambi i casi, moltiplicando e smistamento.

Answer 3

Senza prove, io sono in sintonia con la sua tesi. Si può fare in 4 moltiplicazioni, rispetto a cernita, che è n log n. Specificamente, la rete ottimale classificare richiede 9 comparazioni. Il valutatore deve quindi almeno guardare ad ogni elemento della matrice ordinato, che è un altro 5 operazioni.

Answer 4

5 elementi possono essere ordinati tramite un albero decisionale ottimizzato, che è molto più veloce rispetto all'utilizzo di un generico algoritmo di ordinamento.

Tuttavia, resta il fatto che i mezzi di smistamento sacco di rami (come fanno i confronti che sono necessarie in seguito). Rami sono davvero male moderne architetture CPU pipeline, soprattutto rami che vanno in entrambi i casi con analoga probabilità (vanificando così logica branch prediction). Che, molto di più del costo teorico di confronti moltiplicazione contro, rende più veloce la moltiplicazione.

Ma se si potrebbe costruire hardware personalizzato per fare la cernita, potrebbe finire più velocemente.

Answer 5

Non dovrebbe essere davvero rilevante, ma è corretto. L'ordinamento richiede molto più tempo rispetto a moltiplicarsi.

La vera questione è quello che ha fatto con il numero primo risultato, e come che era disponibile (in quanto factoring che mi sarei aspettato di richiedere più di ordinamento.

Answer 6

E 'difficile pensare a qualsiasi operazione di ordinamento che potrebbe essere più veloce di moltiplicare lo stesso insieme di numeri. A livello di processore, la moltiplicazione è solo load, load, multiply, load, multiply, ..., con forse qualche manipolazione dell'accumulatore gettato. È lineare, facilmente pipeline, nessun confronto con il ramo costi mis-predizione associati. Dovrebbe mediamente del 2 istruzioni al valore da moltiplicare. A meno che l'istruzione di moltiplicazione è lentissimo, è davvero difficile immaginare un più veloce sorta.

Answer 7

Un aspetto degno di nota è che anche se un'istruzione di moltiplicazione della CPU è morto lento (o inesistente ...) è possibile utilizzare una tabella di ricerca per accelerare le cose ancora di più.

Answer 8

  

Dopo un sacco di pensiero, ho avuto un lampo di genio di usare numeri primi. Vorrei assegnare un valore numero primo per ciascuno dei tredici ranghi della carta ... La bellezza di questo sistema è che se si moltiplicano i valori principali del rango di ogni carta in mano, si ottiene un prodotto unico, indipendentemente dall'ordine delle cinque carte.

Questo è un esempio di un sistema di numero non posizionale.

Non riesco a trovare il link alla teoria. Ho studiato che, come parte di algebra applicata, da qualche parte intorno totient e la crittografia di Eulero. (Posso essere sbagliato con la terminologia, come ho studiato tutto quello che nella mia lingua madre.)

  

Che cosa succede se osserviamo i suoi rappresentanza (carte come integer a 4 byte)? Può Ordinamento di un array di 5 interi essere più veloce di loro moltiplicare?

RAM è una risorsa esterna ed è generalmente più lento rispetto alla CPU. Ordinamento 5 di int avrebbe sempre dovuto andare in RAM a causa di operazioni di swap. Inserisci qui il sovraccarico di funzione stessa di smistamento, e la moltiplicazione si ferma cercando così male.

Credo che sulla CPU moderne intero moltiplicazione sarebbe quasi sempre più veloce di smistamento, dal momento che diversi moltiplicazioni possono essere eseguiti contemporaneamente su diversi ALU, mentre c'è solo un bus che collega CPU RAM.

  

In caso contrario, che tipo di ottimizzazioni di basso livello può essere fatto per rendere l'ordinamento di un piccolo numero di elementi più veloce?

5 interi può essere ordinata abbastanza rapidamente utilizzando bubble sort : qsort userebbe più memoria ( per ricorsione) mentre bolla ben ottimizzato sorta funzionerebbe completamente dalla d-cache.

Answer 9

Come altri hanno fatto notare, l'ordinamento da sola non è più veloce di moltiplicare per 5 valori. Questo ignora, però, il resto della sua soluzione. Dopo disdegnare un 5-elemento sorta, egli procede a fare una ricerca binaria su un array di 4888 valori - almeno 12 i confronti, più che il genere mai necessaria

Si noti che non sto dicendo che c'è una soluzione migliore che coinvolge l'ordinamento - non ho dato abbastanza pensiero, personalmente -. Solo che l'ordinamento solo è solo una parte del problema

Inoltre non doveva usare numeri primi. Se semplicemente codificato il valore di ogni carta a 4 bit, avrebbe bisogno di 20 bit per rappresentare una mano, dando un intervallo da 0 a 2 ^ 20 = 1048576, circa 1 / 100esimo della gamma prodotte con numeri primi, e abbastanza piccolo (anche se ancora soffrono problemi di coerenza della cache) per produrre una tabella di ricerca sopra.

Naturalmente, una variante ancora più interessante è quello di prendere 7 carte, come si trovano in giochi come Texas Holdem, e trovare la migliore mano di 5 carte che può essere fatto da loro.

Answer 10

La moltiplicazione è più veloce.

La moltiplicazione di una data serie sarà sempre più velocemente di quanto l'ordinamento della matrice, presumendo i risultati di moltiplicazione in un risultato significativo, e la tabella di ricerca è irrilevante perché il codice è stato progettato per valutare una mano di poker in modo avresti bisogno di fare una ricerca sul set ordinato comunque.

Answer 11

Un esempio di un ready made Texas Hold'em 7 e valutatore di 5 carte possono essere trovati qui con la documentazione e l'ulteriore spiegato qui . Tutte le valutazioni di benvenuto presso l'indirizzo di posta elettronica ha trovato in esso.

Non c'è bisogno di sorta, e può in genere (~ 97% del tempo) uscire solo con 6 aggiunte e un paio di turni di bit al momento di valutare le mani 7-card. L'algo utilizza uno sguardo generato fino tavolo che occupa circa 9 MB di RAM ed è generata in un quasi istantaneo. A buon mercato. Tutto questo è fatto all'interno di 32-bit, e "inlining" valutatore 7-card è un bene per la valutazione circa 50 mani generate casualmente per secondo sul mio portatile.

Oh, e la moltiplicazione è più veloce di smistamento.