Je comprend mieux ^^. Mais par contre j'ai du mal à saisir comment on l'utilise...

Ricocotam a écrit:

Je comprend mieux ^^. Mais par contre j'ai du mal à saisir comment on l'utilise...

Hum, c'est bien de mon code dont tu parles ?

Si oui, j'explique^^

La constante N_GEN, détermine jusqu'à quelle génération on calcule.

La constante N_CELLS bah c'est le nombre de cellules(le nombre de cellules sur une ligne quoi)

Enfin, c'est dans le main que tu définies la configuration de départ. C'est le tableau cells.

Ici, il est juste renseigné avec une cellule centrale vivante.


Désolé que ce soit aussi chiant, à utiliser et tester. 

 

Je ne parlais pas du tiens en particulier :). En fait dans tout les codes je ne comprend pas comment est utilisé la règle (30 ou 201 je m'en fiche ^^). Notamment dans ceux de Pouet et.... (désolé :/).

Au passage, j'ai essayé de regarder ton code mais il est difficilement compréhensible, aère le et commente le un peu

Nelxiost a écrit:

Etrange : chez moi, c'est beaucoup plus lent (1730/570 comparé à 1050/440) ... J'ai loupé quelque chose ?

Bizarre, j'ai supprimé des calculs et j'ai fait un accès direct dans la table.

Tu peux poster le code assembleur obtenu ? Les 2 en fait, celui-là et celui sans la table.

Tu m'en demandes un peu trop là !

Voilà les deux codes : l'original ; la table.

Ricocotam a écrit:

Je comprend mieux ^^. Mais par contre j'ai du mal à saisir comment on l'utilise...

Quand tu as une règle X, tu veux pouvoir la traduire dans le comportement des cellules de ton jeu. Il faut d'abord que tu écrives X en binaire, ce qui donnera un nombre comme ça : ABCDEFGH (chaque lettre représente un bit). Le bit A sera celui qui définira le comportement d'une cellule dont le voisinage est "111" (les deux voisins ainsi que la cellule en question sont vivants). Le bit B, quant à lui, définira la même chose avec un voisinage "110". Et ainsi de suite, jusqu'au bit H qui correspond au voisinage "000" (les trois cellules mortes). A chaque génération, il faut donc vérifier le voisinage de chaque cellule, et faire évoluer celle-ci à partir de la règle. Tu regardes le bit correspondant à son voisinage, et tu lui assignes la vie ou la mort en fonction de ce bit.

Haaan !

J'avais pas compris qu'il y avait un ordre ^^. Merci beaucoup

Salut à tous !

Joyeux réveillon, tout ce que vous voulez, POUET N'EST PAS MORT ! 'Content de te revoir Pouet_forever.

Et merci beaucoup de ta participation (ahlala, si tu avais utilisé un autre pseudo, je t'aurais reconnu direct'). Merci à toi aussi GurneyH, et à tout les autres

Bref, avant d'avoir rédigé l'énoncé de cet exo', j'avais déjà fais ça pour la règle de 30 :

typedef struct
{
    int tab[3];
    int boolean;
} Rule;

int cmp(int *tab1, int *tab2, int len)
{
    int i;

    for(i = 0; i < len; i++)
    {
        if(tab1[i] != tab2[i])
            return 0;
    }

    return 1;
}

int *next(int *state, int len, Rule rule[])
{
    int *ret = calloc(len, sizeof(int));
    int tmp[3] = {0};
    int i, j;

    for(i = 0; i < len-2; i++)
    {
        tmp[0] = state[i];
        tmp[1] = state[i+1];
        tmp[2] = state[i+2];

        for(j = 0; j < 8; j++)
        {
            if(cmp(rule[j].tab, tmp, 3))
            {
                ret[i+1] = rule[j].boolean;
            }
        }
    }

    free(state);

    return ret;
}

Le main est absolument dégueulasse, je vous l'épargne pour cette fois-ci.

Fuck off la manipulation de bits, j'étais déjà content de moi avec mes petits tableaux. On verra ce soir si j'ai le courage de transformer l'écriture décimale d'un nombre en binaire (chose que je n'ai jamais faîte), et de mettre le tout dans mon tableau de règles.

Et encore une fois, merci pour toutes ces participations !

Edit : Pour le moment, je remplis mon tableau de règles comme ceci :

    Rule rule[8] = {{{1,1,1}, 0},
                    {{1,1,0}, 0},
                    {{1,0,1}, 0},
                    {{1,0,0}, 1},
                    {{0,1,1}, 1},
                    {{0,1,0}, 1},
                    {{0,0,1}, 1},
                    {{0,0,0}, 0}};

-
Edité par paraze 24 décembre 2013 à 15:02:32

paraze a écrit:

Et encore une fois, merci pour toutes ces participations !

Ca, c'est uniquement grâce à moi !

paraze a écrit:

Le main est absolument dégueulasse, je vous l'épargne pour cette fois-ci.

Fuck off la manipulation de bits, j'étais déjà content de moi avec mes petits tableaux. On verra ce soir si j'ai le courage de transformer l'écriture décimale d'un nombre en binaire (chose que je n'ai jamais faîte), et de mettre le tout dans mon tableau de règles.

Moi, j'aurais bien aimé voir ce main, justement ! Et tu n'es pas obligé de faire une conversion de base, à moins que tu veuilles pouvoir entrer le numéro de la règle en décimal.

J'ai rapidement lu ton code, et je pense avoir trouvé une erreur : tu ne modifies jamais ret[0] et ret[len-1]. A moins que ça ne soit voulu et que ton tableau comprenne deux cases de plus pour traiter les bords... Je ne peux pas savoir : je n'ai pas le main ! Mais si c'est effectivement le cas, c'est une idée intéressante.

Moi, j'aurais bien aimé voir ce main, justement ! Et tu n'es pas obligé de faire une conversion de base, à moins que tu veuilles pouvoir entrer le numéro de la règle en décimal.

C'est un bon prétexte pour enfin je m'y mettre à cette foutu conversation, donc bon.

moins que ça ne soit voulu et que ton tableau comprenne deux cases de plus pour traiter les bords

En fait, je pensais que c'était normal, et que ce truc était faux (ou du moins, était coupé pour que ça fasse plus joli). La représentation graphique de la règle montre bien que c'est la case du milieu qui risque de changer d'état. S'il y avait ça, d'accord :

111 110
1   0

Mais ce n'est pas le cas. T'en penses quoi ?

Sinon, j'ai vite-fait arrangé le main (et la fonction d'affichage par la même occasion, pour faire un truc à la nodrak), et ça donne quelque chose comme ça :

#include <stdio.h>
#include <stdlib.h>

#define N 150
#define M 75

typedef struct
{
    int tab[3];
    int boolean;
} Rule;

int cmp(int *tab1, int *tab2, int len)
{
    int i;

    for(i = 0; i < len; i++)
    {
        if(tab1[i] != tab2[i])
            return 0;
    }

    return 1;
}

void print_tab(int *tab, int len)
{
    int i;

    for(i = 0; i < len; i++)
    {
        printf("%c", (tab[i]) ? 'X' : ' ');
    }

    puts("");
}

int *next(int *state, int len, Rule rule[])
{
    int *ret = calloc(len, sizeof(int));
    int tmp[3] = {0};
    int i, j;

    for(i = 0; i < len-2; i++)
    {
        tmp[0] = state[i];
        tmp[1] = state[i+1];
        tmp[2] = state[i+2];

        for(j = 0; j < 8; j++)
        {
            if(cmp(rule[j].tab, tmp, 3))
            {
                ret[i+1] = rule[j].boolean;
            }
        }
    }

    free(state);

    return ret;
}

int main(void)
{
    Rule rule[8] = {{{1,1,1}, 0},
                    {{1,1,0}, 0},
                    {{1,0,1}, 0},
                    {{1,0,0}, 1},
                    {{0,1,1}, 1},
                    {{0,1,0}, 1},
                    {{0,0,1}, 1},
                    {{0,0,0}, 0}};

    int *tab = NULL;
    int i;

    tab = calloc(N, sizeof(int));

    tab[N/2] = 1;

    print_tab(tab, N);

    for(i = 0; i < M; i++)
    {
        tab = next(tab, N, rule);
        print_tab(tab, N);
    } 

    free(tab);

    return 0;
}</stdlib.h></stdio.h>

-
Edité par paraze 24 décembre 2013 à 16:06:07

paraze a écrit:

En fait, je pensais que c'était normal, et que ce truc était faux (ou du moins, était coupé pour que ça fasse plus joli). La représentation graphique de la règle montre bien que c'est la case du milieuqui risque de changer d'état. S'il y avait ça, d'accord :

111 110
1   0

Mais ce n'est pas le cas. T'en penses quoi ?

En fait, ça dépend uniquement de notre propre conception du jeu :

Ricocotam a écrit:

Par contre, On considère une cellule inexistante (bout de tableau) comme morte ? vivante ? ou on considère une boucle ?

Si tu considères le jeu comme borné et que les bords sont inactifs et se comportent comme des cellules mortes (en permanence), alors ton code est faux et ton image est bonne. Si tu considères que les bords sont inactifs mais se comportent comme des cellules vivantes, ton code est faux, tout comme tous les autres codes présentés ici. Dans le mien, par exemple, il faudrait modifier la manipulation de bits pour ajouter un quelque chose au début et à la fin de la boucle (qui ne pourrait d'ailleurs plus aller jusqu'à la dernière cellule).

Si tu considères que les bords sont actifs, ça revient à faire un tableau avec deux cases de plus, et on revient à la même question, puisque les bords sont maintenant des cellules.

Enfin, si tu considères qu'il n'y a pas de bord et que les cellules du début et de la fin sont voisines, ça résout de suite la question, mais c'est un peu plus compliqué à coder (à peine plus).

Dans ton code, les deux cases aux extrémités de ton tableau représentent des bords inactifs dont l'état est spécifié au départ (ici, c'est 0 à cause du calloc). D'ailleurs, si je ne me trompe pas, tu obtiendrais la même image que celle de ton lien en mettant N = 33 et M = 15. Tu auras juste deux colonnes de plus aux extrémités, toujours blanches.

Nelxiost a écrit:

paraze a écrit:

En fait, je pensais que c'était normal, et que ce truc était faux (ou du moins, était coupé pour que ça fasse plus joli). La représentation graphique de la règle montre bien que c'est la case du milieuqui risque de changer d'état. S'il y avait ça, d'accord :

111 110
1   0

Mais ce n'est pas le cas. T'en penses quoi ?

En fait, ça dépend uniquement de notre propre conception du jeu :

Ricocotam a écrit:

Par contre, On considère une cellule inexistante (bout de tableau) comme morte ? vivante ? ou on considère une boucle ?

Si tu considères le jeu comme borné et que les bords sont inactifs et se comportent comme des cellules mortes (en permanence), alors ton code est faux et ton image est bonne. Si tu considères que les bords sont inactifs mais se comportent comme des cellules vivantes, ton code est faux, tout comme tous les autres codes présentés ici. Dans le mien, par exemple, il faudrait modifier la manipulation de bits pour ajouter un quelque chose au début et à la fin de la boucle (qui ne pourrait d'ailleurs plus aller jusqu'à la dernière cellule).

Si tu considères que les bords sont actifs, ça revient à faire un tableau avec deux cases de plus, et on revient à la même question, puisque les bords sont maintenant des cellules.

Enfin, si tu considères qu'il n'y a pas de bord et que les cellules du début et de la fin sont voisines, ça résout de suite la question, mais c'est un peu plus compliqué à coder (à peine plus).

Dans ton code, les deux cases aux extrémités de ton tableau représentent des bords inactifs dont l'état est spécifié au départ (ici, c'est 0 à cause du calloc). D'ailleurs, si je ne me trompe pas, tu obtiendrais la même image que celle de ton lien en mettant N = 33 et M = 15. Tu auras juste deux colonnes de plus aux extrémités, toujours blanches.

