A maneira mais eficiente de incrementar um valor de Mapa em Java

Espero que esta pergunta não seja considerada muito básica para este fórum, mas veremos. Eu estou querendo saber como refatorar algum código para obter um melhor desempenho que está sendo executado várias vezes.

Digamos que eu esteja criando uma lista de frequência de palavras, usando um Mapa (provavelmente um HashMap), em que cada chave é uma String com a palavra que está sendo contada e o valor é um Inteiro que é incrementado cada vez que um token da palavra é encontrado.

No Perl, incrementar esse valor seria trivialmente fácil:

$map{$word}++;

Mas em Java, é muito mais complicado. Aqui da maneira que estou fazendo atualmente:

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

É claro que depende do recurso de caixa automática nas versões mais recentes do Java. Gostaria de saber se você pode sugerir uma maneira mais eficiente de aumentar esse valor. Existem ainda boas razões de desempenho para evitar a estrutura de coleções e usar outra coisa?

Atualização: Eu fiz um teste de várias respostas. Ver abaixo.

Alguns resultados do teste

Eu recebi muitas respostas boas para essa pergunta - obrigado pessoal -, então decidi executar alguns testes e descobrir qual método é realmente mais rápido. Os cinco métodos que testei são os seguintes:

• o método "ContainsKey" que apresentei na pergunta
• o método "TestForNull" sugerido por Aleksandar Dimitrov
• o método "AtomicLong" sugerido por Hank Gay
• o método "Trove" sugerido por jrudolph
• o método "MutableInt" sugerido por phax.myopenid.com

Método

Aqui está o que eu fiz ...

1. criou cinco classes que eram idênticas, exceto pelas diferenças mostradas abaixo. Cada classe teve que executar uma operação típica do cenário que apresentei: abrindo um arquivo de 10 MB e lendo-o e executando uma contagem de frequência de todos os tokens de palavras no arquivo. Como isso levou uma média de apenas 3 segundos, eu fiz a contagem de frequência (não a E / S) 10 vezes.
2. cronometrou o loop de 10 iterações, mas não a operação de E / S, e registrou o tempo total gasto (em segundos do relógio), essencialmente usando o método de Ian Darwin no Java Cookbook .
3. realizou todos os cinco testes em série e depois fez isso mais três vezes.
4. calculou a média dos quatro resultados para cada método.

Resultados

Vou apresentar os resultados primeiro e o código abaixo para quem estiver interessado.

O método ContainsKey foi, como esperado, o mais lento, portanto, darei a velocidade de cada método em comparação com a velocidade desse método.

• ContainsKey: 30.654 segundos (linha de base)
• AtomicLong: 29.780 segundos (1,03 vezes mais rápido)
• TestForNull: 28.804 segundos (1,06 vezes mais rápido)
• Trove: 26.313 segundos (1,16 vezes mais rápido)
• MutableInt: 25.747 segundos (1,19 vezes mais rápido)

Conclusões

Parece que apenas o método MutableInt e o método Trove são significativamente mais rápidos, pois apenas eles oferecem um aumento de desempenho superior a 10%. No entanto, se o threading for um problema, o AtomicLong pode ser mais atraente que os outros (não tenho muita certeza). Também executei o TestForNull comfinal variáveis, mas a diferença era insignificante.

Observe que não analisei o uso de memória nos diferentes cenários. Eu ficaria feliz em ouvir de alguém que tenha boas idéias sobre como os métodos MutableInt e Trove provavelmente afetarão o uso da memória.

Pessoalmente, acho o método MutableInt o mais atraente, pois não requer o carregamento de nenhuma classe de terceiros. Então, a menos que eu descubra problemas, é assim que provavelmente vou.

O código

Aqui está o código crucial de cada método.

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

Agora há uma maneira mais curta com o Java 8 usando Map::merge.

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

O que faz:

• se a chave não existir, coloque 1 como valor
• caso contrário, some 1 ao valor vinculado à chave

Mais informações aqui .

Uma pequena pesquisa em 2016: https://github.com/leventov/java-word-count , código fonte de referência

Melhores resultados por método (quanto menor, melhor):

                 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

Tempo \ espaço resultados:

