我希望这个问题对于本论坛来说不是太基本了，但是我们会看到的。我想知道如何重构一些代码以获得更好的性能，而这些性能已经运行了很多次。

假设我正在使用地图(可能是HashMap)创建一个单词频率列表，其中每个键是一个带有要计数单词的字符串，并且值是一个整数，每次找到该单词的标记时，该值都会增加。

在Perl中，增加这样的值非常容易：

$map{$word}++;

但是在Java中，它要复杂得多。这是我目前的操作方式：

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

当然，哪个依赖于较新的Java版本中的自动装箱功能。我想知道我们是否可以建议一种更有效的递增此值的方法。避开Collections框架并改用其他东西，甚至有良好的性能原因吗？

更新：我已经测试了几个答案。见下文。

解决方案

回答

我认为解决方案将是标准方法，但是正如我们自己指出的那样，这可能不是最快的方法。

我们可以看一下GNU Trove。那是一个包含各种快速原始集合的库。示例将使用一个TObjectIntHashMap，它具有方法AdjustOrPutValue，它可以完全满足需求。

回答

各种原始包装器(例如Integer)是不可变的，因此，除非我们可以使用AtomicLong之类的方法，否则实际上并没有更简洁的方法来处理我们要的内容。我可以在一分钟内进行更新。顺便说一句，哈希表是集合框架的一部分。

回答

有两种方法：

• 像Google Collections中包含的集合那样使用Bag的算法。
• 创建可在地图中使用的可变容器：

class My{
        String word;
        int count;
    }

并使用put(" word"，new My(" Word"));然后，我们可以检查它是否存在并在添加时增加。

避免使用列表来滚动自己的解决方案，因为如果进行innerloop搜索和排序，则性能会发臭。第一个HashMap解决方案实际上是非常快的，但是像Google收藏夹中找到的那样可能更好。

使用Google收藏夹计数单词的过程看起来像这样：

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

使用HashMultiset非常精巧，因为在计算单词时便需要袋算法。

回答

@汉克·盖伊

作为我自己的评论(而不是毫无用处)的跟进：Trove看起来很可行。如果出于某种原因想要使用标准JDK，则可以使用YMMV来使ConcurrentMap和AtomicLong使代码更好一点。

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

会将1保留为foo映射中的值。实际上，这种方法必须向人们推荐增加对线程的友好性。

回答

另一种方法是创建一个可变的整数：

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)相比，开销也不应该太多。

回答

与其调用containsKey()，不如调用map.get并检查返回的值是否为null，会更快。

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

回答

我们应该意识到以下事实：我们最初的尝试

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

在地图上包含两个潜在的昂贵操作，即" containsKey"和" get"。前者执行的操作可能与后者非常相似，因此我们要完成两次相同的工作！

如果我们查看Map的API，则当地图不包含所请求的元素时，" get"操作通常会返回" null"。

请注意，这将使解决方案像

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

为了完成答案(由于编辑功能，我忘了先输入答案！)，本机执行此操作的最佳方法是将其放入"最终"变量中，检查" null"和"将其放回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()));"之类的话。

回答

我将使用Apache Collections Lazy Map(将值初始化为0)，并使用来自Apache Lang的MutableIntegers作为该映射中的值。

最大的成本是我们必须使用方法两次搜索地图。在我这里，我们只需要执行一次。只需获取值(如果不存在，它将被初始化)并将其递增。

回答

我们确定这是瓶颈吗？我们是否进行过任何性能分析？

尝试使用NetBeans Profiler(它是免费的且内置于NB 6.1中)来查看热点。

最后，JVM升级(例如从1.5-> 1.6)通常是廉价的性能提升器。甚至内部版本号的升级也可以提供良好的性能提升。如果我们在Windows上运行，并且这是服务器类应用程序，请在命令行上使用-server来使用服务器热点JVM。在Linux和Solaris计算机上，这是自动检测到的。

回答

