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

type Queue struct {
    slice []int
    len   int
}
func newq() Queue {
    q := Queue{}
    q.slice = make([]int, 0)
    q.len = 0
    return q
}
func (q *Queue) Add(v int) {
    q.slice = append(q.slice, v)
    q.len++
}

func (q *Queue) PopLeft() int {
    a := q.slice[0]
    q.slice = q.slice[1:]
    q.len--
    return a
}
func (q *Queue) Pop() int {
    a := q.slice[q.len-1]
    q.slice = q.slice[:q.len-1]
    q.len--
    return a
}

Pour vos besoins de base, le code ci-dessus devrait suffire

Answer 2

O(1) Temps pour EnQueue, DeQueue, Recherche Frontale & Arrière O(n) Espace pour la capacité

type Queue struct {
    front    int
    rear     int
    size     int
    capacity int
    q        []string
}

func (q *Queue) IsFull() bool {
    return q.size == q.capacity
}

func (q *Queue) IsEmpty() bool {
    return q.size == 0
}
func (q *Queue) EnQueue(s string) error {
    if q.IsFull() {
        return fmt.Errorf("la file d'attente est pleine")
    }
    q.rear = (q.rear + 1) % q.capacity
    q.q[q.rear] = s
    q.size++
    return nil
}

func (q *Queue) DeQueue() (string, error) {
    if q.IsEmpty() {
        return "", fmt.Errorf("la file d'attente est vide")
    }
    defer func() { q.front, q.size = (q.front+1)%q.capacity, q.size-1 }()
    return q.q[q.front], nil

}

func (q *Queue) Front() (string, error) {
    if q.IsEmpty() {
        return "", fmt.Errorf("la file d'attente est vide")
    }
    return q.q[q.front], nil
}

func (q *Queue) Rear() (string, error) {
    if q.IsEmpty() {
        return "", fmt.Errorf("la file d'attente est vide")
    }
    return q.q[q.rear], nil
}

func (q *Queue) Print() []string {
    return q.q[q.front : q.rear+1]
}

func New(capacity int) *Queue {
    q := &Queue{
        capacity: capacity,
        rear:     capacity - 1,
        q:        make([]string, capacity),
    }
    return q
}

func main() {
    queue := New(6)
    queue.EnQueue("10")
    queue.EnQueue("20")
    queue.EnQueue("30")
    queue.EnQueue("40")
    queue.EnQueue("50")
    queue.EnQueue("60")
    fmt.Println(queue.EnQueue("70")) // Test Capcacity Exceeded EnQueue.
    fmt.Println(queue.Print())
    fmt.Println(queue.DeQueue())
    fmt.Println(queue.DeQueue())
    fmt.Println(queue.DeQueue())
    fmt.Println(queue.Print())
    fmt.Println(queue.DeQueue())
    fmt.Println(queue.DeQueue())
    fmt.Println(queue.DeQueue())
    fmt.Println(queue.DeQueue()) // Test Empty DeQueue.
    fmt.Println(queue.Print())
    queue.EnQueue("80")
    fmt.Println(queue.Print())
    fmt.Println(queue.DeQueue())
    fmt.Println(queue.Print())
}

Answer 3

J'ai implémenté une file d'attente qui va automatiquement étendre le tampon sous-jacent :

package types

// Remarque : cette file d'attente ne réduit pas le tampon sous-jacent.
type queue struct {
        buf  [][4]int // changer par le type de données de l'élément dont vous avez besoin
        head int
        tail int
}

func (q *queue) extend(need int) {
        if need-(len(q.buf)-q.head) > 0 {
                if need-len(q.buf) <= 0 {
                        copy(q.buf, q.buf[q.head:q.tail])
            q.tail = q.tail - q.head
                        q.head = 0
                        return
                }

                newSize := len(q.buf) * 2
                if newSize == 0 {
                    newSize = 100
            }
                newBuf := make([][4]int, newSize)
                copy(newBuf, q.buf[q.head:q.tail])
                q.buf = newBuf
        q.tail = q.tail - q.head
                q.head = 0
        }
}

func (q *queue) push(p [4]int) {
        q.extend(q.tail + 1)
        q.buf[q.tail] = p
        q.tail++
}

func (q *queue) pop() [4]int {
        r := q.buf[q.head]
        q.head++
        return r
}

func (q *queue) size() int {
        return q.tail - q.head
}

// mettre ce qui suit dans queue_test.go
package types