On peut aussi considérer une partie active et deux parties inactives à gauche et à droite s'étendant à l'infini, c'est ce que j'avais fait dans mon programme.

Exemple pattern 01 = ...00001111... à T0

Pour T1 seul 000111 a besoin d'être pris en compte pour le calcul, le reste des cases peut être recopié à partir de la 1ère et la dernière case calculée (le résultat pour 000 ou 111 étant toujours le même quelle que soit la règle).

On a juste besoin de gérer pour l'affichage un nombre de cases égal au nombre de cases de la partie active à T0 + 2 fois le nombre de générations à calculer (la partie active n'évoluera pas au delà de cette taille).

Le "truc" de Paraze est vrai également dans ce cas-là.

EDIT: article avec des règles intéressantes à tester

-
Edité par fromvega 25 décembre 2013 à 22:01:56

@Nelxiost : je comprends pas trop cette syntaxe assembleur... je préfère la syntaxe intel !

Je vais regarder chez moi quand j'aurai un peu de temps.

Ouesh paraze !

Genre si j'avais pris un autre pseudo tu m'aurais reconnu ? xD

Alalalalala

Joyeux noël à tous !

fromvega a écrit:

Pour la génération 1 seul 000111 a besoin d'être pris en compte pour le calcul, le reste des cases peut être recopié à partir de la 1ère et la dernière case calculée

