java - 使用 hashmap 改进词频计数

Question

对于我的一个应用程序，必须经常调用以下函数。此功能占用大量CPU，因此我想知道您是否知道如何提高性能。

该代码计算四个字符组合的出现次数。测试时发现map中的条目数在100左右。文本长度在100到800之间。200的初始大小是猜测，代码似乎比不指定初始值运行得更快尺寸。不过，这可能不是最佳值。

private Map<String, Integer> getTetagramCount(final String text) {
    final Map<String, Integer> cipherTetagrams = new HashMap<String, Integer>(200);

    for (int i = 0; i < text.length() - 4; i++) {
        final String tet = text.substring(i, i + 4);

        final Integer count = cipherTetagrams.get(tet);
        if (count != null) {
            cipherTetagrams.put(tet, count + 1);
        } else {
            cipherTetagrams.put(tet, 1);
        }
    }

    return cipherTetagrams;
}

Answer 1

我在NLP和机器学习方面做了很多工作，所以我必须一直做这种事情，还有吨 优化的机会。
需要考虑的几点:

首先，您被标准的 JDK HashMap 类杀死了。对于通用计算来说，这是一个很好的容器，但对于高性能计算来说却很糟糕。对于集合中的每个条目(一个四字符字符串(8 个字节)和一个整数(4 个字节)，标准的 java HashMap 将使用:

一个字符串对象

8 字节对象开销

对数组的 4 字节引用

4 字节字符串长度字段

一个字符数组

8 字节对象开销

每个字符 2 个字节(乘以 4 个字符)= 8 个字节

4 字节数组长度字段

一个整数对象

8 字节对象开销

4 字节整数值

一个 HashMap.Entry 对象

8 字节对象开销

4 字节 key 引用

4 字节值引用

所以你的 12 字节数据变成了 64 字节。那是在 HashMap 分配了一个哈希值数组以在其查找操作期间使用之前。请记住，所有这些微小的小对象都意味着 GC 需要做更多的工作，但更重要的是，这意味着您的对象跨越更大的主内存，不太可能适合 CPU 缓存。当您有大量缓存未命中时，您会损失性能。
注意:一位评论者提醒我，所有子字符串都将共享相同的底层字符数组，这是我忘记的一个好点。但是，这仍然意味着每个映射条目从 64 字节减少到 44 字节。这仍然是一种耻辱，因为应该只有 12 个字节。

装箱和拆箱所有这些整数值会导致您的代码运行更慢并消耗更多内存。在大多数情况下，我们并不真正关心这一点， Vanilla HashMap 实现很好，即使它有强制装箱和贪婪的内存消耗。但是在您的情况下，如果此代码在紧密的内部循环中运行，我们宁愿有一个专门的类，该类知道其值始终为整数并消除了装箱的需要。

如果您深入研究 JDK 源代码，您会发现您的代码最终会调用字符串的 hashCode()和 equals()方法两次。曾经为map.get()还有一次是为 map.put() .但是有一种不同的集合叫做 HashBag 只需一次查找即可执行查找、插入和计数递增。 “包”集合有点像“集合”，除了它可以包含重复项，并且它会跟踪有多少重复项。对于您的每个四边形，您只需拨打 bag.put(tetragram)无需先检索和更新计数。不幸的是，JDK 中没有包实现，因此您需要在别处找到一个，或者自己编写一个。

幸运的是，您的四边形可以无损编码为 long值(因为每个 java 字符的宽度为 2 个字节，而 long 为您提供了八个字节)。因此，您可以遍历字符数组并将每个四边形转换为 long ，并避免构建这么多小字符串的所有开销。然后，您可以将结果保存在 LongIntHashMap 中。 (来自 Trove 图书馆)。这将比您当前的实现快得多，因为您可以避免创建所有这些微小的字符串对象。

虽然宝藏LongIntHashMap相当优秀，不如LongHashBag将是。没有 equals调用(因为可以将 longs 与 == 运算符进行比较)，但您仍将支付两个 hashCode 的代价调用。如果你想真正积极地进行优化，你可以查看 LongIntHashMap 的源代码。并弄清楚如何将其修改为 LongHashBag .这并不难，最终，这正是我在自己的代码中所做的。

更新 1:
好的，这里有一些代码:

private LongHashBag countTetragrams(String text) {

  // Homework assignment: find a good LongHashBag implementation, or
  // grab the LongIntHashMap implementation from Trove, and tweak it
  // to work as a Bag
  LongHashBag bag = new LongHashBag(500);

  // There are no tetragrams in this string.
  if (text.length() < 4) return bag;

  // Shortcut: if we calculate the first tetragram before entering
  // the loop, then we can use bit-shifting logic within the loop
  // to create all subsequent tetragram values.
  char[] c = text.toCharArray();
  long tetragram = ((long) c[0] << 48) |
     (((long) c[1]) << 32) |
     (((long) c[2]) << 16) |
     ((long) c[3]);

  bag.add(tetragram);

  for (int i = 4, last = text.length(); i < last; i++) {
     // During each loop iteration, the leftmost 2-bytes are shifted
     // out of the tetragram, to make room for the 2-bytes from the
     // current character.
     tetragram = (tetragram << 16) | ((long) c[i]);
     bag.add(tetragram);
  }

  return bag;
}

更新 2:
我刚刚对各种解决方案进行了一些测试，我即将使用 LongHashBag 获得大约 25% 的性能提升。方法而不是标准 HashMap方法。
但是，通过回收生成的对象，我将获得 300% 的改进。基本上，而不是这样做:

private LongHashBag countTetragrams(String text) {

  // Creates a new HashBag on every invocation. Very wasteful.
  LongHashBag bag = new LongHashBag(500);

  // ...blah blah blah...

  return bag;
}

......我现在正在这样做......

private void countTetragrams(String text, LongHashBag bag) {

  // Return the object to a neutral state, and recycle it.
  bag.clear()

  // ...blah blah blah...
}

调用代码负责创建 LongHashBag 对象并确保在我们再次调用 count 方法时已经完成了它。
但它也可以做到这一点......

private LongHashBag countTetragrams(String text) {

  // Return the object to a neutral state, and recycle it.
  LongHashBag bag = retrieveLongHashBagFromObjectPool();

  // ...blah blah blah...
  return bag;
}

...这将增加一点维护池的开销。并且调用代码必须记住在使用完袋子后将袋子放回池中。但性能优势绝对值得。
顺便说一句，这些正是我每天使用的技巧。对象池已成为我提高性能的最可靠技巧之一。
但就像我说的，回收这些对象会带来 300% 的性能提升。