Chcę utworzyć wydajny bufor cykliczny w Pythonie (w celu pobierania średnich wartości całkowitych w buforze).
Czy jest to skuteczny sposób używania listy do zbierania wartości?
def add_to_buffer( self, num ):
self.mylist.pop( 0 )
self.mylist.append( num )
Co byłoby bardziej wydajne (i dlaczego)?
python
circular-buffer
jedierikb
źródło
źródło
Odpowiedzi:
Chciałbym skorzystać
collections.deque
zmaxlen
argW dokumentacji jest przepis na
deque
podobny do tego, co chcesz. Moje twierdzenie, że jest najbardziej efektywny, opiera się całkowicie na fakcie, że jest implementowany w C przez niesamowicie wykwalifikowaną załogę, która ma zwyczaj tworzenia kodu najwyższej klasy.źródło
maxlen
jest zdefiniowane. O (n) jest zrozumiałe, gdydeque
może rosnąć do nieskończoności, ale jeślimaxlen
jest podane, indeksowanie elementu powinno być stałe w czasie.wyskakiwanie z początku listy powoduje skopiowanie całej listy, więc jest nieefektywne
Zamiast tego powinieneś użyć listy / tablicy o stałym rozmiarze i indeksu, który przesuwa się przez bufor podczas dodawania / usuwania elementów
źródło
W oparciu o odpowiedź MoonCactus , oto
circularlist
klasa. Różnica w stosunku do jego wersji polega na tym, że tutajc[0]
zawsze będzie dawał najstarszy dołączony element,c[-1]
ostatni dołączony element,c[-2]
przedostatni… Jest to bardziej naturalne dla aplikacji.Klasa:
[Edytowano]: Dodano opcjonalny
data
parametr umożliwiający inicjalizację z istniejących list, np .:źródło
c[-1]
zawsze właściwy element.__getitem__
robi to dobrze.Deque Pythona jest powolny. Możesz także użyć numpy.roll. Jak obrócić liczby w tablicy numpy o kształcie (n,) lub (n, 1)?
W tym teście deque wynosi 448 ms. Numpy.roll to 29 ms http://scimusing.wordpress.com/2013/10/25/ring-buffers-in-pythonnumpy/
źródło
numpy.roll
zwraca kopię tablicy, prawda?ok z użyciem klasy deque, ale dla wymagań pytania (średnia) jest moje rozwiązanie:
źródło
TypeError: 'numpy.float64' object is not callable
, próbując wywołaćaverage
metodęcollections
jest częścią biblioteki standardowej,numpy
nie jest. Zależności od bibliotek stron trzecich byłyby okropną biblioteką standardową.Chociaż jest tu już wiele świetnych odpowiedzi, nie mogłem znaleźć żadnego bezpośredniego porównania czasów dla wymienionych opcji. Dlatego proszę, znajdź moją skromną próbę porównania poniżej.
Wyłącznie do celów testowych, klasa może przełączać się między
list
buforemcollections.deque
opartym na a , buforze a iNumpy.roll
buforze opartym na a .Zauważ, że
update
metoda dodaje tylko jedną wartość naraz, aby była prosta.W moim systemie daje to:
źródło
A co z rozwiązaniem z książki kucharskiej języka Python , w tym ponownej klasyfikacji instancji bufora pierścieniowego, gdy się zapełni?
Kredyt: Sébastien Keim
źródło
Możesz również zobaczyć ten dość stary przepis w Pythonie .
Oto moja własna wersja z tablicą NumPy:
źródło
O(n)
czas. Aby zaimplementować odpowiedni bufor cykliczny , powinieneś mieć zarówno indeks, jak i zmienną rozmiaru, i musisz poprawnie obsłużyć przypadek, gdy dane „zawijają się” na końcu bufora. Podczas pobierania danych może być konieczne połączenie dwóch sekcji na początku i na końcu bufora.Ten nie wymaga żadnej biblioteki. Tworzy listę, a następnie przechodzi do niej według indeksu.
Ślad jest bardzo mały (brak biblioteki) i działa przynajmniej dwa razy szybciej niż usuwanie z kolejki. Rzeczywiście dobrze jest obliczyć średnie kroczące, ale należy pamiętać, że elementy nie są sortowane według wieku, jak powyżej.
Aby uzyskać średnią wartość, np .:
Prowadzi do:
To około 1/3 czasu odpowiednika z kolejką.
źródło
__getitem__
być trochę mocniejszyself._data[(key + self._index + 1) % self._size]
:?Miałem ten problem przed programowaniem szeregowym. Nieco ponad rok temu też nie mogłem znaleźć żadnej wydajnej implementacji, więc napisałem jedną jako rozszerzenie C i jest ona również dostępna na pypi na licencji MIT. Jest super podstawowy, obsługuje tylko bufory 8-bitowych znaków ze znakiem, ale ma elastyczną długość, więc możesz użyć Struct lub czegoś na nim, jeśli potrzebujesz czegoś innego niż znaki. Widzę teraz w wyszukiwarce Google, że obecnie jest kilka opcji, więc warto też je przejrzeć.
źródło
Twoja odpowiedź jest nieprawidłowa. Główny bufor kołowy ma dwie zasady (https://en.wikipedia.org/wiki/Circular_buffer )
twój kod poniżej:
Rozważmy sytuację, w której lista jest pełna, używając swojego kodu:
teraz dodajemy 6, lista zmienia się na
pozycje oczekujące na 1 na liście zmieniły swoją pozycję
Twój kod jest kolejką, a nie buforem koła.
Myślę, że odpowiedź Basja jest najbardziej skuteczna.
Nawiasem mówiąc, bufor koła może poprawić wydajność operacji dodania elementu.
źródło
Z Githuba:
https://github.com/heineman/python-data-structures/blob/master/2.%20Ubiquitous%20Lists/circBuffer.py
źródło
Pierwotne pytanie brzmiało: „ wydajny ” bufor cykliczny. Zgodnie z tą żądaną skutecznością, odpowiedź udzielona przez aaronasterling wydaje się być definitywnie poprawna. Użycie dedykowanej klasy zaprogramowanej w Pythonie i porównanie przetwarzania czasu z collections.deque pokazuje przyspieszenie x5,2 razy z deque! Oto bardzo prosty kod do przetestowania tego:
Aby przekształcić deque w listę, po prostu użyj:
Otrzymasz wtedy O (1) losowy dostęp do przedmiotów Deque. Oczywiście jest to cenne tylko wtedy, gdy musisz wykonać wiele losowych dostępów do deque po jednokrotnym ustawieniu.
źródło
Powoduje to zastosowanie tej samej zasady do niektórych buforów przeznaczonych do przechowywania najnowszych wiadomości tekstowych.
źródło
Możesz sprawdzić ten cykliczny bufor oparty na predefiniowanej tablicy numpy o rozmiarze. Pomysł polega na tym, że tworzysz bufor (przydzielasz pamięć dla tablicy numpy), a następnie dodajesz do niego. Wprowadzanie danych i wyszukiwanie jest bardzo szybkie. Stworzyłem ten moduł w podobnym celu, jakiego potrzebujesz. W moim przypadku mam urządzenie, które generuje dane całkowite. Przeczytałem dane i umieściłem je w buforze okrężnym w celu późniejszej analizy i przetwarzania.
źródło