Map 值增加的最高效的方法 —— 只一次搜索键 已翻译 100%

oschina 投递于 2013/10/19 11:39 (共 5 段, 翻译完成于 10-20)
阅读 6680
收藏 99
2
加载中

这个问题初看起来可能会比较基础,但却在论坛里频繁地讨论。在这篇文章中,我将会讨论一种只在 Map 中搜索一次键的方法。

让我们看一个例子。假设我正在创建一个词频表,使用 Map 来保存,每一个键都是一个待统计的词而值则是其频率(每次添加词的时候都递增)。一个直接的实现方法是:

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

由于这段代码包含了3 个潜在的浪费时间的操作(containsKey()、get()、put()),所以效率不会很高。每次执行统计操作,都会搜索 Map 中的键。现在,我们以此为例子,看如何为 Map 值增加提高性能。

yfwz100
yfwz100
翻译于 2013/10/19 13:21
1

Integer VS MutableInteger VS AtomicInteger

我们不得不调用三次消耗性能的操作,一个重要的原因就是使用了Integer来计数。在Java中,Integer是不可以被改变的。它在构造完成以后就会阻止我们修改其整数值。因而,为了让计数器增长,我们就不得不从map中先获得整数,然后再创建另外一个新的整数,新增并且添加回map中

需要使得计数器可修改,有几种方法。其中一个就是简单的创建你自己的MutableInteger,想我在下面展示的这样:

public class MutableInteger {

  private int val;

  public MutableInteger(int val) {
    this.val = val;
  }

  public int get() {
    return val;
  }

  public void set(int val) {
    this.val = val;
  }
}
另外一种方法也许就是使用Java中AtomicInteger了,它被用于诸如需要原子增长计数器的应用程序之中。而把AtomicInteger作为首选是因为你会想要在对整数进行操作的时候实现线程安全。因此它不能作为Integer的替代。基于此,如果线程安全并不是你的项目一个重要的考虑事项,那我就不会推荐AtomicInteger。
LeoXu
LeoXu
翻译于 2013/10/19 18:16
1

只一次搜索键

在使用MutableInteger之后,我们改变上面的代码如下:

if (map.containsKey(string)) {
  MutableInteger count = map.get(string);
  count.set(count.get() + 1);
} else {
  map.put(string, new MutableInteger(1));
}

或者

MutableInteger count = map.get(string);
if (count != null) {
  count.set(count.get() + 1);
} else {
  map.put(string, new MutableInteger(1));
}

