2

私のコードには、数秒で数千回も頻繁に使用されるマップがあります。もともと私は TreeMap を持っていましたが、9,000 エントリでテストすると、古いプロセッサが溶けるのが見えました。そして、これはスケーリングする必要があります。そのため、HashMap に移行したところ、パフォーマンスは優れていました。

現在、設計を変更しており、MultiMap を探しています。get()ただし、一致するキーを選択する大きなマップを反復処理する必要があり、何度も呼び出されても同期が遅いように見えるため、パフォーマンスへの影響が懸念されます。

このような大きな値を優れたパフォーマンスで処理できる優れた MultiMap はありますか? このアプリケーションではパフォーマンスが重要です。非常に大きなワークロードを処理する大きな個別のマップが多数存在する可能性があり、「小さな」パフォーマンスの損失が非常に大きな問題になる可能性があるからです。

依存関係なしで単独で動作するように抽出できる場合は、ボーナス ポイントです。

4

5 に答える 5

4

私の質問の 1 つで推奨されたのは、Apache Commons MultiMap でした: http://commons.apache.org/collections/api-3.2.1/org/apache/commons/collections/MultiHashMap.html

これはフリー ソフトウェアなので、少なくともソースを参照することはできます。また、ライセンスの状況に応じて、変更したり、スタンドアロンで使用したりできます。

内部では ArrayList を使用していますが、おそらく HashSet などを使用するように変更できると思います。その方法を見ていきますcreateCollection(Collection coll)。

更新: 実際、Guava の HashMultiMap は、私が話していたもののようです: https://github.com/google/guava/blob/master/guava/src/com/google/common/collect/Multimap.java

ソースを見たところ、値の各コレクションは実際には HashSet によってサポートされているようです。

于 2010-08-10T04:44:46.620 に答える
2

マップへの場所の挿入と対応するセットへの同時挿入が必要であるという要件がありましたMap<Comparable, Set<Comparable>>が、キーがマップから消費されたら、キーを削除する必要がありました。2 秒ごとに実行されるジョブとして特定のキーから全体を消費していますSet<Comparable>が、挿入は完全に同時であるため、ジョブが開始されたときにほとんどの値がバッファリングされます。これが私の実装です:

注: Guava のヘルパー クラス Maps を使用して同時実行マップを作成します。また、このソリューションは、プラクティス リスト 5.19 で Java 同時実行をエミュレートします。

import com.google.common.collect.MapMaker;

import java.util.concurrent.ConcurrentMap;

/**
 * Created by IntelliJ IDEA.
 * User: gmedina
 * Date: 18-Sep-2012
 * Time: 09:17:50
 */
public class LockMap<K extends Comparable>
{
  private final ConcurrentMap<K, Object> locks;

  public LockMap()
  {
    this(16, 64);
  }

  public LockMap(final int concurrencyLevel)
  {
    this(concurrencyLevel, 64);
  }

  public LockMap(final int concurrencyLevel, final int initialCapacity)
  {
    locks=new MapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(initialCapacity).weakValues().makeMap();
  }

  public Object getLock(final K key)
  {
    final Object object=new Object();
    Object lock=locks.putIfAbsent(key, object);
    return lock == null ? object : lock;
  }

}


import com.google.common.collect.MapMaker;
import com.google.common.collect.Sets;

import java.util.Collection;
import java.util.Set;
import java.util.concurrent.ConcurrentMap;

/**
 * A general purpose Multimap implementation for delayed processing and concurrent insertion/deletes.
 *
 * @param <K> A comparable Key
 * @param <V> A comparable Value
 */
public class ConcurrentMultiMap<K extends Comparable, V extends Comparable>
{
  private final int initialCapacity;
  private final LockMap<K> locks;
  private final ConcurrentMap<K, Set<V>> cache;

  public ConcurrentMultiMap()
  {
    this(16, 64);
  }

  public ConcurrentMultiMap(final int concurrencyLevel)
  {
    this(concurrencyLevel, 64);
  }

  public ConcurrentMultiMap(final int concurrencyLevel, final int initialCapacity)
  {
    this.initialCapacity=initialCapacity;
    cache=new MapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(initialCapacity).makeMap();
    locks=new LockMap<K>(concurrencyLevel, initialCapacity);
  }

  public void put(final K key, final V value)
  {
    synchronized(locks.getLock(key)){
      Set<V> set=cache.get(key);
      if(set == null){
        set=Sets.newHashSetWithExpectedSize(initialCapacity);
        cache.put(key, set);
      }
      set.add(value);
    }
  }

  public void putAll(final K key, final Collection<V> values)
  {
    synchronized(locks.getLock(key)){
      Set<V> set=cache.get(key);
      if(set == null){
        set=Sets.newHashSetWithExpectedSize(initialCapacity);
        cache.put(key, set);
      }
      set.addAll(values);
    }
  }

  public Set<V> remove(final K key)
  {
    synchronized(locks.getLock(key)){
      return cache.remove(key);
    }
  }

  public Set<K> getKeySet()
  {
    return cache.keySet();
  }

  public int size()
  {
    return cache.size();
  }

}
于 2012-09-12T21:00:49.430 に答える
1

選択は、あなたが何をしたいかに大きく依存します。多くのデータ構造があり、特定の領域で他のデータ構造より優れているものもあれば、その逆もあります。

私はあなたに潜在的な候補者を推薦することができます。完全に読み取られている場合は、ImmutableMultiMapが適している可能性があります。

同時読み取り/書き込みが必要な場合は、おそらくConcurrentHashMapとConcurrentSkipListSetを使用して独自のマルチマップを実装します（同期マルチマップと非ブロッキングデータ構造を使用してこの方法で作成されたマルチマップのセマンティクスは異なるため、注意が必要です）。ConcurrentSkipListSetを使用すると、バイナリ検索を使用できるようになり、反復するよりも高速になります。

行が多い場合は、ConcurrentHashMapと同期リストを使用することから始めることもできます。これにより、競合を大幅に減らすことができます。これは、パフォーマンスの問題を解決するのに十分であり、簡単です。

于 2010-08-10T11:01:32.913 に答える
0

「一致するキーを選択する大きなマップを反復処理する」と言うと、最適なデータ構造を使用しているかどうか疑問に思います。その繰り返しを避ける方法はありますか？

Guava には、異なるパフォーマンス特性を持つ複数のマルチマップ実装が含まれていることに注意してください。Zwei が述べたように、 ImmutableMultimap は変更可能な multimap よりも優れたパフォーマンスを発揮します。マルチマップに特定の値が含まれているかどうかをコードでチェックする場合、SetMultimaps はより高速です。それ以外の場合は、ArrayListMultimap のパフォーマンスが向上します。

于 2010-09-07T02:29:48.267 に答える