Quel est le moyen efficace de mettre en œuvre une file d'attente, l'inondation d'apprendre comment elle est mise en œuvre?
EDIT: J'ai regardé sur STL :: Code de la file d'attente INDERORER pour apprendre à savoir comment il est mis en œuvre, mais le code de modèle rendant difficile la compréhension. Après tout, il est utilisé de manière meilleure efficacité que d'avoir une liste liée.
9 Réponses :
Dans le sens le plus générique, une liste liée serait votre meilleure mise si vous maintenez un avant et arrière pointeur. Dans ce cas, l'insertion et la suppression de la file d'attente est une opération O (1) . Vous pouvez également implémenter un à l'aide d'un tableau et de maintenir des indices pour l'avant et l'arrière. Le calcul est marginalement plus impliqué (lorsque vous insérez ou supprimez, vous devez prendre en compte "Emballage" pour éviter de sortir des limites).
La manière la plus efficace est d'avoir quelqu'un d'autre le faire.
C ++ et C # (et .Net et al) ont un dans leurs bibliothèques indigènes.
J'ai regardé sur STL :: Code de la file d'attente INDERORER pour apprendre à savoir comment il est mis en œuvre, mais le code de modèle rendant difficile la compréhension. Après tout, il est mieux utilisé que d'avoir une lisk lié.
pour C ++, STL :: Queue <>.
Si vous avez besoin d'une mise en œuvre de la file d'attente du thread, vous pouvez essayer Ma propre bibliothèque . Ce n'est pas encore complet, mais il est bien documenté.
edit: Il est saisi par des listes liées.
Bien sûr, pour tout code de production, vous devez compter sur une implémentation de la bibliothèque robuste qui a déjà été transformée à l'épreuve du temps.
Cela dit, pour l'auto-enseignement, cela peut être amusant d'écrire un vous-même. Je l'ai déjà fait auparavant.
La manière la plus efficace que je connaisse consiste à utiliser une approche similaire de ce que les collections la plus rééviable font en interne: stocker une matrice, qui est augmentée de taille (généralement doublée) selon les besoins lorsque la taille de la collection atteint la longueur de la matrice.
Une file d'attente est un peu différente d'une collection ordinaire, cependant, car vous souhaitez pouvoir apparaître de l'extrémité opposée de l'endroit où les éléments sont poussés.
Évidemment, pour supprimer le premier élément et déplacer tous les autres éléments d'un indice serait coûteux et inutile. Donc, au lieu de cela, vous gardez une trace des indices de départ et de fin. Lorsque la collection atteint la fin de la matrice, vous utilisez La clé utilise simplement vos mathématiques afin que vous gérez tous les cas, par exemple, de développer correctement le tableau lorsque la file d'attente est pleine, obtenez vos limites correctes, incrémentation de l'index de démarrage (ou en boucle de 0) sur chaque pop , etc.
Clairement, la conception que j'ai décrite ci-dessus présente de nombreuses limitations: la sécurité du fil, par exemple. Mais pour une implémentation simple, à une seule fois filetée et efficace, c'est un très bon point de départ.
Bonne chance - et je vous recommande également de poster votre code si / lorsque vous en avez un que vous pensez fonctionner! % pour commencer à repousser les éléments au début.
Merci, cette approche s'applique aussi à la file d'attente circulaire.
Bien sûr. La lecture sur DESQUES vous indiquera un peu de choses sur ce genre de choses; Ils sont généralement mis en œuvre sous forme de tampon circulaire (comme Dan Tao suggère) ou une liste liée. Ce dernier est généralement moins efficace.
@Passionate: Ouais, vraiment toute mise en œuvre de la file d'attente peut être trivialement enveloppée pour fournir la fonctionnalité d'une file d'attente circulaire (je suppose par «la file d'attente circulaire», vous voulez dire une file d'attente avec une limite supérieure sur sa longueur?). Ou bien sûr, vous pouvez en mettre en œuvre une façon de commencer.
Combien de threads peut lire votre file d'attente à la fois? Combien peut-il l'écrire à la fois? Un fil peut-il lire tandis qu'un autre écrit? Voulez-vous pré-allouer de l'espace pour la taille maximale de la file d'attente? Avez-vous besoin d'un moyen de bloquer un lecteur lors de l'attente des données ou de bloquer un écrivain lorsque la file d'attente est pleine? Combien d'objets par seconde prévoyez-vous nourrir la file d'attente?
L'approche optimale dépendra des réponses à ces questions.
Comprends-tu Comment une file d'attente fonctionne ?
Comprends-vous Comment la file d'attente STL fonctionne ?
Comprenez-vous que "le plus efficace" est un concept abstrait qui peut " Tenez vrai pour chaque cas?
Si vous obtenez tout cela, l'algorithme "la plus efficace de la file d'attente C ++" viendra à vous
Si vous pouvez accepter une taille maximale pour la file d'attente, un tampon circulaire est super efficace . Parce que les fonctions de la bibliothèque ne peuvent pas supposer une taille maximale, elles n'utilisent pas cette technique.
Pourriez-vous jeter un peu de lumière sur la manière dont la fonction de bibliothèque est-elle implémente?
@Passionnate, je ne connais que très bien que STD :: Queue. Il encapsule tout conteneur qui implémente avant , arrière , push_back et pop_front . Parce que ces conteneurs commencent à vider et à se développer au besoin, la file d'attente.
Si votre objectif principal est d'apprendre comment il est implémenté, vous devez travailler avec des listes liées. Ils sont amusants à travailler avec et présentent vraiment la différence entre les matrices séquentielles et enseigne beaucoup de mémoire.
Et quelle est la manière inefficace? Vous implémentez une file d'attente ou non :)
Vous devez vraiment être plus spécifique et prendre plus de soin de poser votre question si vous vous attendez à ce que les meilleurs programmeurs du monde prennent leur temps pour générer une réponse intéressante à cette question.
En C ++, mais je demande à apprendre comment elle est mise en œuvre.
Veuillez éditer votre question plutôt que de répondre directement aux commentaires. Cela aidera lorsque les gens tentent de répondre à la question.