Je n'ai pas compris.

(le résultat pour 000 ou 111 étant toujours le même quelle que soit la règle).

Ah ? Soit je n'ai encore une fois pas compris, soit tu te trompes : la règle prend bien en compte les cas 000 et 111.

On a juste besoin de gérer pour l'affichage un nombre de cases égal au nombre de cases de la partie active + 2 fois le nombre de générations à calculer (la partie active n'évoluera pas au delà de cette taille).

Je pense que tu as mal compris ce que j'ai définis par bord actif ou inactif... Tel que je l'ai présenté, un bord inactif ne change jamais. Ce n'est pas une cellule, c'est juste un bord qui peut être considéré comme un voisin pour les autres cellules. Un cellule, par contre, ne peut pas être inactive : par définition, elle doit changer d'état selon une règle prédéfinie. En revanche, elle peut être morte.

Nelxiost a écrit:

Si tu considères le jeu comme borné et que les bords sont inactifs et se comportent comme des cellules mortes (en permanence)

On peut effectivement considérer un bord inactif comme une cellule morte ou vivante, mais qui ne change pas d'état. Faire cela ne sert qu'à appliquer la règle aux vraies cellules voisines des bords.

J'ai différencié les bords actifs et inactifs pour montrer qu'un bord actif est en fait une cellule, puisqu'il correspondrait à la définition d'une cellule (avoir un état, et changer d'état en fonction d'une règle). Cela revient à dire qu'il est nécessaire d'avoir des bords inactifs aux extrémités du "plateau" de cellules.

