it-swarm-ru.tech

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

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

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

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

$map{$Word}++;

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

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

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

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

327
gregory

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

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

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

Метод

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

  1. создал пять классов, которые были идентичны, за исключением различий, показанных ниже. Каждый класс должен был выполнить операцию, типичную для сценария, который я представил: открыть файл 10 МБ и прочитать его, а затем выполнить подсчет частоты всех токенов Word в файле. Так как это заняло в среднем всего 3 секунды, мне пришлось выполнять подсчет частоты (не I/O) 10 раз.
  2. рассчитал цикл из 10 итераций, но , а не операции ввода-вывода , и записал общее время, затраченное (в секундах), по существу, используя метод Яна Дарвина в Java Кулинарная книга .
  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();
}
344
gregory

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

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

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

175
LE GALL Benoît

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

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

42
leventov

Google Гуава твой друг ...

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

Например.

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

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

map.getAndAdd(Word, 112L); 
33
H6.

@ Хэнк Гей

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

31
Hank Gay

Это всегда хорошая идея, чтобы посмотреть Библиотека коллекций Google для такого рода вещей. В этом случае Multiset добьется цели:

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>, поэтому вы не будете нести расходы на бокс.

25
Chris Nokleberg

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

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

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

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

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

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

опасно, так как это может привести к NullPointerExceptions. Сначала вы должны проверить null.

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

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

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

 final HashMap map = generateRandomHashMap (); 
 final ключ объекта = fetchSomeKey (); 
 final целое число i = map.get (key); 
 if (i ! = null) {
 map.put (i + 1); 
} else {
 // сделать что-то 
} 

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

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

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

Выгода:

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

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

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

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

20
off99555

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

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

18
Philip Helger

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

9
i_am_zero

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

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

7
volley

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

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

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

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

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


    class My{
        String Word;
        int count;
    }

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

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

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



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

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

3
tovare

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

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

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

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

3
the felis leo

Вариант подхода 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);
3
Eamonn O'Brien-Strain

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

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

3
jrudolph

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

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

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

3
John Wright

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

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

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

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
  }
}
2
the felis leo

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

HashBag поддерживается MutableObjectIntMap, в котором хранятся примитивные целые числа вместо объектов 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.

1
Craig P. Motlin

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

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

1
jb.

В структуре Функциональная 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".

1
Apocalisp

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

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

1
Hank Gay

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

1
Alex Miller