optimization map更新value - 用Java增加Map值的最有效方法




map获取value map设置值 (21)

我希望这个问题不被视为这个论坛的基础,但我们会看到。 我想知道如何重构一些代码以获得更好的性能,而这些代码正在运行很多次。

假设我使用一个Map(可能是一个HashMap)创建一个词频列表,其中每个键都是一个字符串,并且该字符被计数,并且该值是一个整数,每当找到该单词的一个标记时该值就会递增。

在Perl中,递增这样一个值将非常简单:

$map{$word}++;

但在Java中,它更复杂。 这是我目前正在做的事情:

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

这当然依赖于较新Java版本中的自动装箱功能。 我想知道你是否可以提出一种更有效的方式来增加这种价值。 是否有避免使用Collections框架和使用其他方法的良好性能原因?

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


Answers

MutableInt方法的一个变体可能会更快,如果有点破解的话,就是使用单元素int数组:

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

如果你可以用这个变化重新运行你的性能测试,这将是有趣的。 这可能是最快的。

编辑:上面的模式对我来说工作得很好,但最终我更改为使用Trove的集合来减少我创建的一些非常大的地图中的内存大小 - 作为奖励,它也更快。

一个非常好的特性是adjustOrPutValue类有一个adjustOrPutValue调用,根据该键是否已经有一个值,将调用初始值或递增现有值。 这对于递增是完美的:

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

如果您使用Eclipse集合 ,则可以使用HashBag 。 这将是内存使用方面最有效的方法,并且在执行速度方面也会表现出色。

HashBag由一个MutableObjectIntMap支持,它存储基本整数而不是Counter对象。 这减少了内存开销并提高了执行速度。

HashBag提供了您需要的API,因为它是一个Collection ,它还允许您查询项目出现的次数。

下面是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"));

注意:我是Eclipse集合的提交者。


有几种方法:

  1. 像使用Google收藏集中的套件一样使用Bag算法。

  2. 创建可在Map中使用的可变容器:


    class My{
        String word;
        int count;
    }

并用put(“word”,new My(“Word”)); 然后你可以检查它是否存在并在增加时增加。

避免使用列表滚动你自己的解决方案,因为如果你得到内部搜索和排序,你的表现会很糟糕。 第一个HashMap解决方案实际上是相当快的,但是像Google Collections那样的适当的解决方案可能会更好。

使用Google Collections计算单词,看起来像这样:



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


使用HashMultiset非常优雅,因为在计算单词时,bag-algorithm就是您所需要的。


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”。


内存旋转可能是一个问题,因为每个大于或等于128的int都会导致对象分配(请参阅Integer.valueOf(int))。 虽然垃圾收集器非常有效地处理短暂的对象,但性能会受到一定程度的影响。

如果你知道所做增量的数量将远远超过键的数量(在这种情况下=字),请考虑使用int保持器。 Phax已经为此提供了代码。 这里又有两个变化(持有者类设置为静态和初始值设置为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

顺便说一句,这个主题的好搜索词是“直方图”。


好的,可能是一个老问题,但Java 8有一个较短的方法:

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

它做什么:如果密钥不存在,则将1作为值,否则将1与链接到密钥的值相加 。 更多信息here


我不知道它的效率如何,但下面的代码也可以工作。你需要在开头定义一个BiFunction 。 另外,你可以使用这种方法做更多的事情。

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

输出是

3
1

你应该知道你最初的尝试

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

在地图上包含两个潜在的昂贵操作,即containsKeyget 。 前者执行的操作可能与后者非常相似,所以你要做两次相同的工作!

如果您查看Map的API,则当地图不包含请求的元素时, get操作通常会返回null

请注意,这将会产生类似的解决方案

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

危险的,因为它可能产生NullPointerException 。 你应该首先检查null

还要注意 ,这非常重要, HashMap 可以按照定义包含nulls 。 因此,不是每个返回的null表示“没有这样的元素”。 在这方面, containsKey行为不同于实际告诉你是否存在这样的元素。 有关详细信息,请参阅API。

但是,对于您的情况,您可能不想区分存储的null和“noSuchElement”。 如果你不想允许null你可能更喜欢一个Hashtable 。 根据应用程序的复杂性,使用其他答案中已经提出的包装库可能是更好的手动处理解决方案。

为了完成答案(并且我首先忘记了这一点,感谢编辑功能!),最好的方式就是进入final变量,检查是否为null然后putput回到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())); 代替。


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

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

@Hank Gay

