用hashmap改进字频的计数

Question

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

代码计算四个字符组合的出现次数.在测试期间,我发现地图中的条目数大约为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

我做了很多自然语言处理和机器学习的工作,所以我必须做这样的事情的时候,并有吨的优化机会.

需要考虑以下几点:

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

   • 一个字符串对象
     • 8字节的对象开销
     • 对数组的4字节引用
     • 4字节字符串长度字段
   • 一个字符数组
     • 8字节的对象开销
     • 每个字符2个字节(4个字符)= 8个字节
     • 4字节数组长度字段
   • 一个Integer对象
     • 8字节的对象开销
     • 4字节的int值
   • 一个HashMap.Entry对象
     • 8字节的对象开销
     • 4字节密钥参考
     • 4字节值参考

   所以你的小12字节数据变成64字节.而且在HashMap分配了一系列哈希值之前,它们在查找操作期间使用.请记住,所有这些微小的对象是指为GC更多的工作,但更重要的是,这意味着你的对象横跨主内存较大大片,而且不太可能以适应CPU缓存中.如果有大量缓存未命中,则会丢失性能.

   注意:一位评论者提醒我,所有子串将共享相同的底层字符数组,这是我忘记的一个好点.但是,这意味着每个映射条目从64字节变为44字节.这仍然是一个耻辱,当应该只有12个字节.

2. 对所有这些整数值进行装箱和拆箱会导致代码运行速度变慢并消耗更多内存.在大多数情况下,我们并不真正关心它,并且香草HashMap实现很好,即使它具有强制性的拳击和贪婪的内存消耗.但是在你的情况下,如果这个代码在一个紧密的内部循环中运行,我们宁愿有一个专门的类知道它的值总是整数并且不需要装箱.

3. 如果您深入研究JDK源代码,您将看到您的代码最终会两次调用字符串hashCode()和equals()方法.一次为了map.get()和一次为了map.put().但是有一种称为HashBag的不同类型的集合,只需一次查找即可执行查找,插入和计数增量."bag"集合有点像"set",除了它可以包含重复项,并且它跟踪有多少重复项.对于每个四元组,您只需bag.put(tetragram)在不必先检索和更新计数的情况下调用即可.遗憾的是,JDK中没有包实现,因此您需要在其他地方找到一个,或者自己编写一个.

4. 幸运的是,您的四元组可以无损编码为long值(因为每个java字符宽度为2个字节,并且a long可以使用8个字节).因此,您可以遍历字符数组并将每个四元数转换为a long,并避免构造这么多小字符串的所有开销.然后,您可以将结果保存在LongIntHashMap(来自Trove库)中.这将是很多比你目前的执行速度更快,因为你可以避免创建所有这些微小的字符串对象.

5. 虽然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方法而不是标准HashMap方法,我即将获得25%的性能提升.

然而,通过回收生成的物体,我即将获得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%.

Answer 2

您可以尝试将前缀树(trie)实现为数据结构,特别是如果您知道字符的范围.最多可达4级,为您提供潜在的恒定(和更快的恒定)时间.与hashmap相比,它的执行方式实际上取决于您拥有的数据.

编辑

或者,如果您知道字符的范围,您可以将它们填充到更快的数据类型中.

由于您知道所有字符都在A和Z或0和9之间,因此您可以将其压缩为6位:

 public int index(String str, int startPos) {
     return 
    ((str.charAt(startPos+3) - '0') << 18) + 
    ((str.charAt(startPos+2) - '0') << 12) + 
    ((str.charAt(startPos+1) - '0') << 6) + 
     (str.charAt(startPos) - '0');
 }

 //...    
 int[] counts = new int[42*42*42*42];
 final int max = text.length() - 4;
 for ( int i = 0; i < max; i++ ) {
     counts[index(text, i)]++;
 }    

编辑:更新上面的示例以涵盖A-Z, 0-9.现在注意两件事:首先,你必须创建一个大数组,但你不需要每次都这样做(你必须每次都清除它!).其次,这提供了对某个单词出现次数的快速查找,但是如果要迭代所有单词(比如查找实际出现的所有单词),则需要O(42^4)时间.