fromvega a écrit:

On peut aussi considérer une partie active et deux parties inactives à gauche et à droite s'étendant à l'infini.

D'après ce que j'ai pu déduire de ton message, tu veux considérer une partie continue des cellules comme vivantes ou mortes au début, et le reste comme mort, jusqu'à l'infini. En fait, ça revient à mettre les bords inactifs à l'infini. Ils existent quand même, on ne peux juste pas les atteindre en un nombre de générations fini. Et c'est équivalent à les mettre aux extrémités de la partie des cellules définie comme ça : [première cellule vivante - nombre de générations; dernière cellule vivant + nombre de générations]. En gros, un bord sera placé à n+1 cases avant la première cellule vivante, n étant le nombre de générations, et l'autre sera placé à n+1 cases après la dernière cellule vivante.

-
Edité par Nelxiost 25 décembre 2013 à 22:15:09

@nexiost:

J'ai du me faire mal comprendre ...000111... Pour moi c'est une infinité de 0 à gauche et une infinité de 1 à droite, il n'y a pas de bord. Pour la génération suivante tu as juste besoin de calculer la partie centrale, le calcul du reste des cases à droite et à gauche sera le même que la 1ère et la dernière case recalculée (une suite infinie de 0 deviendra une suite infinie de 1 ou restera une suite de 0 suivant la règle, dans le lien que j'ai donné tu vois que certaines règles alternent entre une infinité de 1 et de 0 à chaque génération).

Pour la règle 30

000 Donne 0

111 Donne 0 aussi

Mais je ne disais pas que 000 et 111 donnent la même chose pour toutes les règles bien entendu.

Simplement la partie centrale à calculer (qu'on peut appeler active, significative ou autre) peut croître à chaque génération de 1 case à droite et à gauche au maximum (tu le vois sur l'image de Paraze par exemple, la zone à calculer deviendra plus large à chaque génération avec la règle 30 pour un pattern ...010... initial).

Pour finir et bien clarifier les choses je suis d'accord avec l'ensemble des interprétations que tu donnes, la mienne est simplement une interprétation de plus.

-
Edité par fromvega 25 décembre 2013 à 22:30:49

