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

Pour développer du côté implémentation, Moraes propose dans son gist quelques structures de file d'attente et de pile :

// La pile est une structure de données LIFO de base qui redimensionne au besoin.
type Stack struct {
    nodes   []*Node
    count   int
}
// La file d'attente est une file d'attente FIFO de base basée sur une liste circulaire qui redimensionne au besoin.
type Queue struct {
    nodes   []*Node
    head    int
    tail    int
    count   int
}

Vous pouvez le voir en action dans cet exemple de playground.

Answer 2

Utiliser une tranche et un schéma d'indexation approprié ("circulaire") semble toujours être la voie à suivre. Voici mon avis à ce sujet : https://github.com/phf/go-queue Les benchmarks là-bas confirment également que les canaux sont plus rapides, mais au prix d'une fonctionnalité plus limitée.

Answer 3

Malheureusement, les files d'attente ne font pas actuellement partie de la bibliothèque standard de Go, donc vous devez écrire votre propre solution / importer la solution de quelqu'un d'autre. C'est dommage car les conteneurs écrits en dehors de la bibliothèque standard ne peuvent pas utiliser les génériques.

Un exemple simple d'une file d'attente à capacité fixe serait :

type MyQueueElement struct {
  blah int // ce que vous voulez
}

const MAX_QUEUE_SIZE = 16
type Queue struct {
  content  [MAX_QUEUE_SIZE]MyQueueElement
  readHead int
  writeHead int
  len int
}

func (q *Queue) Push(e MyQueueElement) bool {
  if q.len >= MAX_QUEUE_SIZE {
    return false
  }
  q.content[q.writeHead] = e
  q.writeHead = (q.writeHead + 1) % MAX_QUEUE_SIZE
  q.len++
  return true
}

func (q *Queue) Pop() (MyQueueElement, bool) {
  if q.len <= 0 {
    return MyQueueElement{}, false
  }
  result := q.content[q.readHead]
  q.content[q.readHead] = MyQueueElement{}
  q.readHead = (q.readHead + 1) % MAX_QUEUE_SIZE
  q.len--
  return result, true
}

Les pièges évités ici comprennent le fait de ne pas avoir de croissance de tranche illimitée (causée par l'utilisation de l'opération de tranche [1:] pour éliminer) et de mettre à zéro les éléments extraits pour garantir que leur contenu soit disponible pour la collecte des déchets. Notez que dans le cas d'une structure MyQueueElement contenant seulement un int comme ici, cela ne fera aucune différence, mais si la structure contenait des pointeurs, cela ferait une différence.

La solution pourrait être étendue pour réallouer et copier si une file d'attente à croissance automatique est souhaitée.

Cette solution n'est pas sécurisée pour les threads, mais un verrou pourrait être ajouté à Push/Pop si cela est souhaité.

Plage de jeux https://play.golang.org/

Answer 4

J'implémente également la file d'attente à partir de la tranche comme ci-dessus. Cependant, ce n'est pas thread-safe. J'ai donc décidé d'ajouter un verrou (mutex lock) pour garantir la sécurité des threads.

package queue

import (
  "sync"
)

type Queue struct {
  lock *sync.Mutex
  Values []int
}

func Init() Queue {
  return Queue{&sync.Mutex{}, make([]int, 0)}
}

func (q *Queue) Enqueue(x int) {
  for {
    q.lock.Lock()
    q.Values = append(q.Values, x)
    q.lock.Unlock()
    return
  }
}

func (q *Queue) Dequeue() *int {
  for {
    if (len(q.Values) > 0) {
      q.lock.Lock()
      x := q.Values[0]
      q.Values = q.Values[1:]
      q.lock.Unlock()
      return &x
    }
    return nil
  }
  return nil
}

Vous pouvez consulter ma solution sur github ici file d'attente simple

Answer 5

Vous pouvez essayer quelque chose comme ça,

// queue.go
package queue

type Queue struct {
    data []int
}

func (q *Queue) Enqueue(d int) {
    q.data = append(q.data, d)
}

func (q *Queue) Dequeue() int {
    dequeued := q.data[0]
    q.data = q.data[1:]
    return dequeued
}

func (q *Queue) IsEmpty() bool {
    return len(q.data) == 0
}

func NewQueue() *Queue {
    return &Queue{
        data: make([]int, 0),
    }
}

//queue_test.go

package queue

import (
    "testing"

    "github.com/stretchr/testify/assert"
)

func TestQueue_ShouldInitialiseWithEmpty(t *testing.T) {
    q := NewQueue()
    assert.Equal(t, true, q.IsEmpty())
}

func TestQueue_ShouldErrorIfDequeuePerformedOnEmpty(t *testing.T) {
    q := NewQueue()
    _, err := q.Dequeue()
    assert.NotNil(t, err)
    assert.Equal(t, "nothing to dequeue", err.Error())
}

func TestQueue(t *testing.T) {
    q := NewQueue()
    q.Enqueue(1)
    q.Enqueue(2)
    q.Enqueue(3)
    q.Enqueue(4)

    dequeued1, err1 := q.Dequeue()
    assert.Nil(t, err1)
    assert.Equal(t, 1, dequeued1)

    dequeued2, err2 := q.Dequeue()
    assert.Nil(t, err2)
    assert.Equal(t, 2, dequeued2)

    dequeued3, err3 := q.Dequeue()
    assert.Nil(t, err3)
    assert.Equal(t, 3, dequeued3)

    dequeued4, err4 := q.Dequeue()
    assert.Nil(t, err4)
    assert.Equal(t, 4, dequeued4)
}