Я хочу создать эффективный кольцевой буфер в python (с целью получения средних значений целочисленных значений в буфере).
Является ли это эффективным способом использования списка для сбора значений?
def add_to_buffer( self, num ):
self.mylist.pop( 0 )
self.mylist.append( num )
Что было бы эффективнее (и почему)?
python
circular-buffer
jedierikb
источник
источник
Ответы:
Я бы использовал
collections.deque
сmaxlen
аргументомСуществует рецепт в документации для ,
deque
который похож на то , что вы хотите. Мое утверждение, что это самый эффективный, полностью основывается на том факте, что он реализован на C невероятно опытной командой, которая имеет обыкновение создавать первоклассный код.источник
maxlen
он определен. O (n) понятно, когдаdeque
может расти до бесконечности, но еслиmaxlen
задан, индексирование элемента должно быть постоянным по времени.выскакивание из заголовка списка вызывает копирование всего списка, поэтому неэффективно
Вместо этого вы должны использовать список / массив фиксированного размера и индекс, который перемещается через буфер при добавлении / удалении элементов.
источник
Основываясь на ответе MoonCactus , вот
circularlist
класс. Разница с его версией в том, что здесьc[0]
всегда будет отображаться элемент с самым старым добавлением, элементc[-1]
с последним добавлением,c[-2]
предпоследний ... Это более естественно для приложений.Класс:
[Отредактировано]: добавлен необязательный
data
параметр, разрешающий инициализацию из существующих списков, например:источник
c[-1]
это всегда правильный элемент.__getitem__
делает это правильно.Deque Python работает медленно. Вместо этого вы также можете использовать numpy.roll. Как вы поворачиваете числа в массиве numpy формы (n,) или (n, 1)?
В этом тесте deque составляет 448 мс. Numpy.roll составляет 29 мс http://scimusing.wordpress.com/2013/10/25/ring-buffers-in-pythonnumpy/
источник
numpy.roll
возвращает копию массива, верно?хорошо с использованием класса deque, но для требований вопроса (в среднем) это мое решение:
источник
TypeError: 'numpy.float64' object is not callable
при попытке вызватьaverage
методcollections
является частью стандартной библиотеки,numpy
не является. Зависимости от сторонних библиотек сделали бы стандартную библиотеку ужасной.Хотя здесь уже есть множество отличных ответов, я не смог найти прямого сравнения таймингов для упомянутых вариантов. Поэтому, пожалуйста, найдите мою скромную попытку сравнения ниже.
Только для целей тестирования класс может переключаться между
list
буфером наcollections.deque
основе, буфером наNumpy.roll
основе и буфером на основе.Обратите внимание, что
update
для простоты метод добавляет за раз только одно значение.В моей системе это дает:
источник
Как насчет решения из Поваренной книги Python , включая реклассификацию экземпляра кольцевого буфера, когда он становится заполненным?
Предоставлено: Себастьян Кейм.
источник
Вы также можете увидеть этот довольно старый рецепт Python .
Вот моя собственная версия с массивом NumPy:
источник
O(n)
времени. Чтобы реализовать правильный кольцевой буфер , у вас должны быть как индекс, так и переменная размера, и вам нужно правильно обрабатывать случай, когда данные «оборачиваются» вокруг конца буфера. При извлечении данных вам может потребоваться объединить две секции в начале и в конце буфера.Это не требует какой-либо библиотеки. Он увеличивает список, а затем цикл по индексу.
Размер места очень мал (без библиотеки), и он работает по крайней мере в два раза быстрее, чем удаление из очереди. Это действительно хорошо для вычисления скользящих средних, но имейте в виду, что элементы не отсортированы по возрасту, как указано выше.
Чтобы получить среднее значение, например:
Результаты в:
Это примерно 1/3 времени эквивалента с удалением из очереди.
источник
__getitem__
быть немного более мощным:self._data[(key + self._index + 1) % self._size]
?У меня была эта проблема до последовательного программирования. В то время, чуть больше года назад, я тоже не мог найти никаких эффективных реализаций, поэтому в итоге я написал его как расширение C, и оно также доступно на pypi по лицензии MIT. Он супер простой, обрабатывает только буферы 8-битных подписанных символов, но имеет гибкую длину, поэтому вы можете использовать Struct или что-то поверх него, если вам нужно что-то другое, кроме символов. Теперь с помощью поиска в Google я вижу, что в наши дни есть несколько вариантов, так что вы, возможно, захотите посмотреть и на них.
источник
Вы ответ неверный. Главный круговой буфер имеет два принципа ( https://en.wikipedia.org/wiki/Circular_buffer )
ваш код ниже:
Давайте рассмотрим ситуацию, когда список заполнен, используя ваш код:
теперь мы добавляем 6, список меняется на
элементы, ожидающие 1 в списке, изменили свое положение
ваш код - это очередь, а не круговой буфер.
Ответ Басжа я считаю наиболее действенным.
Кстати, круговой буфер может улучшить производительность операции добавления элемента.
источник
Из Github:
https://github.com/heineman/python-data-structures/blob/master/2.%20Ubiquitous%20Lists/circBuffer.py
источник
Первоначальный вопрос был: « эффективный » кольцевой буфер. В соответствии с запрошенной эффективностью ответ от aaronasterling кажется окончательно правильным. Использование специального класса, запрограммированного на Python, и сравнение обработки времени с помощью collections.deque показывает ускорение в 5,2 раза с deque! Вот очень простой код для проверки:
Чтобы преобразовать двухстороннюю очередь в список, просто используйте:
Затем вы получите O (1) произвольный доступ к элементам двухсторонней очереди. Конечно, это полезно только в том случае, если вам нужно сделать много случайных обращений к двухсторонней очереди после ее однократной установки.
источник
Это применяет тот же принцип к некоторым буферам, предназначенным для хранения самых последних текстовых сообщений.
источник
Вы можете проверить этот круговой буфер на основе массива numpy предопределенного размера. Идея состоит в том, что вы создаете буфер (выделяете память для массива numpy), а затем добавляете к нему. Ввод данных и извлечение происходит очень быстро. Я создал этот модуль для той же цели, что и вам. В моем случае у меня есть устройство, которое генерирует целочисленные данные. Я читаю данные и помещаю их в кольцевой буфер для дальнейшего анализа и обработки.
источник