Newsgroup: it.comp.lang.c
Titolo: Mantenere array ordinato

Ora qui tutto sembra funzionare, però questo accrocchio proprio non mi piace:
--8<---------------cut here---------------start------------->8---
void
remove_card_from_deck(Card c, Deck *deck) {
     int i;
     // - swap the found card with the last card
     // - decrease the array by 1
     // FIXME: better maybe to keep it sorted somehow and use a binary search
     for (i = 0; i < deck->len; i++) {
          if (deck->cards[i] == c) {
               swap_cards(i, deck->len-1, deck->cards);
               deck->len--;
               return;
          }
     }
}
--8<---------------cut here---------------end--------------->8---
In sostanza per rimuovere una carta data dal deck faccio una scansione
lineare, ora l'array è teoricamente più o meno ordinato, ma non
abbastanza da usare bsearch, ci sono degli algoritmi di ricerca
randomizzati che potrebbero essere più efficienti nel caso medio?
Meglio ancora sarebbe riuscire a mantenere ordinato l'array, ma per come
agisce
[1, 2, 3, 4]
! 2
[1, 4, 3 | 2]
! 1
[3, 4 | 1 2]
E così via la vedo dura.
Anche se magari tenendo ordinate le due parti (eliminate e non) potrei
poi usare un algoritmo di merge per tornare all'array ordinato.
Provo anche a usare semplicemente qsort e bsearch, non è detto che
rallentino così tanto l'esecuzione.

Secondo me stai sbagliando approccio.
Se non ho capito male vuoi pescare una carta casuale e toglierla dal
mazzo.
Se ho capito bene, se il tuo intento è quello, ti conviene creare un
array iniziale con le carte ordinate. Poi da questo peschi casualmente
delle carte per creare un secondo array non ordinato (carte casuali,
diciamo che mischi il primo array per ottenere il secondo).
A questo punto peschi sempre l'ultima. Così la carta è casuale e sai
dove finisce il mazzo.
O vuoi ottenere altro?

 writes:

Eh no direi di no, dovrie mescolare il mazzo 10^K volte, mentre ottengo
lo stesso risultato non mescolandolo MAI.
Mi infastidisce solo un po' quella ricerca a forza bruta, tutto qui...

 Mi infastidisce solo un po' quella ricerca a forza bruta, tutto qui...
Cioè il tuo scopo qual è? Ora sono curioso :)

Andrea Crotti ha scritto:

Scusa, ma la carta non la estrai dallo stesso array?
Sai già qual'è l'indice
int ix = rand() % deck->len;
Card c = remove_card_from_deck(ix, deck);
Card remove_card_from_deck(int ix, Deck *deck) {
   Card c = deck->cards[ix];
   swap_cards(ix, deck->len-1, deck->cards);
   deck->len--;
   return c;
}
o puoi anche mettere il rand() direttamente all'interno, visto che 
dovrebbe essere il solo posto in cui viene usato.
Ciao

 Cioè il tuo scopo qual è? Ora sono curioso :)
Vedere qui per un abbozzo di doc, è un problema giocattolo oper scrivere
codice ottimizzato in sostanza..
http://github.com/AndreaCrotti/Razz/raw/master/razz.pdf

 Ciao
Quando la estraggo casualmente è chiaro che non ho bisogno di quella
schifezza... Ma mi serve anche estrarre alcune carte passate in input,
ma ora che ci penso sono estremamente pirla.
Al momento in cui ricevo queste carte il mazzo creato è perfettamente
ordinato, quindi posso
- eliminare velocemente tutte quelle carte
- usare quel mazzo creato senza le carte iniziali per il resto del
  programma
ottimo :)

 ottimo :)
