Как оттолкнуть элементы от asyncio.PriorityQueue, когда он в максимальном размере, и я положил () новые элементы? - PullRequest
Новая
       26

Как оттолкнуть элементы от asyncio.PriorityQueue, когда он в максимальном размере, и я положил () новые элементы?

0 голосов
/ 26 января 2019

У меня есть asyncio.PriorityQueue, который я использую в качестве очереди URL-адреса для веб-сканера, при этом URL-адреса с наименьшей оценкой являются первыми, удаленными из очереди при вызове url_queue.get().Когда очередь достигает элементов maxsize, поведение по умолчанию заключается в блокировке вызовов на url_queue.put(), пока вызов get() не удалит элемент из очереди, чтобы освободить место.

То, что я хотел бы сделать, это никогда не блокировать, а вместо этого отталкивать элемент очереди с наивысшим баллом (или наименьший элемент с одним из наивысших баллов) всякий раз, когда я пытаюсь put() элементэто имеет более низкий балл.Есть ли способ автоматически удалять элементы из нижней части кучи в asyncio.PriorityQueue?Если нет, есть ли альтернативная реализация очереди приоритетов / кучи, которая работает с asyncio, что позволило бы мне это сделать?Или какая-то другая структура данных / техника, которая позволила бы мне иметь некую блокирующую приоритетную очередь с максимальным размером?

Спасибо!

1 Ответ

0 голосов
/ 26 января 2019

Есть ли способ автоматического удаления элементов из нижней части кучи таким образом в asyncio.PriorityQueue?

Не по умолчанию, но он должен быть простым для наследования от asyncio.PriorityQueue и просто реализовать желаемое поведение.В отличие от многопоточных реализаций очереди, асинхронная очередь выполняется в одном потоке, и поэтому не нужно беспокоиться о проблемах синхронизации.

Возможная проблема с производительностью заключается в том, что PriorityQueue не предназначен для двусторонней работы.очереди, поэтому он использует кучу для хранения предметов.Куча либо min , либо max , но не оба;Модуль Python heapq реализует минимальную кучу, но вы можете легко смоделировать максимальную кучу, умножив приоритеты на -1.В минимальной куче можно получить доступ к самым маленьким элементам за логарифмическое время, но не к самому большому, а в максимальной - наоборот.Чтобы эффективно манипулировать как самым маленьким, так и самым большим элементом, вам необходимо унаследовать от asyncio.Queue и использовать другую структуру данных для хранения элементов, например, отсортированный список .

Дляпример (не проверено): 

class DroppingPriorityQueue(asyncio.Queue):
    def _init(self, maxsize):
        # called by asyncio.Queue.__init__
        self._queue = sortedcontainers.SortedList()

    def _put(self, item):
        # called by asyncio.Queue.put_nowait
        self._queue.add(item)

    def _get(self):
        # called by asyncio.Queue.get_nowait
        # pop the first (most important) item off the queue
        return self._queue.pop(0)

    def __drop(self):
        # drop the last (least important) item from the queue
        self._queue.pop()
        # no consumer will get a chance to process this item, so
        # we must decrement the unfinished count ourselves
        self.task_done()

    def put_nowait(self, item):
        if self.full():
            self.__drop()
        super().put_nowait(item)

    async def put(self, item):
        # Queue.put blocks when full, so we must override it.
        # Since our put_nowait never raises QueueFull, we can just
        # call it directly
        self.put_nowait(item)

Класс реализует две различные задачи:

  • Он переопределяет защищенные методы _get, _put и _init для использованияSortedList в качестве основного хранилища.Хотя они и не документированы, эти методы используются для создания настраиваемых очередей, таких как PriorityQueue и LifoQueue, и использовались в течение десятилетий, впервые в модуле Queue (queue в Python 3) и позже в asyncio.queue.
  • Он переопределяет публичные методы put и put_nowait для реализации семантики отбрасывания при заполнении.
...