要素の一意性を保証するキュー?

Question

java.util.Queue またはキューのように動作する Google コレクションの実装を探していますが、キューの各要素が一意であることも保証します。(それ以上挿入しても効果はありません)

それは可能ですか、それとも手動で行う必要がありますか?

今のところ、LinkedList 実装を備えた Queue を使用しており、挿入前に一意性をチェックしています。(これを行うにはサイドマップを使用し、キューの前後にサイドマップの要素を追加/削除します)。あまり好きではありません。

あらゆるご意見を歓迎します。それが java.util パッケージに含まれていない場合、おそらくそれは悪い考えでしょうか?

Answer 1

どのように LinkedHashSet のでしょうか？そのイテレータジャムの挿入順序が、それはSetだから、その要素が一意である。

そのドキュメントが言うように、

  

オーダーがセットに要素が再挿入された場合、しないのの影響を受けることに注意してください。

効率的にそのイテレータを通過し、この「キュー」の先頭から要素を削除するには：

Iterator<?> i = queue.iterator();
...
Object next = i.next();
i.remove();

Answer 2

これは私の知る限りでは存在しませんが、LinkedListと一緒にSetを使用して実装することはかなりシンプルになります：

/**
 * Thread unsafe implementation of UniqueQueue.
 */
public class UniqueQueue<T> implements Queue<T> {
  private final Queue<T> queue = new LinkedList<T>();
  private final Set<T> set = new HashSet<T>();

  public boolean add(T t) {
    // Only add element to queue if the set does not contain the specified element.
    if (set.add(t)) {
      queue.add(t);
    }

    return true; // Must always return true as per API def.
  }

  public T remove() throws NoSuchElementException {
    T ret = queue.remove();
    set.remove(ret);
    return ret;
  }

  // TODO: Implement other Queue methods.
}

Answer 3

私は維持するために誘惑されるだろう HashSetのを一意にそれをキューに並べてアイテムを識別するキーを含みます。それからちょうど項目がそれを追加する前に、キューにあるかどうかを確認するためにHashSetのを確認してください。あなたはキューから項目を削除すると、単に同様のHashSetからキーを削除します。

Answer 4

もちろん、一意性のチェックにはコストがかかります (スペースまたは時間のいずれか)。要素の Comparator によってソートされたヒープを維持する PriorityQueue のようなものから作業するのは興味深いかもしれません。これを利用すると、サイド マップを維持せずに、より効率的に (O(log n)) 存在を確認できる可能性があります。

一意性チェッカーでキューをラップしたい場合は、Google コレクションを使用することを強くお勧めします。 転送キュー そのようなものを構築するために。

Answer 5

だけがアダムスキーの答えを完了します：

/**
 * A queue that keeps each element only once. 
 * If you try to add an element that already exists - nothing will happen.
 * 
 * @author Adamski http://stackoverflow.com/a/2319156/827927
 * @NotThreadSafe
 */
public class UniqueQueue<T> implements Queue<T> {

private final Queue<T> queue = new LinkedList<T>();
private final Set<T> set = new HashSet<T>();

@Override public boolean add(T t) {
    // Only add element to queue if the set does not contain the specified element.
    if (set.add(t))
        queue.add(t);
    return true; // Must always return true as per API def.
}

@Override public boolean addAll(Collection<? extends T> arg0) {
    boolean ret = false;
    for (T t: arg0)
        if (set.add(t)) {
            queue.add(t);
            ret = true;
        }
    return ret;
}

@Override public T remove() throws NoSuchElementException {
    T ret = queue.remove();
    set.remove(ret);
    return ret;
}

@Override public boolean remove(Object arg0) {
    boolean ret = queue.remove(arg0);
    set.remove(arg0);
    return ret;
}

@Override public boolean removeAll(Collection<?> arg0) {
    boolean ret = queue.removeAll(arg0);
    set.removeAll(arg0);
    return ret;
}

@Override public void clear() {
    set.clear();
    queue.clear();
}

@Override public boolean contains(Object arg0) {
    return set.contains(arg0);
}

@Override public boolean containsAll(Collection<?> arg0) {
    return set.containsAll(arg0);
}

@Override public boolean isEmpty() {
    return set.isEmpty();
}

@Override public Iterator<T> iterator() {
    return queue.iterator();
}

@Override public boolean retainAll(Collection<?> arg0) {
    throw new UnsupportedOperationException();
}

@Override public int size() {
    return queue.size();
}

@Override public Object[] toArray() {
    return queue.toArray();
}

@Override public <T> T[] toArray(T[] arg0) {
    return queue.toArray(arg0);
}

@Override public T element() {
    return queue.element();
}

@Override public boolean offer(T e) {
    return queue.offer(e);
}

@Override public T peek() {
    return queue.peek();
}

@Override public T poll() {
    return queue.poll();
}
}

Answer 6

これはとても良い質問です。既存の単純な解決策はありません。これを実行しようとして少し前に書いたコードを掘り出し、戻ってこの回答を編集します。

編集： 戻ってきました。実際、同時実行性が必要ない場合は、Queue と Set を別々に管理する方が良いでしょう。私がやっていたのは同時実行が目標でしたが、その制約に問題があることを考慮すると、私が思いつく最善の解決策はありませんでした。基本的に、ConcurrentHashMap を使用しているため、キューから "head" 要素を削除すればするほど (キューの基本的な操作です)、時間の経過とともにハッシュ テーブルのバランスが崩れます。このコードをまだ共有することはできますが、本当にそれを望んでいるとは思えません。

編集： 同時実行性が必要な場合には、次の答えを与えました。同時セットキュー

Answer 7

残念ながら、それは存在しません。私はブロッキングキューを開発している、そのようなキューIを必要とするので、のjava.util.concurrent.LinkedBlockingQueue のに触発され、セットに裏打ちされています。

あなたがここでそれを見つけることができます：

https://github.com/bvanalderweireldt/concurrent-unique-queueする

例：

final BlockingQueue<Integer> queue = new ConcurrentSetBlockingQueue<>(1);
queue.offer(new Integer(1)); //True
queue.offer(new Integer(1)); //False

あなたはMavenのでそれを使用することができます：

<dependency>
  <groupId>com.hybhub</groupId>
  <artifactId>concurrent-util</artifactId>
  <version>0.1</version>
</dependency>

Answer 8

私は少し遅れて答えにしていますが、私はArrayDequeを使用して同様の問題を解決し、私は必要なことをaddメソッドをオーバーライドしてしまっています。

    Deque<Long> myQueue = new ArrayDeque<Long>() {
        @Override
        public boolean add(Long e) { return !this.contains(e) && super.add(e);}
    };