Java：线性算法但非线性性能下降,它来自哪里？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java：线性算法但非线性性能下降,它来自哪里？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3492字，纯文字阅读大概需要5分钟。

内容图文

我目前正在使用自然语言处理开发的应用程序遇到严重的性能问题.基本上,给定文本,它收集各种数据并进行一些数字处理.

对于每个句子,它确实完全相同.用于收集统计数据的算法不会随先前读取的数据而发展,因此保持不变.

问题是处理时间根本不是线性演变的：10k句子为1分钟,100k为1小时,1M为1天……

我尽我所能,从重新实现基本数据结构到对象池再循环实例.行为不会改变.我得到的时间非线性增加似乎无法通过更多的hashmap冲突,IO等待,也没有任何东西来证明这一点！当数据增加时,Java开始变得迟缓,我感到完全无助.

如果您想要一个示例,请尝试以下操作：计算大文件中每个单词的出现次数.一些代码如下所示.通过这样做,我需要3秒超过100k句子和326秒超过1.6M …所以乘法器110次而不是16次.随着数据越来越多,它变得更糟……

这是一个代码示例：
请注意,我通过引用比较字符串(出于效率原因),这可以通过’String.intern()’方法完成,该方法返回每个字符串的唯一引用.并且在上面给出的数字的整个过程中,地图永远不会被重新散列.

public class DataGathering
{
 SimpleRefCounter<String> counts = new SimpleRefCounter<String>(1000000);

 private void makeCounts(String path) throws IOException
 {

  BufferedReader file_src = new BufferedReader(new FileReader(path));

  String line_src;

  int n = 0;
  while (file_src.ready())
  {
   n++;

   if (n % 10000 == 0)
    System.out.print(".");

   if (n % 100000 == 0)
    System.out.println("");

   line_src = file_src.readLine();

   String[] src_tokens = line_src.split("[ ,.;:?!'\"]");

   for (int i = 0; i < src_tokens.length; i++)
   {
    String src = src_tokens[i].intern();
    counts.bump(src);
   }

  }
  file_src.close();
 }

 public static void main(String[] args) throws IOException
 {
  String path = "some_big_file.txt";

  long timestamp = System.currentTimeMillis();

  DataGathering dg = new DataGathering();
  dg.makeCounts(path);


  long time = (System.currentTimeMillis() - timestamp) / 1000;
  System.out.println("\nElapsed time: " + time + "s.");
 }
}

public class SimpleRefCounter<K>
{
 static final double GROW_FACTOR = 2;
 static final double LOAD_FACTOR = 0.5;

 private int capacity;

 private Object[] keys;
 private int[] counts;


 public SimpleRefCounter()
 {
  this(1000);
 }

 public SimpleRefCounter(int capacity)
 { 
  this.capacity = capacity;
  keys = new Object[capacity];
  counts = new int[capacity];
 }



 public synchronized int increase(K key, int n)
 {
  int id = System.identityHashCode(key) % capacity;

  while (keys[id] != null && keys[id] != key) // if it's occupied, let's move to the next one!
   id = (id + 1) % capacity;


  if (keys[id] == null)
  {
   key_count++;
   keys[id] = key;

   if (key_count > LOAD_FACTOR * capacity)
   {
    resize((int) (GROW_FACTOR * capacity));
   }
  }


  counts[id] += n;

  total += n;

  return counts[id];
 }



 public synchronized void resize(int capacity)
 {
  System.out.println("Resizing counters: " + this);

  this.capacity = capacity;

  Object[] new_keys = new Object[capacity];
  int[] new_counts = new int[capacity];

  for (int i = 0; i < keys.length; i++)
  {
   Object key = keys[i];
   int count = counts[i];

   int id = System.identityHashCode(key) % capacity;

   while (new_keys[id] != null && new_keys[id] != key) // if it's occupied, let's move to the next one!
    id = (id + 1) % capacity;

   new_keys[id] = key;
   new_counts[id] = count;
  }

  this.keys = new_keys;
  this.counts = new_counts;
 }


 public int bump(K key)
 {
  return increase(key, 1);
 }

 public int get(K key)
 {
  int id = System.identityHashCode(key) % capacity;

  while (keys[id] != null && keys[id] != key) // if it's occupied, let's move to the next one!
   id = (id + 1) % capacity;


  if (keys[id] == null)
   return 0;
  else
   return counts[id];
 }
    }

有什么解释吗？想法？建议？

……并且,正如开头所说的那样,特别是对于这个玩具示例而言,不是更一般的情况.在更复杂和更大的程序中,这种爆炸行为无缘无故地发生.

解决方法:

而不是感觉无助使用剖析器！这会告诉你你的代码到底花了多少时间.

内容总结

以上是互联网集市为您收集整理的Java：线性算法但非线性性能下降,它来自哪里？全部内容，希望文章能够帮你解决Java：线性算法但非线性性能下降,它来自哪里？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---