Le topic de la programmation: Et envoyez des sioux!

**ducon** · 28/09/2018, 06h44

Envoyé par Tramb

Après comme dit Moglu, dès 1983 il y avait un langage qui te laissait définir les bornes de tes tableaux et qui définissait le comportement de taper en dehors.

Ça s’appelle un dictionnaire ordonné en Python.

**deathdigger** · 28/09/2018, 07h48

Après, y'a pire. Dans un langage que j'utilise, les tableaux commencent parfois à 1, parfois à 0. D'ailleurs parfois false=-1 et parfois false=0

**olih** · 28/09/2018, 08h50

C'est une convention en Lua aussi, les tableaux commençant à 1

**Lazyjoe** · 28/09/2018, 09h03

Toute façons le tableau il commence à array.begin() et se termine à array.end()
Et le compilateur a intérêt à bien l'avoir placé en mémoire pour que ça vectorise namého !

**Tramb** · 28/09/2018, 09h42

Envoyé par ducon

Ça s’appelle un dictionnaire ordonné en Python.

Ah c'est O(1) les accès ?

**Tramb** · 28/09/2018, 09h58

Envoyé par Lazyjoe

Toute façons le tableau il commence à array.begin() et se termine à array.end()
Et le compilateur a intérêt à bien l'avoir placé en mémoire pour que ça vectorise namého !

Voi-là.

**Nattefrost** · 28/09/2018, 10h05

Envoyé par Tramb

Ah c'est O(1) les accès ?

C'est implémenté en python et pas en C (au contraire du dict classique et de la list) donc les perfs sont plus faibles que le dict anyway.

Code:

def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
    'od.__setitem__(i, y) <==> od[i]=y'
    # Setting a new item creates a new link at the end of the linked list,
    # and the inherited dictionary is updated with the new key/value pair.
    if key not in self:
        root = self.__root
        last = root[0]
        last[1] = root[0] = self.__map[key] = [last, root, key]
    return dict_setitem(self, key, value)

**Møgluglu** · 28/09/2018, 10h15

Faisons la paix et coupons la poire en deux en suivant l'exemple des programmeurs graphiques. Le premier texel est à la coordonnée 0,5, le deuxième à 1,5, le troisième à 2,5, et ainsi de suite. Problème résolu.

**vectra** · 28/09/2018, 10h21

Ca me rappelle ces travaux sur la topologie qui définissaient un espace spéciale pour qu'une sélection de voxels soit un contour qui passe exactement 'entre' les voxels internes et externes.

**Tramb** · 28/09/2018, 11h29

Envoyé par Møgluglu

Faisons la paix et coupons la poire en deux en suivant l'exemple des programmeurs graphiques. Le premier texel est à la coordonnée 0,5, le deuxième à 1,5, le troisième à 2,5, et ainsi de suite. Problème résolu.

Sampling D3D7 ou OpengL ?

**vectra** · 28/09/2018, 15h15

Tiens, à propos de tableaux...

En C++11, y'a pas un itérateur du genre

Code:

for (size_t i : 0 : 5)
    cout << i

qui afficherait les entiers de 0 à 4 (ou 1 à 5

) ?
Bref, un truc qui serait aussi facile que le parcours d'un conteneur avec for(const auto &bin : conteneur) ?

En lisp, on a bien iota pour ce genre de bêtises.

**Cwningen** · 28/09/2018, 15h44

std::iota existe en C++, mais il remplit un tableau, c'est un peu du gaspillage de mémoire. Tu peux créer ton propre itérateur si écrire "for (size_t i = 0; i <=5; ++i)" te dérange tant.

**Helix** · 28/09/2018, 15h54

Envoyé par vectra

Tiens, à propos de tableaux...

En C++11, y'a pas un itérateur du genre

Code:

for (size_t i : 0 : 5)
    cout << i

qui afficherait les entiers de 0 à 4 (ou 1 à 5

) ?
Bref, un truc qui serait aussi facile que le parcours d'un conteneur avec for(const auto &bin : conteneur) ?

En lisp, on a bien iota pour ce genre de bêtises.

