Python Queue положил (), get () в один цикл Превышено ограничение по времени - PullRequest
Новая
       10

Python Queue положил (), get () в один цикл Превышено ограничение по времени

0 голосов
/ 28 октября 2018

Я вычисляю скользящее среднее всех целых чисел в скользящем окне, используя Очередь.Однако я получил TLE, когда хочу сначала получить число из очереди, добавить к сумме, а затем вернуть его обратно.Я думаю, что это из-за моего цикла for, кто-нибудь может помочь? 

import queue

class MovingAverage:
    """
    @param: size: An integer
    """
    def __init__(self, size):
        # do intialization if necessary
        self.q = queue.Queue(size)

    """
    @param: val: An integer
    @return:  
    """
    def next(self, val):
        # write your code here
        if self.q.qsize() > 3:
            self.q.get()

        self.q.put(val)
        a = 0
        **for _ in range(self.q.qsize()):
            n = self.q.get()
            a += n 
            self.q.put(n)**

        return a

1 Ответ

0 голосов
/ 28 октября 2018

Вы используете не тот инструмент здесь.Модуль queue в целом и queue.Queue в частности предназначены для использования в многопоточных программах!В однопоточной программе вы не можете добавлять элементы за пределы maxsize.Из документов:

Вставка будет заблокирована после достижения этого размера, пока элементы очереди не будут израсходованы.

Эта блокировка просто остановит вашу программу на первом put за maxsize.

Вам лучше использовать, например, collections.deque.Кроме того, вы должны улучшить свой алгоритм.Скользящая средняя (или скользящая сумма, согласно вашему коду) не должна (и) повторять все окно все время ...

Например: 

from collections import deque

class MovingAverage:
    def __init__(self, size):
        self.q = deque()
        self.a = 0
        self.size = size

    def next(self, val):
        if len(self.q) == self.size:
            self.a -= self.q.popleft()
        self.q.append(val)
        self.a += val
        return self.a
        # or, for the average
        return self.a / len(self.q)

>>> m = MovingAverage(3)
>>> m.next(1)
1.0
>>> m.next(2)
1.5
>>> m.next(3)
2.0
>>> m.next(4)
3.0
>>> m.next(5)
4.0
>>> m.next(1)
3.3333333333333335
>>> m.next(1)
2.3333333333333335
>>> m.next(1)
1.0
...