MultiMap с хорошей производительностью

Question

В моем коде у меня есть карта, которая в значительной степени используется, несколько тысяч раз за несколько секунд. Первоначально у меня был TREEWAP, но при тестировании с 9 000 записей я смотрел, как мой старый процессор тает. И это должно масштабироваться. Поэтому я переехал в хесмап и производительность была превосходной.

Теперь я изменяю свой дизайн и ищу MultiMap. Однако я боюсь влияния на производительность на get() Сторона, поскольку она должна повторяться, как она должна повторяться, указанная большая карта, выбирая подходящие ключи, и когда он называется много раз даже синхронизированным, похоже, что это будет медленным.

Есть ли хорошие многопроизводительные, которые могут справиться с такими большие значения с большой производительностью? Производительность имеет решающее значение в этом приложении, так как может быть много больших отдельных карт, обрабатывающих очень большую рабочую нагрузку, создавая «небольшие» потери производительности очень большие проблемы.

Бонусные баллы, если его можно извлечь, чтобы работать в одиночку без каких-либо зависимостей.

Answer 1

Тот, который мне порекомендовал в одном из моих вопросов, был MultiMap Apache Commons:http://commons.apache.org/collections/ap-3.2.1/org/apache/Commons/Collions/multihashmap.html.

Это бесплатное программное обеспечение, поэтому вы можете по крайней мере получить источник, чтобы посмотреть на него, и в зависимости от вашей лицензии, вы можете изменить его или использовать его автономной.

Он использует ArrayList внутри внутренне, но я представляю, что вы, вероятно, можете изменить его, чтобы использовать хеш-сайт или что-то. Я бы посмотрел на createCollection(Collection coll) метод.

Обновление: На самом деле, HashmultiMap Guava, похоже, уже будет то, о чем я говорил:https://github.com/google/guava/blob/master/guava/src/com/google/common/collect/multimap.java.

Я посмотрел на источник, и кажется, что каждая коллекция ценностей на самом деле поддерживается хеш-классом.

Answer 2

У меня было требование, где я должен был иметь Map<Comparable, Set<Comparable>> Там, где вставка на карту быть одновременно, а также на соответствующем наборе, но после того, как ключ был использован с карты, он должен был быть удален, подумать, если в качестве работы работает каждые две секунды, которые потребляют все Set<Comparable> Из определенного ключа, но вставка быть полностью одновременно, так что большинство значений буферируются при удалении работы, вот моя реализация:

Примечание: Я использую карты помощника в Гуавы, чтобы создать параллельные карты, также эмулирует это решение Java Changurency на практике Листинг 5.19:

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();
  }

}

Answer 3

Выбор во многом будет зависеть от того, что вы хотите сделать. Есть много данных-структур, а некоторые лучше других в определенных областях и наоборот.

Я мог бы порекомендовать вам потенциальные кандидаты. Если он полностью прочитан, ImmutabluTableMULTIMAP может быть хорошей пригодностью.

Если тебе нужно одновременно read / write, тогда я внедрил свой собственный multiMap, возможно, используя concurrenthartashmap и concurrendkiplistset (вам нужно быть осторожным, потому что семантика между синхронизированным многопроизводительным и многопроизводительным, созданным таким образом, используя неблокирующие структуры данных). Если вы используете CONCURURENDKIPLISSET, вы можете использовать двоичный поиск, и это быстрее, чем просто итерация.

Если у вас много строк, вы также можете начать, просто используя CONCURRENTHASHMAP и синхронизированный список. Это может значительно снизить спор, что может быть достаточно, чтобы решить вашу проблему с производительностью, и это просто.

Answer 4

Я использовал Google Guava в качестве замены в Apache Commons, когда это возможно ... Вот пример с его внедрением его MultiMap Hashmultimap и обратите внимание, что значения карты представляют собой набор значений вместо единой ссылки. Метод «содержит ()» используется для результата получения (ключа).

private Multimap<Phase, ResultingState> phaseResults = HashMultimap.create();

/**
 * @param withState is the state to be verified.
 * @param onPhase is the phase to be verified.
 * @return Whether the given result was reported in the given phase.
 */
public boolean wasReported(ResultingState withState, Phase onPhase) {
    return phaseResults.containsKey(onPhase) && phaseResults.get(onPhase).contains(withState);
}

/**
 * @param resultingState is the resulting state.
 * @return Whether the given resulting state has ever been reported.
 */
public boolean anyReported(ResultingState resultingState) {
    return phaseResults.values().contains(resultingState);
}

Answer 5

Когда вы упоминаете, что вы «итерация по поводу указанной большой карты, выбирая подходящие клавиши», что заставляет меня задаться вопросом, используете ли вы лучшую структуру данных. Есть ли способ избежать этой итерации?

Обратите внимание, что Guava включает несколько реализаций MultiMap с различными характеристиками производительности. Как упомянул Zwei, ImmutableMUltiMAP имеет лучшую производительность, чем мультимапты. SetMultimaps быстрее, если ваш код проверяет, содержит ли MultiMap определенное значение; В противном случае ArrayListMultiMap работает лучше.