Самый эффективный способ увеличения значения карты в Java

Ответ 1

Некоторые результаты тестирования

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

• метод "ContainsKey", который я представил в вопрос
• метод "TestForNull", предложенный Александром Димитровым
• метод "AtomicLong", предложенный Hank Gay
• метод "Тропа", предложенный jrudolph
• метод "MutableInt", предложенный phax.myopenid.com

Метод

Вот что я сделал...

• создано пять классов, которые были идентичны, за исключением различий, показанных ниже. Каждый класс должен был выполнить операцию, типичную для представленного мной сценария: открытие 10 МБ файла и его чтение, а затем выполнение частоты подсчета всех токенов в файле. Так как это заняло в среднем всего 3 секунды, мне приходилось выполнять частоту (не I/O) 10 раз.
• синхронизировал цикл из 10 итераций, но не операцию ввода-вывода, и записал общее время (в секундах), используя по существу метод Яна Дарвина в Java Поваренная.
• выполнил все пять тестов подряд, а затем сделал это еще три раза.
• усреднил четыре результата для каждого метода.

Результаты

Сначала я представлю результаты и код ниже для тех, кто интересуется.

Метод ContainsKey был, как и ожидалось, самым медленным, поэтому я дам скорость каждого метода по сравнению со скоростью этого метода.

• ContainsKey: 30.654 секунд (базовый уровень)
• AtomicLong: 29.780 секунд (в 1.03 раза быстрее)
• TestForNull: 28.804 секунды (в 1.06 раза быстрее)
• Тройка: 26.313 секунд (в 1,16 раза быстрее)
• MutableInt: 25.747 секунд (в 1,19 раза быстрее)

Выводы

Похоже, что только метод MutableInt и метод Trove значительно быстрее, поскольку только они дают повышение производительности более чем на 10%. Однако, если проблема с потоками является проблемой, AtomicLong может быть более привлекательной, чем другие (я не уверен). Я также запускал TestForNull с переменными final, но разница была незначительной.

Обратите внимание, что я не профилировал использование памяти в разных сценариях. Я был бы рад услышать от любого, у кого есть хорошее представление о том, как методы MutableInt и Trove могут повлиять на использование памяти.

Лично я считаю метод MutableInt наиболее привлекательным, так как он не требует загрузки каких-либо сторонних классов. Поэтому, если я не обнаружу проблем с ним, я скорее всего пойду.

Код

Вот критический код каждого метода.

ContainsKey

import java.util.HashMap;
import java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
int count = freq.containsKey(word) ? freq.get(word) : 0;
freq.put(word, count + 1);

TestForNull

import java.util.HashMap;
import java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
Integer count = freq.get(word);
if (count == null) {
    freq.put(word, 1);
}
else {
    freq.put(word, count + 1);
}

AtomicLong

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.atomic.AtomicLong;
...
final ConcurrentMap<String, AtomicLong> map = 
    new ConcurrentHashMap<String, AtomicLong>();
...
map.putIfAbsent(word, new AtomicLong(0));
map.get(word).incrementAndGet();

Trove

import gnu.trove.TObjectIntHashMap;
...
TObjectIntHashMap<String> freq = new TObjectIntHashMap<String>();
...
freq.adjustOrPutValue(word, 1, 1);

MutableInt

import java.util.HashMap;
import java.util.Map;
...
class MutableInt {
  int value = 1; // note that we start at 1 since we're counting
  public void increment () { ++value;      }
  public int  get ()       { return value; }
}
...
Map<String, MutableInt> freq = new HashMap<String, MutableInt>();
...
MutableInt count = freq.get(word);
if (count == null) {
    freq.put(word, new MutableInt());
}
else {
    count.increment();
}

Ответ 2

Хорошо, может быть старый вопрос, но в Java 8 есть более короткий путь:

Map.merge(key, 1, Integer::sum)

Что он делает: если ключ не существует, укажите 1 в качестве значения, иначе сумма 1 к значению, связанному с ключом. Более подробная информация здесь

Ответ 3

Небольшое исследование в 2016 году: https://github.com/leventov/java-word-count, исходный код теста