在最糟糕的时候,当键还没有出现过,这段代码会执行2个搜索:一次是获取MutableInteger另一次是是设值。这比前面的那段代码更优化。但我们不应该仅仅满足现在,如果你查看了[Map.putt()]方法。(http://docs.oracle.com/javase/7/docs/api/java/util/Map.html#put(K, V)) 在java文档中的方法。你会发现这个方法会返回先前与之关联键的值。这就意味着我们可以合并重新获取对象和设置方法。然而,也许你会好奇:如果我们不首先获得计数器,我们怎么来设置新的计数器呢?现在我们终于碰到了这篇文章中最棘手的部分:我们可以简单的使用零频率计数器!

public int incrementCount(K key, int count) {
    MutableInteger tmpCount = new MutableInteger(0);
    MutableInteger oldCount = map.put(key, tmpCount);
    if (oldCount != null) {
      count += oldCount.get();
    }
    tmpCount.set(count);
    return count;
  }
NCThinker
NCThinker
翻译于 2013/10/19 16:45
1

另一个计数器

把所有必要操作放入到类中看起来对以后的使用非常有用。因此我创建了一个Counter类, 并声明它为公共可用。在这个Counter中定义了一个集合,用于记录一个对象在集合中出现的次数。假如你有一个包含集合{a, a, b, c}的计数器。调用getCount()方法,那么“a”将会返回2,然而调用keySet()将会返回{a,b,c}。这个类和Map的工作原理很像,但是它却比Map有更简单的方法。

获得/设置/递增计数对象并计算各种函数的计数。Counter的构造器和addAll()方法可用来复制另一个计数器的内容。可以通过 IntCounter AbstractMapBagCounter类进行修改。

NCThinker
NCThinker
翻译于 2013/10/19 16:09
1

Counter中一些被强调的操作方法如下:

  • incrementCount()和 decrementCount():根据给定的键值对当前的计数增加/减去给定的数值。如果这个键值在以前没有出现过,那么可以断定它的计数是0,增加计数的方法将会设置它的计数到给定的值。减值的方法将会把它的值设置为-1。
  • getCount():返回给定键值当前的计数,如果以前没有出现过就返回0。
  • keysAt(), keysAbove()keysBelow():返回给定键值的计数,计数必须是与给定的阈值相等,大于或者小于。这个集合可能有0个元素,但是它不会为空。
  • argmin() 和 argmax():查找并返回在这个计数器中最小或者最大计数的键值。如果有多个最小或者最大计数,那么就随机返回一个值。当Counter为空的时候返回空值。
NCThinker
NCThinker
翻译于 2013/10/19 16:26
1
本文中的所有译文仅用于学习和交流目的,转载请务必注明文章译者、出处、和本文链接。
我们的翻译工作遵照 CC 协议,如果我们的工作有侵犯到您的权益,请及时联系我们。
加载中

评论(13)

martin_li
martin_li

引用来自“mystar”的评论

引用来自“dqsun”的评论

引用来自“mystar”的评论

这代码在多线程环境下根本没法用吧?何况结合一下concurrenthashmap里的一些特性来做根本不需要这么复杂。就算是做简单词频统计,为了系统性能保证,多线程处理也是很常见的手段吧?另外,修改入参再作为返回值,典型的bad smell哦,而且极易引起潜在问题。
结论:这就是一片垃圾文章。

此文只是为大家提供一个如何在搜索一次键的情况下修改map的值的思路,线程安全等问题实现着可以很解决。

我说不靠谱,是因为可以简单扩展put方法,实现效率更高的做法。

+10086
mystar
mystar

引用来自“dqsun”的评论

引用来自“mystar”的评论

这代码在多线程环境下根本没法用吧?何况结合一下concurrenthashmap里的一些特性来做根本不需要这么复杂。就算是做简单词频统计,为了系统性能保证,多线程处理也是很常见的手段吧?另外,修改入参再作为返回值,典型的bad smell哦,而且极易引起潜在问题。
结论:这就是一片垃圾文章。

此文只是为大家提供一个如何在搜索一次键的情况下修改map的值的思路,线程安全等问题实现着可以很解决。

我说不靠谱,是因为可以简单扩展put方法,实现效率更高的做法。
mystar
mystar

引用来自“throwable”的评论

对于HashMap,contains和get操作的耗时比put要少得多吧。
这个优化方法效果应该不会太明显。
而且为了优化,降低了代码的可读性。下个来接手维护的可能一时就转不过弯来了。

java的hashmap实现,put的执行时间大约是get的1.x-2左右,差别并不大。contains比get略微大一点。我真正觉得有问题的事他这实现思路不靠谱。
excepiton
excepiton
对于HashMap,contains和get操作的耗时比put要少得多吧。
这个优化方法效果应该不会太明显。
而且为了优化,降低了代码的可读性。下个来接手维护的可能一时就转不过弯来了。
啊哈米老鼠
啊哈米老鼠
有借鉴的地方,mark
frank21
frank21

引用来自“mystar”的评论

这代码在多线程环境下根本没法用吧?何况结合一下concurrenthashmap里的一些特性来做根本不需要这么复杂。就算是做简单词频统计,为了系统性能保证,多线程处理也是很常见的手段吧?另外,修改入参再作为返回值,典型的bad smell哦,而且极易引起潜在问题。
结论:这就是一片垃圾文章。

此文只是为大家提供一个如何在搜索一次键的情况下修改map的值的思路,线程安全等问题实现着可以很解决。
Ken5233
Ken5233

引用来自“mystar”的评论

这代码在多线程环境下根本没法用吧?何况结合一下concurrenthashmap里的一些特性来做根本不需要这么复杂。就算是做简单词频统计,为了系统性能保证,多线程处理也是很常见的手段吧?另外,修改入参再作为返回值,典型的bad smell哦,而且极易引起潜在问题。
结论:这就是一片垃圾文章。

文章应该只是阐述一些map的优化措施和思想,不一定是解决方法.我们也只能这么想了
_Kiven_
_Kiven_
我是来看3楼的
阿影
阿影
此文想表达些什么意思?
vingzhang
vingzhang
楼上好亮,哈哈
返回顶部
顶部