43

次のような状況があります。

  1. 拡張することしかできないデータ構造 (私は末尾にのみ追加します)
  2. すでに見た要素を追跡できるようにする必要があります (インデックスがあり、理想的には、この特定の要素からリストを再度トラバースできるようにしたい)
  3. 読み取りがブロックされないようにし、新しい要素を追加して、キュー全体ではなくキューの末尾のみをロックしたいと思います

これは、複数のスレッドによって大幅に変更される構造です。

これに最適なデータ構造は何でしょうか?

配列リスト。これは、インデックスを使用して最後に表示された要素に直接アクセスできるのが理想的ですが、同時変更の例外が発生します。私はそれを同期させることができましたが、ロックを避けたいです（または、新しい要素を追加するために同時書き込みが発生する可能性がある唯一の要素であるため、最後の要素以外のロックは避けたいです）

ConcurrentLinkedQueue。これで同時実行性の問題は解決しますが、整数インデックスではなく反復の現在の位置を保存する必要があるという問題があります。これには、反復子が作成されてからリストに追加された新しいオブジェクトを返すことが保証されていない、一貫性の低い反復子を返すという問題があります (ソース: javadoc)。

インデックスをキーとするConcurrentHashMap 。これには、正しいインデックスに対応するデータに直接アクセスできるという利点がありますが、要素をインデックスからインデックス + 1 などに効率的にトラバースできる「getNext」演算子がないという問題があります。

ベクトルこれは、同時変更例外をスローせず、直接アクセスを許可するものを許可するという私の問題のほとんどを解決します。ただし、すべてのメソッドが同期されているため、アレイリストに比べてパフォーマンスが低下します。構造を拡張したいだけで、途中にレコードを挿入したくないことを考えると、読み取りもパフォーマンスに影響を与えるこの重いソリューションに行くのは気が進まない (一方、私のユースケースを考えると、要素のインデックス実際には変更されないため、テールではない読み取りを同期する必要はありません)

カスタムデータ構造：保存したいオブジェクトの配列と、この配列の末尾（最後の要素セット）へのポインターを保持し、新しいオブジェクトを挿入するときに、末尾と末尾が指すオブジェクトをロックします。オブジェクトが現在のサイズを超えると、サイズ変更操作がロックされます。

最善の戦略/他のより効率的な実装は何ですか?

4

8 に答える 8

11

CopyOnWriteArrayList構造が問題を解決する可能性があります (java.util.concurrent) 。

  • CopyOnWriteArrayLists は、リストのコピーを作成することによってすべての変更操作が実装されるため、スレッドセーフです。

  • ConcurrentModificationException反復中に配列が変更されないため、の問題は回避されます。いわゆるsnapshot style iteratorイテレータが作成されたときの配列の状態への参照を使用します。

  • 書き込みより読み取りの方がはるかに多い場合は を使用しCopyOnWriteArrayList、それ以外の場合は を使用しますVector。

  • Vectorでは、CopyOnWriteArrayList(コピーによる) 書き込みの遅延は長くなりますが、読み取りの遅延はありません。

  • Vector反復するときに明示的な同期が必要です (したがって、書き込み操作を同時に実行することはできません)、そうでCopyOnWriteArrayListはありません。

于 2013-04-25T09:35:08.813 に答える
4

これは、ディスラプターが必要になるか、簡単に言えばロックフリーキューが必要になるように聞こえます。ここに例を追加できればと思いますが、昨日作業を開始したばかりです。それがどのように機能するかを説明することもできます。または、ここではるかに優れた説明を読むことができます。

一般的な考え方は、これは完全にロックフリーであり、CAS レジスタ (java AtomicXXX 内) のみを使用するということです。私は単にそのアイデアに恋をしました。

LMAX

于 2013-04-25T09:40:46.420 に答える
4

これを調べると、@MissingNumber と同じ解決策にたどり着きました。

ConcurrentHashMap をバッキング データ構造として使用します。

  • 非ブロッキング読み取り
  • スレッドセーフな追加

インデックスによるランダム アクセスを追加するには、AtomicInteger を使用してインデックスを維持し、マップ値を取得するためのキーとして配置します。

public class ConcurrentListMap {

  private final ConcurrentHashMap<Integer, Object> backingMap;
  private final AtomicInteger index;

  public ConcurrentListMap() {
    backingMap = new ConcurrentHashMap();
    index = new AtomicInteger(0);
  }

  public int append(final Object value) {
    final int newIndex = index.incrementAndGet();
    backingMap.put(newIndex, value);
    return newIndex;
  }

  public Object get(final int entry) {
    return backingMap.get(entry);
  }

  public int getTailIndex() {
    return index.get();
  }
}
于 2013-04-25T15:34:37.043 に答える
1

sk2212さんのおっしゃるjava.util.Vector通り、3点は満たしていると思います。

  1. addリストの最後に要素を追加するメソッドを使用して、ベクトルを拡張できます。
  2. ベクトルには、get(index)特定のインデックスで具体的な要素を取得するメソッドがあります。
  3. ベクトルはスレッドセーフです: Java ベクトルとスレッドセーフ http://docs.oracle.com/javase/7/docs/api/java/util/Vector.html
于 2013-04-25T09:40:12.343 に答える
1

キーとしてインデックスを使用したConcurrentHashMapは問題を解決できますが、そのためにはさらに多くの作業を行う必要があります..

次の Pseudo Code のように。

Map<Integer , ConfiguredObject > myMap = new ConcurrentHashMap<Integer,ConfiguredObject >();

class ConfiguredObject 
{
   YourObject Object;// the object which you want to map for map[key];
   ConfiguredObject Next;//the object which you want to map for map[key+1];
   ConfiguredObject Previous;//the object which you want to map for map[key-1];
   YourObject NextObject;
   YourObject PrevObject;
}

したがって、これですべての問題が解決するはずです。

コンカレンシーフレームワークが処理します。

インデックスキーはインデックスです。

Iteration 、使用できるインデックスがある場合はこのコードで

myMap.get(key).Next ;
myMap.get(key).Previous ;

あなたがする必要があるのは、構成可能なオブジェクトを定義し、それに応じて慎重にコンストラクターを書くことだけです。

これがお役に立てば幸いです。

于 2013-04-25T11:08:41.037 に答える
0

を提供しますConcurrentSkipListSet。理由は次のとおりです。

1) 同時進行です。

2)Setです。

3) それもでありNavigableSet、したがってまたSortedSetです。

これにより多くの柔軟性が得られますが、その多くはおそらく必要ありません。しかし、「すでに存在するアイテムを追加することはできません」（問題なのか恩恵なのかはわかりません）を除けば、すべての要件を満たしているようです。

于 2013-04-25T14:11:50.037 に答える
0

配列リスト。これは、インデックスを使用して最後に表示された要素に直接アクセスできるのが理想的ですが、同時変更の例外が発生します。私はそれを同期させることができますが、ロックを避けたいです（または、新しい要素を追加するための同時書き込みが発生する可能性がある唯一の要素であるため、最後の要素以外のロックは避けたいです）

一時的なリストを使用して追加するオブジェクトを配置し、読み取ったものがブロック解除されたら、tmpList のコンテンツを ArrayList に追加します。

于 2013-04-25T09:36:45.533 に答える