Y a-t-il une implémentation de file d'attente ?

Question

Est-ce que quelqu'un peut suggérer un conteneur Go pour une file d'attente simple et rapide, Go a 3 conteneurs différents: heap, list et vector. Lequel est le plus adapté pour mettre en œuvre une file d'attente?

Answer 1

En fait, si ce que vous voulez est une file d'attente fifo de base et facile à utiliser, slice fournit tout ce dont vous avez besoin.

queue := make([]int, 0)
// Pousser dans la file d'attente
queue = append(queue, 1)
// Haut (obtenir simplement l'élément suivant, ne pas le supprimer)
x = queue[0]
// Supprimer l'élément en haut
queue = queue[1:]
// Est-ce vide ?
if len(queue) == 0 {
    fmt.Println("La file d'attente est vide !")
}

Bien sûr, nous supposons que nous pouvons faire confiance à la mise en œuvre interne de l'ajout et du tranchage pour éviter les redimensionnements inutiles et les réallocations. Pour une utilisation de base, c'est parfaitement suffisant.

Answer 2

Surpris de voir que personne n'a encore suggéré les chaînes tamponnées, de toute façon, pour une file d'attente FIFO de taille limitée.

//Ou autant que nécessaire + tampon.
c := make(chan int, 300)

//Pousser
c <- valeur

//Pop
x <- c

Answer 3

La plupart des implémentations de files d'attente se présentent sous trois formes : basées sur des tranches, basées sur des listes chaînées et basées sur des tampons circulaires (tampon en anneau).

• Les files d'attente basées sur des tranches ont tendance à gaspiller de la mémoire car elles ne réutilisent pas la mémoire précédemment occupée par les éléments supprimés. De plus, les files d'attente basées sur des tranches ont tendance à n'avoir qu'une seule extrémité.
• Les files d'attente basées sur des listes chaînées peuvent être meilleures en termes de réutilisation de la mémoire, mais sont généralement un peu plus lentes et utilisent plus de mémoire dans l'ensemble en raison du surcoût de la maintenance des liens. Elles peuvent offrir la possibilité d'ajouter et de supprimer des éléments du milieu de la file d'attente sans déplacer la mémoire, mais si vous faites beaucoup de cela, une liste est la mauvaise structure de données.
• Les files d'attente basées sur des tampons circulaires offrent toute l'efficacité des tranches, avec l'avantage de ne pas gaspiller de mémoire. Moins d'allocation signifie de meilleures performances. Elles sont tout aussi efficaces pour ajouter et supprimer des éléments des deux extrémités, vous obtenez naturellement une file d'attente à double extrémité. Ainsi, je recommanderais généralement une implémentation de file d'attente basée sur un tampon circulaire. C'est ce qui est discuté dans le reste de cet article.

La file d'attente basée sur un tampon circulaire réutilise la mémoire en enveloppant son stockage : lorsque la file d'attente dépasse l'une des extrémités de la tranche sous-jacente, elle ajoute des nœuds supplémentaires à l'autre extrémité de la tranche. Voir diagramme de la deque

Aussi, un peu de code pour illustrer :

// PushBack ajoute un élément à l'arrière de la file d'attente. Implémente FIFO lorsque
// les éléments sont supprimés avec PopFront(), et LIFO lorsque les éléments sont supprimés
// avec PopBack().
func (q *Deque) PushBack(elem interface{}) {
    q.growIfFull()
    q.buf[q.tail] = elem
    // Calculer la nouvelle position de la queue.
    q.tail = q.next(q.tail)
    q.count++
}

// next retourne la position suivante du tampon en wrappant autour du tampon.
func (q *Deque) next(i int) int {
    return (i + 1) & (len(q.buf) - 1) // modulo bit à bit
}

Cette implémentation particulière utilise toujours une taille de tampon qui est une puissance de 2, et peut donc calculer le modulo bitwise de manière un peu plus efficace.

Cela signifie que la tranche doit augmenter uniquement lorsque toute sa capacité est utilisée. Avec une stratégie de redimensionnement qui évite de développer et réduire le stockage sur la même limite, cela le rend très efficace en termes de mémoire.

Voici le code qui redimensionne le tampon de la tranche sous-jacente :

// resize redimensionne la deque pour s'adapter exactement à deux fois son contenu actuel. Cela est
// utilisé pour agrandir la file d'attente lorsqu'elle est pleine, et aussi pour la réduire lorsqu'elle est
// seulement remplie au quart.
func (q *Deque) resize() {
    newBuf := make([]interface{}, q.count<<1)
    if q.tail > q.head {
        copy(newBuf, q.buf[q.head:q.tail])
    } else {
        n := copy(newBuf, q.buf[q.head:])
        copy(newBuf[n:], q.buf[:q.tail])
    }
    q.head = 0
    q.tail = q.count
    q.buf = newBuf
}

Une autre chose à considérer est si vous voulez une sécurité de concurrence intégrée à l'implémentation. Vous voudrez peut-être éviter cela pour pouvoir faire ce qui fonctionne le mieux pour votre stratégie de concurrence, et vous ne le voulez certainement pas si vous n'en avez pas besoin ; même raison de ne pas vouloir une tranche qui a une sérialisation intégrée.

Il existe un certain nombre d'implémentations de files d'attente basées sur des tampons circulaires pour Go si vous faites une recherche sur godoc pour deque. Choisissez celle qui convient le mieux à vos goûts.

Answer 4

Soit vector soit liste devrait fonctionner, mais vector est probablement la meilleure option. Je dis cela parce que vector va probablement allouer moins souvent que liste et la collecte des déchets (dans l'implémentation actuelle de Go) est assez coûteuse. Dans un petit programme, cela ne devrait probablement pas avoir d'importance, cependant.

Answer 5

Modifier, implémentation plus propre d'une file d'attente :

package main

import "fmt"

type Queue []interface{}

func (self *Queue) Push(x interface{}) {
    *self = append(*self, x)
}

func (self *Queue) Pop() interface{} {
    h := *self
    var el interface{}
    l := len(h)
    el, *self = h[0], h[1:l]
    // Ou utilisez ceci à la place pour une pile
    // el, *self = h[l-1], h[0:l-1]
    return el
}

func NewQueue() *Queue {
    return &Queue{}
}

func main() {
  q := NewQueue()
  q.Push(1)
  q.Push(2)
  q.Push(3)
  q.Push("L")

  fmt.Println(q.Pop())
  fmt.Println(q.Pop())
  fmt.Println(q.Pop())
  fmt.Println(q.Pop())

}

Ou incorporez simplement un "container/list" dans une implémentation simple et exposez l'interface :

package queue

import "container/list"

// Queue est une file d'attente
type Queue interface {
    Front() *list.Element
    Len() int
    Add(interface{})
    Remove()
}

type queueImpl struct {
    *list.List
}

func (q *queueImpl) Add(v interface{}) {
    q.PushBack(v)
}

func (q *queueImpl) Remove() {
    e := q.Front()
    q.List.Remove(e)
}

// Nouveau est une nouvelle instance d'une file d'attente
func Nouveau() Queue {
    return &queueImpl{list.New()}
}