有效地删除添加到ConcurrentQueue的元素 [英] Efficiently removing an element added to a ConcurrentQueue
问题描述
原则上，从 ConcurrentLinkedQueue 或类似的实现。例如，该类的 Iterator 支持对当前元素进行有效的O（1）移除：
In principle it is easy to remove an element from ConcurrentLinkedQueue or similar implementation. For example, the Iterator for that class supports efficient O(1) removal of the current element:
public void remove() {
Node<E> l = lastRet;
if (l == null) throw new IllegalStateException();
// rely on a future traversal to relink.
l.item = null;
lastRet = null;
}
我想使用向队列添加元素add（），然后从队列中删除该确切元素。我可以看到的唯一选项是：
I want to add an element to the queue with add(), and then later delete that exact element from the queue. The only options I can see are:
-
保存对对象的引用并调用
ConcurrentLinkedQueue.remove （对象o）与对象-但这会在最坏的情况下强制遍历整个队列（平均一半为随机添加和删除模式）。
Save a reference to the object and call
ConcurrentLinkedQueue.remove(Object o)with the object - but this forces a traversal of the whole queue in the worst case (and half on average with a random add and removal pattern).
这还有一个问题，即不一定删除我插入的 same 对象。它将删除一个 equal 对象，如果我的队列中的多个对象相等，则该对象可能会大不相同。
This has the further issue that it doesn't necessarily remove the same object I inserted. It removes an equal object, which may very be a different one if multiple objects in my queue are equal.
使用 ConcurrentLinkedDeque ，然后是 addLast（）我的元素，然后立即获取 descendingIterator（）并进行迭代，直到找到我的元素为止（通常是第一个元素，但可能会晚一点，因为我实际上是在顺应并发添加的潮流中游泳）。
Use ConcurrentLinkedDeque instead, then addLast() my element, then immediately grab a descendingIterator() and iterate until I find my element (which will often be the first one, but may be later since I'm effectively swimming against the tide of concurrent additions).
除了笨拙而且可能很慢之外，这迫使我使用 Deque 类，在这种情况下，该类对于许多操作而言更为复杂和缓慢（请查看 Iterator.remove（）该类！）。
This addition to being awkward and potentially quite slow, this forces me to use Deque class which in this case is much more complex and slower for many operations (check out Iterator.remove() for that class!).
此外，如果相同，该解决方案仍具有微妙的故障模式（例如，可以插入 == 身份），因为我可能会找到其他人插入的对象，但是在通常情况下这是不可能的。
Furthermore this solution still has a subtle failure mode if identical (i.e., == identity) can be inserted, because I might find the object inserted by someone else, but that can ignored in the usual case that is not possible.
两者都溶似乎确实很尴尬，但是在这种结构中删除任意元素似乎是一项核心操作。我缺少什么？
Both solutions seem really awkward, but deleting an arbitrary element in these kind of structures seems like a core operation. What am I missing?
在我看来，这是其他并发列表和出队，甚至是非并发结构（如 LinkedList 。
It occurs to me this is a general issue with other concurrent lists and dequeues and even with non concurrent structures like LinkedList.
C ++以类似插入。
推荐答案
如果您特别需要此功能（例如您将要拥有大量集合），则可能需要实现自己的集合，该集合返回对add条目的引用，并具有在O（1）中删除的能力。
If you specifically need this capability (e.g. you are going to have massive collections) then you will likely need to implement your own collection that returns a reference to the entry on add and has the ability to remove in O(1).
class MyLinkedList<V> {
public class Entry {
private Entry next;
private Entry prev;
private V value;
}
public Entry add(V value) {
...
}
public void remove(Entry entry) {
...
}
}
换句话说
MyLinkedList<Integer> intList;
MyLinkedList.Entry entry = intList.add(15);
intList.remove(entry);
显然，要实施的工作量很大。
That's obviously a fair amount of work to implement.
这篇关于有效地删除添加到ConcurrentQueue的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
