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

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

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

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

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

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

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

    class My{
        String word;
        int count;
    }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

опасно, так как это может привести к выходу NullPointerException. Вы должны сначала проверить 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()));.

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

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

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

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

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

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

Ротация памяти может быть здесь проблемой, поскольку каждая упаковка 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();
}

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

Кстати, хороший поисковый запрос по этой теме - «гистограмма».

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

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

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

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

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

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

Методика

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

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

Полученные результаты

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

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

• ContainsKey: 30,654 секунды (базовый уровень)
• AtomicLong: 29,780 секунд (в 1,03 раза быстрее)
• TestForNull: 28,804 секунды (в 1,06 раза быстрее)
• Trove: 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();
}

В структуре данных TreeMap библиотеки Функциональная Java есть метод 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».

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

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
}

Если счетчик начинается с 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
  }
}

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

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

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

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

Вариант подхода 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 Гуава - ваш друг ...

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

Например.

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

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

map.getAndAdd(word, 112L); 

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

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

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

Вот пример из Ката Коллекции Затмения.

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.

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

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

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

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

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

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

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

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

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

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

• если ключ не существует, поместите 1 как значение
• в противном случае сумма 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 с Python, поэтому я могу посочувствовать вашей борьбе.

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

map.put(key, 1)

ты бы сделал

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

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

Довольно просто, просто используйте встроенную функцию в Map.java, как показано ниже.

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

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

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

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

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