Лучшие результаты по методу (меньше - лучше):

                 time, ms
kolobokeCompile  18.8
koloboke         19.8
trove            20.8
fastutil         22.7
mutableInt       24.3
atomicInteger    25.3
eclipse          26.9
hashMap          28.0
hppc             33.6
hppcRt           36.5

Время\пространство:

Ответ 4

Google Guava - твой друг...

... по крайней мере, в некоторых случаях. У них есть этот хороший AtomicLongMap. Особенно приятно, потому что вы имеете дело с длинной ценностью на вашей карте.

Например

AtomicLongMap<String> map = AtomicLongMap.create();
[...]
map.getAndIncrement(word);

Также возможно добавить более 1 к значению:

map.getAndAdd(word, 112L); 

Ответ 5

@Hank Gay

В качестве следствия моего собственного (довольно бесполезного) комментария: Trove выглядит как путь. Если по какой-то причине вы хотели придерживаться стандартного JDK, ConcurrentMap и AtomicLong может сделать код чуть-чуть приятнее, хотя YMMV.

    final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
    map.putIfAbsent("foo", new AtomicLong(0));
    map.get("foo").incrementAndGet();

оставит 1 в качестве значения на карте для foo. Реально, повышенная дружественность к потоку - это все, что этот подход должен рекомендовать.

Ответ 6

Всегда полезно посмотреть на Google Collections Library для такого рода вещей. В этом случае Multiset выполнит трюк:

Multiset bag = Multisets.newHashMultiset();
String word = "foo";
bag.add(word);
bag.add(word);
System.out.println(bag.count(word)); // Prints 2

Существуют методы, подобные карте, для итерации по ключам/элементам и т.д. Внутренне реализация в настоящее время использует HashMap<E, AtomicInteger>, поэтому вы не будете нести расходы на бокс.

Ответ 7

Вы должны знать, что ваша первоначальная попытка

int count = map.containsKey(word) ? map.get(word) : 0;

содержит две потенциально дорогостоящие операции на карте, а именно containsKey и get. Первый выполняет операцию, потенциально очень похожую на последнюю, поэтому вы выполняете ту же работу дважды!

Если вы посмотрите на API для карты, операции get обычно возвращают null, когда карта не содержит запрошенный элемент.

Обратите внимание, что это сделает решение вроде

map.put( key, map.get(key) + 1 );

опасно, так как это может привести к NullPointerException s. Сначала нужно проверить null.

Также обратите внимание на, и это очень важно, что HashMap может содержать nulls по определению. Поэтому не каждый возвращенный null говорит "нет такого элемента". В этом отношении containsKey ведет себя иначе, чем get, фактически говоря вам, есть ли такой элемент. Подробнее см. В API.

Однако для вашего случая вы можете не захотеть различать сохраненные null и "noSuchElement". Если вы не хотите разрешать null, вы можете выбрать Hashtable. Использование библиотеки обертки, как уже было предложено в других ответах, может быть лучшим решением для ручного лечения, в зависимости от сложности вашего приложения.

Чтобы выполнить ответ (и я забыл поместить это сначала, благодаря функции редактирования!), лучший способ сделать это изначально, - это get в переменную final, проверьте null и put обратно с помощью 1. Переменная должна быть final, потому что она неизменна в любом случае. Компилятору может не понадобиться этот намек, но он более ясен.

final HashMap map = generateRandomHashMap();
final Object key = fetchSomeKey();
final Integer i = map.get(key);
if (i != null) {
    map.put(i + 1);
} else {
    // do something
}

Если вы не хотите полагаться на автобоксинг, вы должны сказать что-то вроде map.put(new Integer(1 + i.getValue()));.

Ответ 8

Map<String, Integer> map = new HashMap<>();
String key = "a random key";
int count = map.getOrDefault(key, 0);
map.put(key, count + 1);

И как вы увеличиваете значение с помощью простого кода.

Преимущество:

• Не создавать другой класс для mutable int
• Короткий код
• Легко понять
• Исключить исключение нулевого указателя

Другой способ - использовать метод слияния, но это слишком важно для просто увеличения значения.