Rieccomi, ho fatto come dicevo e ho guadagnato un altro 30% di velocità!
Ora il make_deck è molto più complicato (sicuramente si può scrivere
meglio infatti) però evito quelle brutture precedenti
--8<---------------cut here---------------start------------->8---
Deck *
make_deck(int start, int end, int rep, Card init_cards[], int to_remove) {
     int i, j, idx, init_idx;
     idx = init_idx = 0;
     int range_len = end - start;
     int len = range_len * rep - to_remove;
     Deck *deck = malloc(sizeof(Deck));
     deck->cards = malloc(sizeof(Card) * len); // not allocating useless space
     deck->len = len;
     deck->orig_len = len;
 
     for (j = 0; j < rep; j++) {
          for (i = start; i < end; i++) {
               /// here is the actual trick, remove all the possible cards
               if (to_remove && (i == init_cards[init_idx])) {
                    to_remove--;
                    init_idx++;
               }
               else {
                    deck->cards[idx] = i;
                    idx++;
               }
          }
     }
     return deck;
}
--8<---------------cut here---------------end--------------->8---
Praticamente alloco solo il necessario, e nei due cicli for annidati
aggiungo normalmente a meno che non sia no nella lista di quelle da
rimuovere.
Anche se non è una lista ordinata mi pare che dovrebbe sempre funzionare
comunque, anzi, rettifico!
Avendo più di 4 carte potrebbe già non funzionare, [9,9,9,9,1] per
esempio.
Qualche idea su come tenere quel for? Mi conviene ordinare l'array mi sa...

 writes:
Ecco fatto, l'array lo ordino con qsort quindi posso andare più
tranquillo in fase di rimozione carte.
Mi sembra il 2% più lento ma almeno è più corretto.
Non è il massimo della vita questo triplo ciclo carpiato però, consigli
sul refactoring?
--8<---------------cut here---------------start------------->8---
for (i = start; i < end; i++) {
     j = 0;
     for (;;) {
          while (i == init_cards[init_idx]) {
               j++;
               init_idx++;
          }
          assert(j <= rep);
          if (j < rep) {
               deck->cards[idx] = i;
               idx++;
               j++;
          }
          else
               break;
     }
}
return deck;
--------------cut here---------------end--------------->8---

 meglio infatti) però evito quelle brutture precedenti
Ti conviene tenere ordinato l'elenco delle carte da eliminare. In questo 
modo sai in che ordine le troverai, e basta che fai una unica 
iterazione. Aggiungi ad una ad una le carte nel mazzo (in maniera 
ordinata) e controlli solo di non aggiungere la prima di quelle da 
eliminare. Quando trovi la prima, incrementi un indice nelle carte da 
eliminare e controlli solo per la seconda. Unica accortezza, nel mazzo 
devi mettere le carte in ordine:
1,1,1,1,2,2,2,2,....
invece che 1,2,3,...,1,2,3.
Inoltre, come già ti suggerivo, non credo che hai bisogno di usare 
l'allocazione dinamica. Puoi benissimo mantenere una array statico, 
visto che se capisco bene non hai bisogno di avere una quantità 
indefinita di mazzi in contemporanea.
E.

 E.
Sì mi sembra un'ottima idea, stavo già provando e sembra che funzioni.
Ci guadagno qualcosa con l'allocazione statica come prestazioni?
Tanto finiscono comunque in cache essendo pochi dati no?
Avere delle cose globali in giro mi sta un po' sulle balle...(passando
i puntatori risulta più chiaro chi fa cosa).
Tra l'altro sono un po' fuori allenamento, ma quando voglio fare delle
magie con i puntatori del tipo
--8<---------------cut here---------------start------------->8---
while (*s++ == *k++)
--8<---------------cut here---------------end--------------->8---
il puntatore viene sempre comunque modificato giusto, come si possono
usare questi trucchi nelle funzioni, mi salvo il valore originale?
Ora che ci penso dovrebbero essere variabili locali, ma avevo provato
qualcosa del genere ed era successo un patatrac... boh
E poi perché il mio programma risulta allocare al sistema operativo 328Kb??
Dichiarare come static anche le funzioni può servire a qualcosa nel mio
caso?

 caso?
No, lo static posto nelle dichiarazioni globali ha un significato 
diverso, legato alla visibilità della variabile.
Una variabile dichiarata al di fuori delle funzioni (globalmente) è 
sempre statica. Credo che nel tuo codice non dovresti mai usare la 
keyword "static".
E.

 Perché, quanti te ne aspetteresti?
