Gioco della vita di Conway: da Python a C
Vi ricordate il post sul gioco della vita di Conway (life)? Avevo scritto un algoritmo che oltre a implementare questo giochino (vedi Gioco della vita di Conway), ricercasse, con un bruteforce, tutte le figure che si ripetevano. Ora l’ho riscritto in C, supportando come parametri anche shift e step (sono un metodo grezzo per permettere un balance tra cpu/pc lanciando processi con parametri diversi) e un metodo economico (ma stupido) per il calcolo delle figure successive (vedere la variabile dirty e la nota n. 1). Quest’ultima caratteristica rende l’algoritmo intrinsecamente più veloce rispetto a quello che avevo scritto in Python, per cui le prestazioni sono sfasate (penso che questo trucco possa rendere il codice cinque volte più veloce mediamente, ma devo ancora studiare meglio gli effetti).
Tenendo conto di questo, il rapporto tra il programma in C, il programma Python convertito in C++ con Shedskin, la versione che usa Psyco, e la versione “classica”, è: (approssimativamente) 1:10:70:300. Ripeto: devo ancora applicare l’algoritmo nuovo in Python, e pare che gli ultimi tre dati si possano dividere per cinque circa, portando la versione Shedskin nello stesso ordine di grandezza della versione in C (questo sottolinea la validità del progetto), mentre la versione Pythonica sarebbe meno di due ordini di grandezza più lenta.
Il codice è questo 
Non lo commenterò passo passo, in quanto mi pare molto leggibile e simile a quello della versione in Python. Oltretutto, è già lungo di suo, quindi eviterei di riprendere inutilmente pezzi di codice per commentare la loro funzione 
Ho tolto la licenza… Tenete conto che, ovviamente, è sotto GPLv3:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 | #include <stdio.h> #include <stdlib.h> void clean(int *p, int dim) { int c; for (c=0; c<=dim; c++, p++) *p = 0; } void clone(int *from, int *to, int dim) { int c; for (c=0; c<=dim; c++) to[c] = from[c]; } int compare(int *from, int *to, int dim) { int c; for (c=0; c<=dim; c++) { if (*to != *from) return 0; from++; to++; } return 1; } int main(int argc, char *argv[]) { if ((argc != 3) && (argc != 5)) { printf("Usage: %s [rows] [columns] [shift] [step]\n", argv[0]); return 1; } const int rows = atoi(argv[1]); const int columns = atoi(argv[2]); const int dim = rows*columns; int shift = 0; int step = 1; if (argc == 5) { shift = atoi(argv[3]); step = atoi(argv[4]); } if (shift >= step) { printf("shift/step are invalid.\n"); return 2; } int clean_stage[dim]; int *clean_p = &clean_stage[0]; clean(clean_p, dim); int alpha_stage[dim]; int *alpha_p = &alpha_stage[0]; clean(alpha_p, dim); int beta_stage[dim]; int *beta_p = &beta_stage[0]; clean(beta_p, dim); int first_stage[dim]; int *first_p = &first_stage[0]; clean(first_p, dim); int i; int dirty; int p = dim-1; int r, sum, row, column, row_p, row_n; r = 0; while (1) { p = dim-1; while (first_stage[p] == 1) p--; first_stage[p] = 1; for (p++; p<dim; p++) first_stage[p] = 0; if (r%step != shift) { r++; continue; } else r = 0; clone(first_p, alpha_p, dim); dirty = 0; while (dirty != 18) { /* [1] Nota a fine programma... */ for (i=0; i<dim; i++) { row = i/columns; column = i%columns; if (row == 0) { row_n = i+columns; if (column == 0) sum =\ alpha_stage[i+1] +\ alpha_stage[row_n] +\ alpha_stage[row_n+1]; else if (column < columns-1) sum =\ alpha_stage[i-1] +\ alpha_stage[i+1] +\ alpha_stage[row_n-1] +\ alpha_stage[row_n] +\ alpha_stage[row_n+1]; else sum = \ alpha_stage[i-1] +\ alpha_stage[row_n-1] +\ alpha_stage[row_n]; } else if (row < rows-1) { row_p = i-columns; row_n = i+columns; if (column == 0) sum =\ alpha_stage[row_p] +\ alpha_stage[row_p+1] +\ alpha_stage[i+1] +\ alpha_stage[row_n] +\ alpha_stage[row_n+1]; else if (column < columns-1) sum =\ alpha_stage[row_p-1] +\ alpha_stage[row_p] +\ alpha_stage[row_p+1] +\ alpha_stage[i-1] +\ alpha_stage[i+1] +\ alpha_stage[row_n-1] +\ alpha_stage[row_n] +\ alpha_stage[row_n+1]; else sum =\ alpha_stage[row_p-1] +\ alpha_stage[row_p] +\ alpha_stage[i-1] +\ alpha_stage[row_n-1] +\ alpha_stage[row_n]; } else { row_p = i-columns; if (column == 0) sum =\ alpha_stage[row_p] +\ alpha_stage[row_p+1] +\ alpha_stage[i+1]; else if (column < columns-1) sum =\ alpha_stage[row_p-1] +\ alpha_stage[row_p] +\ alpha_stage[row_p+1] +\ alpha_stage[i-1] +\ alpha_stage[i+1]; else sum =\ alpha_stage[row_p-1] +\ alpha_stage[row_p] +\ alpha_stage[i-1]; } beta_stage[i] = 0; switch (sum) { case 2: beta_stage[i] = alpha_stage[i]; break; case 3: beta_stage[i] = 1; } } if (compare(beta_p, first_p, dim)) { for (i=0; i<dim-1; i++) printf("%d ", first_stage[i]); printf("%d\n", first_stage[dim-1]); break; } if (compare(alpha_p, beta_p, dim)) break; clone(beta_p, alpha_p, dim); dirty++; } if (compare(first_p, clean_p, dim)) break; } return 0; } /* Nota [1]: Per non comparare sempre lo stage corrente con quelli precedenti, ho creato una modalità "stupida" di computazione. Il valore 18 indica che non è necessario calcolare ulteriori stages se non si è ancora usciti dal ciclo, in quanto pare che non ci siano figure nel primo stadio, che si ripetano dopo il 18esimo stadio. */ |
P.S. Ho trovato una implementazione di questo giochino, molto carina, (senza bruteforce ovviamente) nella directory di Python 3.1.1 (ma penso si trovi anche in versioni precedenti) che usa curses, sotto Python-3.1.1/Demo/curses/life.py
