PFX ConcurrentQueue - c'è un modo per rimuovere un elemento dalla coda

Question

Ho un app che ha un ConcurrentQueue di elementi che hanno una proprietà ID e una ConcurrentQueue di attività per ogni elemento, la coda di elementi di simile:

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

e la coda si presenta come:

ConcurrentQueue<QueueItem> itemQueue;

Ho un thread per fare un foreach su itemQueue, l'annullamento dell'accodamento di un elemento dalla coda e facendo un lavoro su di esso:

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

Sto usando ConcurrentQueues perché ho un thread separato potenzialmente aggiunta di queueItems per il itemQueue, e l'aggiunta di elementi di lavoro per ogni workItemQueue.

Il mio problema arriva quando non ho più elementi di lavoro in un queueItem - vorrei rimuovere queueItem dal itemQueue - qualcosa di simile...

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

...ma non riesco a trovare un modo per farlo facilmente.Il modo in cui mi è venuta in mente è quello di far uscire ogni QueueItem e poi Enqueue se ci sono ancora elementi di lavoro in 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;
}

C'è un modo migliore per ottenere quello che voglio usando il PFX ConcurrentQueue, o è questo un modo ragionevole per fare questo, è necessario utilizzare un custom concorrente/coda lista di attuazione o mi manca qualcosa?

Answer 1

In generale, non ci sono modi efficaci per rimuovere elementi specifici dalle code. In genere hanno O (1) coda e Ritiri dalla coda, ma O (n) rimuove, che è ciò che l'implementazione fa.

Una struttura alternativa è qualcosa che si chiama un LinkedHashMap. Date un'occhiata alla Java implementazione se sei interessato.

Si tratta essenzialmente di una tabella di hash e una lista collegata, che consente O (1) della coda, dequeue e rimuovere.

Questa non è implementata in Net ancora, ma ci sono alcune implementazioni che galleggiano intorno al web.

Ora, la domanda è: perché è itemQueue una coda? Dalle vostre esempi di codice, non hai mai enqueue o dequeue nulla da esso (tranne che per navigare intorno al problema Rimuovi). Ho il sospetto che il problema potrebbe essere semplificata se si utilizza una struttura dati più adatto. Potrebbe dare esempi su quali altri pezzi di codice di accesso itemQueue?

Answer 2

Questo potrebbe non funzionare per tutti, ma la seguente è la soluzione che mi è venuta per la rimozione di un elemento da un concorrente di coda, dal momento che questo è il primo risultato di google, ho pensato di lasciare la mia soluzione dietro.

Cosa che ho fatto è stato sostituire temporaneamente la coda di lavoro con un vuoto, la conversione originale per una lista e rimuovere la voce(s), quindi creare una nuova coda l'elenco modificato e rimetterlo.

Nel codice (scusa questa è VB.net piuttosto 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

A parte:Questa è la mia prima risposta, quindi sentitevi liberi di mettere un po ' di editing di consulenza e/o modificare la mia risposta.

Answer 3

Le code hanno lo scopo quando si desidera gestire gli elementi in stile FIFO, pile per LIFO. C'è anche un concurrentdictionary e concurrentbag. Assicurarsi che una coda è in realtà ciò che si desidera. Non credo che avrei mai fare un foreach su un concurrentqueue.

Quello che probabilmente si desidera è una singola coda per i vostri elementi di lavoro (hanno li usano un'interfaccia comune e fare una coda sull'interfaccia, l'interfaccia dovrebbe esporre il tipo ereditata a cui può essere rifuso in seguito, se necessario). Se gli elementi di lavoro appartengono a un genitore, quindi una proprietà può essere utilizzata che terrà una chiave per il genitore (si consideri un GUID per la chiave), e il genitore può essere conservato in un concurrentdictionary e referenziato / rimossi, se necessario.

Se si deve fare nel modo che avete, considerare l'aggiunta di un flag. quindi è possibile contrassegnare l'elemento nel itemqueue come 'chiuso' o qualsiasi altra cosa, in modo che quando viene eliminato dalla coda, si otterrà ignorato.