Newsgroup: it.comp.lang.c
Titolo: quale struttura dati per velocità?

Devo scrivere del codice possibilmente veloce e possibilmente ben
scritto in C.
Il problema è questo, devo sostanzialmente simulare una versione
semplificata della versione razz del poker.
Il codice funzionante in python è qui
http://github.com/AndreaCrotti/Razz/blob/master/razz.py
Ho quindi questi oggetti in sostanza:
- carta
- mazzo
- mano del giocatore
La carta è un intero da 0-13 (usare unsigned char magari aiuta)?
Sul mazzo devo sostanzialmente estrarre carte casuali, e non so quale
sia il modo migliore.
In python uso un dizionario
(carta, #rimanent) e lavoro su quello.
In C forse converrebbe tenere solo una array.
Che dite?
A proposito non si può scrivere meglio questo?
--8<---------------cut here---------------start------------->8---
#define STR_EQ(x,y) (!strcmp(x, y))
int str_to_card(char *card) {
  if (STR_EQ(card, "A")) {
    return 1;
  }
  if (STR_EQ(card, "J")) {
    return 11;
  }  
  if (STR_EQ(card, "Q")) {
    return 12;
  }
  if (STR_EQ(card, "K")) {
    return 13;
  }  
  // means that it's an integer
  return atoi(card);
}
--8<---------------cut here---------------end--------------->8---
Il case non funziona a quanto pare, qualche struttura potrebbe essere
utile?

 writes:
Dimenticavo, qui c'è il codice C che ho iniziato a scrivere.
http://github.com/AndreaCrotti/Razz/blob/master/razz.c
Qualsiasi consiglio anche stilistico (non programmo mai in C) è ben accetto...

  return atoi(card);
int char_to_card(char c) {
    switch ( c ) {
      case 'A': return 1;
      case 'J': return 11;
      case 'Q': return 12;
      case 'K': return 13;
      default : return (c - '0');
    }
}

 }
Ottimo grazie corretto, in effetti faceva proprio schifo...
Comunque pensavo di fare così, una mano è una struttura di questo tipo.
--8<---------------cut here---------------start------------->8---
typedef struct hand {
  // this is small can be allocated in stack memory
  card cards[RAZZ_HAND];
  int actual_len;
} hand;
--8<---------------cut here---------------end--------------->8---
Ma mi domandavo, in quel modo quando creo un
hand h;
lo spazio di cards è già allocato? E rimane nello stack?
O devo comunque fare un
hand *h = (hand *) malloc(sizeof(hand))
O forse mi conviene dare direttamente il puntatore nel typedef per usare
sempre i puntatori?
Comunque la mano è un semplice array in cui aggiorno a ogni remove/add
l'actual_len.

hand *h = (hand *) malloc(sizeof(hand))
Puoi anche solo scrivere:
hand h;
ed allocare quindi staticamente la "mano" h. Non � necessario allocare
dinamicamente (nota che il ritorno di malloc() non va castato in C).

 dinamicamente (nota che il ritorno di malloc() non va castato in C).
Ah capisco, in quel caso allocando staticamente hand alloco anche tutte
i possibili array contenuti in essa sono anch'essi allocati
staticamente?
Come mai il ritorno di malloc non va castato?
L'ho sempre visto fare, forse è solo un abitudine da tempi passati?

 dinamicamente (nota che il ritorno di malloc() non va castato in C).
Anzi no scusa, malloc ritorna un puntatore a void, capisco che la
dimensione comunque è giusta e non ci sono problemi ma fare un casting
di sicuro non fa male, no?

 hand h;
Tra l'altro l'allocazione statica funziona solo se devo stare nella
stessa funzione giusto?
Volendo scrivere in modo più "funzionale" possible ho paura che dovrò
passare puntatori in giro e allocare solo dinamicamente, o mi sbaglio?


