go - ¿Hay una implementación de cola?

queue fifo

Question

¿Alguien puede sugerir Go contenedor para FIF / queue simple y rápido, Go tiene 3 contenedores diferentes: heap , list y vector . ¿Cuál es más adecuado para implementar una cola?

Answer 1

Cualquiera de los vectores o listas debería funcionar, pero el vector es probablemente el camino a seguir. Digo esto porque el vector probablemente se asignará con menos frecuencia que la lista y la recolección de basura (en la implementación actual de Go) es bastante costosa. Sin embargo, en un programa pequeño probablemente no importará.

Answer 2

De hecho, si lo que quieres es una cola fifo básica y fácil de usar, slice te proporciona todo lo que necesitas.

queue := make([]int, 0)
// Push to the queue
queue = append(queue, 1)
// Top (just get next element, don''t remove it)
x = queue[0]
// Discard top element
queue = queue[1:]
// Is empty ?
if len(queue) == 0 {
    fmt.Println("Queue is empty !")
}

Por supuesto, suponemos que podemos confiar en la implementación interna de append y slicing para evitar el reajuste y la reasignación inútiles. Para un uso básico, esto es perfectamente suficiente.

Answer 3

El uso de una porción y un esquema de indexación apropiado ("circular") en la parte superior todavía parece ser el camino a seguir. Este es mi punto de vista: https://github.com/phf/go-queue Los puntos de referencia allí también confirman que los canales son más rápidos, pero a costa de una funcionalidad más limitada.

Answer 4

Implementé una cola que ampliará automáticamente el búfer subyacente:

package types

// Note: this queue does not shrink the underlying buffer.                                                                                                               
type queue struct {
        buf  [][4]int // change to the element data type that you need                                                                                                   
        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
}


// put the following into 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 5

La mayoría de las implementaciones de cola están en uno de los tres sabores: basado en sectores, vinculado basado en listas y circular-buffer (anillo-buffer) basado.

• Las colas basadas en sectores tienden a desperdiciar memoria porque no reutilizan la memoria ocupada previamente por los elementos eliminados. Además, las colas basadas en sectores suelen ser de un solo extremo.
• Las colas de listas enlazadas pueden ser mejores sobre la reutilización de memoria, pero generalmente son un poco más lentas y usan más memoria en general debido a la sobrecarga de mantener enlaces. Pueden ofrecer la capacidad de agregar y eliminar elementos del medio de la cola sin mover la memoria, pero si está haciendo mucho de eso, una cola es la estructura de datos incorrecta.
• Las colas de buffer de anillo ofrecen toda la eficacia de las divisiones, con la ventaja de no desperdiciar memoria. Menos asignaciones significa un mejor rendimiento. Son igual de eficaces para agregar y eliminar elementos de cada extremo, por lo que naturalmente obtienes una cola doble. Entonces, como recomendación general, recomendaría una implementación de cola basada en el buffer de anillo. Esto es lo que se discute en el resto de esta publicación.

La cola basada en el buffer de anillo reutiliza la memoria envolviendo su almacenamiento: a medida que la cola crece más allá de un extremo del segmento subyacente, agrega nodos adicionales al otro extremo del segmento. Ver diagrama de deque

Además, un poco de código para ilustrar:

// PushBack appends an element to the back of the queue.  Implements FIFO when
// elements are removed with PopFront(), and LIFO when elements are removed
// with PopBack().
func (q *Deque) PushBack(elem interface{}) {
    q.growIfFull()
    q.buf[q.tail] = elem
    // Calculate new tail position.
    q.tail = q.next(q.tail)
    q.count++
}

// next returns the next buffer position wrapping around buffer.
func (q *Deque) next(i int) int {
    return (i + 1) & (len(q.buf) - 1) // bitwise modulus
}

Esta implementación particular siempre usa un tamaño de búfer que es una potencia de 2, y por lo tanto puede calcular el módulo bit a bit para que sea un poco más eficiente.

Esto significa que la porción debe crecer solo cuando se agote toda su capacidad. Con una estrategia de redimensionamiento que evita el crecimiento y la reducción del almacenamiento en el mismo límite, esto hace que sea muy eficiente en cuanto a la memoria.

Aquí hay un código que cambia el tamaño del buffer de la rebanada subyacente:

// resize resizes the deque to fit exactly twice its current contents. This is
// used to grow the queue when it is full, and also to shrink it when it is     
// only a quarter full.                                                         
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
}

Otra cosa a considerar es si desea seguridad de concurrencia integrada en la implementación. Es posible que desee evitar esto para que pueda hacer lo que funcione mejor para su estrategia de simultaneidad, y ciertamente no lo desea si no lo necesita; mismo motivo por el que no se quiere un sector que tenga una serialización incorporada.

Hay una serie de implementaciones de cola basadas en el buffer de anillo para Go si realiza una búsqueda en godoc para deque. Elija el que mejor se adapte a sus gustos.

Answer 6

Lamentablemente, las colas actualmente no forman parte de la biblioteca estándar go, por lo que debe escribir la suya / importar la solución de otra persona. Es una pena que los contenedores escritos fuera de la biblioteca estándar no puedan usar genéricos.

Un ejemplo simple de una cola de capacidad fija sería:

type MyQueueElement struct {
  blah int // whatever you want
}

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
}

Las cosas que se evitan aquí incluyen no tener un crecimiento de corte ilimitado (causado por el uso de la operación de corte [1:] para descartar), y poner a cero los elementos revelados para garantizar que su contenido esté disponible para la recolección de elementos no utilizados. Tenga en cuenta que, en el caso de una estructura MyQueueElement contenga solo un int como aquí, no hará ninguna diferencia, pero si struct contiene punteros lo haría.

La solución podría ampliarse para reasignar y copiar si se deseara una cola de crecimiento automático.

Esta solución no es segura para subprocesos, pero se podría agregar un bloqueo a Push / Pop si así lo desea.

Área de juegos https://play.golang.org/

Answer 7

Para ampliar en el lado de la implementación, Moraes propone en su esencia algunas estructuras de cola y pila:

// Stack is a basic LIFO stack that resizes as needed.
type Stack struct {
    nodes   []*Node
    count   int
}
// Queue is a basic FIFO queue based on a circular list that resizes as needed.
type Queue struct {
    nodes   []*Node
    head    int
    tail    int
    count   int
}

Puedes verlo en acción en este ejemplo de patio de recreo .

Answer 8

Slice se puede usar para implementar cola.

type queue struct {
    values []*int
}

func New() *queue {
   queue := &queue{}
   return queue
}

func (q *queue) enqueue(val *int) {
   q.values = append(q.values, val)
}

//deque function

Actualizar:

aquí está la implementación completa en mi página de GitHub https://github.com/raiskumar/algo-ds/blob/master/tree/queue.go

Answer 9

Sorprendido de ver que nadie ha sugerido canales almacenados aún, para el tamaño de FIFO Queue enlazado de todos modos.

//Or however many you might need + buffer.
c := make(chan int, 300)

//Push
c <- value

//Pop
x <- c

Answer 10

También implemento la cola de slice como se indica arriba. Sin embargo, no es seguro para subprocesos. Así que decidí agregar un bloqueo (bloqueo mutex) para garantizar la seguridad de subprocesos.

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
}

Puedes verificar mi solución en github aquí simple cola