Google Guava é seu amigo ...

... pelo menos em alguns casos. Eles têm esse ótimo AtomicLongMap . Especialmente interessante porque você está lidando com o valor contido no seu mapa.

Por exemplo

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

Também é possível adicionar mais de 1 ao valor:

map.getAndAdd(word, 112L); 

@Hank Gay

Como acompanhamento do meu comentário (bastante inútil): Trove parece o caminho a percorrer. Se, por qualquer razão, que queria ficar com o JDK padrão, ConcurrentMap e AtomicLong pode tornar o código um minúsculo pouco mais agradável, embora YMMV.

    final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
    map.putIfAbsent("foo", new AtomicLong(0));
    map.get("foo").incrementAndGet();

deixará 1como o valor no mapa para foo. Realisticamente, o aumento da cordialidade com o encadeamento é tudo o que essa abordagem precisa para recomendá-lo.

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

E é assim que você incrementa um valor com código simples.

Benefício:

• Não há necessidade de adicionar uma nova classe ou usar outro conceito de int mutável
• Não confiando em nenhuma biblioteca
• Fácil de entender o que está acontecendo exatamente (sem muita abstração)

Desvantagem:

• O mapa de hash será pesquisado duas vezes por get () e put (). Portanto, não será o código com melhor desempenho.

Teoricamente, depois de chamar get (), você já sabe onde colocar (), para que não precise procurar novamente. Mas pesquisar no mapa de hash geralmente leva um tempo muito mínimo para você ignorar esse problema de desempenho.

Mas se você é muito sério sobre o assunto, é um perfeccionista, outra maneira é usar o método de mesclagem, isso é (provavelmente) mais eficiente que o snippet de código anterior, pois você (teoricamente) pesquisará o mapa apenas uma vez: (embora esse código não é óbvio à primeira vista, é curto e tem bom desempenho)

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

Sugestão: você deve se preocupar com a legibilidade do código mais do que com pouco ganho de desempenho na maioria das vezes. Se o primeiro trecho de código for mais fácil para você entender, use-o. Mas se você é capaz de entender a segunda multa, também pode ir em frente!

É sempre uma boa ideia procurar na Biblioteca de coleções do Google esse tipo de coisa. Nesse caso, um Multiset fará o truque:

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

Existem métodos semelhantes a mapas para iterar sobre chaves / entradas, etc. Internamente, a implementação atualmente usa a HashMap<E, AtomicInteger>, para que você não incorra em custos de boxe.

Você deve estar ciente do fato de que sua tentativa original

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

contém duas operações potencialmente caras em um mapa, a saber, containsKeye get. O primeiro executa uma operação potencialmente muito semelhante ao último, então você está fazendo o mesmo trabalho duas vezes !

Se você olhar a API para Map, as getoperações geralmente retornam nullquando o mapa não contém o elemento solicitado.

Observe que isso criará uma solução como

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

perigoso, pois pode produzir NullPointerExceptions. Você deve verificar pela nullprimeira vez.

Observe também , e isso é muito importante, que HashMaps pode conter nullspor definição. Portanto, nem todos os retornados nulldizem "não existe esse elemento". A esse respeito,containsKey comporta-se de maneira diferente de getrealmente dizer se existe esse elemento. Consulte a API para obter detalhes.

Para o seu caso, no entanto, talvez você não queira distinguir entre um armazenado nulle "noSuchElement". Se você não deseja permitir nulls, pode preferir a Hashtable. Usar uma biblioteca de wrapper como já foi proposto em outras respostas pode ser uma solução melhor para o tratamento manual, dependendo da complexidade do seu aplicativo.

Para completar a resposta (e eu esqueci de inseri-la no início, graças à função de edição!), A melhor maneira de fazer isso de forma nativa é getentrar em uma finalvariável, verificar nulle putretornar com a 1. A variável deve ser finalporque é imutável de qualquer maneira. O compilador pode não precisar dessa dica, mas é mais claro assim.

mapa final do HashMap = generateRandomHashMap ();
chave final do objeto = fetchSomeKey ();
Número inteiro final i = map.get (chave);
if (i! = nulo) {
    map.put (i + 1);
} outro {
    // faça alguma coisa
}

