En ce qui concerne les performances de la queue, ce qui représente une meilleure mise en œuvre – Tableau ou liste chaînée

Quel chemin donne la mise en queue et la mise en queue plus rapides lorsque je dois insérer très peu d’éléments? Un tableau est-il préférable à une liste chaînée?

Je dois insérer quelques éléments et je dois supprimer et lire cet élément supprimé de la queue. Si c’est un tableau, il se peut que je doive modifier les index à chaque fois que je supprime un élément. L’insertion et la suppression peuvent également se produire simultanément.

Lequel est le meilleur de cas ci-dessous?

typedef struct{ mylist list; struct mylistQ *next; }mylistQ; 

Code de tableau

  static mylist myListQ[QUEUESIZE+1]; int qLast = 0; void enqueue_element(mylist qItem) { myListQ[qLast] = qItem; qLast++; } mylist dequeue_element() { retryq: if(qLast >0) { mylist qReturn = myListQ[0]; int i; for (i = 0; i < qLast - 1; i++){ myListQ[i] = myListQ[i + 1]; } qLast--; return qReturn; } else { goto retryq; } } 

Liste liée

  int qLast = 0; mylistQ *headElement = NULL; mylistQ *tailElement = NULL; void enqueue_element(mylist *List) { mylistQ *newnode; newnode=(mylistQ*)av_malloc(sizeof(mylistQ)); newnode->next=NULL; newnode->list=*List; qLast++; if(headElement==NULL && tailElement==NULL) { headElement=newnode; tailElement=newnode; } else { tailElement->next=newnode; tailElement=newnode; } } mylist dequeue_element() { mylistQ *delnode; /* Node to be deleted */ mylist Dellist; if(headElement==NULL && tailElement==NULL){ LOg( "Queue is empty to delete any element"); } else { Log("In dequeue_picture queue is not empty"); delnode=headElement; headElement=headElement->next; if (!headElement){ tailElement=NULL; } Dellist = delnode->list; av_free(delnode); qLast--; } return Dellist; } 

    Cela dépend du nombre d’opérations que vous allez effectuer et de la manière dont la version du tableau est implémentée.

    Si vous effectuez relativement peu d’opérations, c’est-à-dire moins de 1 000 ou plus de files de mise en queue / de files d’attente, un tableau serait plus rapide car il est contigu en mémoire. Maintenez un pointeur vers l’avant et un pointeur vers l’arrière, ajoutez toujours à l’arrière et retirez la queue à l’avant.

    D’un autre côté, même si la liste ne contient pas plus de 30 elem plus longs, si cela doit persister pendant une longue période, vous ne rencontrerez pas de problèmes de redimensionnement de tableau, ce qui pourrait poser problème.

    La liste chaînée garantit d’excellentes performances, vous devez surveiller le redimensionnement.

    EDIT: Comme mentionné par @Hans Passant, les tableaux sont rapides car ils ont la localité du cache du processeur. Tant que votre masortingce est petite, votre matériel optimisera les performances de sorte que la mémoire associée au stockage de la masortingce sera conservée dans votre L2. Indices susceptibles dans les registres. C’est vraiment rapide. A en juger par le fait que vous n’avez pas besoin de beaucoup d’éléments, un tableau serait idéal dans ce cas. Et oui, vous devrez modifier les index lorsque vous déplacez des éléments, mais il s’agit en fait d’une opération extrêmement rapide, car si vous construisez le code avec optimisation, les index seront stockés dans des bureaux d’enregistrement.

    Voici le piège cependant, vous dites que vous devrez peut-être faire la queue et la queue en même temps, voulez-vous dire par là que c’est parallèle, c’est-à-dire que plusieurs threads accèdent à la mémoire? Si tel est le cas, les tableaux seront toujours plus rapides, mais vous constaterez une diminution des performances 800 fois supérieure. Pourquoi? car le processeur ne peut plus mettre en mémoire tampon la mémoire associée à votre queue sur la puce, mais elle doit être stockée dans la mémoire principale. En outre, vous courez le risque de créer une condition de concurrence critique entre les threads. Imaginez que si un thread essayait de se retirer de la file pendant qu’un autre essayait de faire une queue et qu’il n’y avait qu’un seul élément dans la liste, vous pourriez avoir un désastre. Quoi qu’il en soit, si cette application est très performante, assurez-vous de comstackr (en supposant que gcc) avec les drapeaux NDEBUG et -O3 activés.

    Deuxième édition: en examinant le code et les réponses ci-dessous, nous vous suggérons de rendre votre code de tableau plus efficace et de le transformer en tableau circulaire car il semble que vous ayez une limite supérieure sur le nombre d’éléments. En remarque, l’implémentation actuelle de votre tableau est extrêmement inefficace. Chaque fois que vous supprimez, le rest de la queue est transféré, cela n’a aucun sens, il suffit d’incrémenter un pointeur int sur le “premier” index.

    Pseudo Code:

     int ciruclarArray[SIZE]; int front = 0; int back = 0; void enqueue(int elem) { circularArray[back] = elem; if(back < (circularArray.length - 1)) back++; else back = 0; return elem; } int dequeue() { int toReturn = circularArray[front]; //do same check for incrementing as enqueue return toReturn; } 

    N'oubliez pas de vérifier les erreurs pour les choses normales.

    S’il existe une limite supérieure sur le nombre total d’éléments que vous allez stocker dans la queue, utilisez un tableau circulaire . Cela évite d’avoir à redimensionner un tableau lors de l’ajout continu d’éléments à sa fin.

    Même si vous avez beaucoup d’éléments, l’implémentation de tableau est probablement la plus rapide. Comme source d’inspiration, j’ai jeté un coup d’œil à la queue C ++ de GCC. Il stocke la queue sous forme de tableau de tableaux. Je ne suis pas sûr si les iterators se retournent comme dans un tampon circulaire. L’implémentation de la masortingce dispose également d’un access aléatoire rapide, si vous en avez besoin ultérieurement.