Il principale motivo per cui il cast non si mette sono tre:
- ti accorgi se ti sei dimenticato di includere la stdlib.h (il
compilatore si lamenta subito).
- non è necessario in quanto da void* la conversione a qualsiasi altro
tipo di puntatore è implicita.
- se cambi il tipo della variabile non devi andare a cambiare tutti i
cast
Mentre il primo motivo è abbastanza "futile", il secondo ed il terzo
ti assicurano meno lavoro (oltre a rendere il codice più leggibile e
meno prolisso).
Ciao!

 Ciao!
Ottimo grazie mille, chiarissimo.
Sto cercando di usare tpyedef dappertutto comunque per i tipi semplici,
se una carta adesso è int e domani diventa un unsigned char mi basta
cambiare una riga.
Comunque, ho bisogno di un mazzo di carte, (52 int in sostanza) che
dovrò allocare inizialmente e su cui poi dovrò sostanzialmente fare solo
delle "rimozioni", 1/3 decise a priori e 2/3 casuali più o meno.
--8<---------------cut here---------------start------------->8---
typedef struct deck {
  card *cards; // here it's not allocated in the stack because it's much bigger
               // does it make sense?
} deck;
--8<---------------cut here---------------end--------------->8---
Tenere un grosso array è una buona idea per questo genere di operazioni?
Altrimenti cosa potrei usare?
In python tengo una struttura
(carta, #rimanenti)
e rimuovere è molto semplice, l'unico problema è la ricerca casuale, che
per essere fair dev'essere pesata o fare un "choice" su tutta la lista.
Spero di essere stato chiaro, grazie a intanto

 wrote:

Un array di 52 interi di tutto sembra fuorché "grosso" :)
Detto questo: perché ti serve una struttura? Dentro c'è solo un array?
A che serve?
Non conosco il gioco, ma probabilmente quello che farei è fare uno o
più array o liste (tipo carte per persona, mazzo rimanente,
etc.etc.) . Il fatto che siano così pochi gli elementi da ordinare/
cancellare/inserire non giustifica secondo me la scelta di un
algoritmo super-performante :/
Ciao!

 Ciao!
Sì al momento c'è solo un array, ma non sono sicuro che sia la cosa
migliore...
Io pensavo di usare avere delle hands e dei decks, sono entrambi array
di carte in sostanza ma siccome hanno usi differenti vorrei
implementarli in modo differente.
Con un array come gestisco l'eliminazione di elementi?
Se li setto a NULL per esempio poi la ricerca random deve tenere conto
del fatto che ci sono elementi nulli.
Se invece creo una struttura (carta, #rimanenti) che sarebbe molto più
veloce per l'eliminazione ho poi problemi con l'estrazione di una carta
casuale.
Diciamo che punto al top perché è in un certo senso una gara di
velocità, devo fargli giocare 10^n molto grande partite, quindi
qualsiasi furbizia è ben accetta ;)


Bah, la regola prima è (o meglio, dovrebbe essere) "prima fallo
andare, poi (se serve) ottimizzalo"
Magari ti accorgi alla fine che ci hai messo tre giorni di più per
scrivere un programma che è più veloce di un minuto su due giorni di
elaborazione :-)
Secondo me dovresti provare a scriverlo così come viene poi, se è
effettivamente lento, prendi i tempi e isoli i colli di bottiglia, e
in caso richiedi qui ;)
Ciao!

 passare puntatori in giro e allocare solo dinamicamente, o mi sbaglio?
Non è chiaro quello che intendi. Comunque credo anch'io che il consiglio 
di Andrea non sia da applicare, in questo caso.
E.


Occhio che l'attributo "static" messo ad una variabile globale o ad
una variabile locale ad una funzione assume due significati *pratici*
ben diversi!
Ciao!

 A proposito non si può scrivere meglio questo?
Ti hanno già risposto. Ma ovviamente non ti serve avere maggiore 
velocità in quella funzione.
E.

L'ho sempre visto fare, forse � solo un abitudine da tempi passati?
In molti casi � una pessima abitudine dei tempi andati (tipicamente
del C pre ANSI C89 / ISO C90), in molti altri � perch� il codice � in
realt� compilato come C++ e il C++ obbliga a castare, perch� essendo
pi� "strict-typed" del C, non prevede una conversione automatica.

