python - कुशल परिपत्र बफर?




circular-buffer (8)

मैं अजगर में एक कुशल परिपत्र बफर बनाना चाहता हूं ( बफर में पूर्णांक मानों का औसत लेने के लक्ष्य के साथ)।

मूल्यों को इकट्ठा करने के लिए सूची का उपयोग करने का यह एक प्रभावी तरीका है?

def add_to_buffer( self, num ):
    self.mylist.pop( 0 )
    self.mylist.append( num )

क्या अधिक कुशल होगा (और क्यों)?


आप जवाब सही नहीं है। परिपत्र बफर मुख्य में दो priciples ( https://en.wikipedia.org/wiki/Circular_buffer ) है

  1. बफर का दसवां भाग निर्धारित किया जाता है;
  2. पहला अंदर पहला बाहर;
  3. जब आप कोई आइटम जोड़ते या हटाते हैं, तो अन्य वस्तुओं को अपनी स्थिति नहीं लेनी चाहिए

नीचे आपका कोड:

def add_to_buffer( self, num ):
    self.mylist.pop( 0 )
    self.mylist.append( num )

चलो एक स्थिति पर विचार करें कि सूची पूरी है, अपने कोड का उपयोग करके:

self.mylist = [1, 2, 3, 4, 5]

अब हम 6 जोड़ते हैं, सूची बदल दी गई है

self.mylist = [2, 3, 4, 5, 6]

सूची में 1 आइटम की उम्मीद है कि उनकी स्थिति बदल गई है

आपका कोड एक कतार है, सर्कल बफर नहीं।

बसज का जवाब, मुझे लगता है कि सबसे प्रभावशाली है।

वैसे, एक सर्कल बफर एक आइटम जोड़ने के लिए ऑपरेशन के प्रदर्शन को लागू कर सकता है।


आप यह पुरानी पायथन रेसिपी भी देख सकते हैं।

NumPy सरणी के साथ मेरा अपना संस्करण यहां दिया गया है:

#!/usr/bin/env python

import numpy as np

class RingBuffer(object):
    def __init__(self, size_max, default_value=0.0, dtype=float):
        """initialization"""
        self.size_max = size_max

        self._data = np.empty(size_max, dtype=dtype)
        self._data.fill(default_value)

        self.size = 0

    def append(self, value):
        """append an element"""
        self._data = np.roll(self._data, 1)
        self._data[0] = value 

        self.size += 1

        if self.size == self.size_max:
            self.__class__  = RingBufferFull

    def get_all(self):
        """return a list of elements from the oldest to the newest"""
        return(self._data)

    def get_partial(self):
        return(self.get_all()[0:self.size])

    def __getitem__(self, key):
        """get element"""
        return(self._data[key])

    def __repr__(self):
        """return string representation"""
        s = self._data.__repr__()
        s = s + '\t' + str(self.size)
        s = s + '\t' + self.get_all()[::-1].__repr__()
        s = s + '\t' + self.get_partial()[::-1].__repr__()
        return(s)

class RingBufferFull(RingBuffer):
    def append(self, value):
        """append an element when buffer is full"""
        self._data = np.roll(self._data, 1)
        self._data[0] = value

किसी सूची के प्रमुख से पॉप-अप करने से पूरी सूची कॉपी हो जाती है, इसलिए अक्षम है

इसके बजाय आपको निश्चित आकार की सूची / सरणी और एक इंडेक्स का उपयोग करना चाहिए जो बफर के माध्यम से चलता है जब आप आइटम जोड़ते / हटाते हैं


डेक वर्ग के उपयोग के साथ ठीक है, लेकिन प्रश्न (औसत) की आवश्यकता के लिए यह मेरा समाधान है:

>>> from collections import deque
>>> class CircularBuffer(deque):
...     def __init__(self, size=0):
...             super(CircularBuffer, self).__init__(maxlen=size)
...     @property
...     def average(self):  # TODO: Make type check for integer or floats
...             return sum(self)/len(self)
...
>>>
>>> cb = CircularBuffer(size=10)
>>> for i in range(20):
...     cb.append(i)
...     print "@%s, Average: %s" % (cb, cb.average)
...
@deque([0], maxlen=10), Average: 0
@deque([0, 1], maxlen=10), Average: 0
@deque([0, 1, 2], maxlen=10), Average: 1
@deque([0, 1, 2, 3], maxlen=10), Average: 1
@deque([0, 1, 2, 3, 4], maxlen=10), Average: 2
@deque([0, 1, 2, 3, 4, 5], maxlen=10), Average: 2
@deque([0, 1, 2, 3, 4, 5, 6], maxlen=10), Average: 3
@deque([0, 1, 2, 3, 4, 5, 6, 7], maxlen=10), Average: 3
@deque([0, 1, 2, 3, 4, 5, 6, 7, 8], maxlen=10), Average: 4
@deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10), Average: 4
@deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], maxlen=10), Average: 5
@deque([2, 3, 4, 5, 6, 7, 8, 9, 10, 11], maxlen=10), Average: 6
@deque([3, 4, 5, 6, 7, 8, 9, 10, 11, 12], maxlen=10), Average: 7
@deque([4, 5, 6, 7, 8, 9, 10, 11, 12, 13], maxlen=10), Average: 8
@deque([5, 6, 7, 8, 9, 10, 11, 12, 13, 14], maxlen=10), Average: 9
@deque([6, 7, 8, 9, 10, 11, 12, 13, 14, 15], maxlen=10), Average: 10
@deque([7, 8, 9, 10, 11, 12, 13, 14, 15, 16], maxlen=10), Average: 11
@deque([8, 9, 10, 11, 12, 13, 14, 15, 16, 17], maxlen=10), Average: 12
@deque([9, 10, 11, 12, 13, 14, 15, 16, 17, 18], maxlen=10), Average: 13
@deque([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], maxlen=10), Average: 14

