Параллельная коллекция, поддерживающая удаление указанного элемента?

Довольно просто: кроме ConcurrentDictionary (который я буду использовать, если нужно, но это не совсем правильная концепция), существует ли какая-либо параллельная коллекция (реализация IProducerConsumer), которая поддерживает удаление определенных элементов на основе простого равенства элемента или предикат, определяющий условие для удаления?

Объяснение: У меня многопоточный многоступенчатый алгоритм рабочего процесса, который вытягивает объекты из БД и вставляет их в "стартовую" очередь. Оттуда они захватываются следующим этапом, дальше работают и набиваются в другие очереди. Этот процесс продолжается еще на нескольких этапах. Между тем, первый этап снова запускается его супервизором и вытаскивает объекты из БД, и они могут включать объекты, все еще находящиеся в процессе (потому что они еще не закончили обрабатываться и поэтому не были повторно сохранены с установленным флагом, говорящим они сделаны).

Решение, которое я разрабатываю, является коллекцией мастеров "в работе"; объекты попадают в очередь, когда они извлекаются для обработки на первом этапе, и удаляются после того, как они были повторно сохранены в БД как "обработанные" на каком-либо этапе рабочего процесса, завершили необходимую обработку. Пока объект находится в этом списке, он будет проигнорирован, если он будет повторно извлечен на первом этапе.

Я планировал использовать ConcurrentBag, но единственный метод удаления (TryTake) удаляет произвольный элемент из пакета, а не указанный (и ConcurrentBag медленнее в .NET 4). ConcurrentQueue и ConcurrentStack также не позволяют удалить элемент, отличный от следующего, который он вам даст, оставив ConcurrentDictionary, который будет работать, но больше, чем мне нужно (мне действительно нужно хранить Id обрабатываемых записей; они не меняются во время рабочего процесса).

Ответ 1

Причина отсутствия такой структуры данных заключается в том, что все коллекции имеют время работы поиска O(n). Это IndexOf, Remove(element) и т.д. Все они перечисляют все элементы и проверяют их на равенство.

Только хэш-таблицы имеют время поиска O (1). В параллельном сценарии O (n) время поиска приведет к очень длительной блокировке коллекции. Другие потоки не смогут добавлять элементы за это время.

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

Мой совет: продолжайте и используйте ConcurrentDictionary.

Кстати, вы правы, что ConcurrentDictionary немного негабарит для вашего решения. То, что вам действительно нужно, это быстро проверить погоду, когда объект работает или нет. A HashSet был бы идеальным для этого. В основном это ничего не значит Add(element), Contains(element), Remove(element). В java есть реализация ConcurrentHeshSet. Для С# я нашел это: Как реализовать ConcurrentHashSet в .Net, не знаю, насколько это хорошо.

В качестве первого шага я все равно напишу обертку с интерфейсом HashSet вокруг ConcurrentDictionary, чтобы запустить ее и запустить, а затем попробовать различные реализации и увидеть различия в производительности.

Ответ 2

Как уже объяснялось другими сообщениями, по умолчанию невозможно удалить элементы из Queue или ConcurrentQueue, но на самом деле самый простой способ обойти - это расширить или обернуть элемент.

public class QueueItem
{
    public Boolean IsRemoved { get; private set; }
    public void Remove() { IsRemoved = true; }
}

И при удалении:

QueueItem item = _Queue.Dequeue(); // Or TryDequeue if you use a concurrent dictionary
if (!item.IsRemoved)
{
    // Do work here
}

Ответ 3

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

Обычно рекомендуется использовать любую коллекцию, которую вы хотите, и получать доступ к ней поточно-безопасным способом. В основном это связано с тем, что в структуре не существует больше поточно-безопасных коллекций. Подробнее об этом можно узнать в http://blogs.msdn.com/b/bclteam/archive/2005/03/15/396399.aspx#9534371