Beh in teoria alloco 52 interi per il mazzo (anzi qualcosa meno) e 13
interi per la mano considerata, poi c'è il risultato ma insomma a 328
non dovrei arrivaarci..

Ah comunque questo è razz.c:
http://gist.github.com/299108
e questo razz.h
http://gist.github.com/299109
Se avete altri consigli stilistici sono benvenuti.
Non saprei se rimuovere altre malloc possa servire, l'unica operazione
costosa che rimane è
copy_hand, che riinizializza alla mano iniziale ogni volta.
Ma non penso si possa rimuovere, giusto?

>
Mm sto provando ma non riesco a capire come usare il tuo consiglio
Il problema è che a ogni partita devo ripristinare la mano iniziale per
poi aggiungere le carte pescate casualmente.
Adesso faccio praticamente questo
--8<---------------cut here---------------start------------->8---
     for (i = 0; i < simulations; i++) {
          d->len = d->orig_len;
          copy_hand(init_hands[0], h0);
          rank = play(d, nplayers, h0);
          idx = rank_to_result_idx(rank);
          result[idx]++;
     }
--8<---------------cut here---------------end--------------->8---
E quel copy_hand è un po' pesante
--8<---------------cut here---------------start------------->8---
void
copy_hand(Hand *h1, Hand *h2) {
     int i;
     for (i = 0; i < RAZZ_CARDS; i++) {
          h2->cards[i] = h1->cards[i];
     }
     h2->len = h1->len;
     h2->diffs = h1->diffs;
}
--8<---------------cut here---------------end--------------->8---
Tra l'altro ho appena provato a sostituirlo con un memcpy, ma è più
lento, non pensavo!
Comunque in sostanza dovrei dichiarare un array static globale e usare
sempre quello in qualche modo (passandolo a make_hand ad esempio), ma
ogni volta dovrei comunque sempre resettarlo, con un altro array static?

Ho avuto un'ideuzza che o è una grossa cazzata oppure è geniale, il
mazzo come un grosso numero a 64 bit riempito di 1.
Il mazzo intero potrebbe essere
x = 2^53 - 1
Togliere e aggiungere è semplicissimo
x | 2^k
x & ~(2^k)
Pescare a caso è più complicato ma potrei usare il truccone che sta
usando un mio collega, lancio un random tra 52, se trovo bene se no ne
lancio un altro.
Avendo pochissime estrazioni per partita non è un grosso problema, che
dite?


Che dovresti finire di scrivere 'sto programma e vedere quanto è
veloce. Se ti viene in mente qualcosa fai la correzione e rimisuri.

 writes:

Eh eh sì calma, purtroppo per voi ho ancora 2 settimane volendo.
Devo anche fare altro e andrebbe già benissimo, è solo per divertimento
che provo a spemerlo ancora di più.
Comunque ad esempio questo
--8<---------------cut here---------------start------------->8---
void
remove_card_from_int_deck(IntDeck *deck, Card card) {
     *deck =& (~(powl(2, card)));
}
--8<---------------cut here---------------end--------------->8---
si lamenta dicendomi
razz.c:189: error: wrong type argument to bit-complement
Un long non si può complementare?
E' sbagliata la sintassi?
Tra l'altro potrei fare così, make_deck genera un unsigned long (sono 64
bit giusto?), poi le altre funzioni che ci lavorano prendono l'indirizzo
di questo.
Così posso dichiararlo statico e siamo tutti felici e contenti, è
corretto il ragionamento?

 E' sbagliata la sintassi?
devi scrivere (1<<card), invece che powl(2,card)
E.

 Ma non penso si possa rimuovere, giusto?
copy_hand è ridotta all'osso. Comunque le strutture le puoi anche 
copiare con il normale assegnamento.
E.

 E.
Ora vediamo se il deck diventa un intero cancello tutto :)
Ah ottimo non lo sapevo, ma è la stessa cosa in sostanza?

 E.