di sicuro non fa male, no?
Non fa bene, � quello il punto.

il consiglio di Andrea non sia da applicare, in questo caso.
Io non ho dato nessun consiglio, gli ho mostrato solo le opzioni.

 Ciao!
Sì sono perfettamente d'accordo, io non voglio cercare di ottimizzarlo
prima che vada, vorrei solo capire quel è la struttura dati che date
certe operazioni si comporta meglio.
Scegliendola bene poi la velocità verrebbe di conseguenza ;)
Comunque ho avuto anche una malsana idea, usare i numeri primi.
Un mazzo potrebbe essere
somma([prime[x]**rep for x in cards])
where prime =
{1 : 2, 2: 3, 3:5 ...}
Togliere o mettere carte sarebbe semplicissimo, ma naturalmente sul
mazzo intero il numero diventa enorme, forse per le "mani" andrebbe
bene.
Inoltre non sarebbe comoda l'estrazione casuale, però forse per le mani
andrebbe bene, anche se fare conteggi e verificare doppioni la vedo
dura.
Comunque in python sono passato a una semplice lista per il mazzo e ho
migliorato del 50% più o meno.
L'estrazione casuale è fatta semplicemente mescolando le carte alla
creazione del mazzo e poi facendo un pop() sulla lista, molto più astuto
di quello che facevo prima.

 no, direi che signed o unsigned non ti cambi niente.
Ma da "int" a "char" dovrebbe cambiare qualcosa no?
Grazie

Andrea Crotti ha scritto:

Ah ecco non me n'ero accorto... Io lascerei int, che sono più veloci. 
Almeno se non hai bisogno di memorizzare MOLTI dati, ma non credo sia il 
tuo caso.
E.

 :-)
Sì verissimo, ora però profilando vedo che questa operazione è parecchio
costosa, mi sarebbe utile un generatore di mazzi casuali, senza dover
mescolare tutto ogni volta.
Mm scrivendo mi è venuta un'idea, perché invece di avere mazzi casuali
non provo a generare tutti i possibili mazzi?
Si potrebbe usare qualcosa tipo l'algoritmo di Johnson per le
permutazioni, o è un follia (il seme non conta ma in effetti solo le
permutazioni di 13 carte sono 13! quindi mmm).

 non provo a generare tutti i possibili mazzi?
secondo te generare TUTTI i possibili mazzi e' poi' veloce che
generarne uno casuale?
Ciao Jack

 Ciao Jack
Ovvio che non lo è, ma mentre generandoli tutti ho la VERA probabilità
che sarà uguale a quella che potrei calcolare a priori generandoli
casualmente mi devo basare su un alto numero di simulazioni e sperare
che il generatore random dia una distribuzione uniforme.
Per carità poi cambia poco e nulla ma teoricamente c'è una differenza
sostanziale.

Non ho ancora risposto alla domanda fondamentale comunque, come
implementereste voi
- il mazzo
  sul quale verrano fatte solo estrazioni casuali o rimozioni
- la mano del giocatore
  sulla quale verrano aggiunti, verificata la presenza dei duplicati e
  rimossi
Un mio collega masochista ha usato delle linked list per il secondo, e
il suo programma in C (non ancora ottimizzato per carità) va esattamente
veloce come il mio in python, quindi direi che c'è qualcosa che non
va...

 mescolare tutto ogni volta.
Scusa, ma che algoritmo usi per mescolare il mazzo?
Prova questo (pseudo-codice scritto al volo, non garantito):
const int n=13*4;
for (i=0;i<n-1; ++i) {
   j=rand(n-i);
   swap(mazzo[i],mazzo[i+j]);
}
Generare tutti i mazzi è impensabile...
E.

   rimossi
array
E.

 E.