import (
        "testing"

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

func TestQueue(t *testing.T) {
        const total = 1000
        q := &queue{}
        for i := 0; i < total; i++ {
                q.push([4]int{i, i, i, i})
                assert.Equal(t, i+1, q.size())
        }

    for i := 0; i < total; i++ {
                v := q.pop()
                assert.Equal(t, [4]int{i, i, i, i}, v)
                assert.Equal(t, total-1-i, q.size())
        }
}

Answer 4

La liste est suffisante pour la file d'attente et la pile, ce que nous devons faire est l.Remove(l.Front()) pour la file d'attente Poll, l.Remove(l.Back()) pour la pile Poll, PushBack pour l'opération Ajouter pour la pile et la file d'attente. Il y a des pointeurs front et back pour la liste, de sorte que la complexité temporelle est O(1).

Answer 5

À partir de Go v1.18, des génériques ont été ajoutés que j'utiliserais pour créer une file d'attente générique.

Voici mes implémentations

type queue[T any] struct {
    bucket []T
}

func newQueue[T any]() *queue[T] {
    return &queue[T]{
        bucket: []T{},
    }
}

func (q *queue[T]) append(input T) {
    q.bucket = append(q.bucket, input)
}

func (q *queue[T]) tryDequeue() (T, bool) {
    if len(q.bucket) == 0 {
        var dummy T
        return dummy, false
    }
    value := q.bucket[0]
    var zero T
    q.bucket[0] = zero // Éviter les fuites mémoire
    q.bucket = q.bucket[1:]
    return value, true
}

Chaque fois que dequeue est appelé, la file d'attente est redimensionnée pour libérer de la mémoire en utilisant le découpage pour éviter de copier la mémoire. Ce n'est pas sécurisé pour les threads, dans ces cas, les canaux sont probablement meilleurs - mais il faut connaître la capacité des files d'attente pour spécifier une taille de tampon correcte.

Pour le plaisir, j'ai fait un benchmark comparant une file d'attente qui utilise interface{} - la manière d'avoir une solution générique avant Go v1.18. Le test ajoute et extrait ensuite 1, 10, 100 et 1 000 entiers. Dans tous les cas, les génériques sont beaucoup plus rapides avec moins d'utilisation de mémoire.

Benchmark_queues/QueueGeneric-Size_1-8          38296201                32.78 ns/op            8 B/op          1 allocs/op
Benchmark_queues/QueueInterface-Size_1-8        11626666                147.6 ns/op           16 B/op          1 allocs/op
Benchmark_queues/QueueGeneric-Size_10-8          7846665                168.2 ns/op          160 B/op          2 allocs/op
Benchmark_queues/QueueInterface-Size_10-8        1501284                752.8 ns/op          320 B/op          2 allocs/op
Benchmark_queues/QueueGeneric-Size_100-8         1000000                 1088 ns/op         1536 B/op          1 allocs/op
Benchmark_queues/QueueInterface-Size_100-8        240232                 6798 ns/op         3072 B/op          1 allocs/op
Benchmark_queues/QueueGeneric-Size_1000-8         120244                13468 ns/op        17920 B/op          3 allocs/op
Benchmark_queues/QueueInterface-Size_1000-8        20310                54528 ns/op        35776 B/op          4 allocs/op

L'implémentation de la file d'attente utilisant interface{} est donnée ci-dessous - la gestion des erreurs est ajoutée, ce que je pense est nécessaire.

type queueInterface struct {
    bucket []interface{}
}

func newQueueInterface() *queueInterface {
    return &queueInterface{
        bucket: []interface{}{},
    }
}

func (q *queueInterface) append(input interface{}) error {
    if len(q.bucket) != 0 && reflect.TypeOf(q.bucket[0]) != reflect.TypeOf(input) {
        return errors.New("le type d'entrée n'est pas le même que ceux déjà dans la file d'attente")
    }
    q.bucket = append(q.bucket, input)
    return nil
}

func (q *queueInterface) tryDequeue(out interface{}) (bool, error) {
    if len(q.bucket) == 0 {
        return false, nil
    }

    valuePtr := reflect.ValueOf(out)
    if valuePtr.Kind() != reflect.Ptr {
        return false, errors.New("doit être un pointeur")
    }

    value := q.bucket[0]
    if valuePtr.Elem().Type() != reflect.TypeOf(value) {
        return false, errors.New("la sortie doit être du même type que les éléments de la file d'attente")
    }
    valuePtr.Elem().Set(reflect.ValueOf(value))

    var zero interface{}
    q.bucket[0] = zero // Éviter les fuites mémoire
    q.bucket = q.bucket[1:]
    return true, nil
}