作为我自己的(相当无用的)评论的后续:Trove看起来像要走的路。 如果不管什么原因,你想坚持使用标准的JDK, ConcurrentMapAtomicLong可以使代码更好一点,虽然YMMV。

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

将在foo的地图中留下1作为值。 实际上,线程的友好性增加是这种方法必须推荐的。


“放”需要“获得”(确保没有重复的键)。
所以直接做一个“放”,
并且如果有以前的值,则添加一个:

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
}

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

我认为你的解决方案将是标准方式,但是 - 正如你自己所指出的 - 这可能不是最快的方式。

你可以看看GNU Trove 。 这是一个包含各种快速原始集合的库。 你的例子会使用一个TObjectIntHashMap,它有一个方法adjustOrPutValue,它正是你想要的。


@Vilmantas Baranauskas:关于这个答案,我会评论我是否有重点,但我不这样做。 我想要注意的是Counter类定义的不是线程安全的,因为仅仅在没有同步value()的情况下同步inc()是不够的。 其他调用value()的线程不保证能够看到该值,除非已经与更新建立了事前关系。


由于很多人在Groovy的答案中搜索Java主题,因此您可以在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}

查看Google Collections Library以了解这种情况总是一个好主意。 在这种情况下, Multiset可以做到这一点:

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

有迭代键/条目等Map-like方法,内部实现当前使用HashMap<E, AtomicInteger> ,所以你不会产生装箱成本。


您可以在Java 8中提供的Map接口中使用computeIfAbsent方法。

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]

computeIfAbsent方法检查指定的键是否已经与某个值相关联? 如果没有关联值,那么它会尝试使用给定的映射函数来计算其值。 在任何情况下,它都返回与指定键相关联的当前(现有或计算的)值,如果计算的值为空,则返回null。

在附注中,如果您遇到多线程更新常见金额的情况,您可以查看LongAdder类。在较高的争用情况下,此类的预期吞吐量显着高于AtomicLong ,但代价是空间消耗较高。


各种原始包装,例如Integer是不可改变的,所以除非你可以像AtomicLong那样做, 否则真的没有更简洁的方法去做你正在问的东西。 我可以在一分钟内给出一个结果并更新。 顺便说一下, Hashtable 集合框架的一部分。


谷歌Guava是你的朋友...

......至少在某些情况下。 他们有这个不错的AtomicLongMap 。 特别好,因为你在地图上处理的价值很高。

例如

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

也可以添加1以上的值:

map.getAndAdd(word, new Long(112)); 

Google Collections HashMultiset:
- 使用起来非常优雅
- 但消耗CPU和内存

最好的办法是像这样: Entry<K,V> getOrPut(K); (优雅,低成本)

这种方法只会计算散列和索引一次,然后我们可以用条目来做我们想要的(替换或更新值)。

更优雅:
- 取一个HashSet<Entry>
- 扩展它,以便get(K)如果需要的话放入一个新的条目
- 进入可能是你自己的对象。
- > (new MyHashSet()).get(k).increment();


This is just too complicated. Maps were not supposed to do such job as sorting them by Value. The easiest way is to create your own Class so it fits your requirement.

In example lower you are supposed to add TreeMap a comparator at place where * is. But by java API it gives comparator only keys, not values. All of examples stated here is based on 2 Maps. One Hash and one new Tree. Which is odd.

The example:

Map<Driver driver, Float time> map = new TreeMap<Driver driver, Float time>(*);

So change the map into a set this way:

ResultComparator rc = new ResultComparator();
Set<Results> set = new TreeSet<Results>(rc);

You will create class Results ,

public class Results {
    private Driver driver;
    private Float time;

    public Results(Driver driver, Float time) {
        this.driver = driver;
        this.time = time;
    }

    public Float getTime() {
        return time;
    }

    public void setTime(Float time) {
        this.time = time;
    }

    public Driver getDriver() {
        return driver;
    }

    public void setDriver (Driver driver) {
        this.driver = driver;
    }
}

and the Comparator class:

public class ResultsComparator implements Comparator<Results> {
    public int compare(Results t, Results t1) {
        if (t.getTime() < t1.getTime()) {
            return 1;
        } else if (t.getTime() == t1.getTime()) {
            return 0;
        } else {
            return -1;
        }
    }
}

This way you can easily add more dependencies.

And as the last point I'll add simple iterator:

Iterator it = set.iterator();
while (it.hasNext()) {
    Results r = (Results)it.next();
    System.out.println( r.getDriver().toString
        //or whatever that is related to Driver class -getName() getSurname()
        + " "
        + r.getTime()
        );
}




java optimization collections