Queue.Queue vs. Коллекции.deque

Question

Мне нужна очередь, в которую может помещаться несколько потоков, и несколько потоков могут читать из нее.

В Python есть как минимум два класса очереди, Queue.Queue и collection.deque, причем первый, по-видимому, использует последний для внутреннего использования. Оба утверждают, что они являются потокобезопасными в документации.

Однако в документации очереди также указано:

collection.deque является альтернативой реализация неограниченных очередей с быстрым атомным добавлением () и popleft () операции, которые не требуется блокировка.

Что, я полагаю, я не совсем понимаю: означает ли это, что deque в конце концов не является полностью поточно-ориентированным?

Если это так, я не могу полностью понять разницу между двумя классами. Я вижу, что очередь добавляет функциональность блокировки. С другой стороны, он теряет некоторые функции, такие как поддержка оператора in-operator.

Прямой доступ к внутреннему объекту deque,

x в очереди (). Deque

потокобезопасной

Кроме того, почему Queue использует мьютекс для своих операций, когда deque уже поточно-ориентирован?

Answer 1

Queue.Queue и collections.deque служат различным целям. Queue.Queue предназначен для того, чтобы позволить различным потокам взаимодействовать с использованием сообщений / данных, находящихся в очереди, тогда как collections.deque просто предназначен как структура данных. Вот почему у Queue.Queue есть такие методы, как put_nowait(), get_nowait() и join(), а у collections.deque нет. Queue.Queue не предназначен для использования в качестве коллекции, поэтому ему не хватает операторов in.

Это сводится к следующему: если у вас есть несколько потоков, и вы хотите, чтобы они могли общаться без необходимости блокировок, вы ищете Queue.Queue; если вы просто хотите использовать очередь или двустороннюю очередь в качестве структуры данных, используйте collections.deque.

Наконец, доступ к внутренней деке Queue.Queue и манипулирование ею - это игра с огнем - вы действительно не хотите этого делать.

Answer 2

Если все, что вам нужно, это потокобезопасный способ передачи объектов между потоками , тогда оба будут работать (как для FIFO, так и для LIFO). Для FIFO:

• Queue.put() и Queue.get() являются поточно-ориентированными
• deque.append() и deque.popleft() являются поточно-ориентированными

Примечание:

• Другие операции на deque могут быть не поточно-ориентированными, я не уверен.
• deque не блокируется на pop() или popleft(), поэтому вы не можете основывать поток своих потребительских потоков на блокировании до прибытия нового элемента.

Однако, похоже, что deque имеет значительное преимущество в эффективности . Вот некоторые результаты тестов в секундах с использованием CPython 2.7.3 для вставки и удаления 100 тыс. Элементов

deque 0.0747888759791
Queue 1.60079066852

Вот код теста:

import time
import Queue
import collections

q = collections.deque()
t0 = time.clock()
for i in xrange(100000):
    q.append(1)
for i in xrange(100000):
    q.popleft()
print 'deque', time.clock() - t0

q = Queue.Queue(200000)
t0 = time.clock()
for i in xrange(100000):
    q.put(1)
for i in xrange(100000):
    q.get()
print 'Queue', time.clock() - t0

Answer 3

Для информации есть билет Python, на который ссылаются для безопасности потоков deque (https://bugs.python.org/issue15329). Заголовок «уточнить, какие методы deque являются поточно-ориентированными»

Итог здесь: https://bugs.python.org/issue15329#msg199368

Присоединение (), appendleft (), pop (), popleft () и len (d) в деке операции являются поточно-ориентированными в CPython. Методы добавления имеют DECREF в конце (для случаев, когда установлен maxlen), но это происходит после того, как все обновления структуры были сделаны и инварианты были восстановлены, поэтому можно лечить эти операции как атомарный.

В любом случае, если вы не уверены на 100% и предпочитаете надежность, а не производительность, просто поставьте «Lock»;)

Answer 4

Все одноэлементные методы на deque являются атомарными и поточно-ориентированными. Все остальные методы также поточно-ориентированы. Такие вещи, как len(dq), dq[4] дают мгновенные правильные значения. Но подумайте, например, о dq.extend(mylist): вы не получаете гарантию того, что все элементы в mylist подаются подряд, когда другие потоки также добавляют элементы с той же стороны - но это обычно не является обязательным требованием для связи между потоками и для опрошенных задача.

Таким образом, deque в ~ 20 раз быстрее, чем Queue (который использует deque под колпаком), и если вам не нужен "удобный" API синхронизации (блокировка / тайм-аут), строгий maxsize obeyance или "Переопределить эти методы (_put, _get, ..) для реализации других организаций очереди" Поведение подкласса, или когда вы сами позаботитесь о таких вещах, тогда голый deque будет хорошая и эффективная сделка для высокоскоростной связи между потоками.

На самом деле интенсивное использование дополнительного мьютекса и дополнительных вызовов методов ._get() и т. Д. В Queue.py связано с ограничениями обратной совместимости, прошлым чрезмерным дизайном и отсутствием заботы о предоставлении эффективного решения для этой важной скорости. проблема узкого места в межпотоковой связи. Список использовался в более старых версиях Python, но даже list.append () /. Pop (0) был и является атомарным и безопасным для потоков ...

Answer 5

deque 0.469802
Queue 0.667279

@ Джонатан немного изменил свой код, и я получил эталонный тест с использованием cPython 3.6.2 и добавил условие в цикл deque для имитации поведения, которое делает Queue do.

import time
from queue import Queue
import threading
import collections

mutex = threading.Lock()
condition = threading.Condition(mutex)
q = collections.deque()
t0 = time.clock()
for i in range(100000):
    with condition:
        q.append(1)
        condition.notify_all()
for _ in range(100000):
    with condition:
        q.popleft()
        condition.notify_all()
print('deque', time.clock() - t0)

q = Queue(200000)
t0 = time.clock()
for _ in range(100000):
    q.put(1)
for _ in range(100000):
    q.get()
print('Queue', time.clock() - t0)

И, похоже, производительность ограничена эта функция condition.notify_all()

collection.deque - это альтернативная реализация неограниченных очередей с быстрыми атомарными операциями append () и popleft (), которые не требуют блокировки. Очередь документов

Answer 6

(кажется, у меня нет репутации, чтобы комментировать ...) Вы должны быть осторожны, какие методы deque вы используете из разных потоков.

deque.get () кажется поточно-безопасным, но я обнаружил, что выполнение

for item in a_deque:
   process(item)

может завершиться ошибкой, если другой поток добавляет элементы одновременно. Я получил RuntimeException, который жаловался на "deque mutated во время итерации".

Проверьте collectionmodule.c , чтобы увидеть, какие операции затронуты

Answer 7

deque является поточно-ориентированным. «Операции, которые не требуют блокировки» означает, что вам не нужно выполнять блокировку самостоятельно, deque позаботится об этом.

Взглянув на источник Queue, внутренняя дека называется self.queue и использует мьютекс для аксессоров и мутаций, поэтому Queue().queue является не поточно-ориентированным для использования.

Если вы ищете оператор "in", то, вероятно, не самая подходящая структура данных для вашей проблемы - это очередь или очередь.