-4

これは、Java でキューを実装するためのインタビュアーからの問題です。基本的に、このキューは Enqueue/Dequeue 操作を提供するだけで済みます。

実行速度が速い実装は、より高いスコアを取得します。各メソッドが同じ頻度で呼び出されると仮定します。したがって、すべてのメソッドが同様に高速である必要があります。

4

1 に答える 1

4

彼はディスラプターライブラリのようなリング バッファーを探していたようです。

ArrayBlockingQueue よりも 10 倍も高速になる可能性があります。

それほど高速ではありませんが、キューの永続性という別の問題を解決するライブラリを作成しました。ArrayBlockingQueue よりも高速になる可能性がありますが、すべてのデータを保持し、プロセス間で共有できます。ジャワクロニクル

" 各メソッドが同じ頻度で呼び出されると仮定します。" これが当てはまる場合、必要なリング バッファーは 1 だけです。最も単純なのは AtomicReference です。注: これはロックレスであり、gc もありません。

public class AtomicReferenceQueue<T> {
    private final AtomicReference<T> ringBufferOfOne = new AtomicReference<T>();

    /**
     * @return true if added.
     */
    public boolean add(T t) {
        return ringBufferOfOne.compareAndSet(null, t);
    }

    public void offer(T t) throws InterruptedException {
        while (!ringBufferOfOne.compareAndSet(null, t))
            if (Thread.interrupted())
                throw new InterruptedException();
    }

    public T poll() {
        return ringBufferOfOne.getAndSet(null);
    }

    public T take() throws InterruptedException {
        T t;
        while ((t = ringBufferOfOne.getAndSet(null)) == null)
            if (Thread.interrupted())
                throw new InterruptedException();
        return t;
    }
}

実際、マイクロ秒レベルでまったく同じ周波数を確保することは不可能です。この「リング バッファ」は、エンキューの頻度がデキューの頻度よりもほとんど常に低い場合に最適に機能します (そして、CPU を燃やすことは気にしません ;)

于 2012-09-15T08:04:43.720 に答える