Блог

Главная - Вопросы по программированию - эффективное хранение коллекции из последних N отправленных элементов

эффективное хранение коллекции из последних N отправленных элементов

#arrays #go #memory #slice

#массивы #Вперед #память #срез

Вопрос:

Учитывая:

  1. фрагмент с заранее известной емкостью
  2. емкость и количество фрагментов велики, и будет использоваться около 15 МБ памяти, поэтому я не хочу тратить память впустую и хочу сохранить минимум памяти.
  3. фрагмент будет обновлен путем удаления первого элемента и добавления нового элемента в конец фрагмента.

b = append(b[1:], n) увеличит емкость

чтобы сдвинуть и назначить себя, я написал

 func shiftAndPut(a []int, n int) (b []int) {
    b = make([]int, cap(a), cap(a))
    for i,v := range(a[1:]) {
        b[i] = v
    }
    b[len(b)-1] = n
    return
}

https://play.golang.org/p/7xIBh0UPp2w

Он сохраняет ту же емкость, но требует различных вычислений

  1. повторение фрагмента за один раз,
  2. вызов функции,
  3. новая переменная для малого времени,
  4. функция подрезки в диапазоне, которая добавляет больше вычислений,
  5. и т. д

Есть ли какой-либо более оптимизированный способ сделать это?

Комментарии:

1. Для того, чтобы переместить значения в срезе (или массиве), вам нужно переместить каждое значение, «более оптимизированного» способа сделать это нет. Похоже, вам нужна другая структура данных, вы пытаетесь создать кольцевой буфер?

2. Временный буфер может быть устранен: play.golang.org/p/72T8AquHG-B . Если стоимость переноса высока, то вы можете захотеть использовать кольцевой буфер , как предлагает JimB.

3. @MikaelBrenner: конечно, я упомянул только одну другую возможность для краткости, поскольку кольцевой буфер часто является наиболее эффективной реализацией, и вопрос был действительно о срезах.

4. @mkmayank: если вы всегда удаляете из заголовка и добавляете к хвосту с фиксированным объемом памяти, то вам нужен какой-то циклический буфер. В stdlib есть container/ring пакет, или вы можете просто абстрагировать концепцию над фиксированным фрагментом (или найти другой пакет, который подходит для вас)

5. Очевидно, что выполнение меньшего объема работы происходит быстрее. Если вы можете предварительно выделить то, что вам нужно, и манипулировать только индексом фрагмента, тогда оптимизировать больше нечего. Если сомневаетесь, проведите тест и измерьте.

Ответ №1:

Кольцевой буфер среза, пользовательская реализация :

 data := make([]int, cap, cap)
pointer := 0

data[pointer] = newData
pointer = (pointer 1) % cap

реализация контейнера / кольцевого пакета :

 data := ring.New(cap)
data.Value = newData
data = data.Next()

После предложения в ветке комментариев я провел сравнительный анализ между пользовательским сдвигом среза и контейнером / кольцом

 BenchmarkCustom1000-4         100000         17322 ns/op
BenchmarkRing1000-4           100000         22824 ns/op
BenchmarkCustom-4           100000000           17.4 ns/op
BenchmarkRing-4             100000000           22.8 ns/op

пользовательский сдвиг фрагмента с использованием переменной (указатель или флаг) быстрее, а также оптимизирована память.