@Vilmantas Baranauskas：关于这个答案，如果我有代表点，我会发表评论，但我没有。我想指出，那里定义的Counter类不是线程安全的，因为仅同步inc()而不同步value()是不够的。除非已通过更新建立事前发生的关系，否则其他调用value()的线程不能保证看到该值。

回答

这里的内存轮换可能是个问题，因为每个大于或者等于128的int的每次装箱都会导致对象分配(请参阅Integer.valueOf(int))。尽管垃圾收集器非常有效地处理了寿命短的对象，但是性能会受到一定程度的影响。

如果我们知道增加的次数将大大超过键的数目(在这种情况下，=字)，请考虑使用int持有人。 Phax已经为此提供了代码。再次出现以下两个更改(将holder类设为静态，并将初始值设置为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实现。 jrudolph提到了GNU Trove。

顺便说一句，这个主题的一个很好的搜索词是"直方图"。

回答

对于此类事情，最好查看Google收藏库。在这种情况下，Multiset可以解决问题：

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>"，因此不会产生装箱费用。

回答

一些测试结果

对于这个问题，我已经得到了很多很好的答案-谢谢大家-因此，我决定进行一些测试，并弄清楚哪种方法实际上是最快的。我测试的五种方法是：

• 我在问题中介绍的" ContainsKey"方法
• Aleksandar Dimitrov建议的" TestForNull"方法
• 汉克·盖伊(Hank Gay)提出的" AtomicLong"方法
• jrudolph建议的"激励"方法
• phax.myopenid.com建议的" MutableInt"方法

方法

这就是我所做的...

• 创建了五个相同的类，除了以下所示的差异。每个班级都必须执行我所介绍的情景的典型操作：打开一个10MB的文件并读入它，然后对文件中所有单词标记的频率进行计数。由于平均只需要3秒钟，因此我让它执行了10次频率计数(而不是I / O)。
• 对10次迭代(而非I / O操作)的时间进行计时，并基本上使用Java Cookbook中的Ian Darwin的方法记录所花费的总时间(以时钟秒为单位)。
• 依次进行了所有五个测试，然后又进行了三次。
• 将每种方法的四个结果取平均值。

结果

我将首先介绍结果，并为感兴趣的人提供以下代码。

如所预期的，ContainsKey方法是最慢的，因此，与该方法的速度相比，我将给出每种方法的速度。

• ContainsKey：30.654秒(基准)
• AtomicLong：29.780秒(速度的1.03倍)
• TestForNull：28.804秒(速度的1.06倍)
• 精通：26.313秒(是1.16倍的速度)
• MutableInt：25.747秒(1.19倍的速度)

总结

看起来只有MutableInt方法和Trove方法要快得多，因为它们的性能提升超过10％。但是，如果线程成为问题，则AtomicLong可能比其他线程更具吸引力(我不确定)。我也用final变量运行了TestForNull，但是差别可以忽略不计。

请注意，我没有介绍不同情况下的内存使用情况。我很高兴听到任何对MutableInt和Trove方法将如何影响内存使用情况有深刻见解的人。

我个人认为MutableInt方法最吸引人，因为它不需要加载任何第三方类。因此，除非我发现问题，否则这就是我最有可能采取的方法。

代码

这是每种方法的关键代码。

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

原子长

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

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

回答

Functional 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"。

回答

"放置"需要"获取"(以确保没有重复的密钥)。
因此，直接进行"放置"
如果以前有一个值，则进行加法：

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
}

如果count从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
  }
}

回答

Google Collections HashMultiset：
使用起来相当优雅
但是会消耗CPU和内存

最好的方法是：Entry <K，V> getOrPut(K);
(优雅，低成本)

这样的方法只会计算一次哈希和索引，
然后我们可以根据条目做我们想做的事
(替换或者更新值)。

更优雅：
接受一个HashSet <Entry>
扩展它，以便get(K)在需要时放置一个新条目
输入可能是我们自己的对象。
->(new MyHashSet())。get(k).increment();