Ho il sentore che una cosa del genere non mi generi una buona mescolata.
Stavo pensando (e ho scritto) la seguente cosa.
- non mi interessa dell'ordine nel mazzo
- estraggo una carta a caso usando un random() e il modulo
Il trucco sta nello spostare dopo l'ultima carta la carta estratta, e
decrementando la lunghezza.
Non sono sicuro che questo swap non vada ad inficiare sulla
randomizzazione (in teoria un po' dovrebbe) ma se dovesse funzionare
sarebbe fantasticamente veloce.
Ecco qui più o meno il codice.
--8<---------------cut here---------------start------------->8---
card get_random_card_from_deck(deck *deck) {
  int pos = random() % deck->len;
  card c = deck->cards[pos];
  swap_cards(pos, deck->len-1, deck->cards);
  deck->len--;
  return c;
}
void swap_cards(int c1_idx, int c2_idx, card *cards) {
  card tmp;
  tmp = cards[c1_idx];
  cards[c1_idx] = cards[c2_idx];
  cards[c2_idx] = tmp;
}
--8<---------------cut here---------------end--------------->8---

 E.
Qui anche più o meno, sto provando un array che si comporta da
dizionario dove indice->chiave del dizionario, quindi
 [2,3,2,4]
significa che ho 2 1, 3 2 e così via.
Per le operazioni che devo fare mi sembra che vada benissimo..

 significa che ho 2 1, 3 2 e così via.
Non ti conviene mettere nell'array la sequenza ordinata delle carte?
Ad esempio
[1,1,2,2,2]
se hai un full di 2 e assi. Mi pare che sia più veloce da creare e da usare.
E.

 - estraggo una carta a caso usando un random() e il modulo
Sì, puoi anche fare così. In effetti se non usi tutto il mazzo ti 
conviene. Se invece hai bisogno di usare più volte lo stesso mazzo, 
oppure vuoi poterci re-inserire le carte, lo devi mescolare all'inizio.
E.

 sarebbe fantasticamente veloce.
Perche' e' veloce?
1. immagino userai get_random_card_from_deck() 52 volte (una per carta), no? 
Quindi fai un ciclo di 52 ripetizioni, come l'algoritmo di ?manu*
2. usi % , che potrebbe essere lento
Pleg

 E.
No perché in realtà non considero full poker e così via, appena trovo
una coppia che non riesco a togliere sono già a posto.
Il ranking mi sembra molto efficiente ed eccolo qui:
--8<---------------cut here---------------start------------->8---
card rank_hand(hand *h) {
  int to_remove = h->len - RAZZ_EVAL;
  /// here we don't need the CARD_TO_IDX macro since we only check for duplicates
  for (i = 0; i < RAZZ_CARDS; i++) {
    while (h->cards[i] > 1) {
      if (to_remove == 0)
        return NON_HIGH_HAND;
 
      h->cards[i]--;
      h->len--;
      to_remove--;
    }
  }
  /// scan the whole array from the end and grab the to_remove_th element
  for (i = RAZZ_CARDS-1; i > 0; i--) {
    assert(h->cards[i] < 2); /**< if failing means that the previous part didn't work correctly */
    if (h->cards[i] > 0) {
      if (to_remove == 0)
        return IDX_TO_CARD(i);
      else
        to_remove--;
    }
    /// when equal to 0 implicitly go to previous card
  }
  return 0; /// never getting here
--8<---------------cut here---------------end--------------->8---
In sostanza prima elimino tutti i doppioni che posso, poi se non è
almeno una coppia scorro al contrario e prendo la carta più alta tra le
RAZZ_EVAL che mi servono.

 E.
In realtà nel caso più semplificato estraggo SOLO 4 carte dal mazzo,
mescolarlo tutto non ha molto senso...

 Pleg
No perché dovrei, ogni get_random_card_from_deck mi restituisce una
carta, come dicevo non ho bisogno di tutto il mazzo ma solo di una
piccola parte...
Ci sono modi per usare il modulo più velocemente?
Ah tra l'altro, quale caspita di random dovrei usare??
Ho visto almeno
- rand
- random
- lrand48
con le rispettive famiglie, ma non mi è chiaro che cosa cambi tra essi e
perché diavolo ce ne siano così tanti..

 - lrand48
Dai un'occhiata qui:
http://linux.die.net/man/3/lrand48
http://linux.die.net/man/3/rand
Probabilmente vuoi usare rand(). Non e' certo crittograficamente sicura :) 
ma per estrarre delle carte da un mazzo dovrebbe bastare.
E' interessante la nota sui bit meno significativi, con la relativa 
precauzione di non usare il modulo. Ma, come dice, ormai il problema 
dovrebbe essere stato risolto.
Per la velocita' della funzione modulo, dovresti fare delle prove sul tuo 
sistema.
Pleg 

     }
 >   }
 >
 >   /// scan the whole array from the end and grab the to_remove_th element
 >   for (i = RAZZ_CARDS-1; i > 0; i--) {
 >     assert(h->cards[i] < 2); /**< if failing means that the previous 
part didn't work correctly */
 >     if (h->cards[i] > 0) {
 >
 >       if (to_remove == 0)
 >         return IDX_TO_CARD(i);
 >       else
 >         to_remove--;
 >     }
 >     /// when equal to 0 implicitly go to previous card
 >   }
 >   return 0; /// never getting here
 > --8<---------------cut here---------------end--------------->8---
