+ Répondre à la discussion
Affichage des résultats 1 à 9 sur 9
  1. #1
    Membre Expert

    Inscrit en
    décembre 2006
    Messages
    2 261
    Détails du profil
    Informations forums :
    Inscription : décembre 2006
    Messages : 2 261
    Points : 1 405
    Points
    1 405

    Par défaut Comment sont implémentées les listes Python ?

    Bonjour,
    tout est dans la question ou presque. Lors de la "compilation" d'un script Python, quel type C est utilisé pour les listes ?

    Je pose la question pour mieux comprendre les différences de performance entre maListe.pop() et maListe.pop(0).

  2. #2
    Modérateur

    Homme Profil pro
    Architecte technique
    Inscrit en
    juin 2008
    Messages
    5 563
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Architecte technique
    Secteur : Industrie

    Informations forums :
    Inscription : juin 2008
    Messages : 5 563
    Points : 8 403
    Points
    8 403

    Par défaut

    Salut,

    Une liste Python n'existe pas en C "standard", c'est un objet Python implémenté dans listobject.c.

    En gros, les items de cette liste sont rangés dans un tableau (ob_item).
    Si c'est le dernier élément, il suffit de redimensionner la capacité du tableau.

    Lorsqu'il s'agit d'un autre élément, il faut "avancer" les éléments suivants: c'est cette opération qui va coûter.
    - W
    Architectures Post-Modernes

  3. #3
    Membre Expert
    Inscrit en
    août 2010
    Messages
    1 021
    Détails du profil
    Informations forums :
    Inscription : août 2010
    Messages : 1 021
    Points : 1 203
    Points
    1 203

    Par défaut

    Il est conseillé d'utiliser collections.deque plutôt que List si on veut append/pop rapidement aux deux extrémités

  4. #4
    Expert Confirmé Sénior
    Avatar de Sve@r
    Homme Profil pro Frédéric
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    4 680
    Détails du profil
    Informations personnelles :
    Nom : Homme Frédéric
    Âge : 46
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 4 680
    Points : 10 605
    Points
    10 605

    Par défaut

    Salut

    A mon avis, le plus simple pour toi (qui a tant envie de comprendre) serait de refaire en C un ersatz de liste Python.

    Et (désolé de contredire wiztricks qui est notre maitre à penser Python), au lieu de passer par un tableau je passerais par une liste chainée, un peu dans ce style...
    Code c :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    typedef struct s_elem {
        void *pt_data;
        struct s_elem *next;
    } t_elem;
     
    typedef struct {
        t_elem *first;
        size_t nb_elem;
    } t_liste;

    ...ce qui simplifierait assez grandement les opérations append(), del() et pop()...
    Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
    Tout ce qu'un individu reçoit sans rien faire pour l'obtenir, un autre individu a dû travailler pour le produire sans en tirer profit.
    Tout Pouvoir ne peut distribuer aux uns que ce qu'il a préalablement confisqué à d'autres car on n'accroît pas les biens en les divisant.
    Quand la moitié d'un peuple croit qu'il ne sert à rien de faire des efforts car l'autre moitié les fera pour elle, et quand cette dernière moitié se dit qu'il ne sert à rien d'en faire car ils bénéficieront à d'autres, cela s'appelle le déclin et la fin d'une nation.
    Dr. Adrian Rogers (1931-2005)

  5. #5
    Expert Confirmé
    Avatar de fred1599
    Homme Profil pro Fred
    Enseignant
    Inscrit en
    juillet 2006
    Messages
    1 834
    Détails du profil
    Informations personnelles :
    Nom : Homme Fred
    Localisation : France, Meurthe et Moselle (Lorraine)

    Informations professionnelles :
    Activité : Enseignant
    Secteur : Enseignement

    Informations forums :
    Inscription : juillet 2006
    Messages : 1 834
    Points : 2 848
    Points
    2 848

    Par défaut

    Tout à fait Sve@r, je suis d'accord avec toi, c'est un équivalent d'une deque.

    Mais en fait ce que Wiztrick veut dire est qu'on utilise l'API C avec un tableau (**ob_item) et les dérivés à PyObject. La librairie utilisée est Python.h

    Donc une lib C oui, mais qui sort du standard C habituel, voilà pourquoi la réponse est difficile à donner si tu ne te connais pas un minimum dans l'API C...
    Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
    La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)

  6. #6
    Modérateur

    Homme Profil pro
    Architecte technique
    Inscrit en
    juin 2008
    Messages
    5 563
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Architecte technique
    Secteur : Industrie

    Informations forums :
    Inscription : juin 2008
    Messages : 5 563
    Points : 8 403
    Points
    8 403

    Par défaut

    Si rambc a posé cette question, c'est sans doute parce que sa liste est de très grande taille.

    Faire du FIFO sur une structure adaptée pour du LIFO n'est pas "top" et si son cas d'utilisation est FIFO, collections.deque sera mieux.

    Comme il n'a pas indiqué ce qu'il faisait avec, ce mieux côté FIFO ne sera pas forcément bien (dans son contexte).
    - W
    Architectures Post-Modernes

  7. #7
    Membre Expert
    Homme Profil pro
    Inscrit en
    mars 2007
    Messages
    895
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : mars 2007
    Messages : 895
    Points : 1 300
    Points
    1 300

    Par défaut

    Je me suis justement intéressé à ce sujet récemment; je voulais implémenter une structure de donnée similaire au listes Python dans un autre langage et je voulais voir comment elles étaient implémentées.

    Comme l'a dit wiztricks, les listes Python sont implémentées par des tableaux en C dans listobject.c
    Si le tableau devient trop petit, il est redimensionné avec realloc, ce qui peut impliquer la copie complète du tableau. Pour amortir ce coût, une surallocation est faite: chaque fois qu'on doit agrandir le tableau, on alloue environ 12,5% de plus que la taille demandée (pour de grand tableaux; plus que ça quand le tableau est petit):
    Code :
    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6); /* dans list_resize */
    newsize est la taille demandée; new_allocated correspond à la surallocation. La taille finalement allouée est la somme des deux.

    Si la taille demandée est inférieure à la moitié de la taille allouée, il y a aussi un realloc pour réduire la taille allouée.

    Un pop(0) finira par exécuter le code suivant:
    Code :
    1
    2
    3
    4
    5
        if (d < 0) { /* Delete -d items */
            memmove(&item[ihigh+d], &item[ihigh],
                (Py_SIZE(a) - ihigh)*sizeof(PyObject *));
            list_resize(a, Py_SIZE(a) + d);
            ...
    a est un pointeur vers la structure qui représente la liste. item est a->ob_item, le tableau proprement dit. Pour un pop(0), on aura d = -1; ihigh=1. C'est ce memmove qui est coûteux pour un pop(0).

    L'appel à list_resize ci-dessus ne fera la plupart du temps pas de réallocation, sauf si la taille de la liste descend au-dessous de la moitié de la taille actuellement allouée.

    Pour un pop(), le memmove se ferait sur 0 éléments et retournerait donc immédiatement, mais, sans doute pour optimiser, ce code est même court-circuité:
    Code :
    1
    2
    3
    4
    5
       if (i == Py_SIZE(self) - 1) {
            status = list_resize(self, Py_SIZE(self) - 1);
            assert(status >= 0);
            return v;
        }
    Si l'élément à supprimer est le dernier, il fait juste un appel à list_resize et c'est tout.

  8. #8
    Membre Expert

    Inscrit en
    décembre 2006
    Messages
    2 261
    Détails du profil
    Informations forums :
    Inscription : décembre 2006
    Messages : 2 261
    Points : 1 405
    Points
    1 405

    Par défaut

    Bonssir,
    désolé pour ce retard mais en ce moment c'est un méga rush... Je regarde vos messages et réponds ce weekend.

  9. #9
    Membre Expert

    Inscrit en
    décembre 2006
    Messages
    2 261
    Détails du profil
    Informations forums :
    Inscription : décembre 2006
    Messages : 2 261
    Points : 1 405
    Points
    1 405

    Par défaut

    Citation Envoyé par rambc Voir le message
    Bonssir,
    désolé pour ce retard mais en ce moment c'est un méga rush... Je regarde vos messages et réponds ce weekend.
    Disons plutôt pendant les vacances de Noël...

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •