2

私は、正確に似ているConcurrentSkipListSetが線形size演算がない特定のデータ構造を探しています。これは、より大きなセットに対して頻繁に呼び出される可能性があります。

については知ってCollections.synchronizedNavigableSet(new TreeSet())いますが、同期された反復:

synchronized (set) {
    Iterator<T> iter = set.iterator();
    while (iter.hasNext())
    iter.next();
}

かなり遅いです。

では、 Apache Commons や GuavaNavigableSetなど、まったく同じですConcurrentSkipListSetが、線形操作がない実装について知っていますか? sizeまたは、セットを別の方法で反復する必要がありますか?

4

1 に答える 1

3

彼らがそれをそのように実装しなかったのには十分な理由があります（つまり、カウンターを使用）。これは、マルチプロセッサ プログラミングのセマンティクスに関するものです。同時実行プログラムには多くの正確性モデルがあり、強い (順次整合性と呼ばれる) とリラックスした (静止整合性と呼ばれる) モデルがあります (Maurice Herlihy と Nir ​​Shavit による The Art of Multiprocessor Programming またはQuasi-Linearizabilityを参照してください)。

カウンターを使用した実装は、それらのいずれにも準拠していません。実際の追加および削除操作の前にサイズが更新されると、負になることがあります (空のセットで削除および追加を行ったと仮定すると、最初にサイズを更新した削除により、-1 サイズになります...)。後でサイズが更新された場合も同様です。追加操作の前にサイズを増やし、削除後にサイズを減らすソリューションでさえ、重大な欠点があります (ただし、負の値は生成されません)。引数 'x' を使用した 2 つの追加操作と、同じ引数 'x' を使用した 1 つの削除操作 (すべて同じ要素を使用) を考えてみましょう。サイズが 2 に設定される (2 つの追加操作によってカウンターが増加する) という状況が存在する可能性がありますが、これは決して存在しなかった状態です (セットのサイズが 2 になることはありません。常に同じ要素 'x' を追加することに注意してください)。

それが実装される方法（要素を数えることによって、線形時間の複雑さで）は、少なくともある時点で存在していた値を生成します（より正確には、静止一貫性があります）。

于 2013-08-23T11:29:19.237 に答える