Puoi fare un po' meglio, così:
card rank_hand(hand *h) {
    int to_remove = h->len - RAZZ_EVAL;
int higher=0;
for (i = 0; i < RAZZ_CARDS; i++) {
   if (h->cards[i]>1) {
     if (h->cards[i]>to_remove) {
       h->cards[i]-=to_remove;
       return NON_HIGH_HAND;
     } else {
       to_remove-=h->cards[i]-1;
       h->cards[i]=1;
     }
     higher=i;
   }
}
return IDX_TO_CARD(higher);
}
Inoltre ti converrebbe non fare le conversioni IDX_TO_CARD durante i 
calcoli. Le conversioni basta che le fai per l'input e l'output, per il 
resto usi il tuo formato interno (più veloce).
E.

 mescolarlo tutto non ha molto senso...
Sì, infatti.
E.

 Il ranking mi sembra molto efficiente ed eccolo qui:
In realtà puoi essere ancora molto più efficiente, se ho capito bene 
quello che stai facendo. Ti conviene calcolare il ranking man mano che 
peschi le carte. Questo è più efficiente perché le carte pescate (sono 
5?) sono molte meno di tutte le carte possibili (13).
Farei qualcosa del tipo:
struct hand {
   unsigned int card[13];
   unsigned int rank;
   unsigned int n_doppie;
};
void init_hand(struct hand *h) {
   ....
}
void add_card_to_hand(struct hand *h, card c) {
   if (c>h->rank)
     h->rank=c;
   if (h->card[c]) {
     if (h->n_doppie) {
        h->card[c]++;
        h->n_doppie--;
     } else {
        h->randk=MAX_RANK;
     }
   }
}
E.

 E.
Magnifico, stavo giusto cercando un modo (anche in python avevo lo
stesso problema) di usare un solo ciclo.
Tra l'altro ottengo risultati diversi (questi mi sembrano più corretti)
quindi mi sa che era pure sbagliata la mia versione...
Un'ulteriore ottimizzazione potrebbe essere scorrere l'array al
contrario, gli elementi sono comunque già ordinati quindi in teoria
appena ho rimosso abbastanza e ho ancora 1 elemento in quell'indice lo
posso ritornare.

 faccia il suo dovere...
Sì però mi aspetto una distribuzione uniforme, e io cambio un po' la
struttura, ad esempio il mio algoritmo fa questo
[1, 2, 3, 4, 5]
- estraggo indice 2
[1, 2, 5, 4 | 3]
- estraggo indice 1
[1, 4, 5 | 2, 3]
e così via.
Se inizialmente il 5 aveva uguali probabilità di essere estratto dopo la
prima estrazione diventa meno probabile, o dico cazzate?

 writes:

