Maneira mais eficiente de incrementar um valor Map em Java
https://stackoverflow.com/questions/81346
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Espero que esta questão não seja considerada muito básica para este fórum, mas veremos.Estou me perguntando como refatorar algum código para obter melhor desempenho que está sendo executado várias vezes.
Digamos que estou criando uma lista de frequência de palavras, usando um mapa (provavelmente um HashMap), onde cada chave é uma String com a palavra que está sendo contada e o valor é um número inteiro que é incrementado cada vez que um token da palavra é encontrado.
Em Perl, incrementar tal valor seria trivialmente fácil:
$map{$word}++;
Mas em Java é muito mais complicado.Aqui está o jeito que estou fazendo atualmente:
int count = map.containsKey(word) ? map.get(word) : 0;
map.put(word, count + 1);
O que, claro, depende do recurso de autoboxing nas versões mais recentes do Java.Gostaria de saber se você pode sugerir uma forma mais eficiente de incrementar tal valor.Existem boas razões de desempenho para evitar a estrutura de coleções e usar outra coisa?
Atualizar:Eu fiz um teste de várias respostas.Veja abaixo.
Solução
Alguns resultados de testes
Recebi muitas respostas boas para essa pergunta - obrigado, pessoal - então decidi fazer 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 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...
- criou cinco classes idênticas, exceto pelas diferenças mostradas abaixo.Cada turma teve que realizar uma operação típica do cenário que apresentei:abrindo um arquivo de 10 MB e lendo-o e, em seguida, realizando uma contagem de frequência de todos os tokens de palavras no arquivo.Como isso levou em média apenas 3 segundos, fiz com que ele realizasse a contagem de frequência (não a E/S) 10 vezes.
- cronometrou o loop de 10 iterações, mas não a operação de E/S e registrou o tempo total gasto (em segundos) essencialmente usando O método de Ian Darwin no Java Cookbook.
- realizou todos os cinco testes em série e depois fez isso mais três vezes.
- calculou a média dos quatro resultados para cada método.
Resultados
Apresentarei primeiro os resultados e o código abaixo para quem tiver interesse.
O ContémKey O método foi, como esperado, o mais lento, então darei a velocidade de cada método em comparação com a velocidade desse método.
- ContémChave: 30,654 segundos (linha de base)
- Atômico Longo: 29,780 segundos (1,03 vezes mais rápido)
- TestForNull: 28,804 segundos (1,06 vezes mais rápido)
- Tesouro: 26,313 segundos (1,16 vezes mais rápido)
- MutávelInt: 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 proporcionam um aumento de desempenho de mais de 10%.No entanto, se o threading for um problema, o AtomicLong pode ser mais atraente que os outros (não tenho certeza).Eu também executei TestForNull com final variáveis, mas a diferença foi insignificante.
Observe que não criei um perfil de uso de memória nos diferentes cenários.Eu ficaria feliz em ouvir de alguém que tenha bons insights sobre como os métodos MutableInt e Trove provavelmente afetariam o uso da memória.
Pessoalmente, considero 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 com isso, é o caminho que provavelmente seguirei.
O código
Aqui está o código crucial de cada método.
ContémKey
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);
}
Atômico Longo
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();
Tesouro
import gnu.trove.TObjectIntHashMap;
...
TObjectIntHashMap<String> freq = new TObjectIntHashMap<String>();
...
freq.adjustOrPutValue(word, 1, 1);
MutávelInt
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();
}
Outras dicas
OK, pode ser uma pergunta antiga, mas existe um caminho mais curto com Java 8:
Map.merge(key, 1, Integer::sum)
O que faz :se chave não existe, coloque 1 como valor, caso contrário soma 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
Resultados de tempo\espaço:
Google Goiaba é seu amigo...
...pelo menos em alguns casos.Eles têm isso legal AtomicLongMap.Especialmente agradável porque você está lidando com longo 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);
@Hank Gay
Na sequência do meu próprio comentário (bastante inútil):Trove parece ser o caminho a seguir.Se, por qualquer motivo, você quiser continuar com o JDK padrão, Mapa Concorrente e Atômico Longo pode tornar o código um pequeno um pouco melhor, 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, uma maior facilidade de threading é tudo o que esta abordagem tem para recomendar.
É sempre uma boa ideia dar uma olhada Biblioteca de coleções do Google para esse tipo de coisa.Neste caso um Multiconjunto 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 chaves/entradas, etc.Internamente, a implementação atualmente usa um HashMap<E, AtomicInteger>, portanto você não incorrerá em custos de boxe.
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 à última, então você está fazendo o mesmo trabalho duas vezes!
Se você olhar a API do Map, get operações geralmente retornam null quando o mapa não contém o elemento solicitado.
Observe que isso criará uma solução como
map.put( key, map.get(key) + 1 );
perigoso, pois pode render NullPointerExceptionS.Você deve verificar se há um null primeiro.
Observe também, e isso é muito importante, que HashMapé pode conter nulls por definição.Então nem todos retornaram null diz "não existe tal elemento".A este respeito, containsKey se comporta diferentemente de get em realmente dizer a você se existe tal elemento.Consulte a API para obter detalhes.
Para o seu caso, entretanto, talvez você não queira distinguir entre um arquivo armazenado null e "noSuchElement".Se você não quiser permitir nullvocê pode preferir um Hashtable.Usar uma biblioteca wrapper como já foi proposto em outras respostas pode ser uma solução melhor para o tratamento manual, dependendo da complexidade da sua aplicação.
Para completar a resposta (e esqueci de colocar isso no início, graças à função de edição!), a melhor forma de fazer isso nativamente é get dentro de final variável, verifique null e put de volta com um 1.A variável deve ser final porque é imutável de qualquer maneira.O compilador pode não precisar dessa dica, mas é mais claro assim.
final HashMap map = generateRandomHashMap();
final Object key = fetchSomeKey();
final Integer i = map.get(key);
if (i != null) {
map.put(i + 1);
} else {
// do something
}
Se você não quiser confiar no autoboxing, você deve dizer algo como map.put(new Integer(1 + i.getValue())); em vez de.
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 código simples.
Beneficiar:
- 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 merge, mas isso é demais para apenas incrementar um valor.
map.merge(key, 1, (a,b) -> a+b);
Sugestão:você deve se preocupar mais com a legibilidade do código do que com o pequeno ganho de desempenho na maior parte do tempo.
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 a criação de um objeto adicional, mas a sobrecarga em comparação à criação de um número inteiro (mesmo com Integer.valueOf) não deve ser tão grande.
Você pode fazer uso computarIfAbsent método em Map interface 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 tenta calcular seu valor usando a função de mapeamento fornecida.Em qualquer caso, retorna o valor atual (existente ou computado) associado à chave especificada, ou nulo se o valor computado for nulo.
Por outro lado, se você tiver uma situação em que vários threads atualizam uma soma comum, você pode dar uma olhada LongAdder class.Sob alta contenção, o rendimento esperado desta classe é significativamente maior do que AtomicLong, às custas de maior consumo de espaço.
A rotação de memória pode ser um problema aqui, já que cada 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 será prejudicado até certo ponto.
Se você sabe que o número de incrementos feitos superará em grande parte o número de chaves (= palavras neste caso), considere usar um suporte int.Phax já apresentou código para isso.Aqui está novamente, com duas alterações (classe titular tornada 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 Map que seja diretamente adaptada para tipos de valores primitivos.Jrudolph mencionou GNU Trove.
Aliás, um bom termo de busca 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ê fez alguma análise de desempenho?
Tente usar o criador de perfil do NetBeans (é gratuito e integrado ao NB 6.1) para observar pontos de acesso.
Finalmente, uma atualização da JVM (digamos de 1.5-> 1.6) costuma ser um impulsionador de desempenho barato.Até mesmo uma atualização no número da compilação pode fornecer bons aumentos de desempenho.Se você estiver executando no Windows e este for um aplicativo de classe de servidor, use -server na linha de comando para usar o Server Hotspot JVM.Em máquinas Linux e Solaris isso é detectado automaticamente.
Existem algumas abordagens:
Use um algoritmo Bag como os conjuntos contidos nas Coleções do Google.
Crie um contêiner mutável que você pode usar no mapa:
class My{
String word;
int count;
}
E use put("word", new 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ê fizer busca e classificação no innerloop, seu desempenho será péssimo.A primeira solução HashMap é bastante rápida, mas uma solução adequada como a encontrada no Google Collections é provavelmente melhor.
Contar palavras usando as Coleções do Google é mais ou menos assim:
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.
Acho que sua solução seria a maneira padrão, mas - como você mesmo observou - provavelmente não é a maneira mais rápida possível.
Você pode olhar 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 da abordagem MutableInt que pode ser ainda mais rápida, embora seja um pouco complicada, é usar um array 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 esta variação.Pode ser o mais rápido.
Editar: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 estava criando - e como bônus também foi mais rápido.
Um recurso muito interessante é que o TObjectIntHashMap classe tem um único adjustOrPutValue chame isso, dependendo se já existe um valor naquela 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);
HashMultiset das coleções do Google:
- 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)
Tal método calculará hash e índice apenas uma vez, e então poderíamos fazer o que quiséssemos com o verbete (substitua ou atualize o valor).
Mais elegante:
- dê uma HashSet<Entry>
- estenda-o para que get(K) coloque uma nova entrada se necessário
- A entrada pode ser seu próprio objeto.
--> (new MyHashSet()).get(k).increment();
"put" precisa de "get" (para garantir que não haja chave duplicada).
Então faça diretamente um "put",
e se houvesse 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
}
Perceber : Este código não é thread-safe.Use-o para construir e depois 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 wrappers 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ê pode fazer isso com algo como Atômico Longo.Posso tentar isso em um minuto e atualizar.POR FALAR NISSO, Tabela hash é uma parte do Estrutura de coleções.
Eu usaria o Apache Collections Lazy Map (para inicializar os valores como 0) e usaria MutableIntegers do Apache Lang como valores nesse mapa.
O maior custo é ter que pesquisar o mapa duas vezes no seu método.No meu você tem que fazer isso apenas uma vez.Basta obter o valor (ele será inicializado se estiver ausente) e incrementá-lo.
O Java Funcional biblioteca TreeMap estrutura de dados tem um update método no último cabeçalho do 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".
@Vilmatas Baranauskas:Em relação a esta resposta, eu comentaria se tivesse pontos de representação, mas não tenho.Gostaria de observar que a classe Counter definida NÃO é thread-safe, pois não é suficiente apenas sincronizar inc() sem sincronizar value().Não é garantido que outros threads que chamam value() vejam o valor, a menos que um relacionamento anterior tenha sido estabelecido com a atualização.
Não sei o quão eficiente é, mas o código abaixo também funciona. Você precisa definir um BiFunction no inicio.Além disso, você pode fazer mais do que apenas incrementar com este 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"));
}
a saída é
3
1
Se você estiver usando Coleções 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 objetos.Isso reduz a sobrecarga de memória e melhora a velocidade de execução.
HashBag fornece a API que você precisa, já que é um Collection isso também permite consultar o número de ocorrências de um item.
Aqui está um exemplo do Coleções Eclipse 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"));
Observação: Eu sou um committer das Coleções Eclipse.
Muito simples, basta usar a função integrada em Map.java conforme seguido
map.put(key, map.getOrDefault(key, 0) + 1);
Como muitas pessoas pesquisam tópicos Java em busca de respostas do Groovy, veja como você pode fazer isso 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}
Espero estar entendendo sua pergunta corretamente, estou vindo do Python para Java para poder ter empatia com sua luta.
se você tem
map.put(key, 1)
você faria
map.put(key, map.get(key) + 1)
Espero que isto ajude!
