1

私は興味深い問題を抱えており、助けが必要です。FIFO に基づく条件と、キーの自然な順序 (ConcurrentMap) に基づく条件の 2 つの個別の条件に対して、いくつかのキューを実装しました。つまり、両方のキューに同じデータがあり、順序が異なるだけであるとイメージできます。いくつかの基準に基づいて ConcurrentMap でキーを見つけた場合、FIFO マップでキーの「位置」を見つける最良の方法は何ですか? 基本的に、それが最初のキーなのか (これは簡単です)、それとも 10 番目のキーなのかを知りたいのです。

どんな助けでも大歓迎です。

4

3 に答える 3

1

FIFO マップの注文にアクセスするための API はありません。あなたがそれを行うことができる唯一の方法はkeySet()、values()またはとentrySet()カウントを繰り返すことです。

于 2012-04-26T06:32:49.580 に答える
0

以下のコードのようなものがうまくいくと思います。element --> key の実装は抽象メソッドとして残しました。増加する数を要素に割り当てるために使用されているカウンターに注意してください。add(...)また、 が複数のスレッドによって呼び出されている場合、FIFO 内の要素は大まかにしか順序付けされていないことに注意してください。それは空想max(...)とmin(...)論理を強制します。また、位置が概算である理由でもあります。最初と最後は特殊なケースです。まず明確に示すことができます。現在の実装は実際のインデックスを返すため、最後は注意が必要です。

これはおおよその位置であるため、キュー内の相対的な位置を示すために API がとのfloat間を返すようにすることを検討することをお勧めします。0.01.0

コードで 以外の手段を使用した削除をサポートするpop(...)必要がある場合は、おおよそのサイズを使用し、戻り値を に変更して((id - min) / (max - min)) * size、すべての適切なint/floatキャストと丸めを行う必要があります。

public abstract class ApproximateLocation<K extends Comparable<K>, T> {

    protected abstract K orderingKey(T element);

    private final ConcurrentMap<K, Wrapper<T>> _map = new ConcurrentSkipListMap<K, Wrapper<T>>();
    private final Deque<Wrapper<T>> _fifo = new LinkedBlockingDeque<Wrapper<T>>();
    private final AtomicInteger _counter = new AtomicInteger();

    public void add(T element) {
        K key = orderingKey(element);
        Wrapper<T> wrapper = new Wrapper<T>(_counter.getAndIncrement(), element);
        _fifo.add(wrapper);
        _map.put(key, wrapper);
    }

    public T pop() {
        Wrapper<T> wrapper = _fifo.pop();
        _map.remove(orderingKey(wrapper.value));
        return wrapper.value;
    }

    public int approximateLocation(T element) {
        Wrapper<T> wrapper = _map.get(orderingKey(element));
        Wrapper<T> first = _fifo.peekFirst();
        Wrapper<T> last = _fifo.peekLast();
        if (wrapper == null || first == null || last == null) {
            // element is not in composite structure; fifo has not been written to yet because of concurrency
            return -1;
        }
        int min = Math.min(wrapper.id, Math.min(first.id, last.id));
        int max = Math.max(wrapper.id, Math.max(first.id, last.id));
        if (wrapper == first || max == min) {
            return 0;
        }
        if (wrapper == last) {
            return max - min;
        }
        return wrapper.id - min;
    }

    private static class Wrapper<T> {
        final int id;
        final T value;

        Wrapper(int id, T value) {
            this.id = id;
            this.value = value;
        }
    }
}
于 2012-04-26T17:34:44.037 に答える
0

を使用できる場合ConcurrentNavigableMap、 のサイズはheadMapまさにあなたが望むものを提供します。

于 2012-04-26T06:39:52.150 に答える