Caspita ottima idea, però è vero fino a un certo punto, perché in realtà
devo scegliere le 5 carte migliori su 7.. 
Però potrei vedere subito quando ho troppe coppie e settare il -1.
Se poi proseguendo trovo -1 non faccio nulla, altrimenti aggiorno il
rank al nuovo valore massimo, sì direi che può funzionare grazie.

Andrea Crotti ha scritto:

propenderei per la seconda ;-)
Alla prima estrazione il 5 ha probabilità 1/5 di essere estratto, come 
tutte le 5 carte. Se non viene estratto alla prima, alla seconda 
estrazione ha probabilità 1/4, come le altre carte...
E.

 E.
Non sono tuttora convinto, è vero che tutti i numeri nel range sono
equiprobabili in teoria, ma è anche vero che è un generatore di numeri
PSEUDO CASUALI.
Questo significa che in realtà ho una sequenza di numeri che dato un
certo seed è sempre la stessa.
Cambia le cose questo?
Comunque a proposito del mazzo, ora ad ogni partita lo rigenero da 0, e
ciò è molto stupido, in ordine di furbizia potrei fare:
- lo tengo sempre allocato (non malloc/free ogni volta) e ogni volta lo
  resetto
- faccio in modo di resettarlo invertendo le swap che ho fatto nella
  (complicato e non so se così fattibile)
- non lo resetto per nulla e tengo sempre lo stesso mazzo, cambiando
  solo l'attributo "len" (qui però ho sempre paura di fare casini con le
  probabilità e random)
Che dite

Un altro paio di cose non direttamente correlate.
Avendo tutte funzioni molto brevi che fanno una sola cosa ho sempre
comunque bisogno di un qualche indice, quindi praticamente ho "int i"
dappertutto nel codice.
Dichiarandolo globale non è una buona idea ho notato, non ci sono altri
modi vero?
Altra cosetta, tutte le funzioni con side effect (aggiungi togli etc)
le ho dichiarate void, forse dovrebbero essere tutte bool (int insomma)
e tornare se è andato tutto bene?
Propendo di più a mettere delle assert su condizioni che non dovrebbero
mai verificarsi, ma non so se è il modo migliore.

   probabilità e random)
Sì, tieni sempre lo stesso. Al massimo lo puoi reinizializzare con la 
sequenza iniziale. Comunque se temi che il codice sia sbagliato, è 
meglio scoprirlo piuttosto che nascondere il problema.
E.

 mai verificarsi, ma non so se è il modo migliore.
Sì, è una buona pratica. Quando poi ti fidi del codice e vuoi andare in 
velocità, passi il parametro -DNDEBUG al compilatore.
E.

 vuoi un mazzo casuale?
Pescando a caso sarebbe meglio tenere sempre lo stesso mazzo iniziale.

 carte.
Ma come fai a sapere se una carta l'hai già pescata?
E.

 E.
step0
deck = [1, 2, 3, 4, 3]
estraggo 2
step1
deck = [1,3,3,4]
estraggo 3
etc. etc..
Usando lo swap che ho già descritto, il deck in realtà rimane sempre
uguale, cambia solo la lunghezza dichiarata (e usata poi come modulo per
il random).

Andrea Crotti ha scritto:

Ok, allora non ho capito qual è il problema. Sempre che ci sia.
E.

Dopo parecchi bug risolti pare finalmente funzionare!
--8<---------------cut here---------------start------------->8---
bash-3.2$ time ./razz_fast  10000000 1 A 2 3
-1:	284160
5:	715784
6:	1179588
7:	1430219
8:	1502732
9:	1429042
10:	1256783
11:	1011381
12:	732877
13:	457434
real	0m3.238s
user	0m3.187s
sys	0m0.008s
--8<---------------cut here---------------end--------------->8---
Direi che 10 * 1000 * 1000 partite in 3 secondi non è male, sebbene con
tutti i trucconi del caso.
Così a occhio le probabilità sembrano giuste e molto praticamente uguali
a quelle date da python...