D'accord, je vois ce que tu veux dire ; et le dernier paragraphe de mon dernier message explique que ma représentation comprend bien ton cas, à une chose près : soit on simplifie en disant que les bords ne sont pas atteignables et qu'on ne calcule l'état des cellules voisines, soit on ajoute que les bords peuvent aussi être, en permanence, à l'état de la cellule voisine. On a donc trois cas pour les bords (je ne parle plus des bords actifs ou inactifs) : toujours considérés vivants, toujours considérés morts, ou considérés au même état que la cellule d'à côté.

Ca résume assez bien les possibles règles concernant la forme du plateau (en comptant la possibilité de faire une boucle).

Bon, j'ai regardé un peu les 2 codes assembleurs. Je ne vois pas pourquoi la table est plus lente chez toi, chez moi le code est censé être plus rapide (il l'est, mais pas de bueacoup...).

Voilà les 2 codes obtenus (juste la ligne qui diffère) :

La ligne : s[j] = (((rule & 0xFF) >> n) & 1) + '0';

mov    eax,DWORD PTR [ebp-0x34]
mov    edx,DWORD PTR [ebp-0x28]
and    edx,0xff
mov    esi,DWORD PTR [ebp-0x38]
mov    ecx,esi
shr    edx,cl
and    dl,0x1
add    dl,0x30
mov    BYTE PTR [ebp+eax-0x21],dl

La ligne : 

s[j] = table[n];

mov    eax,DWORD PTR [ebp-0x3c]
mov    edx,DWORD PTR [ebp-0x40]
mov    edx,DWORD PTR [ebp+edx*4-0x60]
mov    BYTE PTR [ebp+eax-0x29],dl

Je vais tenter de décrypter tes codes assembleurs, mais je promets rien.

Il me semble que les seules lignes qui changent entre les appels à clock() sont ici :

movzbl  %al, %edx       // original, ligne 59
movl    52(%esp), %eax
movl    %eax, %ecx
shrl    %cl, %edx
movl    %edx, %eax
andl    $1, %eax
addl    $48, %eax

movl    24(%esp,%eax,4), %eax  // table, ligne 98

En tout cas, entre les labels L5 et L3. Mais vu que je ne connais pas les instructions, je ne peux pas aller plus loin.

Edit : en fait, en comparant, tes codes semblent identiques (sans les deux premières et la dernière lignes de tes codes). Par contre, la première instruction est différente...

-
Edité par Nelxiost 26 décembre 2013 à 23:12:02

Non, ils ne sont pas identiques. Les 2 codes font littéralement ce que le code en C fait.

mov    eax,DWORD PTR [ebp-0x34] // mets 'j' dans eax
mov    edx,DWORD PTR [ebp-0x28] // mets 'rule' dans edx
and    edx,0xff // instruction &OxFF
mov    esi,DWORD PTR [ebp-0x38]
mov    ecx,esi
shr    edx,cl // décalage de 1 à droite >> 1
and    dl,0x1 // &1
add    dl,0x30 // + '0'
mov    BYTE PTR [ebp+eax-0x21],dl // affectation

Dans la deuxième j'ai juste une affectation, aucun calcul.

Pour ton code, faut que je regarde, il doit manquer quelques lignes 'utiles'.

Pardon, je voulais dire "identiques aux miens". Et les instructions qui diffèrent :

movzbl  %al, %edx

and    edx,0xff

Pour être complet ça doit être ça (je suppose) :

movl    48(%esp), %eax // mets 'rule' dans eax
movzbl  %al, %edx // fais &0xFF sur eax et le met dans edx (charge juste les 8bits en fait)
movl    52(%esp), %eax // mets 'n' dans eax
movl    %eax, %ecx
shrl    %cl, %edx // décale les bits ">>n"
movl    %edx, %eax
andl    $1, %eax // &1
addl    $48, %eax // +'0'
leal    27(%esp), %ecx // 's'
movl    56(%esp), %edx // 'j'
addl    %ecx, %edx // s[j]
movb    %al, (%edx) // s[j] = ...

movl    84(%esp), %eax // 'n'
movl    24(%esp,%eax,4), %eax // 'table[n]'
leal    59(%esp), %ecx // 's'
movl    88(%esp), %edx // 'j'
addl    %ecx, %edx // 's[j]'
movb    %al, (%edx) // s[j] = table[n]

Tout ça pour dire que je ne vois pas pourquoi le code est plus long.

Tu es sûr d'avoir compilé avec les mêmes options et sur les mêmes chaînes ?