Se você não quiser confiar no autoboxing, deve dizer algo parecido map.put(new Integer(1 + i.getValue()));.

Outra maneira seria criar um número inteiro mutável:

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

é claro que isso implica criar um objeto adicional, mas a sobrecarga em comparação à criação de um número inteiro (mesmo com o número inteiro.valueOf) não deve ser muito.

Você pode usar o método computeIfAbsent na Mapinterface fornecida no 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]

O método computeIfAbsent verifica se a chave especificada já está associada a um valor ou não? Se nenhum valor associado, ele tenta calcular seu valor usando a função de mapeamento fornecida. Em qualquer caso, ele retorna o valor atual (existente ou calculado) associado à chave especificada ou nulo se o valor calculado for nulo.

Além disso, se você tiver uma situação em que vários threads atualizem uma soma comum, poderá dar uma olhada na classe LongAdder . Sob alta contenção, o rendimento esperado dessa classe é significativamente maior do que AtomicLong, às custas de um maior consumo de espaço.

A rotação da memória pode ser um problema aqui, pois todo boxe de um int maior ou igual a 128 causa uma alocação de objeto (consulte Integer.valueOf (int)). Embora o coletor de lixo lide de maneira muito eficiente com objetos de vida curta, o desempenho sofrerá até certo ponto.

Se você souber que o número de incrementos feitos superará em grande parte o número de chaves (= palavras neste caso), considere usar um titular int. Phax já apresentou o código para isso. Aqui está novamente, com duas alterações (a classe de detentor estática e o valor inicial definido como 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();
}

Se você precisar de desempenho extremo, procure uma implementação de Mapa diretamente adaptada aos tipos de valor primitivo. jrudolph mencionou o GNU Trove .

A propósito, um bom termo de pesquisa para esse assunto é "histograma".

Em vez de chamar containsKey (), é mais rápido chamar map.get e verificar se o valor retornado é nulo ou não.

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

Tem certeza de que isso é um gargalo? Você já fez alguma análise de desempenho?

Tente usar o profiler do NetBeans (gratuito e embutido no NB 6.1) para verificar pontos de acesso.

Por fim, uma atualização da JVM (por exemplo, de 1.5 a 1.6) geralmente é um impulsionador de desempenho barato. Mesmo uma atualização no número da compilação pode fornecer um bom desempenho. Se você estiver executando no Windows e este for um aplicativo de classe de servidor, use -server na linha de comandos para usar a JVM do Hotspot do Servidor. Nas máquinas Linux e Solaris, isso é detectado automaticamente.

Existem algumas abordagens:

1. Use um aloritmo de bolsa como os conjuntos contidos nas coleções do Google.

2. Crie um contêiner mutável que você possa usar no mapa:

    class My{
        String word;
        int count;
    }

E use put ("word", novo My ("Word")); Depois, você pode verificar se existe e incrementar ao adicionar.

Evite lançar sua própria solução usando listas, porque se você buscar e classificar no interior do loop, seu desempenho será ruim. A primeira solução HashMap é realmente bastante rápida, mas provavelmente a mesma encontrada nas coleções do Google é melhor.

Contando palavras usando o Google Collections, é algo como isto:

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

O uso do HashMultiset é bastante elegante, porque um algoritmo de bolsa é exatamente o que você precisa ao contar palavras.

Acho que sua solução seria a maneira padrão, mas - como você se notou - provavelmente não é a maneira mais rápida possível.

Você pode olhar para o GNU Trove . Essa é uma biblioteca que contém todos os tipos de coleções primitivas rápidas. Seu exemplo usaria um TObjectIntHashMap que possui um método AdjustOrPutValue que faz exatamente o que você deseja.

Uma variação na abordagem MutableInt que pode ser ainda mais rápida, se for um hack, é usar uma matriz int de elemento único:

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

Seria interessante se você pudesse executar novamente seus testes de desempenho com essa variação. Pode ser o mais rápido.

Edit: O padrão acima funcionou bem para mim, mas eventualmente mudei para usar as coleções do Trove para reduzir o tamanho da memória em alguns mapas muito grandes que eu estava criando - e como bônus também foi mais rápido.

