PFX ConcurrentQueue - há uma maneira para remover um item específico da fila

Question

Eu tenho um aplicativo que tem uma ConcurrentQueue de itens que têm uma propriedade ID e uma ConcurrentQueue de tarefas para cada item, os itens da fila parecido:

class QueueItem {
  public int ID { get; set; }
  public ConcurrentQueue<WorkItem> workItemQueue { get; set; }
}

e a fila em si parece com:

ConcurrentQueue<QueueItem> itemQueue;

Eu tenho um segmento fazendo um foreach sobre o itemQueue, deQueueing um item de cada fila e fazendo um trabalho sobre ele:

foreach(var queueItem in itemQueue) {
  WorkItem workItem;
  if (queueItem.workItemQueue.TryDequeue(out workItem))
    doWork(workItem);
  else
    // no more workItems for this queueItem
}

Eu estou usando ConcurrentQueues porque eu tenho um segmento separado potencialmente acrescentando queueItems ao itemQueue, e adicionando WorkItems a cada workItemQueue.

Meu problema surge quando não tenho mais WorkItems em um queueItem - Eu gostaria de remover essa queueItem do itemQueue - algo como ...

  if (queueItem.workItemQueue.TryDequeue(out workItem))
    doWork(workItem);
  else
    itemQueue.TryRemove(queueItem);

... mas não consigo encontrar uma maneira de fazer isso facilmente. A maneira que eu vim acima com é para retirar da fila cada QueueItem e depois Enqueue-lo se ainda há WorkItems no workItemQueue:

for (int i = 0; i < itemQueue.Count; i++) {
  QueueItem item;
  itemQueue.TryDequeue(out queueItem);
  if (queueItem.workItemQueue.TryDequeue(out workItem)) {
    itemQueue.Enqueue(queueItem);
    doWork(workItem);
  }
  else
    break;
}

Existe uma maneira melhor de fazer o que eu quero usar o PFX ConcurrentQueue, ou esta é uma forma razoável para fazer isso, que eu deveria usar um personalizado implementação da fila / lista concorrente ou estou faltando alguma coisa?

Answer 1

Em geral, não há maneiras eficientes para remover itens específicos de filas. Eles geralmente têm O (1) fila e Retiradas da fila, mas O (n) remove, que é o que a sua implementação faz.

Uma estrutura alternativa é algo chamado um LinkedHashMap. Dê uma olhada na Java implementação se você está interessado.

é essencialmente uma tabela de Hash e uma lista encadeada, que permite que o (1) da fila, Desenfileiramento e remover.

Isto não é implementado em .Net ainda, mas há algumas implementações flutuando em torno da web.

Agora, a pergunta é, por que é itemQueue uma fila? De suas amostras de código, você nunca enqueue ou qualquer coisa dequeue a partir dele (exceto para navegar em torno do problema Remove). Eu tenho uma suspeita de que o problema poderia ser simplificado se uma estrutura de dados mais adequado é usado. Você poderia dar exemplos do que outros pedaços de código de acesso itemQueue?

Answer 2

Isto pode não funcionar para todos, mas a seguir é a solução que eu vim com para remover um item de uma fila simultânea, uma vez que este é o primeiro resultado google, eu pensei que eu iria deixar a minha solução para trás.

O que eu fiz foi substituir temporariamente a fila de trabalhar com um vazio, converter o original para uma lista e remova o item (s), em seguida, criar uma nova fila da lista modificada e colocá-lo de volta.

No código (desculpe este é VB.net em vez C #):

Dim found As Boolean = False
//'Steal the queue for a second, wrap the rest in a try-finally block to make sure we give it back
Dim theCommandQueue = Interlocked.Exchange(_commandQueue, New ConcurrentQueue(Of Command))
Try
    Dim cmdList = theCommandQueue.ToList()
    For Each item In cmdList
        If item Is whateverYouAreLookingFor Then
            cmdList.Remove(item)
            found = True
        End If
    Next
    //'If we found the item(s) we were looking for, create a new queue from the modified list.
    If found Then
        theCommandQueue = New ConcurrentQueue(Of Command)(cmdList)
    End If
Finally
    //'always put the queue back where we found it
    Interlocked.Exchange(_commandQueue, theCommandQueue)
End Try

Além:. Esta é a minha primeira resposta, tão à vontade para colocar-se alguns conselhos edição e / ou editar a minha resposta

Answer 3

As filas são quis dizer quando você deseja manipular itens em um estilo FIFO, Pilhas para LIFO. Há também um concurrentdictionary e uma ConcurrentBag. Certifique-se de que a fila é realmente o que você quer. Eu não acho que eu jamais iria fazer um foreach em um ConcurrentQueue.

O que você provavelmente quer é uma única fila para seus itens de trabalho (tê-los usar uma interface comum e fazer uma fila na interface, a interface deve expor o tipo herdado ao qual ele pode ser reformulado posteriormente, se necessário). Se os workitems pertencer a um dos pais, em seguida, uma propriedade pode ser usado que vai realizar uma chave para o pai (considerar um GUID para a chave), e o pai pode ser mantido em um concurrentdictionary e referenciado / removido quando necessário.

Se você deve fazê-lo da maneira que você tem isso, considerar a adição de uma bandeira. você pode, em seguida, marcar o item na itemqueue como 'fechada' ou o que quer, de modo que quando ele é retirado da fila, ele vai ficar ignorado.