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

Question

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

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

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

$map{$word}++;

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

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

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

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

1. Используйте арифметику Bag, как наборы, содержащиеся в 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 довольно элегантно, потому что алгоритм сумок - это то, что вам нужно для подсчета слов.

Answer 5

Вариант подхода 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);

Answer 6

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

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

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

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

Answer 7

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

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

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

Answer 8

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

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
  }
}

Answer 9

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

Answer 10

Если вы используете 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 Collections.