Non è uguale?
In python è esattamente la stessa cosa andando a vedere i tempi...
Pensavo a una cosa così
--8<---------------cut here---------------start------------->8---
int
remove_card_from_int_deck(IntDeck *deck, Card card) {
     IntDeck orig = *deck;
     long l = powl(2, card);
     *deck = *deck & (~l);
     // I want to return 0 when it it doesn't work
     return !(orig - *deck);
}
--8<---------------cut here---------------end--------------->8---
Non sapendo se ho già pescato o no torno un valore diverso da 0 solo se
il nuovo deck è diverso dall'originale, non sono sicurissimo..
Funziona bene quando c'è ma usando l'estrattore random così fatto toglie
troppo
--8<---------------cut here---------------start------------->8---
Card
get_random_card_from_int_deck(IntDeck *deck, int size) {
     int result;
     Card card;
     do {
          // bug here, too many remotions unneeded
          card = lrand48() % size;
          printf("removing card %d from deck\n", card);
          // insert here a check to verify that the card is actually still there
          // otherwise throw another random number
          result = remove_card_from_int_deck(deck, card);
     } while (!result);
     return card; // which is the last one that has been evaluated
}
--8<---------------cut here---------------end--------------->8---
Se avete git per tenerlo aggiornato basta questo...
git clone git://
github.com/AndreaCrotti/Razz.git
Grazie ragazzi, ho imparato un sacco di cosette ;)

Avevo messo un ! di troppo, comunque ho testato al volo la faccenda e
purtroppo mi dà dei risultati un po' sballati (ma vabbeh ci sarà qualche
erroruccio) e soprattutto non è più veloce, praticamente uguale.
Fare tutte questi shift evidentemente alla lunga costa...

 Non è uguale?
No, (1<<card) è un intero, mentre powl(2,card) è un float.
E.

Mannaggia lo sapevo l'approccio binario era una cazzata...
In sostanza stavo rimuovendo carte da 1 a 52, mentre io naturalmente ho
solo carte da 1 a 13 ripetute 4 volte.
Come si potrebbe gestire la cosa?
L'unico modo mi sembra di andare a provare a rimuovere ogni multiplo
while (! removed)
      try_to_remove(card * k)
Avendo poche estrazioni ci sta pure che devo solo rimuovere carte nelle
prime 13, mmm

Dunque ci sono 2 possibilità.
- estraggo un numero 1-52, lo tolgo dal deck e ritorno NUM % 13 (per
  avere la carta giusta)
- estraggo un numero da 1-13, poi provo a toglierlo per i 4 sottomazzi
La prima l'ho provata e mi sembra molto lento (oltre ad avere risultati
bizzarri) non so se provare anche la seconda o lasciare perdere del
tutto...
Altre idee?
Peccato perché l'idea della manipolazione binaria mi piaceva assai..


Alla fine ho capito e ho riscritto come consigliavi, è rimasta 1 malloc
e una free (su un array che non a priori quanto sarà lungo, anche se
volendo posso anche sovradimensionarlo ma insomma non esageriamo).
E' in effetti il 25% più veloce ma non vorrei aver esagerato con le
variabili globali (passo comunque ancora gli indirizzi)
--8<---------------cut here---------------start------------->8---
static Deck global_deck;
static int num_players;
static int num_simulations;
static Card *to_remove;
static Hand hand_init;
static Hand hand_tmp;
static long result[POSSIBLE_RANKS];
int main(int argc, char *argv[])
{
     init_hand(&hand_init);
     to_remove = malloc(sizeof(Card) * INITIAL_CARDS(num_players));
     check_args(argc, argv);
     qsort(to_remove, INITIAL_CARDS(num_players), sizeof(Card), intcmp);
     loop(&hand_init, result, to_remove);
     output_result(result);
     free(to_remove);
     return 0;
}
void check_args(int argc, char *argv[]) {
     Card card;
     int i, j;
     if (argc < 6)
          usage();
     num_simulations = TO_EXP(atol(argv[1]));
     num_players = atoi(argv[2]);
     // max/min bound for players
     if (num_players > 8 || num_players < 1) {
          fprintf(stderr, "wrong number of players\n");
          usage();
     }
     int exp_args = INITIAL_PLAYER + (INITIAL_OTHER * (num_players - 1)) + 3;
 
     // checking consistency between number of players and arguments
     if (exp_args != argc) {
          fprintf(stderr, "wrong number of cards given\n");
          usage();
     }
     for (i = 3, j = 0; i < argc; i++) {
          card = char_to_card_idx(argv[i][0]);
          if (j++ < INITIAL_PLAYER)
               add_card_to_hand(card, &hand_init);
 
          to_remove[i-3] = card;
     }
}
--8<---------------cut here---------------end--------------->8---
Ho cominciato a "globalizzare" quando ho cominciato a riscrivere
quell'osceno main, in sostanza ho solo aggiunto un'osceno check_args ma
d'altronde è comunque C, è il costo di questa velocità paurosa ;)

 static Hand hand_tmp;