map.merge(key, 1, (a,b) -> a+b);

Предложение: вы должны заботиться о читаемости кода больше, чем небольшое увеличение производительности в большинстве случаев.

Ответ 9

Другим способом было бы создание изменяемого целого числа:

class MutableInt {
  int value = 0;
  public void inc () { ++value; }
  public int get () { return value; }
}
...
Map<String,MutableInt> map = new HashMap<String,MutableInt> ();
MutableInt value = map.get (key);
if (value == null) {
  value = new MutableInt ();
  map.put (key, value);
} else {
  value.inc ();
}

конечно, это означает создание дополнительного объекта, но накладные расходы по сравнению с созданием Integer (даже с Integer.valueOf) не должны быть такими.

Ответ 10

Вы можете использовать метод computeIfAbsent в интерфейсе Map представленном в Java 8.

final Map<String,AtomicLong> map = new ConcurrentHashMap<>();
map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet();
map.computeIfAbsent("B", k->new AtomicLong(0)).incrementAndGet();
map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet(); //[A=2, B=1]

Метод computeIfAbsent проверяет, computeIfAbsent ли указанный ключ со значением или нет? Если связанного значения нет, то оно пытается вычислить свое значение, используя данную функцию отображения. В любом случае он возвращает текущее (существующее или вычисленное) значение, связанное с указанным ключом, или ноль, если вычисленное значение равно нулю.

Напомним, что если у вас есть ситуация, когда несколько потоков обновляют общую сумму, вы можете взглянуть на класс LongAdder. Из-за высокой конкуренции ожидаемая пропускная способность этого класса значительно выше, чем у AtomicLong, за счет более высокого потребления пространства.

Ответ 11

Здесь может возникнуть проблема с чередованием памяти, так как каждый бокс для int, который больше или равен 128, вызывает выделение объекта (см. Integer.valueOf(int)). Хотя сборщик мусора очень эффективно работает с недолговечными объектами, производительность будет в некоторой степени страдать.

Если вы знаете, что количество сделанных приращений будет в значительной степени превышать количество ключей (= в этом случае), рассмотрите вместо этого использование владельца int. Phax уже представил код для этого. Здесь он снова, с двумя изменениями (класс держателя статический и начальное значение установлено равным 1):

static class MutableInt {
  int value = 1;
  void inc() { ++value; }
  int get() { return value; }
}
...
Map<String,MutableInt> map = new HashMap<String,MutableInt>();
MutableInt value = map.get(key);
if (value == null) {
  value = new MutableInt();
  map.put(key, value);
} else {
  value.inc();
}

Если вам нужна максимальная производительность, найдите реализацию карты, которая напрямую связана с примитивными типами значений. jrudolph упоминается GNU Trove.

Кстати, хорошим термином поиска для этого предмета является "гистограмма".

Ответ 12

Вместо вызова containsKey() быстрее просто вызвать map.get и проверить, является ли возвращаемое значение нулевым или нет.

    Integer count = map.get(word);
    if(count == null){
        count = 0;
    }
    map.put(word, count + 1);

Ответ 13

Я думаю, что ваше решение будет стандартным, но, как вы отметили сами, это, вероятно, не самый быстрый способ.

Вы можете посмотреть GNU Trove. Это библиотека, которая содержит всевозможные быстрые примитивные коллекции. В вашем примере будет использоваться TObjectIntHashMap, который имеет метод adjustOrPutValue, который делает именно то, что вы хотите.

Ответ 14

Существует несколько подходов:

• Используйте мешок alorithm как набор, содержащийся в Коллекциях Google.

• Создайте изменяемый контейнер, который вы можете использовать на Карте:

    class My{
        String word;
        int count;
    }

И используйте put ( "word", new My ( "Word" )); Затем вы можете проверить, существует ли он и увеличивать при добавлении.

Избегайте откатывания собственного решения с помощью списков, потому что, если вы получите поиск и сортировку внутренней очереди, ваша производительность будет вонять. Первое решение HashMap на самом деле довольно быстро, но правильное, как в Google Collections, возможно, лучше.