Um recurso realmente interessante é que a TObjectIntHashMapclasse tem uma única adjustOrPutValuechamada que, dependendo se já existe um valor nessa chave, colocará um valor inicial ou aumentará o valor existente. Isso é perfeito para incrementar:

TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();
...
map.adjustOrPutValue(key, 1, 1);

Google Collections HashMultiset:
- bastante elegante de usar
- mas consome CPU e memória

O melhor seria ter um método como: Entry<K,V> getOrPut(K); (elegante e de baixo custo)

Esse método calculará o hash e o índice apenas uma vez e, em seguida, poderemos fazer o que queremos com a entrada (substituir ou atualizar o valor).

Mais elegante:
- faça um HashSet<Entry>
- estenda-o para get(K)colocar uma nova entrada, se necessário
- A entrada pode ser seu próprio objeto.
->(new MyHashSet()).get(k).increment();

Muito simples, basta usar a função Map.javainterna da seguinte maneira

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

"put" need "get" (para garantir que nenhuma chave duplicada).
Então, faça um "put" diretamente
e , se houver um valor anterior, faça uma adição:

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
}

Se a contagem começar em 0, adicione 1: (ou qualquer outro valor ...)

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
}

Aviso: Este código não é seguro para threads. Use-o para construir e, em seguida, use o mapa, não para atualizá-lo simultaneamente.

Otimização: em um loop, mantenha o valor antigo para se tornar o novo valor do próximo loop.

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

Os vários invólucros primitivos, por exemplo, Integersão imutáveis, então não há realmente uma maneira mais concisa de fazer o que você está pedindo, a menos que você possa fazê-lo com algo como AtomicLong . Eu posso tentar isso em um minuto e atualizar. Aliás, o Hashtable faz parte do Framework de coleções .

Eu usaria o Mapa Preguiçoso do Apache Collections (para inicializar os valores em 0) e usaria o MutableIntegers do Apache Lang como valores nesse mapa.

O maior custo é ter que anexar o mapa duas vezes no seu método. No meu você tem que fazer isso apenas uma vez. Apenas obtenha o valor (será inicializado se ausente) e aumente-o.

A estrutura de dados da biblioteca Java FuncionalTreeMap possui um updatemétodo no cabeçalho de tronco mais recente:

public TreeMap<K, V> update(final K k, final F<V, V> f)

Exemplo de uso:

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

Este programa imprime "2".

@Vilmantas Baranauskas: Em relação a esta resposta, gostaria de comentar se tivesse os pontos de representante, mas não tenho. Eu queria observar que a classe Counter definida não é segura para threads, pois não é suficiente apenas sincronizar inc () sem sincronizar value (). Outros encadeamentos que chamam value () não têm garantia de ver o valor, a menos que tenha sido estabelecido um relacionamento antes da instalação com a atualização.

Eu não sei o quão eficiente é, mas o código abaixo também funciona. Você precisa definir um BiFunctionno início. Além disso, você pode fazer mais do que apenas incrementar com esse método.

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

saída é

3
1

Se você estiver usando o Eclipse Collections , poderá usar a HashBag. Será a abordagem mais eficiente em termos de uso de memória e também terá bom desempenho em termos de velocidade de execução.

HashBagé apoiado por um MutableObjectIntMapque armazena ints primitivas em vez de Counterobjetos. Isso reduz a sobrecarga de memória e melhora a velocidade de execução.

HashBag fornece a API que você precisa, pois é uma Collection também permite consultar o número de ocorrências de um item.

Aqui está um exemplo do 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"));

Nota: Sou um colaborador das Coleções Eclipse.

Sugiro usar o Java 8 Map :: compute (). Ele considera o caso quando uma chave também não existe.

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

Como muitas pessoas pesquisam nos tópicos Java respostas do Groovy, veja como você pode fazê-lo no 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}

A maneira simples e fácil no java 8 é a seguinte:

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

Espero que eu esteja entendendo sua pergunta corretamente, estou chegando ao Java a partir do Python para poder simpatizar com sua luta.

se você tem

map.put(key, 1)

você faria

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

Espero que isto ajude!