Come ti dicevo, la keyword "static" qui non significa "statico". Se non 
ce la metti comunque la variabile, essendo globale, è necessariamente 
statica, nel senso che ha lo stesso tempo di vita dell'intero programma.
Quindi io non ce l'avrei messa, anche se in questo caso non ti fa alcuna 
differenza.
E.

 E.
Mm no avevo capito che per le funzioni non fa differenza, ma per le
variabili sì..
Infatti passo da 0.8 scarsi a 0,9 secondi abbondanti di esecuzione,
quasi il 15% di differenza solo mettendo lo static..

 quasi il 15% di differenza solo mettendo lo static..
Sto cercando di farti capire che la keyword "static" posta davanti ad 
una variabile globale, non fa quello che pensi.
Togli tutte le occorrenze della parola "static" dal tuo codice sorgente 
e vedrai che l'eseguibile viene identico.
E.

 E.
Eh ma evidentemente il compilatore mette quelle cosuccie in diverse aree
di memoria se trova le variabili, come static, altrimenti non avrei un
tale incremento di prestazioni..
Vedo anche io che non dovrebbe servire a nulla però qualcosa cambia...

 E.
Non sono un genio di assembly ma in effetti il codice assembly generato
è diverso, ad esempio usa leaq invece di movq per result mettendo lo static.
--8<---------------cut here---------------start------------->8---
leaq	_result(%rip), %rdi
movq	_result@GOTPCREL(%rip), %rdi
--8<---------------cut here---------------end--------------->8---

Andrea Crotti ha scritto:

Qualcosa cambia perché hai dichiarato le variabili globali, e non 
locali. Arrivato a questo punto, se vuoi vederci chiaro, è il momento 
giusto di studiarti un manuale.
E.

Andrea Crotti ha scritto:

Può darsi che le variabili "static" vengano trattate diversamente da 
alcuni compilatori. Ma non è questa modifica che ti cambia l'efficienza 
del codice.
E.

 giusto di studiarti un manuale.
No non ci siamo capiti...
Variabili globali e static -> 0.79s
Variabili globali non static -> 0.92s

Andrea Crotti ha scritto:

Mi sembra molto strano... a meno che il compilatore non abbia difficoltà 
a fare certe ottimizzazioni per le variabili globali non "static"...
E.

 wrote:

Ti posso ripetere, per l'ennesima volta, che non sei te a dover
ottimizzare ma bensì il compilatore? Il compilatore si aspetta che te
scriva il codice bene specificando *esattamente* quello che ti serve a
livello di linguaggio. Se inizi a scrivere codice casuale il
compilatore non capisce, s'incasina e inizia a comportarsi in maniera
incomprensibile per i più. Tu vedi di scrivere per bene il codice e
vedrai che il programma finale sarà il migliore.
Ti posso ripetere, poi, ancora una volta che il concetto di micro-
ottimizzazione è una str**zata? Non siamo più negli anni '80: quando
non serve non si fa, e mi sembra chiaro che a te non serve.
Ciao!

 Ciao!
Allora calma non ci alteriamo...
La definizione di static per le variabili non implica alcun incremento
di prestazioni, ma può darsi che sia un effetto collaterale del fatto
che è visibile solo all'interno del mio file.
Non è che sia codice casuale, è perfettamente valido e non insensato
dichiararle come static.
In generale non ottimizzo un tubo (a parte gli algoritmi) ma in questo
caso lo scopo è proprio quello praticamente, quindi ben venga
un'esecuzione più veloce...