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

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

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

В Perl увеличение такого значения было бы несложно:

$map{$word}++;

Но в Java все гораздо сложнее. Вот как я сейчас это делаю:

int count = map.containsKey(word) ? map.get(word) : 0;
map.put(word, count + 1);

Что, конечно, зависит от функции автобокса в новых версиях Java. Интересно, можете ли вы предложить более эффективный способ увеличения такой стоимости? Существуют ли даже хорошие причины производительности для отказа от среды Collections и использования чего-то еще?

Обновление: я проверил несколько ответов. См. ниже.

Некоторые результаты теста

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

• метод "ContainsKey", который я представил в вопросе
• метод «TestForNull», предложенный Александром Димитровым
• метод «AtomicLong», предложенный Хэнком Гей
• метод "Trove", предложенный Джрудолом
• метод "MutableInt", предложенный phax.myopenid.com

метод

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

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

Результаты

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

Метод 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();
}

Теперь есть более короткий путь с использованием Java 8 Map::merge.

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

Что оно делает:

• если ключ не существует, укажите 1 в качестве значения
• иначе сумма 1 к значению, связанному с ключом

Больше информации здесь .

Небольшое исследование в 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

Время \ пространство результаты:

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

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

Например

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

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

map.getAndAdd(word, 112L); 

@ Хэнк Гей

В качестве продолжения моего собственного (довольно бесполезного) комментария: Троув выглядит как путь. Если по каким - либо причинам, вы хотели придерживаться стандартного 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. На самом деле, повышенный уровень дружелюбия к потокам - это все, что этот подход должен рекомендовать.

Map<String, Integer> map = new HashMap<>();
String key = "a random key";
int count = map.getOrDefault(key, 0); // ensure count will be one of 0,1,2,3,...
map.put(key, count + 1);

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

Выгода:

• Нет необходимости добавлять новый класс или использовать другую концепцию изменяемого int
• Не полагаясь ни на какую библиотеку
• Легко понять, что именно происходит (не слишком много абстракции)

Даунсайд:

• Хеш-карта будет дважды найдена для get () и put (). Так что это не будет самый производительный код.

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

Но если вы очень серьезно относитесь к проблеме, вы перфекционист, другой способ - использовать метод слияния, который (вероятно) более эффективен, чем предыдущий фрагмент кода, поскольку вы (теоретически) будете искать карту только один раз: (хотя этот код не очевиден с первого взгляда, он короткий и производительный)

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

Предложение: большую часть времени вы должны заботиться о читабельности кода, а не о небольшом выигрыше в производительности. Если вам проще понять первый фрагмент кода, используйте его. Но если вы в состоянии понять 2-й штраф, вы также можете пойти на это!

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

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

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

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

int count = map.containsKey (word)? map.get (слово): 0;

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

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

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

map.put (ключ, map.get (ключ) + 1);

опасно, так как это может привести к NullPointerExceptionс. Вы должны проверить для nullпервого.

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

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

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

окончательная карта HashMap = generateRandomHashMap ();
окончательный ключ объекта = fetchSomeKey ();
окончательное целое число i = map.get (ключ);
if (i! = null) {
    map.put (i + 1);
} еще {
    // сделай что-нибудь
}

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

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

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) не должны быть такими большими.

Вы можете использовать метод 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 проверяет, связан ли указанный ключ со значением или нет? Если связанного значения нет, то оно пытается вычислить свое значение, используя данную функцию отображения. В любом случае он возвращает текущее (существующее или вычисленное) значение, связанное с указанным ключом, или ноль, если вычисленное значение равно нулю.

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

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

Если вы знаете, что количество сделанных приращений будет в значительной степени превосходить количество ключей (= слов в данном случае), рассмотрите возможность использования вместо этого держателя int Факс уже представил код для этого. Здесь снова, с двумя изменениями (класс держателя сделан статическим и начальное значение установлено в 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();
}

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

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

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

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

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

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

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

Есть несколько подходов:

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

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

    class My{
        String word;
        int count;
    }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

"поставить" нужно "получить" (чтобы избежать дублирования ключа).
Так что прямо сделайте «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
  }
}

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

Я бы использовал Ленивую Карту Коллекций Apache (чтобы инициализировать значения 0) и использовал MutableIntegers из Apache Lang в качестве значений на этой карте.

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

В структуре данных функциональной библиотеки JavaTreeMap есть 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".

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

Я не знаю, насколько это эффективно, но приведенный ниже код также работает. Вам нужно определить a 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

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

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

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

Вот пример из коллекции Eclipse 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 Collections.

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

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

Поскольку многие люди ищут в 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}

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

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

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

если у тебя есть

map.put(key, 1)

ты бы сделал

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

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