Самый эффективный способ увеличить значение карты в Java
https://stackoverflow.com/questions/81346
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Надеюсь, этот вопрос не посчитали слишком принципиальным для этого форума, но посмотрим.Мне интересно, как реорганизовать некоторый код для повышения производительности, который запускается несколько раз.
Скажем, я создаю список частотности слов, используя карту (вероятно, HashMap), где каждый ключ представляет собой строку со словом, которое подсчитывается, а значение представляет собой целое число, которое увеличивается каждый раз, когда находится токен слова.
В Perl увеличить такое значение было бы тривиально просто:
$map{$word}++;
Но в Java все гораздо сложнее.Вот как я сейчас это делаю:
int count = map.containsKey(word) ? map.get(word) : 0;
map.put(word, count + 1);
Что, конечно, зависит от функции автобокса в новых версиях Java.Интересно, можете ли вы предложить более эффективный способ увеличения такого значения?Есть ли веские причины для повышения производительности, чтобы отказаться от платформы коллекций и использовать вместо нее что-то другое?
Обновлять:Я проверил несколько ответов.См. ниже.
Решение
Некоторые результаты испытаний
Я получил много хороших ответов на этот вопрос (спасибо, ребята), поэтому решил провести несколько тестов и выяснить, какой метод на самом деле самый быстрый.Я протестировал пять методов:
- метод «ContainsKey», который я представил в вопрос
- метод TestForNull, предложенный Александром Димитровым
- метод «AtomicLong», предложенный Хэнк Гэй
- метод «Находки», предложенный Джудольфом
- метод MutableInt, предложенный phax.myopenid.com
Метод
Вот что я сделал...
- создал пять классов, которые были идентичны, за исключением различий, показанных ниже.Каждый класс должен был выполнить операцию, типичную для представленного мной сценария:открытие файла размером 10 МБ и чтение его, а затем выполнение подсчета частоты всех токенов слов в файле.Поскольку это занимало в среднем всего 3 секунды, я заставил его выполнить подсчет частоты (а не ввода-вывода) 10 раз.
- рассчитал цикл из 10 итераций, но не операция ввода-вывода и записал общее затраченное время (в секундах), по существу используя Метод Яна Дарвина в Java Cookbook.
- выполнил все пять тестов последовательно, а затем проделал это еще три раза.
- усреднили четыре результата для каждого метода.
Полученные результаты
Сначала я представлю результаты и код ниже для тех, кто заинтересован.
А Содержит ключ Как и ожидалось, этот метод оказался самым медленным, поэтому я приведу скорость каждого метода в сравнении со скоростью этого метода.
- Содержит ключ: 30,654 секунды (базовый уровень)
- Атомиклонг: 29,780 секунды (в 1,03 раза быстрее)
- ТестФорНулл: 28,804 секунды (в 1,06 раза быстрее)
- Находка: 26,313 секунды (в 1,16 раза быстрее)
- МутабельИнт: 25,747 секунды (в 1,19 раза быстрее)
Выводы
Казалось бы, только методы MutableInt и Trove значительно быстрее, поскольку только они дают прирост производительности более чем на 10%.Однако, если многопоточность является проблемой, AtomicLong может быть более привлекательным, чем другие (я не совсем уверен).Я также запустил TestForNull с помощью final переменных, но разница была незначительной.
Обратите внимание, что я не профилировал использование памяти в различных сценариях.Я был бы рад услышать мнение любого, кто имеет хорошее представление о том, как методы MutableInt и Trove могут повлиять на использование памяти.
Лично я считаю метод MutableInt наиболее привлекательным, поскольку он не требует загрузки каких-либо сторонних классов.Так что, если я не обнаружу с этим проблемы, я, скорее всего, пойду именно этим путем.
Код
Вот ключевой код каждого метода.
Содержит ключ
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);
Тестфорнуль
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();
Находка
import gnu.trove.TObjectIntHashMap;
...
TObjectIntHashMap<String> freq = new TObjectIntHashMap<String>();
...
freq.adjustOrPutValue(word, 1, 1);
МутаблеИнт
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(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 Гуава твой друг...
...по крайней мере, в некоторых случаях.У них это здорово AtomicLongMap.Особенно приятно, потому что вы имеете дело с длинный как значение на вашей карте.
Например.
AtomicLongMap<String> map = AtomicLongMap.create();
[...]
map.getAndIncrement(word);
Также возможно добавить к значению более 1:
map.getAndAdd(word, 112L);
@Хэнк Гей
В продолжение моего собственного (довольно бесполезного) комментария:Trove выглядит как путь.Если по какой-либо причине вы хотите придерживаться стандартного JDK, Конкурентная карта и AtomicLong можно сделать код крошечный немного лучше, хотя YMMV.
final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
map.putIfAbsent("foo", new AtomicLong(0));
map.get("foo").incrementAndGet();
покинет 1 как значение на карте для foo.На самом деле, повышенная дружественность к многопоточности — это все, что может рекомендовать этот подход.
Всегда полезно взглянуть на Библиотека коллекций 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>, так что вам не придется нести расходы на бокс.
Вы должны осознавать тот факт, что ваша первоначальная попытка
int count = map.containsKey(word) ? map.get(word) : 0;
содержит две потенциально дорогостоящие операции на карте, а именно containsKey и get.Первый выполняет операцию, потенциально очень похожую на вторую, поэтому вы выполняете ту же работу. дважды!
Если вы посмотрите на API для Map, 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())); вместо.
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);
Предположение:Большую часть времени вам следует заботиться о читаемости кода, а не о небольшом приросте производительности.
Другой способ — создать изменяемое целое число:
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) не должны быть такими большими.
Вы можете использовать вычислитьеслиабсент метод в Map интерфейс, представленный в Ява 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.
Кстати, если у вас есть ситуация, когда несколько потоков обновляют общую сумму, вы можете посмотреть ЛонгАддер class.При высокой конкуренции ожидаемая пропускная способность этого класса значительно выше, чем AtomicLong, за счет более высокого потребления пространства.
Ротация памяти может быть здесь проблемой, поскольку каждая упаковка int, большего или равного 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 сокровище.
Кстати, хороший поисковый запрос по этой теме — «гистограмма».
Вместо вызова containsKey() быстрее просто вызвать 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 это определяется автоматически.
Есть несколько подходов:
Используйте алгоритм сумки, подобный наборам, содержащимся в коллекциях 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 весьма элегантно, поскольку алгоритм Bag — это именно то, что вам нужно при подсчете слов.
Я думаю, что ваше решение будет стандартным, но, как вы сами заметили, это, вероятно, не самый быстрый способ.
Вы можете посмотреть GNU сокровище.Это библиотека, содержащая всевозможные быстрые примитивные коллекции.В вашем примере будет использоваться 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);
HashMultiset коллекций Google:
- довольно элегантно в использовании
- но потребляют процессор и память
Лучше всего было бы иметь такой метод: Entry<K,V> getOrPut(K); (элегантный и недорогой)
Такой метод будет вычислять хэш и индекс только один раз, а затем мы могли бы сделать то, что хотим с входом (заменить или обновить значение).
Более элегантно:
- возьми HashSet<Entry>
- растянуть его так, чтобы get(K) добавьте новую запись, если необходимо
- Вход может быть вашим собственным объектом.
--> (new MyHashSet()).get(k).increment();
«положить» нужно «получить» (чтобы исключить дублирование ключа).
Итак, прямо сделайте «пут»,
и если было предыдущее значение, то делаем дополнение:
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
}
}
Различные примитивные оболочки, например, Integer неизменяемы, поэтому на самом деле нет более краткого способа сделать то, что вы просите пока не вы можете сделать это с помощью чего-то вроде AtomicLong.Я могу попробовать через минуту и обновить.КСТАТИ, Хеш-таблица является часть Платформа коллекций.
Я бы использовал ленивую карту коллекций Apache (для инициализации значений равным 0) и использовал MutableIntegers из Apache Lang в качестве значений на этой карте.
Самая большая стоимость — это дважды искать карту в вашем методе.В моем случае это нужно сделать только один раз.Просто получите значение (оно будет инициализировано, если оно отсутствует) и увеличьте его.
А Функциональная Java библиотека TreeMap структура данных имеет 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».
@Вилмантас Баранаускас:Что касается этого ответа, я бы прокомментировал, если бы у меня были очки повторения, но у меня их нет.Я хотел отметить, что класс Counter, определенный там, НЕ является потокобезопасным, поскольку недостаточно просто синхронизировать inc() без синхронизации value().Другие потоки, вызывающие value(), не гарантированно увидят значение, если только с обновлением не установлена связь «происходит до».
Я не знаю, насколько это эффективно, но приведенный ниже код тоже работает. Вам нужно определить 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
Если вы используете Коллекции затмений, вы можете использовать HashBag.Это будет наиболее эффективный подход с точки зрения использования памяти, а также он будет хорошо работать с точки зрения скорости выполнения.
HashBag поддерживается MutableObjectIntMap который хранит примитивные целые числа вместо Counter объекты.Это уменьшает нагрузку на память и повышает скорость выполнения.
HashBag предоставляет API, который вам понадобится, поскольку это Collection это также позволяет вам запрашивать количество вхождений элемента.
Вот пример из Коллекции Eclipse Ката.
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.
Довольно просто, просто используйте встроенную функцию в Map.java как следует
map.put(key, map.getOrDefault(key, 0) + 1);
Поскольку многие люди ищут ответы на Groovy в темах Java, вот как это можно сделать в 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)
Надеюсь это поможет!