Certain.

Je ne sais pas si c'est en rapport, mais le code avec la table m'indique un warning pour chaque ligne de l'initialisation de la table :

warning: initializer element is not computable at load time

Du coup, j'ai essayé avec ce code-là :

int main(void) {
    char s[] = "000001100000";
    unsigned rule = 0x1E;
    unsigned ngen = 10000000;
    unsigned i, j, n;
    unsigned table[8];
    for (i = 0; i < 8; i++) {
        table[i] = ((rule >> i) & 1) + '0';
    }

    clock_t t = clock();

    for (i = 0; i < ngen; i++) {
        n = (s[0] - '0') << 1;
        for (j = 0; s[j]; j++) {
            n = ((n << 1) | (s[j + 1] ? (s[j + 1] - '0') : 0)) & 0x7;
            s[j] = table[n];
        }
    }

    printf("%f", (double) clock() - t);
    return 0;
}

J'obtiens une légère amélioration : 1580 en moyenne contre 1730 avant. Mais c'est encore loin du 1050 sans la table.

Et en essayant de déclarer table en char ? Pour éviter une conversion implicite ligne 17.

Cela m'étonnerait que ça explique la différence complètement, mais bon...

EDIT: le test sur la fin de chaine dans la boucle j peut être évité aussi en faisant une itération de moins

  l = strlen(s)-1;
  for (i = 0; i < ngen; i++) {
    n = (s[0] - '0') << 1;
    for (j = 0; j < l; j++) {
      n = ((n << 1) | (s[j + 1]-'0')) & 0x7;
      s[j] = table[n];
    }
    s[j] = table[(n << 1) & 0x7];
  }

-
Edité par fromvega 28 décembre 2013 à 12:37:13

En fait, c'est pire !

En déclarant table en char, je me retrouve avec un temps d'environ 1640 au lieu de 1580.

J'ai essayé en déclarant s comme ça pour que ça colle au type de table :

unsigned s[] = {'0', '0', '0', '0', '0', '1', '1', '0', '0', '0', '0', '0', '\0'};

J'ai une légère amélioration (environ 1430)... J'avoue ne pas comprendre ce qu'il se passe.

-
Edité par Nelxiost 28 décembre 2013 à 12:30:44

Le warning c'est à cause du 'rule' qui n'est pas une constante à la compilation. Essaye de le déclarer en 'static', ça devrait faire disparaître le warning.

static unsigned rule = 0x1E;

Essaye de compiler en 32 bits (option -m32 avec gcc) et dis moi ce que tu as.

La déclaration static ne change rien : toujours le même warning. Et l'option pour compiler en 32 bits (ce que je fais déjà, je pense) ne change rien au résultat non plus.

Nelxiost a écrit:

La déclaration static ne change rien : toujours le même warning. Et l'option pour compiler en 32 bits (ce que je fais déjà, je pense) ne change rien au résultat non plus.