मूल सवाल था: " कुशल " परिपत्र बफर। इस दक्षता के मुताबिक, अरोर्नस्टरिंग का जवाब निश्चित रूप से सही लगता है। पायथन में प्रोग्राम किए गए एक समर्पित वर्ग का उपयोग करना और संग्रह के साथ समय प्रसंस्करण की तुलना करना। डेक डेक के साथ x5.2 गुणा त्वरण दिखाता है! इसका परीक्षण करने के लिए यहां बहुत आसान कोड है:

class cb:
    def __init__(self, size):
        self.b = [0]*size
        self.i = 0
        self.sz = size
    def append(self, v):
        self.b[self.i] = v
        self.i = (self.i + 1) % self.sz

b = cb(1000)
for i in range(10000):
    b.append(i)
# called 200 times, this lasts 1.097 second on my laptop

from collections import deque
b = deque( [], 1000 )
for i in range(10000):
    b.append(i)
# called 200 times, this lasts 0.211 second on my laptop

एक सूची में एक डेक को बदलने के लिए, बस उपयोग करें:

my_list = [v for v in my_deque]

फिर आप डेक आइटमों के लिए ओ (1) यादृच्छिक पहुंच प्राप्त करेंगे। बेशक, यह केवल मूल्यवान है यदि आपको इसे एक बार सेट करने के बाद डेक में कई यादृच्छिक पहुंच करने की आवश्यकता है।


मैं maxlen arg के साथ collections.deque उपयोग करता maxlen

>>> import collections
>>> d = collections.deque(maxlen=10)
>>> d
deque([], maxlen=10)
>>> for i in xrange(20):
...     d.append(i)
... 
>>> d
deque([10, 11, 12, 13, 14, 15, 16, 17, 18, 19], maxlen=10)

deque लिए दस्तावेज़ों में एक recipe है जो आप चाहते हैं के समान है। मेरा दावा है कि यह सबसे कुशल है पूरी तरह से इस तथ्य पर निर्भर करता है कि इसे सी में एक अविश्वसनीय रूप से कुशल दल द्वारा लागू किया गया है जो शीर्ष पायदान कोड को क्रैंक करने की आदत में है।


यह हाल ही के पाठ संदेशों को पकड़ने के इरादे से कुछ बफरों के लिए एक ही प्रिंसिपल लगा रहा है।

import time
import datetime
import sys, getopt

class textbffr(object):
    def __init__(self, size_max):
        #initialization
        self.posn_max = size_max-1
        self._data = [""]*(size_max)
        self.posn = self.posn_max

    def append(self, value):
        #append an element
        if self.posn == self.posn_max:
            self.posn = 0
            self._data[self.posn] = value   
        else:
            self.posn += 1
            self._data[self.posn] = value

    def __getitem__(self, key):
        #return stored element
        if (key + self.posn+1) > self.posn_max:
            return(self._data[key - (self.posn_max-self.posn)])
        else:
            return(self._data[key + self.posn+1])


def print_bffr(bffr,bffer_max): 
    for ind in range(0,bffer_max):
        stored = bffr[ind]
        if stored != "":
            print(stored)
    print ( '\n' )

def make_time_text(time_value):
    return(str(time_value.month).zfill(2) + str(time_value.day).zfill(2)
      + str(time_value.hour).zfill(2) +  str(time_value.minute).zfill(2)
      + str(time_value.second).zfill(2))


def main(argv):
    #Set things up 
    starttime = datetime.datetime.now()
    log_max = 5
    status_max = 7
    log_bffr = textbffr(log_max)
    status_bffr = textbffr(status_max)
    scan_count = 1

    #Main Loop
    # every 10 secounds write a line with the time and the scan count.
    while True: 

        time_text = make_time_text(datetime.datetime.now())
        #create next messages and store in buffers
        status_bffr.append(str(scan_count).zfill(6) + " :  Status is just fine at : " + time_text)
        log_bffr.append(str(scan_count).zfill(6) + " : " + time_text + " : Logging Text ")

        #print whole buffers so far
        print_bffr(log_bffr,log_max)
        print_bffr(status_bffr,status_max)

        time.sleep(2)
        scan_count += 1 

if __name__ == '__main__':
    main(sys.argv[1:])  

सीरियल प्रोग्रामिंग करने से पहले मुझे यह समस्या आई है। उस समय एक साल पहले, मुझे कोई भी कुशल कार्यान्वयन नहीं मिला, इसलिए मैंने एक सी एक्सटेंशन के रूप में लिखना समाप्त कर दिया और यह एमआईटी लाइसेंस के तहत पीपीआई पर भी उपलब्ध है। यह सुपर बेसिक है, केवल 8-बिट हस्ताक्षरित वर्णों के बफर हैंडल करता है, लेकिन लचीला लंबाई है, इसलिए यदि आप चार्ज के अलावा कुछ और चाहिए तो आप स्ट्रक्चर या इसके शीर्ष पर कुछ उपयोग कर सकते हैं। अब मैं एक Google खोज के साथ देखता हूं कि इन दिनों कई विकल्प हैं, इसलिए आप उन पर भी देखना चाहेंगे।






circular-buffer