it-swarm-pt.tech

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

Espero que esta questão não seja considerada muito básica para este fórum, mas vamos ver. Eu estou querendo saber como refatorar algum código para melhor desempenho que está sendo executado um monte de vezes.

Digamos que eu esteja criando uma lista de frequência do Word, usando um Mapa (provavelmente um HashMap), onde cada chave é uma String com o Word sendo contado e o valor é um Integer que é incrementado toda vez que um token do Word é encontrado.

Em Perl, incrementar tal valor seria trivialmente fácil:

$map{$Word}++;

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

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

O que, claro, depende do recurso de caixa automática nas versões mais novas Java. Gostaria de saber se você pode sugerir uma maneira mais eficiente de incrementar esse valor. Existem até mesmo boas razões de desempenho para evitar a estrutura de Coleções e usar outra coisa?

Update: Eu fiz um teste de várias das respostas. Ver abaixo.

327
gregory

Alguns resultados de testes

Eu obtive muitas respostas boas para esta pergunta - obrigado pessoal - então eu decidi executar alguns testes e descobrir qual método é realmente mais rápido. Os cinco métodos que testei são estes:

  • o método "ContainsKey" que eu apresentei em a questão
  • 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 turma teve que realizar uma operação típica do cenário apresentado: abrir um arquivo de 10 MB e lê-lo, depois realizar uma contagem de frequência de todos os tokens do Word no arquivo. Como isso levou uma média de apenas 3 segundos, eu realizei 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 de clock) usando essencialmente 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 ContainsKey método foi, como esperado, o mais lento, então eu vou dar 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 aumentam em mais de 10% o desempenho. No entanto, se a segmentação for um problema, o AtomicLong pode ser mais atraente do que os outros (não tenho certeza). Eu também executei TestForNull com variáveis ​​final, mas a diferença foi insignificante.

Observe que não mapeei o uso de memória nos diferentes cenários. Eu ficaria feliz em ouvir de qualquer pessoa que tenha uma boa percepção de como os métodos MutableInt e Trove provavelmente afetariam o uso da memória.

Pessoalmente, acho o método MutableInt o mais atraente, já que não requer o carregamento de nenhuma classe de terceiros. Então, a menos que eu descubra problemas com isso, é assim que estou mais propenso a ir.

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

OK, pode ser uma questão antiga, mas há um caminho mais curto com Java 8:

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

O que faz: if key não existe, coloque 1 como valor, caso contrário sum 1 para o valor vinculado a key . Mais informações aqui

175
LE GALL Benoît

Uma pequena pesquisa em 2016: https://github.com/leventov/Java-Word-count , código fonte do benchmark

Melhores resultados por método (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

Resultados do tempo/espaço: 

42
leventov

Google Goiaba é seu amigo ...

... pelo menos em alguns casos. Eles têm este Nice AtomicLongMap . Especialmente Nice porque você está lidando com long como valor em 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); 
33
H6.

@Hank Gay

Como acompanhamento do meu comentário (um tanto inútil): Trove parece o caminho a percorrer. Se, por qualquer motivo, você quisesse 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();

vai deixar 1 como o valor no mapa para foo. Realisticamente, o aumento da simpatia para threading é tudo o que essa abordagem tem para recomendá-lo.

31
Hank Gay

É sempre uma boa ideia olhar para Google Collections Library para esse tipo de coisa. Neste caso, um Multiset irá fazer 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 chaves/entradas, etc. Internamente, a implementação atualmente usa um HashMap<E, AtomicInteger>, portanto você não incorrerá em custos de boxe.

25
Chris Nokleberg

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

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

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

Se você observar a API do mapa, as operações get geralmente retornarão null quando o mapa não contiver o elemento solicitado.

Note que isso vai fazer uma solução como

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

perigoso, pois pode gerar NullPointerExceptions. Você deve verificar primeiro um null.

Observe também, e isso é muito importante, que HashMaps can contém nulls por definição. Portanto, nem todo null retornado diz "não existe tal elemento". A este respeito, containsKey se comporta diferentemente de get em dizer a você se existe tal elemento. Consulte a API para detalhes.

Para o seu caso, no entanto, você pode não querer distinguir entre um null e um "noSuchElement" armazenados. Se você não quiser permitir nulls, talvez prefira um Hashtable. O uso de 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 esqueci de colocar isso em primeiro lugar, graças à função de edição!), A melhor maneira de fazer isso nativamente, é get em uma variável final, verifique se null e put ele volta com 1 . A variável deve ser final porque é imutável de qualquer maneira. O compilador pode não precisar dessa dica, mas é mais claro dessa maneira.

 final HashMap map = generateRandomHashMap (); 
 final Chave do objeto = fetchSomeKey (); 
 final Integer i = map.get (key); 
 if (i ! = null) {
 map.put (i + 1); 
} else {
 // faz alguma coisa 
} 

Se você não quer confiar em autoboxing, você deve dizer algo como 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);

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

Benefício:

  • Não criando outra classe para int mutável
  • Código curto
  • Fácil de entender
  • Nenhuma exceção de ponteiro nulo

Outra maneira é usar o método de mesclagem, mas isso é demais para apenas incrementar um valor.

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

Sugestão: você deve se preocupar com a legibilidade do código mais do que pouco ganho de desempenho na maioria das vezes.

20
off99555