La fonction iota en Scheme est analogue à celle du C++, elle crée une liste composée de toutes les valeurs, ce n'est pas un itérateur. Donc gaspillage inutile de mémoire comme l'indique Cwningen.
En Common Lisp, tu fais un dotimes ou un loop (voir iterate pour avoir un truc plus propre). Et si la gestion des bornes te casse les pieds, tu fais une macro.

**Cwningen** · 28/09/2018, 16h37

J'ai essayé d'écrire l'itérateur pour voir : https://gcc.godbolt.org/z/eGPOrb. La fin boucle est un peu chiante à écrire à cause de l'opérateur != utilisé au lieu de <= (et je ne suis même pas trop sûr de ce que j'ai écrit). Je sais pas si quelqu'un a une astuce pour faire mieux. Dans le cas constexpr, ça n'a pas l'air trop catastrophique pour l'assembleur généré.

Boucle traditionnelle :

Code:

        movl    $-3, %r14d
.LBB0_1:
        addl    $3, %r14d
...
intérieur de la boucle
...
        cmpl    $8, %r14d
        jl      .LBB0_1

Boucle avec itérateur :

Code:

        xorl    %r14d, %r14d
.LBB0_7:
...
intérieur de la boucle
...
        addl    $3, %r14d
        cmpl    $12, %r14d
        jne     .LBB0_7

J'imagine que le changement d'ordre de la boucle traditionnelle est là mieux remplir le pipeline (mieux séparer l'addition et la comparaison).

**William Vaurien** · 28/09/2018, 17h13

Je vous poste un petit example de code sympa (

) trouvé dans mon cher projet C pour faire une petite revue de code.
J'ai peut-être glissé des erreurs en anonymisant la bête:

Les structures utilisés:

Code:

/* structure avec plein de champs*/
struct Aggregate {
    char* champ1; // ou champ0 au choix ;)
    ...
    char* champN;
    ...
    char* champItemA[];
    char* champItemB[];
    ...
    char* champItemZ[];    
    /* 13 champItem au total */
} 

struc SortItem {
    char* champItemA;
    char* champItemB;
    ...
    char* champItemZ;
    /* 13 champs au total, oui, les même que dans Aggregate */
}

L'algo:

Code:

Aggregate aggregate;
grosseFunctionAvecDuSqlPourRemplir(&aggregate);

SortItem sortItem;

sort = 1; j = nbItem;
while (sort) {
        sort = 0;
        for (i = 0; i < j; i++)   {
            d = compareField (item.fieldX[i], item->fieldX[i+1]);

            if ((d < 0) || ((d == 0) && (compareField (item->fieldY[i], item->fieldY[i+1]) < 0))) {
                memset ((char *)&sortItem, 0, sizeof (sortItem));
                k = i + 1;

                strcpy(sortItem.fieldA, aggregate->fieldA[i]);
                ... /* il y a 13 champs */
                strcpy(sortItem.fieldZ, aggregate->fieldZ[i]);
                
                strcpy(aggregate.fieldA[i], aggregate->fieldA[k]);
                ... /* il y a 13 champs */
                strcpy(aggregate.fieldZ[i], aggregate->fieldZ[k]);
                                    
                strcpy(aggregate.fieldA[k], sortItem->fieldA);
                ... /* il y a 13 champs */
                strcpy(aggregate.fieldA[i], sortItem->fieldZ);
                                
                 sort = 1;
            }
        }
    }

**Frypolar** · 28/09/2018, 18h35

Non mais là il faut les cramer les mecs.

**Cwningen** · 28/09/2018, 20h33

Tu as oublié du code ou ça plante au premier strcpy (la chaine de destination n'est pas allouée) ? En dehors des problèmes de copies de chaines, c'est censé faire quoi ? Une sorte de tri partiel ? Je comprends pas la variable sort.

PS: S'il y a 13 champs, ça va de A à M. Sauf si tu commences par numéroter à B.

**William Vaurien** · 28/09/2018, 21h02

Cwningen, tu ne connais pas encore l'art de l'ellipse et du pseudo-code...
Je n'allais pas copier coller directement du code d'entreprise, très verbeux qui plus est.

Ici c'est l'algo qui est amusant.
Oui, c'est un tri à bulle. Avec recopie de tous les champs à chaque swap.

**Cwningen** · 28/09/2018, 21h18

C'est juste pour être sûr, tu as bien pris la peine de mettre le memset. Mais il y a bien plein de malloc (3 fois 13 ?) à chaque itération, c'est ça ? Pas de tableau réutilisé ?

Et en relisant une deuxième fois, je vois que je m'étais embrouillé avec sort, c'est bien un tri complet (quadratique de la pire sorte, une sorte de tri bulle mal fait).

**Paradox** · 28/09/2018, 21h28

Quel interet d'utiliser un tri a bulles plutot qu'un autre algo de tri dans du code d'entreprise ?

Edit :

Quand je vois ce genre de code, je me dis que pas grand monde n'a entendu parler du principe KISS.

**William Vaurien** · 28/09/2018, 22h16

C'est très KIS en fait. Reste à savoir si c'est le Simple ou le Stupid qui manque...
Il n'y a aucun intérêt à faire ça, en entreprise ou ailleurs et je ne sais pas si c'est vraiment le tri à bulles le pire... Pour moi c'est plutôt ces structures dégueulasse et les recopies de valeurs...

Pour la mémoire elle est toujours dans le code à taille fixe, ce sont des tableaux de tableaux sous cette forme :
char tableau[MAX_ARR_LEN] [MX_STR_LEN]

Le test x < 0 || x == 0 à de la gueule aussi..

**Paradox** · 28/09/2018, 22h20

Ba les structures et les recopies de valeurs, effectivement, c'est pas beau. Et du coup pas tres "simple"

En tout cas, si le tri a bulles est le plus lent. Apres, c'est justement le plus simple a implementer, ce qui fait encore plus de peine de voir ce genre de code etre utilise, puisque tu n'as ni la simplicite, ni la rapidite.

**ducon** · 28/09/2018, 22h24

Il y a plus lent, le bogosort.

**Paradox** · 28/09/2018, 22h54

Envoyé par ducon

Il y a plus lent, le bogosort.

Pas forcement : par nature, ca depend de l'execution consideree.

**Shosuro Phil** · 28/09/2018, 23h34

Envoyé par Tramb

Ah c'est O(1) les accès ?

Les dictionnaires ordonnés de Python, ils sont ordonnés par l'ordre d'insertion, pas par un ordre a priori des clés. Donc je suppose que c'est implémenté par une table de hachage avec chaînage des objets, ou double indirection. L'accès via clé devrait donc être dominé par le calcul de la fonction de hachage.

**Cwningen** · 29/09/2018, 01h36

Envoyé par William Vaurien

Pour la mémoire elle est toujours dans le code à taille fixe, ce sont des tableaux de tableaux sous cette forme :
char tableau[MAX_ARR_LEN] [MX_STR_LEN]

Si ce sont des tableaux et non des pointeurs, on est bien obligé de copier toutes les chaines puisqu'on ne peut pas simplement échanger les pointeurs. Le problème c'est la structure de données, pas les strcpy eux-mêmes.

Envoyé par William Vaurien

Le test x < 0 || x == 0 à de la gueule aussi..

Là t'es malhonnête, il y a des parenthèses importantes. Je ne vois rien de mal dans ce test là.

**Thamior** · 29/09/2018, 03h33

Envoyé par Cwningen

Là t'es malhonnête, il y a des parenthèses importantes. Je ne vois rien de mal dans ce test là.

Peut-être qu'écrire "x <= 0" serait un peu plus succinct. En pratique je pense que le compilateur saura faire mais bon.

**acdctabs** · 29/09/2018, 10h26

Il y a un && après le == 0 pour envoyer une deuxième condition, donc non tu peux pas <=

**William Vaurien** · 29/09/2018, 11h11

Bien vu, j'étais passé complètement par dessus.

**Thamior** · 29/09/2018, 21h01

Eh ben pareil, du coup :D

Discussion: Le topic de la programmation: Et envoyez des sioux!

Outils de la discussion

Règles de messages