Подсчет слов с помощью Google Collections выглядит примерно так:

    HashMultiset s = new HashMultiset();
    s.add("word");
    s.add("word");
    System.out.println(""+s.count("word") );

Использование HashMultiset довольно элегантно, потому что алгоритм суммирования - это то, что вам нужно при подсчете слов.

Ответ 15

Вы уверены, что это узкое место? Провели ли вы анализ производительности?

Попробуйте использовать профилировщик NetBeans (его бесплатный и встроенный в NB 6.1), чтобы посмотреть горячие точки.

Наконец, обновление JVM (скажем, от 1,5 до 1,6) часто является дешевым усилителем производительности. Даже обновление номера сборки может обеспечить хорошее повышение производительности. Если вы работаете в Windows, и это приложение класса сервера, используйте -server в командной строке для использования JVM Hotspot Server. На машинах Linux и Solaris это автоопределяется.

Ответ 16

Коллекции Google HashMultiset:
 - довольно элегантный, чтобы использовать  - но потребляйте процессор и память

Лучше всего было бы иметь такой метод, как: Entry<K,V> getOrPut(K); (элегантная и низкая стоимость)

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

Более элегантный:
 - возьмите HashSet<Entry>
 - расширьте его так, чтобы get(K) поместил новую запись в случае необходимости
 - Запись может быть вашим собственным объектом.
- > (new MyHashSet()).get(k).increment();

Ответ 17

Вариант подхода MutableInt, который может быть еще быстрее, если бит взломать, заключается в использовании массива int-element с одним элементом:

Map<String,int[]> map = new HashMap<String,int[]>();
...
int[] value = map.get(key);
if (value == null) 
  map.put(key, new int[]{1} );
else
  ++value[0];

Было бы интересно, если бы вы могли повторить свои тесты производительности с этим вариантом. Это может быть самый быстрый.

Изменить: вышеприведенный шаблон работал отлично для меня, но в итоге я изменил использование коллекций Trove, чтобы уменьшить объем памяти на некоторых очень больших картах, которые я создавал, и в качестве бонуса это было также быстрее.

Одна действительно приятная особенность заключается в том, что класс TObjectIntHashMap имеет единственный вызов adjustOrPutValue, который, в зависимости от того, уже есть ли значение на этом ключе, либо поместит начальное значение, либо увеличит существующее значение. Это идеально подходит для увеличения:

TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();
...
map.adjustOrPutValue(key, 1, 1);

Ответ 18

"поставить" нужно "получить" (чтобы не было дублирующего ключа).
Так что прямо делайте "put",
и если было предыдущее значение, сделайте добавление:

Map map = new HashMap ();

MutableInt newValue = new MutableInt (1); // default = inc
MutableInt oldValue = map.put (key, newValue);
if (oldValue != null) {
  newValue.add(oldValue); // old + inc
}

Если count начинается с 0, добавьте 1: (или любые другие значения...)

Map map = new HashMap ();

MutableInt newValue = new MutableInt (0); // default
MutableInt oldValue = map.put (key, newValue);
if (oldValue != null) {
  newValue.setValue(oldValue + 1); // old + inc
}

Примечание. Этот код не является потокобезопасным. Используйте его для сборки, затем используйте карту, а не одновременно обновляйте ее.

Оптимизация. В цикле сохраните старое значение, чтобы стать новым значением следующего цикла.

Map map = new HashMap ();
final int defaut = 0;
final int inc = 1;

MutableInt oldValue = new MutableInt (default);
while(true) {
  MutableInt newValue = oldValue;

  oldValue = map.put (key, newValue); // insert or...
  if (oldValue != null) {
    newValue.setValue(oldValue + inc); // ...update

    oldValue.setValue(default); // reuse
  } else
    oldValue = new MutableInt (default); // renew
  }
}

Ответ 19

Все очень просто, просто используйте встроенную функцию в Map.java следующим образом

map.put(key, map.getOrDefault(key, 0) + 1);

Ответ 20

Различные примитивные обертки, например Integer, являются неизменными, поэтому на самом деле не более сжатый способ делать то, что вы просите, если вы не можете сделать это с помощью AtomicLong. Я могу сказать, что пойдет минутку и обновится. BTW, Hashtable является частью Framework Collections.

