Есть ли реализация очереди?

Question

Может кто-нибудь предложить контейнер Go для простой и быстрой FIF / очереди, Go имеет 3 различных контейнера: heap, list и vector. Какой из них больше подходит для реализации очереди?

Answer 1

На самом деле, если то, что вы хотите, является простой и простой в использовании очередью fifo, slice предоставляет все необходимое.

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 !")
}

Конечно, мы полагаем, что можем доверять внутренней реализации добавления и среза, чтобы избежать ненужного изменения размера и перераспределения. Для базового использования этого вполне достаточно.

Answer 2

Удивлен тем, что никто еще не предложил буферизованные каналы для очереди FIFO с ограниченным размером в любом случае.

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

//Push
c <- value

//Pop
x <- c

Answer 3

Либо вектор, либо список должны работать, но, вероятно, вектор - это путь. Я говорю это потому, что vector, вероятно, будет распределяться реже, чем list, а сборка мусора (в текущей реализации Go) довольно дорогая. В маленькой программе это, вероятно, не будет иметь значения.

Answer 4

Чтобы расширить на стороне реализации, Мораес предлагает в его суть некоторую структуру из очереди и стека:

// 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
}

Вы можете увидеть это в действии на этом примере детской площадки .

Answer 5

Использование среза и соответствующей ("круговой") схемы индексации сверху все еще кажется подходящим. Вот мое мнение об этом: https://github.com/phf/go-queue Тесты там также подтверждают, что каналы работают быстрее, но за счет более ограниченной функциональности.

Answer 6

Большинство реализаций очереди представлены в одном из трех вариантов: на основе слайса, на основе связанного списка и на основе кольцевого буфера (кольцевой буфер).

• Очереди на основе слайсов имеют тенденцию тратить впустую память, потому что они не используют память, ранее занятую удаленными элементами. Кроме того, очереди на основе срезов имеют тенденцию быть только односторонними.
• Очереди со связным списком могут быть лучше с памятью Повторное использование , но, как правило, немного медленнее и используют больше памяти в целом из-за накладных расходов на поддержание ссылок. Они могут предлагать возможность добавлять и удалять элементы из середины очереди, не перемещая память, но если вы делаете большую часть этой очереди, неправильная структура данных.
• Очереди кольцевого буфера предлагают всю эффективность срезов, с преимуществом не тратить память. Меньшее распределение означает лучшую производительность. Они одинаково эффективны при добавлении и удалении элементов с любого конца, поэтому вы, естественно, получаете двустороннюю очередь. Поэтому в качестве общей рекомендации я бы рекомендовал реализацию очереди на основе кольцевого буфера. Это то, что обсуждается в оставшейся части этого поста.

Очередь, основанная на кольцевом буфере, повторно использует память, оборачивая свое хранилище: по мере того, как очередь выходит за пределы одного конца основного слайса, она добавляет дополнительные узлы к другому концу слайса. См Диаграмма deque

Также немного кода для иллюстрации:

// 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
}

Эта конкретная реализация всегда использует размер буфера, равный степени 2, и поэтому может вычислить побитовый модуль, чтобы быть немного более эффективным.

Это означает, что срез должен расти только тогда, когда все его возможности исчерпаны. Благодаря стратегии изменения размера, позволяющей избежать увеличения и уменьшения объема хранилища на одной границе, это делает его очень эффективным для использования памяти.

Вот код, который изменяет размер нижележащего буфера слайса:

// 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
}

Еще одна вещь, которую нужно учитывать, - если вы хотите, чтобы безопасность параллелизма была встроена в реализацию. Возможно, вы захотите избежать этого, чтобы вы могли делать все, что лучше всего подходит для вашей стратегии параллелизма, и вы определенно не хотите этого, если она вам не нужна; та же причина, по которой не нужен фрагмент, имеющий некоторую встроенную сериализацию.

Существует ряд реализаций очереди на основе кольцевого буфера для Go, если вы выполняете поиск по godoc для deque. Выберите тот, который лучше всего соответствует вашим вкусам.

Answer 7

Просто вставьте "container/list" в простую реализацию и откройте интерфейс

package queue

import "container/list"

// Queue is a queue
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)
}

// New is a new instance of a Queue
func New() Queue {
    return &queueImpl{list.New()}
}

Answer 8

К сожалению, очереди в настоящее время не входят в стандартную библиотеку go, поэтому вам нужно написать собственное / импортировать чье-либо решение. Обидно, поскольку контейнеры, написанные вне стандартной библиотеки, не могут использовать дженерики.

Простой пример очереди с фиксированной емкостью:

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
}

Gotchas, которых здесь избегают, включают отсутствие неограниченного роста срезов (вызванного использованием операции slice [1:] для отбрасывания) и обнуление вытолкнутых элементов, чтобы гарантировать, что их содержимое доступно для сбора мусора. Обратите внимание, что в случае MyQueueElement структуры, содержащей только int, как здесь, это не будет иметь никакого значения, но если бы структура содержала указатели, это было бы.

Решение может быть расширено для перераспределения и копирования в случае необходимости автоматически растущей очереди.

Это решение не является поточно-ориентированным, но при желании можно добавить блокировку в Push / Pop.

Детская площадка https://play.golang.org/

Answer 9

Я также реализую очередь из фрагмента, как указано выше.Тем не менее, это не потокобезопасный.Поэтому я решил добавить блокировку (блокировку mutex), чтобы гарантировать потокобезопасность.

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
}

Вы можете проверить мое решение на github здесь простая очередь

Answer 10

списка достаточно для очереди и стека, что мы должны сделать: l.Remove(l.Front()) для очереди Poll, l.Remove(l.Back()) для стека Poll, PushBack для операции добавления для стека и очереди. для списка есть передний и задний указатель, так что временная сложность составляет O (1)