Outra maneira seria criar um 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 em criar um objeto adicional, mas a sobrecarga em comparação com a criação de um Integer (mesmo com Integer.valueOf) não deve ser muito.

18
Philip Helger

Você pode fazer uso do método computeIfAbsent na interface Map fornecida em 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 não houver valor associado, ele tentará 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.

Em uma nota lateral, se você tem uma situação onde vários segmentos atualizam uma soma comum, você pode dar uma olhada em LongAdder classe.Em alta contenção, a taxa de transferência esperada desta classe é significativamente maior que AtomicLong, às custas de maior consumo de espaço.

9
i_am_zero

A rotação da memória pode ser um problema aqui, pois cada boxe de um int maior ou igual a 128 causa uma alocação de objeto (veja 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 excederá em muito o número de chaves (= palavras neste caso), considere o uso de um int port. Phax já apresentou código para isso. Aqui está novamente, com duas alterações (classe de suporte feita estática e 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 que seja diretamente adaptada aos tipos de valores primitivos. jrudolph mencionou GNU Trove .

By the way, um bom termo de pesquisa para este assunto é "histograma".

7
volley

Em vez de chamar containsKey (), é mais rápido apenas 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);
5
Glever

Existem algumas abordagens:

  1. Use um aloritmo do Google Bag como os conjuntos contidos nas Coleções do Google.

  2. Crie um container mutável que você pode usar no mapa:


    class My{
        String Word;
        int count;
    }

E use put ("Word", new My ("Word")); Então você pode verificar se existe e incrementar ao adicionar.

Evite criar sua própria solução usando listas, porque se você conseguir pesquisar e classificar o innerloop, seu desempenho será ruim. A primeira solução HashMap é realmente muito rápida, mas um bom como o encontrado no Google Collections é provavelmente melhor.

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



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

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

3
tovare

Coleções do Google HashMultiset:
- bastante elegante de usar
- mas consuma CPU e memória

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

Tal método computará hash e index somente uma vez, e então poderíamos fazer o que quisermos com a entrada (substituir ou atualizar o valor).

Mais elegante:
- pegue um HashSet<Entry>
- estender para que get(K) coloque uma nova entrada, se necessário
- Entrada pode ser seu próprio objeto.
-> (new MyHashSet()).get(k).increment();

3
the felis leo

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

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 eu 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 um bônus, também foi mais rápido.

Um recurso realmente interessante é que a classe TObjectIntHashMap possui uma única chamada adjustOrPutValue que, dependendo se já existe um valor nessa chave, colocará um valor inicial ou incrementará o valor existente. Isso é perfeito para incrementar:

TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();
...
map.adjustOrPutValue(key, 1, 1);
3
Eamonn O'Brien-Strain

Eu acho que a sua solução seria o caminho padrão, mas - como você se observou - provavelmente não é o caminho mais rápido possível.

Você pode olhar para 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.

3
jrudolph

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

Tente usar o gerador de perfil do NetBeans (é gratuito e incorporado em NB 6.1) para examinar os pontos de acesso.

Finalmente, uma atualização da JVM (digamos de 1.5-> 1.6) é muitas vezes um impulsionador de desempenho barato. Até mesmo um upgrade no número de compilação pode fornecer bons aumentos de desempenho. Se você estiver executando no Windows e este for um aplicativo de classe do servidor, use -server na linha de comandos para usar a JVM do Server Hotspot. Em máquinas Linux e Solaris, isso é autodetectado.

3
John Wright

Muito simples, basta usar a função incorporada em Map.Java conforme seguido

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

"put" precisa "get" (para garantir que não haja chave duplicada).
Então faça diretamente um "put",
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 quaisquer outros valores ...)

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 é thread-safe. Use-o para construir, 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
  }
}
2
the felis leo

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

HashBag é apoiado por um MutableObjectIntMap que armazena ints primitivos em vez de Counter. Isso reduz a sobrecarga de memória e melhora a velocidade de execução.

HashBag fornece a API que você precisa, pois é um Collection que 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: Eu sou um committer para coleções do Eclipse.

1
Craig P. Motlin

Eu usaria o Lazy Map do Apache Collections (para inicializar valores para 0) e usaria o MutableIntegers do Apache Lang como valores naquele mapa.

O maior custo é ter que buscar o mapa duas vezes no seu método. Na minha você tem que fazer isso apenas uma vez. Basta obter o valor (ele será inicializado se ausente) e incrementá-lo.

1
jb.

A estrutura de dados Functional Java library's TreeMap possui um método update na última linha de tronco:

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".

1
Apocalisp

Eu não sei o quão eficiente é, mas o código abaixo funciona também. Você precisa definir um BiFunction no começo. 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
1
MGoksu

Os vários invólucros primitivos, por exemplo, Integer são imutáveis, então não há uma maneira mais concisa de fazer o que você está pedindo a menos que você possa fazer isso com algo como AtomicLong . Eu posso fazer isso em um minuto e atualizar. BTW, Hashtable é uma parte do Collections Framework .

1
Hank Gay

@Vilmantas Baranauskas: Com relação a essa resposta, gostaria de comentar se eu tivesse os pontos de repetição, mas não tenho. Eu queria observar que a classe Counter definida NÃO é thread-safe, pois não é suficiente apenas sincronizar o inc () sem sincronizar o valor (). Não é garantido que outros encadeamentos chamando value () vejam o valor a menos que uma relação antes de acontecer tenha sido estabelecida com a atualização.

1
Alex Miller