Потокобезопасная сортированная коллекция

Question

Есть ли реализация поточно-отсортированной коллекции в Python?
Документы Python ссылаются на SortedCollection, но я не уверен, что это потокобезопасно (не так ли?)
Если такой реализации нет - как бы вы ее реализовали?

Answer 1

Просматривая код, он не выглядит потокобезопасным. Чтобы использовать его из нескольких потоков, код приложения, который обращается к нему, должен быть защищен семафорными замками.

Если вы хотите сделать поток класса SortedCollection безопасным, вы можете написать функцию декоратора.

Это будет выглядеть примерно так:

SortedCollection:

def __init__(self):
    self.mysemaphore = threading.Semaphore()

def guard(func):
    def guarded(*args, **kwds):
        self.mysemaphore.acquire()
        try:
            return func(*args, **kwds)
        finally:
            self.mysemaphore.release()

return guarded

# edit the class, applying the decorator to its methods.
@guard
def unsafeFunc(self, a, b, c):
    ''' do work here'''

РЕДАКТИРОВАТЬ

Не думайте, что многопоточная структура данных сделает ваш программный поток безопасным. Если вы выполняете несколько операций над SortedCollection, все эти операции должны быть защищены блокировкой.

Даже если SortedCollection является потокобезопасным, следующий код не будет:

slist.insert(1)
slist.insert(2)

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

semaphore2.acquire()

try:
    slist.insert(1)
    slist.insert(2)
finally:
    semaphore2.release()

Answer 2

Класс collection.OrderedDict не является потокобезопасным для обновлений. Вы можете выполнять одновременное чтение, но для записи необходимы блокировки. Для примера того, как использовать блокировки с OrderedDict, см. Источник для functools.lru_cache ().

Answer 3

Вы можете использовать модуль heapq для поддержки отсортированного списка. В силу GIL все вызовы расширений C являются атомарными (в CPython, если расширение явно не снимает блокировку) и, следовательно, heappush и друзья потокобезопасны.

from heapq import heappush, heappop

class Heap:

    def __init__(self):
        self._heap = []

    def push(self, x):
        heappush(self._heap, x)

    def pop(self):
        return heappop(self.heap)

Answer 4

Python отличается от Java: если класс не определил свое потоковое поведение в документах, можно с уверенностью предположить, что он не является поточно-ориентированным.

Python не написан с учетом потоков. Даже сегодня многопоточность действительно относится ко второму классу, так как постоянно активен только один поток (что не предотвращает большинство проблем с передачей данных). Это называется Global Interpreter Lock (GIL).

Если класс или структура данных не созданы для параллелизма, вы должны защитить доступ к ним с помощью внешней блокировки.

Answer 5

Атомарные операции всегда являются поточно-ориентированными в python. Синхронизировать нужно только в том случае, если операции не являются атомарными. GIL допускает только одну атомарную операцию за раз, независимо от количества потоков. Мультиобработка в python - это другое дело.