Tu compiles peut-être en norme c89 par défaut (c'est le cas si tu utilises le flag -ansi), si tu rajoutes l'option pour compiler en c99 ? L'initialisation de la table avec rule devrait passer sans warning.

-std=c99

EDIT: je reproduis le warning avec les flags ci-dessous

$ gcc -c -ansi -Wall -pedantic testc.c
testc.c: In function 'main':
testc.c:11: warning: initializer element is not computable at load time
testc.c:12: warning: initializer element is not computable at load time
testc.c:13: warning: initializer element is not computable at load time
testc.c:14: warning: initializer element is not computable at load time
testc.c:15: warning: initializer element is not computable at load time
testc.c:16: warning: initializer element is not computable at load time
testc.c:17: warning: initializer element is not computable at load time
testc.c:19: warning: initializer element is not computable at load time
$

 En remplaçant -ansi par -std=c99 ça passe sans warning

$ gcc -c -std=c99 -Wall -pedantic testc.c
$

-
Edité par fromvega 29 décembre 2013 à 10:15:04

Ah, oui, je compilais en C89. En passant en C99, ça enlève les warnings, mais toujours est-il que ça n'améliore pas la vitesse d'exécution.

En revanche, je n'ai vu cet edit de fromvega que maintenant :

fromvega a écrit:

EDIT: le test sur la fin de chaine dans la boucle j peut être évité aussi en faisant une itération de moins

  l = strlen(s)-1;
  for (i = 0; i < ngen; i++) {
    n = (s[0] - '0') << 1;
    for (j = 0; j < l; j++) {
      n = ((n << 1) | (s[j + 1]-'0')) & 0x7;
      s[j] = table[n];
    }
    s[j] = table[(n << 1) & 0x7];
  }

Par curiosité, j'ai du tester... Ca donnait une bonne amélioration, mais pas suffisante. J'ai essayé en déclarant s unsigned (ce qui améliorait aussi la vitesse), et ça m'a donné un résultat entre 60 et 70. Comparé à environ 1500, ça fait une énorme amélioration. Voilà le code pour essayer :

int main(void) {
    unsigned s[] = {'0', '0', '0', '0', '0', '1', '1', '0', '0', '0', '0', '0', '\0'};
    static unsigned rule = 0x1E;
    unsigned ngen = 10000000;
    unsigned i, j, n;
    unsigned table[8] = {
        (rule & 1) + '0',
        ((rule >> 1) & 1) + '0',
        ((rule >> 2) & 1) + '0',
        ((rule >> 3) & 1) + '0',
        ((rule >> 4) & 1) + '0',
        ((rule >> 5) & 1) + '0',
        ((rule >> 6) & 1) + '0',
        ((rule >> 7) & 1) + '0'
        };

    clock_t t = clock();

    unsigned l = strlen((char*)s) - 1;
    for (i = 0; i < ngen; i++) {
        n = (s[0] - '0') << 1;
        for (j = 0; j < l; j++) {
            n = ((n << 1) | (s[j + 1]-'0')) & 0x7;
            s[j] = table[n];
        }
        s[j] = table[(n << 1) & 0x7];
    }

    printf("%f", (double) clock() - t);
    return 0;
}

A priori il y a un problème avec le calcul de l, moi il m'affiche 0 comme calculé ci-dessus. Donc en fait il n'exécute pas la boucle interne d'où les 60/70ms.

J'ai tenté une version qui synthétise tous les cas avec des #define:

ZCELLULAR_TABLE on utilise une table

ZCELLULAR_UNSIGNED on utilise des unsigned int au lieu des char

#include <stdio.h>
#include <string.h>
#include <time.h>

int main(void) {
#ifdef ZCELLULAR_UNSIGNED
  unsigned s[] = { '0','0','0','0','0','1','1','0','0','0','0','0','\0' };
#else
  char s[] = "000001100000";
#endif
  unsigned rule = 0x1E;
  unsigned ngen = 10000000;
  unsigned l, i, j, n;
#ifdef ZCELLULAR_TABLE
#ifdef ZCELLULAR_UNSIGNED
  unsigned table[8] = {
#else
  char table[8] = {
#endif
    (rule & 1) + '0',
    ((rule >> 1) & 1) + '0',
    ((rule >> 2) & 1) + '0',
    ((rule >> 3) & 1) + '0',
    ((rule >> 4) & 1) + '0',
    ((rule >> 5) & 1) + '0',
    ((rule >> 6) & 1) + '0',
    ((rule >> 7) & 1) + '0'
  };
#endif

  clock_t t = clock();

  for (l = 0; s[l]; l++);
  l--;

  for (i = 0; i < ngen; i++) {
    n = (s[0] - '0') << 1;
    for (j = 0; j < l; j++) {
      n = ((n << 1) | (s[j + 1] - '0')) & 0x7;
#ifdef ZCELLULAR_TABLE
      s[j] = table[n];
#else
      s[j] = ((rule >> n) & 1) + '0';
#endif
    }
#ifdef ZCELLULAR_TABLE
    s[j] = table[(n << 1) & 0x7];
#else
    s[j] = ((rule >> ((n << 1) & 0x7)) & 1) + '0';
#endif
  }

  printf("%lu", clock() - t);
  return 0;
}

Il y a donc 4 cas, voici les résultats chez moi sur une moyenne de 10 essais avec chaque cas:

- Sans table, avec char : entre 650 et 700 ms

- Avec table et char : idem

- Avec table et unsigned int : idem

- Sans table, avec unsigned int : entre 700 et 750 ms

Pas de différences notables donc

Effectivement, strlen fonctionne avec un tableau de char... Un int étant (la plupart du temps) 4 fois plus grand, il trouve des caractères nuls un peu partout...