Ответ 21

Я бы использовал Apache Collections Lazy Map (для инициализации значений 0) и использовал MutableIntegers из Apache Lang в качестве значений на этой карте.

Наибольшая стоимость заключается в том, чтобы дважды загрузить карту в свой метод. В моем случае вы должны сделать это только один раз. Просто получите значение (оно будет инициализировано, если оно отсутствует) и увеличьте его.

Ответ 22

@Vilmantas Baranauskas: Что касается этого ответа, я бы прокомментировал, если бы у меня были репрезентации, но я этого не делаю. Я хотел бы отметить, что класс Counter, определенный там, не является потокобезопасным, так как недостаточно просто синхронизировать inc() без синхронизации значения(). В других потоках, вызывающих value(), не гарантируется, что они будут видеть значение, если с обновлением не установлено отношение "доживет".

Ответ 23

Функциональная библиотека Java TreeMap datastructure имеет метод update в последней голове туловища:

public TreeMap<K, V> update(final K k, final F<V, V> f)

Пример использования:

import static fj.data.TreeMap.empty;
import static fj.function.Integers.add;
import static fj.pre.Ord.stringOrd;
import fj.data.TreeMap;

public class TreeMap_Update
  {public static void main(String[] a)
    {TreeMap<String, Integer> map = empty(stringOrd);
     map = map.set("foo", 1);
     map = map.update("foo", add.f(1));
     System.out.println(map.get("foo").some());}}

Эта программа печатает "2".

Ответ 24

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

HashBag поддерживается MutableObjectIntMap, который хранит примитивные int вместо объектов Counter. Это уменьшает издержки памяти и улучшает скорость выполнения.

HashBag предоставляет API, который вам нужен, так как он Collection, который также позволяет запрашивать количество вхождений элемента.

Вот пример из Eclipse Collections Kata.

MutableBag<String> bag =
  HashBag.newBagWith("one", "two", "two", "three", "three", "three");

Assert.assertEquals(3, bag.occurrencesOf("three"));

bag.add("one");
Assert.assertEquals(2, bag.occurrencesOf("one"));

bag.addOccurrences("one", 4);
Assert.assertEquals(6, bag.occurrencesOf("one"));

Примечание: Я являюсь коммиттером для коллекций Eclipse.

Ответ 25

Я не знаю, насколько он эффективен, но работает ниже код. В начале вам нужно определить BiFunction. Кроме того, вы можете сделать больше, чем просто увеличение с помощью этого метода.

public static Map<String, Integer> strInt = new HashMap<String, Integer>();

public static void main(String[] args) {
    BiFunction<Integer, Integer, Integer> bi = (x,y) -> {
        if(x == null)
            return y;
        return x+y;
    };
    strInt.put("abc", 0);


    strInt.merge("abc", 1, bi);
    strInt.merge("abc", 1, bi);
    strInt.merge("abc", 1, bi);
    strInt.merge("abcd", 1, bi);

    System.out.println(strInt.get("abc"));
    System.out.println(strInt.get("abcd"));
}

вывод

3
1

Ответ 26

Я предлагаю использовать Java 8 Map :: compute(). Он также рассматривает случай, когда ключ не существует.

Map.compute(num, (k, v) -> (v == null) ? 1 : v + 1);

Ответ 27

Поскольку многие люди ищут темы Java для ответов Groovy, вот как вы можете это сделать в Groovy:

dev map = new HashMap<String, Integer>()
map.put("key1", 3)

map.merge("key1", 1) {a, b -> a + b}
map.merge("key2", 1) {a, b -> a + b}

Ответ 28

Надеюсь, я правильно понимаю ваш вопрос, я прихожу на Java из Python, чтобы сопереживать вашей борьбе.

если у вас есть

map.put(key, 1)

ты бы сделал

map.put(key, map.get(key) + 1)

Надеюсь это поможет!

Ответ 29

Простой и легкий способ в Java 8 заключается в следующем:

final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
    map.computeIfAbsent("foo", key -> new AtomicLong(0)).incrementAndGet();